|
|
 |
Условие
В ящике лежат два ящика поменьше, в каждом из них ещё по два ящика и т.д. n раз. В каждом из 2n маленьких ящиков лежит по монете, причём одни вверх гербом, а остальные – вверх решкой. За один ход разрешается перевернуть один любой ящик вместе со всем, что в нём лежит. Доказать, что не больше, чем за n ходов можно расположить ящики так, что число монет, лежащих вверх гербом, будет равно числу монет, лежащих вверх решкой.
Решение
Назовём самый большой ящик ящиком ранга n, следующие по величине два ящика – ящиками ранга n – 1 и т. д. до ящиков ранга 1, в которых лежат монеты. Разность между количеством гербов и решек в каком-нибудь ящике назовём дефектом этого ящика; дефект ящика ранга обозначим через d. Докажем, что всегда найдётся ящик, при переворачивании которого |d| уменьшается не меньше, чем вдвое. Этого достаточно, так как в исходном положении |d| ≤ 2n, и любой дефект ящика ранга n чётен.
Рассмотрим случай d > 0. Предположим, что указанное уменьшение невозможно. При переворачивании ящика с дефектом d1 из d вычитается 2d1. По предположению |d – 2d1| > d/2, поэтому либо d1 < d/4, либо d1 > 3d/4 ≥ 3/2.
Дефект каждого ящика ранга 1 не больше 1, что меньше 3d/4, поэтому он меньше d/4. Но тогда дефект каждого ящика ранга 2 меньше d/2, значит, он меньше d/4. Продолжая аналогичные рассуждения, получим, что и дефект самого большого ящика меньше d/2. Противоречие.
