Головоломка Мажордома

Мажордом был хитрым и достаточно образованным человеком. По словам Чосера, "так овцам счет умел вести он, акрам и так подчистить свой амбар иль закром. Что сборщики все оставались с носом. Он мог решать сложнейшие вопросы..." (Здесь и далее цитаты приводятся по книге: Джеффри Чосер, "Кентерберийские рассказы", перевод с англ. И. Кашкина и О. Румера, БВЛ, М.: "Художественная литература", 1973. Примечания переводчика, касающиеся реалий средневековой Англии, также основа- ны на примечаниях к данному изданию, сделанных И. Кашкиным. - Примеч. пер.). Поэт отмечает также, что "он никогда не попадал впросак". Всякого рода забавные задачи и причудливые идеи без труда возникали в его остром уме. В одной придорожной таверне, где остановились паломники, его бдительный взор обнаружил несколько кругов сыра разной величины. И вот, попросив четыре табурета, он предложил показать одну из своих головоломок, которая могла бы позабавить путников во время отдыха. Затем Мажордом положил на крайний табурет восемь кругов сыра так, как это показано на рисунке.

- Вот загадка, - воскликнул он, - которую я задал однажды своим приятелям из Болдсуэлла, что находится в Норфолке, и, клянусь святым Иосифом, среди них не нашлось ни одного, кто осилил бы ее! Однако она очень проста, ибо все, что я хочу, так это чтобы, перекладывая сыры с одного табурета на другой, вы перенесли все их на табурет, стоящий на другом конце, ни разу не положив какой-нибудь круг сыра на круг меньшего размера. Того, кто сумеет это сделать с наименьшим числом перекладываний, угощу я глотком самого лучшего вина, какое только найдется у нашего доброго хозяина.
Интересно решить эту головоломку с наименьшим числом перекладываний сначала с 8, затем с 10 и, наконец, с 21 кругом сыра.

Ответ

8 кругов сыра можно переложить на крайний табурет за 33 хода, 10 сыров - за 49 и 21 сыр - за 321 ход. Ниже приведен общий метод решения для случаев с тремя, четырьмя и пятью табуретами.
Составим следующую таблицу, которую можно продолжить для любого нужного нам числа сыров.

Первая ее строка содержит натуральные числа. Вторая строка получается сложением чисел первой строки от начала до данного места. Числа третьей строки получаются аналогичным путем из чисел, стоящих во второй строке. Четвертая строка состоит из последовательных степеней числа 2 минус 1. Следующие две строки получаются удвоением числа, стоящего в данной строке, и добавлением к произведению числа из предыдущей строки, которое стоит над тем местом, где выписывается результат. Эта таблица дает одновременно решения для любого числа сыров и трех табуретов, для треугольных чисел и четырех табуретов и для пирамидальных чисел и пяти табуретов. В этих случаях метод решения (складывание сыров друг на друга) всегда только один.
В случае трех табуретов первая и четвертая строки таблицы говорят нам, что 4 сыра можно перенести за 15 ходов, 5 - за 31, 7 - за 127 ходов. Вторая и четвертая строки показывают, что в случае четырех табуретов 10 сыров можно переложить за 49, а 21 - за 321 ход. Точно так же в случае пяти табуретов мы находим из третьей и шестой строк, что для 20 сыров требуется 111 ходов, а для 35 - 351 ход. Но из таблицы мы, кроме того, можем определить и нужный способ перекладывания сыров. Так, например, в случае четырех табуретов и 10 сыров предыдущий столбец указывает на то, что мы должны образовать стопки из 6 и 3 сыров, для чего потребуется соответственно 17 и 7 ходов. А именно: сначала мы складываем 6 наименьших сыров за 17 ходов на один из табуретов; затем мы складываем 3 следующих сыра на другой табурет за 7 ходов; далее мы перекладываем самый большой круг сыра за 1 ход; затем перекладываем 3 сыра за 7 ходов; и, наконец, мы перекладываем 6 сыров за 17 ходов, что в сумме и составляет 49 ходов. Точно так же нам известно, что в случае пяти табуретов 35 сыров следует сложить друг на друга из 20, 10 и 4 сыров соответственно, для чего потребуется 111, 49 и 15 ходов.
Если в случае четырех табуретов число сыров не треугольно, а в случае пяти табуретов - не пирамидально, то решений будет больше одного и потребуются дополнительные таблицы. Именно так обстоит дело в случае 8 сыров Мажордома. Но я предоставляю самому читателю обобщить решение нашей задачи на этот случай.