Восстановление значения числа, исходя из двоичных цифр, производится в обратном порядке, слева направо, Сначала вы вычисляете

x0 = ap,

x1 = 2x0 + ap– 1 = 2ap + ap– 1,

x2 = 2x1 + ap– 2 = ap22 + ap– 12 + ap– 2,

и т. д. Последнее x есть искомое значение,

Игра 20.

Об этой игре я вам больше ничего не скажу. Совершенно необходимо, чтобы вы хотя бы время от времени работали, Впрочем, если я вам ничего не говорю, то дело, вероятно, в том, что я вам уже достаточно рассказал. Это — новая головоломка: выясните, почему у меня нет нужды что- либо вам еще говорить…

Игра 21.

Не протестуйте, я вам помогу… Что бы вы без меня делали? Но кстати, нужно быть честным — я был вдохновлен книгой Роуза Болла [BAL].

В начале игры у вас одна-единственная строка: Спраг-Грюнди… По прошествии некоторого времени она разбивается на много строк, и связанное с ними число Спрага-Грюнди есть Ним-сумма чисел Спрага-Грюнди для каждой строки. Следовательно, нужно вычислить числа Спрага-Грюнди для одной строки, и этого будет достаточно, Вот начало:

0 SG(0) = 0

Из 1 вы достигаете 0: SG(1) = 1.

Из 2 вы достигаете либо 1, либо 0. Поэтому SG(2) — наименьшее целое неотрицательное, отличное от 0 и 1; следовательно, SG(2) = 2.

Исходя из 3, вы можете получить либо одну строку с 2 спичками (SG = 2), либо одну строку с одной спичкой (SG = 1), либо две строки по одной спичке в каждой (удалив среднюю спичку). Но число SG(1, 1) есть Ним-сумма 1 в 1 и потому равно нулю. Следовательно, SG(3) равно трем. Таким же образом вы находите

0 1 2 3 1 4 3 2 1 4 2 6 4 1

Р К. Ги доказал, что начиная с 71, эта последовательность становится периодической с периодом 12. Я не представляю себе, для чего это может быть вам нужно — разве что, если это доставит вам удовольствие, чтобы передоказать его.

Задайте компьютеру таблицу первых чисел Спрага-Грюнди, снабдите его Ним-суммой. Остальное просто.

Игра 22.

Каждая вершина может быть связана с 5 другими, что создает 6 x 5 = 30 связей. Но каждая из них считается дважды (связь между A и B и между B и A). Поэтому есть 15 отрезков, которые нужно провести. Если игра полностью сыграна и все пути пройдены, то у одного из игроков на чертеже должно быть 8 отрезков (у того, который начинает). Они связывают 16 вершин, и поскольку в игре участвует только 6 вершин, то имеется хотя бы одна вершина, из которой выходят три отрезка. Пусть B, C и D — достигаемые этими отрезками вершины (см. рис. 36). Либо этот игрок прошел один из путей связывающих эти вершины, и тогда он проиграл. Либо он ни одного из них не провел, и тогда их провел его противник и противник проиграл…

Может оказаться, что проведено 14 отрезков, не образующих треугольников (как показано на рис. 37).

В этой позиции можно быть уверенным, что кто начинал, тот и проиграет, поскольку нет возможности свести партию вничью. Число возможных комбинаций очень велико, и вы не можете ожидать, что компьютер перепробует все возможные комбинации, прежде чем принять решение. Нужно отказаться от комбинаторных соображений и играть эвристически. Первый ход, если его делает компьютер, не важен: все прямые равноценны. После этого у компьютера остается не более 14 возможных линий, и он их все исследует. Каждой из них он сопоставляет вес: О, если эта линия завершает треугольник из его линия, и он тем самым проигрывает; 1, если эта линия завершает треугольник для его противника, так как она оставляет противнику шанс проиграть; максимальный вес, если эта линия связывает еще не использованные вершины. Когда все линии испытаны таким образом, компьютер делает ход с наибольшим весом. Его стратегия оценит шкалу весов, которые вы будете выбирать.

Игра 23.

В этой игре вы не можете охарактеризовать ситуации числом спичек, оставшихся в кучке, потому что этого недостаточно; нужно еще знать, сколько спичек только что было взято, так как именно это определяет максимальное число спичек, которые вы можете взять. Поэтому нужно определить ситуацию парой

p: число спичек, оставшихся в кучке,

q: число спичек, которое только что было взято.

Положение 0 является выигрывающим, каково бы ни было число спичек, только что взятых, чтобы достичь этого состояния:

SG(0, q) = 0.

Исходя из 1, мы всегда проигрываем, поскольку обязаны взять единственную оставшуюся спичку:

SG(1, q) = 1.

Если у вас осталось две спички, то всегда можно одну взять и одну оставить, следовательно, SG(2, q) /= 1, или можно взять две и закончить игру:

SG(2, q) = 2.

Начиная с трех, выбор меняется.

Для 3, 1 ваш противник может взять 1 и оставить пару 2, 1, следовательно, SG(3, 1) /= 2, либо взять 2 и оставить пару 1, 2, так что SG(3, 1) /= 1. Но большее количество изымать нельзя. Наименьшее неотрицательное целое, отличное от 1 и 2, есть 0: