Номер 11, страница 5, часть 2 - гдз по математике 2 класс учебник Петерсон

11 Игра «Ханойские башни»

Французский математик Эдуард Люка придумал игру, похожую на детскую пирамидку. В игре надо перенести кольца с одного стержня (a) на другой (b), беря по одному кольцу. При этом большое кольцо запрещается класть сверху маленького (как в пирамидке), но можно использовать ещё один дополнительный стержень (c).

а) Составь алгоритм переноса большого и маленького колец с первого стержня (a) на второй (b).

б) Реши эту же задачу, если на первом стержне 3 кольца: большое, среднее и маленькое.

а) Алгоритм переноса двух колец (большого и маленького) со стержня (а) на стержень (b), используя стержень (с) в качестве вспомогательного, заключается в следующем. Сначала необходимо освободить большое кольцо, переместив маленькое на свободный стержень. Затем перенести большое кольцо на целевой стержень и, наконец, положить на него маленькое. Последовательность ходов:

1. Перенести маленькое кольцо со стержня (а) на стержень (c).
2. Перенести большое кольцо со стержня (а) на стержень (b).
3. Перенести маленькое кольцо со стержня (c) на стержень (b).

Таким образом, для переноса двух колец требуется 3 хода.
Ответ: Алгоритм состоит из трех шагов: 1. Маленькое кольцо переместить с (а) на (c). 2. Большое кольцо переместить с (а) на (b). 3. Маленькое кольцо переместить с (c) на (b).

б) Решение задачи для трех колец (большое, среднее, маленькое) основано на решении для двух. Общая стратегия такова: сначала нужно перенести башню из двух верхних колец (маленького и среднего) со стержня (а) на вспомогательный стержень (с); затем перенести самое большое кольцо со стержня (а) на целевой стержень (b); и, наконец, перенести башню из двух колец со стержня (с) на стержень (b).

Детальная последовательность ходов выглядит так:

1. Перенести маленькое кольцо со стержня (а) на стержень (b).
2. Перенести среднее кольцо со стержня (а) на стержень (с).
3. Перенести маленькое кольцо со стержня (b) на стержень (с).
4. Перенести большое кольцо со стержня (а) на стержень (b).
5. Перенести маленькое кольцо со стержня (с) на стержень (а).
6. Перенести среднее кольцо со стержня (с) на стержень (b).
7. Перенести маленькое кольцо со стержня (а) на стержень (b).

Минимальное количество ходов для $n$ колец вычисляется по формуле $2^n - 1$. Для трех колец это $2^3 - 1 = 7$ ходов.
Ответ: Алгоритм переноса трех колец требует 7 шагов: 1. Маленькое (а → b). 2. Среднее (а → с). 3. Маленькое (b → с). 4. Большое (а → b). 5. Маленькое (с → а). 6. Среднее (с → b). 7. Маленькое (а → b).