Номер 17, страница 53 - гдз по математике 5 класс сборник задач Пирютко, Терешко

состоит из трёх стержней, пронумерованных числами $1$, $2$, $3$. На стержень $1$ надета пирамидка из $6$ дисков различного диаметра в порядке возрастания диаметра. Диски можно перекладывать с одного стержня на другой по одному, при этом диск нельзя класть на диск меньшего диаметра.

Необходимо переложить всю пирамидку со стержня $1$ на стержень $3$.

$1$ $2$ $3$

Задача о «Ханойских башнях» является классическим примером задачи, решаемой с помощью рекурсии. Цель — переместить пирамидку из $n$ дисков с одного стержня на другой, соблюдая определённые правила. В данном случае у нас есть $n=6$ дисков, которые нужно переместить со стержня 1 на стержень 3, используя стержень 2 как вспомогательный.

Для решения задачи выделим общую стратегию. Чтобы переместить башню из $n$ дисков со стержня-источника (И) на стержень-приёмник (П), используя вспомогательный стержень (В), необходимо выполнить три последовательных шага. Во-первых, переместить верхние $n-1$ дисков со стержня И на стержень В. Во-вторых, переместить самый большой, $n$-й диск, со стержня И на стержень П. В-третьих, переместить $n-1$ дисков со стержня В на стержень П.

Обозначим минимальное количество ходов, необходимое для перемещения $n$ дисков, как $M(n)$. Исходя из описанного алгоритма, мы можем составить рекуррентное соотношение. Количество ходов на первом шаге равно $M(n-1)$, на втором — 1 ход, на третьем — снова $M(n-1)$. Таким образом, общее количество ходов выражается формулой: $M(n) = M(n-1) + 1 + M(n-1) = 2 \cdot M(n-1) + 1$.

Чтобы решить это рекуррентное соотношение, нам нужен базовый случай. Для перемещения одного диска ($n=1$) требуется всего один ход, то есть $M(1) = 1$. Используя эту базу и рекуррентную формулу, мы можем последовательно найти количество ходов для любого числа дисков. Например, для 2 дисков: $M(2) = 2 \cdot M(1) + 1 = 2 \cdot 1 + 1 = 3$ хода. Для 3 дисков: $M(3) = 2 \cdot M(2) + 1 = 2 \cdot 3 + 1 = 7$ ходов.

Можно заметить, что количество ходов следует закономерности $M(n) = 2^n - 1$. Эта формула является общим решением для задачи о Ханойских башнях. Проверим её для наших вычислений: $M(1) = 2^1 - 1 = 1$; $M(2) = 2^2 - 1 = 3$; $M(3) = 2^3 - 1 = 7$. Формула верна.

Теперь применим её для решения нашей задачи с $n=6$ дисками. Минимальное количество ходов для перемещения 6 дисков со стержня 1 на стержень 3 составляет: $M(6) = 2^6 - 1$.

Вычислим значение $2^6$: $2^6 = 2 \cdot 2 \cdot 2 \cdot 2 \cdot 2 \cdot 2 = 64$.

Следовательно, минимальное количество ходов равно: $M(6) = 64 - 1 = 63$.

Таким образом, для перемещения всей пирамидки из 6 дисков со стержня 1 на стержень 3 потребуется минимум 63 хода.

Ответ: 63