Question

Сизиф играет сам с собой в такую игру. У него есть лестница из 100 ступенек, на каждой ступеньке написан ее номер – число от 1 до 100. На ступеньках с номерами 1, 100 и 64 лежат по камню. За один ход Сизиф берет любой крайний камень (лежащий на ступеньке с самым маленьким или на ступеньке с самым большим номером) и кладет его на ступеньку ровно посередине между двумя другими камнями. Если же между двумя другими камнями четное количество ступенек, он выбирает любую из двух средних. Когда ни один камень нельзя переложить таким образом, игра заканчивается. Какое наибольшее количество ходов может продолжаться игра?

Answer 1

Ответ:

6

Объяснение:

Назовём расстоянием между двумя ступеньками количество ступенек между ними (например, расстояние между ступеньками с номерами 1 и 64 равно 62; между 64 и 100 - 35). Максимальным расстоянием я буду называть наибольшее расстояние от среднего камня до крайнего.

Если положить камень посередине между камнями, расстояние между которыми равно $x$, то если $x$ нечётное, то новые расстояния будут $(x-1)/2$, а если чётное, то $x/2$ и $(x-1)/2$.

Заметим, что максимальное расстояние на $i$-м шаге равно $m_i>0$, то после перекладывания камня оно будет не больше

$\left\lceil\dfrac{m_i-1}{2}\right\rceil,$

где $\lceil x\rceil$ - округление до ближайшего большего целого.

Значит, после первого хода Сизифа максимальное расстояние будет не больше 31, после второго не больше 15, после третьего 7, после четвертого 3, после пятого 1, после шестого 0. Больше новых ходов Сизиф сделать не сможет, значит, количество ходов может быть не больше шести.

Вот как может проходить игра из шести шагов (числа обозначают номера ступенек, на которых лежат камни):

1. До: 1, 64, 100. После: 1, 33, 64.
2. До: 1, 33, 64. После: 1, 17, 33.
3. До: 1, 17, 33. После: 1, 9, 17.
4. До: 1, 9, 17. После: 1, 5, 17.
5. До: 1, 5, 17. После: 1, 3, 5.
6. До: 1, 3, 5. После: 1, 2, 3.