ЗАДАЧИ
problems.ru
О проекте | Об авторах | Справочник
Каталог по темам | по источникам | Поиск |
К задаче N

Проект МЦНМО
при участии
школы 57
Фильтр
Сложность с по   Класс с по  
Задачи

Страница: << 14 15 16 17 18 19 20 >> [Всего задач: 133]      



Задача 77922

Темы:   [ Взвешивания ]
[ Процессы и операции ]
[ Теория алгоритмов (прочее) ]
Сложность: 4
Классы: 8,9,10

Имеется кусок цепи из 60 звеньев, каждое из которых весит 1 г. Какое наименьшее число звеньев надо расковать, чтобы из образовавшихся частей можно было составить все веса в 1 г, 2 г, 3 г, ..., 60 г (раскованное звено весит тоже 1 г)?

Решение

Ответ: 3 звена. Выясним, при каком наибольшем n достаточно расковать k звеньев n-звенной цепи, чтобы из образовавшихся частей можно было составить все веса от 1 до n. Если расковано k звеньев, то любое число звеньев от 1 до k можно набрать из них. Но k + 1 звеньев мы не сможем набрать, если не будет части из k + 1 или менее звеньев (мы здесь не учитываем раскованные звенья). Наиболее выгодно иметь часть из ровно k + 1 звеньев. Тогда мы сможем получить любое число звеньев от 1 до 2k + 1. (Иначе мы сможем получить лишь число звеньев от 1 до l1 + k, где l1$ \le$k.) Затем наиболее выгодно иметь часть из 2(k + 1) звеньев, затем из 4(k + 1) звеньев и т.д. Итак, если мы расковали k звеньев, то наиболее выгодна ситуация, когда полученные при этом k + 1 частей состоят из k + 1, 2(k + 1), 4(k + 1), 8(k + 1), ..., 2k(k + 1) звеньев (раскованные звенья мы здесь не учитываем). В таком случае можно составить любое число звеньев от 1 до n = 2k + 1(k + 1) - 1. Итак, если 2kk$ \le$n$ \le$2k + 1(k + 1) - 1, то можно обойтись k разрывами и нельзя обойтись k - 1 разрывами. В частности, если 24$ \le$n$ \le$63, то наименьшее число раскованных звеньев равно 3. Полученные при расковке четыре части цепи должны состоять при этом из 4, 8, 16, 29 звеньев.
Прислать комментарий


Задача 78572

Темы:   [ Взвешивания ]
[ Делимость чисел. Общие свойства ]
Сложность: 4
Классы: 7,8,9,10

Имеется 11 мешков монет. В 10 из них монеты настоящие, а в одном – все монеты фальшивые. Все настоящие монеты одного веса, все фальшивые монеты – также одного, но другого веса. Имеются весы, с помощью которых можно определить, какой из двух грузов тяжелее и на сколько. Двумя взвешиваниями определить, в каком мешке фальшивые монеты.

Решение

  Первое взвешивание. На одну чашу кладем по одной монете из 10 мешков, на другую – 10 монет из оставшегося мешка.
  Второе взвешивание. На первую чашу кладем одну монету из первого мешка, две монеты из второго, три – из третьего, ..., 10 монет из десятого. На другую – 55 монет из последнего (того же, что в прошлый раз) мешка.
  Пусть x – разность между весом фальшивой и настоящей монеты (возможно,  x < 0,  i – номер мешка с фальшивыми монетами. Разберём два случая.
  1)  i < 11.  Тогда при первом взвешивании весы покажут разность весов x, а при втором – ix.
  2)  i = 11.  Тогда при первом взвешивании весы покажут число – 10x, а при втором – 55x.
  Найдём отношение показаний весов при первом и втором взвешивании. Если это отношение – целое число, то оно равно номеру мешка с фальшивыми монетами (случай 1). Если же оно – нецелое, то фальшивые монеты находятся в мешке номер 11 (случай 2).

Прислать комментарий

Задача 78598

Темы:   [ Взвешивания ]
[ Сочетания и размещения ]
[ Принцип Дирихле (прочее) ]
Сложность: 4
Классы: 8,9,10,11

Из набора гирь весом 1, 2, ..., 26 выделить шесть гирь так, чтобы среди них не было выбрать двух кучек равного веса.
Доказать, что нельзя выбрать семь гирь, обладающих тем же свойством.

Решение


  Набор гирь 26, 25, 24, 22, 19 и 11 удовлетворяет условию.
  Пусть выбраны какие-то семь гирь. Заметим, что нельзя брать одновременно гири 26, 25, 24, 23 (среди них уже есть две кучки равного веса), и поэтому сумма весов любых четырёх гирь из этих семи будет меньше 98. Но существует ровно    разных наборов из семи гирь по 1, 2, 3 и 4 гири. Поэтому веса каких-то двух наборов будут совпадать.

Прислать комментарий

Задача 79471

Темы:   [ Взвешивания ]
[ Линейные рекуррентные соотношения ]
Сложность: 4
Классы: 8

В магазин привезли цистерну молока. У продавца имеются чашечные весы без гирь (на чашки весов можно ставить фляги), а также три одинаковые фляги, две из которых пустые, а в третьей налит 1 л молока. Как отлить в одну флягу ровно 85 л молока, сделав не более восьми взвешиваний?

Решение

Поставим сначала на одну чашу весов две пустые фляги, а на другую чашу — флягу, в которой 1 л молока, и нальём в одну из пустых фляг столько молока, чтобы весы уравновесились. Тогда в этой фляге будет (1 − a) л молока, где a — количество литров молока, уравновешивающих одну пустую флягу. Далее поставим на одну чашу весов флягу с одним литром молока и флягу с (1 − a) л молока, а на другую чашу поставим пустую флягу и нальём в неё столько молока, чтобы весы уравновесились. Тогда в этой фляге будет два литра молока. Перельём содержимое этой фляги во флягу, в которой был один литр. Таким образом, мы получим в одной фляге 3 л молока, а в другой — (1 − a) л молока. Аналогично, имея фляги с (1 − a) л молока и n л молока, можно получить фляги с (1 − a) молока и с (2n + 1) л молока, а если флягу с (1 − a) л молока ставить на другую чашу, то можно получить фляги с (1 − a) и с (2n − 1) л молока. Действуя подобным образом, получаем последовательно 3, 5, 11, 21, 43, 85 л молока. Таким образом, можно отлить в одну флягу ровно 85 л молока за семь взвешиваний.
Прислать комментарий


Задача 98044

Тема:   [ Взвешивания ]
Сложность: 4
Классы: 8,9

Автор: Фомин Д.

Дана 61 монета одинакового внешнего вида. Известно, что две из них – фальшивые, что все настоящие одинакового веса, что фальшивые – тоже одинакового веса, отличающегося от веса настоящих монет. Но неизвестно, в какую сторону отличаются веса фальшивых монет от настоящих. Как можно это узнать с помощью трёх взвешиваний на двухчашечных весах без гирь? (Определить фальшивые монеты не требуется.)

Решение

См. решение задачи 98054.

Прислать комментарий

Страница: << 14 15 16 17 18 19 20 >> [Всего задач: 133]      



© 2004-... МЦНМО (о копирайте)
     
Пишите нам
Rambler's Top100

Проект осуществляется при поддержке Департамента образования г.Москвы и ФЦП "Кадры" .