Все диски имеют общее свойство: нечетные диски перемещаются в том же направлении, что и диск 1, а четные диски — в другом направлении.

В вышеприведенной программе стратегия совершенна с точки зрения исполнения вручную, потому что в каждый данный момент сразу видно, какой диск нужно переместить, если это не самый маленький диск (меньший из двух остальных дисков перемещается на больший). В нашей программе вам нужно вычислить это движение. Один из наиболее простых способов состоит в том, чтобы представить игру с помощью вектора, дающего для диска i номер стержня, на котором он находится. Диск, подлежащий перемещению — это наименьший Диск, который находится не на том же стержне, что и диск 1, следовательно, номер стержня которого отличается от d. Этот самый диск перемещается со стержня, на котором он находится — с номером x — на стержень 3 − x − d.

Обозначим первое перемещение через 1. Поскольку диск 1 перемещается один раз в каждой паре ходов (точнее, перемещается через ход), то он перемещается в каждый нечетный ход. По индукции покажите, что диск p перемещается в ходы с номерами, которые делятся на 2^р−1, но не делятся на 2^p (т. е. являются нечетными кратными числа 2^p−1).

Номер k любого хода может быть единственным способом представлен в виде

k = (2r + 1)2^р-1.

Перемещаемый на этом ходе диск есть диск с номером p, и это — его (r + 1)-е перемещение. Так как он начинает движение со стержня 0 и перемещается в направлении s_p (1, если р нечетно, и 2 в противном случае), то на этом ходе диск перемещается с rs_p-го на (r + 1)s_р-й стержень, где эти числа берутся по модулю 3.

Игра 34.

Попытаемся охарактеризовать значение р, дающее игре оптимум для данного n. Нам известно, что f₃(n − p)= 2^n-p − 1.

Должно выполняться

2f₄(p − 1) + 2^n-p+1 − 1 ≥ 2f₄(р) + 2^n-p − 1,

2f₄(p + 1) + 2^n-p-1 − 1 ≥ 2f₄(р) + 2^n-p − 1.

Удобно пользоваться первыми разностями для функции f₄:

d(р) = f₄(p + 1) − f₄(p).

Два приведенных выше соотношения могут быть переписаны следующим образом:

d(p − 1) < 2^n-p-1, d(р) ≥ 2^n-p-2.

Интересно рассматривать даже не d(р), а скорее 2^pd(р) = g(р):

g(р − 1) ~ 2^n-2 ≤ g(р).

Можно еще упростить запись, беря не g(р), а величину

h(р) = log₂(g(р)) = р + Iog₂(d(р)).

Тогда получаем

h(р − 1) < n − 1 ≤ h(р).

При данном n величина р — наименьшее целое, для которого h больше или равно n − 2.

Приведем здесь первые из полученных таким образом значений:

n	q	f 4	p	d	h
0	0	0		1	0
1	1	1		2	2
2		3		2	3
3	2	5	1	4	5
4		9	1	4	6
5		13	1	4	7
6	3	17	3	8	9
7		25	3	8	10
8		33	4	8	11
9		41	5	8	12
10	4	49	6	16	14
11		65	6	16	15

Мы добавили в таблицу переменное q, связанное с «треугольными» числами. Для n = q(q + 1)/2 действительно убеждаемся, что

h(р) = h(р − 1) + 2

в то время как для других n

h(p) = h(p − 1) + 1.

Исходя из n, можно вычислить q:

q = целая_часть ((

− 1)/2).

Имеем

h(n) = n + целая_часть ((

− 1)/2).

Покажите это по индукции. Исходя отсюда, вычисляется все. Таким образом, если n дано, то р — наименьшее целое, большее или равное

(2n − 1 −

)/2.

Игра 35.

Возьмем, например, игру с 50 дисками. Она реализуется переносом сначала 40 дисков на запасной стержень, а затем 10 последних дисков со стержня 0 на стержень 1, с использованием при этом только трех свободных стержней. Наконец, остается перенести начальные 40 самых маленьких дисков с запасного стержня на первый стержень, используя все 4 стержня.

Чтобы переместить 40 дисков с 4 стержнями, сводим задачу к перемещению 31 диска с 4 стержнями, а затем 9 с 3 стержнями…

Таким образом, дело сводится к разбиению 50 дисков на 8 сегментов:

Каждый сегмент перемещается с использованием 3 стержней, в чем мы следуем итеративной стратегии, которая уже описана выше. Единственный вопрос — это правильный выбор запасных стержней.

Договоримся работать с тремя стержнями 0, 1, 2, так что стержень 3 остается пустым и служит запасным стержнем при любом перемещении какого-либо сегмента. Более точно, перемещение сегмента р со стержня d на стержень а осуществляется с помощью изученной выше процедуры Н, в которой запасным стержнем является стержень 3.

Сегмент 1 перемещается в каждый из двух ходов подряд (под ходом я понимаю последовательность операций, реализующих процедуру Н), всегда в одном и том же направлении.