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

Проект МЦНМО
при участии
школы 57
Задача 98344
Темы:    [ Взвешивания ]
[ Рекуррентные соотношения (прочее) ]
[ Раскладки и разбиения ]
[ Индукция (прочее) ]
Сложность: 5
Классы: 9,10,11
В корзину
Прислать комментарий

Условие

Имеется набор гирь, веса которых в граммах: 1, 2, 4,... , 512 (последовательные степени двойки) – по одной гире каждого веса. Груз разрешается взвешивать с помощью этого набора, кладя гири на обе чашки весов.
  а) Докажите, что никакой груз нельзя взвесить этими гирями более чем 89 способами.
  б) Приведите пример груза, который можно взвесить ровно 89 способами.


Решение

  Пусть Kn(P) – число способов, которыми можно взвесить вес P, используя гири веса  1, 2,..., 2n,  и     (максимальное число способов, которыми можно взвесить какой-либо вес с помощью этих гирь). Очевидно,  K0 = 1,  K1 = 2.

  а) Наша задача – доказать, что  K9 ≤ 89.  Мы докажем, что  Kn+1Kn + Kn–1  для каждого  n ≥ 1.  Последовательно применяя это неравенство, получим:
K2 ≤ 3,  K3 ≤ 5,  ..., K9 ≤ 89.
  Рассмотрим гири  1, 2, ..., 2n+1  и какой-либо вес P. Если P чётно, то, очевидно, при его взвешивании гиря веса 1 не используется, то есть взвесить вес P можно тем же числом способов, что и вес P/2 с помощью гирь  1, 2,..., 2n,  то есть  Kn+1(P) = Kn(P/2).  Если P делится на 4, то аналогично
Kn+1(P) = Kn–1(P/4).
  Пусть P нечётно. Тогда при его взвешивании обязательно должна быть использована гиря веса 1. Её можно положить как на одну, так и на другую чашу весов. В одном случае мы сведём задачу к взвешиванию груза веса  P – 1,  в другом – к взвешиванию груза веса  P + 1  гирями веса  2, 4,..., 2n+1.  Таким образом,  Kn+1(P) = Kn+1(P–1) + Kn+1(P+1).  Так как оба числа  P – 1  и  P + 1  чётны, а одно из них делится на 4, то в одном из случаев мы имеем не более Kn–1 способов взвешивания, в другом – не более Kn. Итак,  Kn+1(P) ≤ Kn + Kn–1.

  б) Пример: 171 г. Рассмотрим последовательность  1, 1, 3, 5, 11, 21, 43, 85, 171.  Легко проверить, что для каждого члена Pn+1 этой последовательности пара чисел  Pn+1 – 1  и  Pn+1 + 1  совпадает с парой чисел  2Pn и 4Pn–1  (не обязательно в том же порядке). Отсюда, как видно из а), следует равенство
Kn+1(Pn+1) = Kn(Pn) + Kn–1(Pn–1),  а так как  K1(P1) = 2,  K2(P2) = 3,  то, последовательно вычисляя, получим  K9(171) = K9(P9) = 89.


Ответ

б) Например, 171 г.

Замечания

1. Вес 171 – не единственный, который можно взвесить ровно 89 способами. Вес  341 = 512 – 171  (и только он) обладает тем же свойством.

2. Последовательность из пункта б) можно продолжить: формула общего члена этой последовательности:     Рассмотрение этой последовательности доказывает, что  Kn+1 = Kn + Kn–1  для всех  n ≥ 1,  то есть числа Kn (с точностью до сдвига нумерации) совпадают с числами Фибоначчи.

3. Эта задача с небольшим изменением формулировки давалась также в Задачнике "Кванта" (задача М1593 б). Более подробное решение см. в решениях Задачника "Кванта".

4. Баллы: 5 + 4.

Источники и прецеденты использования

олимпиада
Название Турнир городов
Турнир
Номер 18
Дата 1996/1997
вариант
Вариант весенний тур, основной вариант, 8-9 класс
Задача
Номер 7

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

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