Если разделить n на 2, вы получаете в остатке а₀, крайнюю справа цифру двоичного представления, а частное

a_p2^p−1 + a_p−12^p-2 + . .. + a₂2 + a₁,

которое также является двоичной записью целого числа, получаемой из предыдущей записи вычеркиванием ее крайней правой цифры. По индукции (или, что то же самое, рекурсивно или итеративно) вы получите все двоичные цифры числа n справа налево.

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

x₀ = a_p,

x₁ = 2x₀ + a_p−1 = 2a_p + a_p−1,

x₂ = 2x₁ + a_p-2 = a_p2² + a_p−12 + a_p-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 × 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:

SG(3, 1) = 0.

Если вы оставляете 3, взяв больше, чем одну спичку, то противник может взять и 3, достигая 0 с SG (0, 3) = 0, и, следовательно,

SG(3, q > 1) = 3.

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

Игра 24.

Я много раз излагал нижеследующее различным программистам и каждый раз оставался в недоумении, видя, что они не считают это «очевидным».

Вы играете в «Гениального отгадчика», вы ищете неизвестную комбинацию; чтобы сделать это, вы предлагаете комбинации c₁, c₂, …, c_k. Для каждой из них вы получаете ответ о числе белых и черных шашек:

б₁, ч₁; б₂, ч₂; …; 6_k, ч_k.

Следующая предлагаемая комбинация должна быть такой, которая при сравнении с c₁ дает ч₁ черных и б₁ белых шашек; …; при сравнении с c_k она должна давать ч_k черных и б_k белых шашек. Почему? Вы ищете неизвестную комбинацию. Но эта комбинация дает при сравнении с комбинацией c_i именно ч_i черных и б_i белых шашек. Бесполезно искать решение вне множества комбинаций, обладающих этим свойством: там его не может быть[23].

Следовательно, у вас есть простая стратегия. Допустите, что вы уже каким-то образом выбрали x первых комбинаций, где x фиксировано. Компьютер располагает значениями ч_i, б_i для i от 1 до x. Вы предоставляете ему возможность перепробовать все комбинации и запоминать только те, которые дают при сравнении с уже испытанными комбинациями правильные значения черных и белых шашек.

Так как возможных комбинаций много, то нужно попытаться не перебирать их все заново при каждой следующей попытке. Вы можете, например, начать с первой позиции новой комбинации. Вы присваиваете ей первый цвет, а затем смотрите, сколько черных шашек он образует с уже испытанными комбинациями. Если он дает черную шашку с комбинацией, с которой ее не следует давать, то этот цвет нужно отбросить. Когда вы уже нашли подходящий цвет для этой позиции, переходите к следующей. Она может дать вам слишком много черных шашек, и это событие очень даже вероятно. Мало таких комбинаций, которые черных шашек не дают совсем, и больше таких, которые дают не более одной. То, что было зафиксировано для первого цвета, не может быть использовано для второго, Но заметьте, что у вас есть и другой случай для отбрасывания: если нужно получить три черных шашки при сравнении с некоторой комбинацией и если первая позиция никакого вклада не вносит, то необходимо, чтобы вторая позиция вносила свой вклад (предполагая, что есть 4 позиции). Действуя таким образом, вы достигаете в конце концов комбинации с правильным числом черных шашек. Тогда нужно проверить белые. Если они принимают нужные значения для всех предложенных комбинаций, то у вас готово новое предложение, и вы получите либо успех, либо новые элементы для сравнения.