Задача приведенная ниже, это одна из вариаций известной задачи под названием "Ханойская башня". Предыдущие задачи по теме: Задача 26, Задача 40.
Условие:
Есть три поля: на одном из них лежит n монет, а остальные свободны. За один ход можно переложить монету на свободное место или поверх любой другой монеты. За какое минимальное количество ходов можно собрать все монеты на первом поле в обратном порядке.
Замечание: Первый ответ который приходит в голову это 3n ходов. С первого поля переложили на второе, со второго на третье, с третьего на первое. Но нужно быть внимательным и даже если бы это был бы верный ответ, он сам по себе не является решением задачи.
Решение:
Оценка: Обозначим поля A, B, C. Покажем, что меньше чем за 3n-2 ходов это сделать нельзя. Очевидно, что имея всего два поля нельзя поменять местами две монетки. Ясно, что никакая монетка не может все время оставаться на A, то есть должна сделать не менее двух ходов. Предположим, что можно справиться менее чем за 2 хода, тогда как минимум три монеты сделали 2 хода. По крайней мере две из них побывали на одном и том же поле B или C. Вы бросим все остальные монеты и повторим ходы этих двух монет. Но имея только два поля поменять их порядок нельзя. Получили противоречие доказывающее, что быстрее чем за 3n-2 управиться нельзя.
Пример: Покажем теперь как это сделать за 3n-2 ходов. Переложим первую монету на B, остальные на C. Теперь монету с B вернем на A, все остальные (кроме самой нижней) с C переложим на B. Оставшуюся на C монету переложим на A. Теперь все монеты с B переложим на A. Сделано 3n-2 хода и монеты находятся в обратном порядке к изначальному.
Всем кто дочитал, спасибо за внимание! Удачных вам вычислений!