|
|
 |
Условие
Имеется набор гирь, веса которых в граммах: 1, 2, 4,... , 512 (последовательные степени двойки) – по одной гире каждого веса. Груз разрешается взвешивать с помощью этого набора, кладя гири на обе чашки весов.
а) Докажите, что никакой груз нельзя взвесить этими гирями более чем 89 способами.
б) Приведите пример груза, который можно взвесить ровно
89 способами.
Решение
Пусть Kn(P) – число способов, которыми можно взвесить вес P, используя гири веса 1, 2,..., 2n, и (максимальное число способов, которыми можно взвесить какой-либо вес с помощью этих гирь). Очевидно, K0 = 1, K1 = 2.
а) Наша задача – доказать, что K9 ≤ 89. Мы докажем, что Kn+1 ≤ Kn + 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.
