Программирование игр и головоломок

вектора, дающего для диска 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	f4	p	d	h
0	0	0		1	0
1	1	1		2	2
2		3		2	3
3	2	5	1	4	5