Олимпиадная задача по комбинаторике: максимум способов взвешивания гирями степеней двойки

  Пусть K_n(P) – число способов, которыми можно взвесить вес P, используя гири веса  1, 2,..., 2ⁿ,  и     (максимальное число способов, которыми можно взвесить какой-либо вес с помощью этих гирь). Очевидно,  K₀ = 1,  K₁ = 2.   а) Наша задача – доказать, что  K₉ ≤ 89.  Мы докажем, что  K_n+1 ≤ K_n + K_n–1  для каждого  n ≥ 1.  Последовательно применяя это неравенство, получим: K₂ ≤ 3,  K₃ ≤ 5,  ..., K₉ ≤ 89.

  Рассмотрим гири  1, 2, ..., 2ⁿ⁺¹  и какой-либо вес P. Если P чётно, то, очевидно, при его взвешивании гиря веса 1 не используется, то есть взвесить вес P можно тем же числом способов, что и вес ^P/₂ с помощью гирь  1, 2,..., 2ⁿ,  то есть  K_n+1(P) = K_n(^P/₂).  Если P делится на 4, то аналогично

K_n+1(P) = K_n–1(^P/₄).

  Пусть P нечётно. Тогда при его взвешивании обязательно должна быть использована гиря веса 1. Её можно положить как на одну, так и на другую чашу весов. В одном случае мы сведём задачу к взвешиванию груза веса  P – 1,  в другом – к взвешиванию груза веса  P + 1  гирями веса  2, 4,..., 2ⁿ⁺¹.  Таким образом,  K_n+1(P) = K_n+1(P–1) + K_n+1(P+1).  Так как оба числа  P – 1  и  P + 1  чётны, а одно из них делится на 4, то в одном из случаев мы имеем не более K_n–1 способов взвешивания, в другом – не более K_n. Итак,  K_n+1(P) ≤ K_n + K_n–1.   б) Пример: 171 г. Рассмотрим последовательность  1, 1, 3, 5, 11, 21, 43, 85, 171.  Легко проверить, что для каждого члена P_n+1 этой последовательности пара чисел  P_n+1 – 1  и  P_n+1 + 1  совпадает с парой чисел  2P_n и 4P_n–1  (не обязательно в том же порядке). Отсюда, как видно из а), следует равенство

K_n+1(P_n+1) = K_n(P_n) + K_n–1(P_n–1),  а так как  K₁(P₁) = 2,  K₂(P₂) = 3,  то, последовательно вычисляя, получим  K₉(171) = K₉(P₉) = 89.

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