k = (2r + 1)2р– 1.

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

Игра 34.

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

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

2f4(p– 1) + 2n– p+1– 1 >= 2f4(р) + 2n– p– 1,

2f4(p + 1) + 2n– p-1– 1 >= 2f4(р) + 2n– p– 1.

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

d(р) = f4(p + 1) - f4(p).

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

d(p– 1) < 2n– p– 1, d(р) >= 2n– p-2.

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

g(р– 1) ~ 2n– 2 <= g(р).

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

h(р) = log2(g(р)) = р + Iog2(d(р)).

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

h(р– 1) < n– 1 <= h(р).

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

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

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

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

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

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

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

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

Имеем

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

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

(2n– 1 -

Игра 35.