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

программы, играющей в 24 карты). — Примеч. ред.

21

Можно доказать, что в играх, подобных игре Нима и обычным шахматам, — в играх с полной информацией — выигрывающая стратегия всегда существует. Это — относительно простая теорема. Другое дело, что эта выигрывающая стратегия может быть не очень простой (Ним) или вообще еще не открытой (шахматы). — Примеч. ред.

22

В частном случае, когда в каждой кучке игра идет по правилам игры Нима, число Спрага-Грюнди каждой кучки равно просто числу спичек. — Примеч. ред.

23

Эти рассуждения безусловно справедливы, если в моем распоряжении остался один-единственный ход — тогда этим ходом я хочу «попасть в десятку», т. е. угадать искомую комбинацию. Если же ход не последний, то моя цель — получить как можно больше информации об искомой комбинации. Может случиться, что для этого выгоднее взять комбинацию вне множества, описанного автором. — Примеч. ред.

24

Маленькая головоломка для знающих французский (или хотя бы имеющих словарь): откуда это обозначение? — Примеч. ред.

25

При чтении этого абзаца вспоминается шутка Маяковского. После одного из своих выступлений он получил из зала записку: «Мы с товарищем слушали ваши стихи и ничего не поняли». Маяковский ответил: «Нужно иметь умных товарищей». — Примеч. ред.

26

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

27

См. головоломку 29. — Примеч. пер.

28

В математике для решения этой задачи есть полезная формула Ньютона-Лейбница:

где F —функция, определяемая условием F (x) = f(x), x ? [p, q]. Впрочем, все эти интегралы нам не понадобятся, так как у этой формулы есть гораздо более простой аналог для сумм: a_i + a_{i +1} + … + a_j = b_j ? b_i?1, где последовательность {b} определяется условием, что b_k ? b_k?1 = а_k для любого k от 1 до n. Последовательность {b} легко построить: b₀ = 0, b_{k +1} = b_k + a_k+1. Для последовательности {b} задача ставится так: найти такие i < j, что разность b_j ? b_i максимальна. С этой задачей уже легче справиться. — Примеч. ред.

29

Вот пара условий, которая не обладает этим свойством: t: x ? 0; u: sin(1/x) > 0. — Примеч. ред.

30

Прочтя весь этот ужас, я решил провести решение, основанное на методике из курса программирования механико-математического факультета МГУ.

Каждой последовательности чисел {a₁,