Математические головоломки и развлечения

Подробное объяснение софизма с треугольником и некоторые другие головоломки можно найти в двух главах «Исчезновение фигур» моей книги «Математические чудеса и тайны».[25] Софизм с галстуком подробно разобран у М. Крайчика.[26]

Заключительное «доказательство» того, что неинтересных чисел не существует, вызвало следующую телеграмму читателя:

Немедленно прекратите вылавливать неинтересные числа и превращать их в интересные. Для интереса оставьте хоть одно неинтересное число!

Глава 14. НИМ И ТАК-ТИКС

Ним — одна из самых старых и занимательных математических игр. Играют в нее вдвоем. Дети используют для игры камешки или клочки бумаги, взрослые предпочитают раскладывать монетки на стойке бара. В наиболее известном варианте нима 12 монет раскладывают в три ряда так, как показано на рис. 84.

Рис. 84

Монеты, разложенные для игры в ним по схеме «3, 4, 5».

Правила нима просты. Игроки по очереди забирают по одной или нескольку монет из любого ряда. Выигрывает тот, кто возьмет последнюю монету. Можно играть и наоборот: считать того, кто возьмет последнюю монету, проигравшим. Хороший игрок вскоре обнаружит, что и в том и в другом варианте можно добиться победы, если после его хода останется два одинаковых ряда монеток (то есть с одним и тем же числом монет в каждом ряду), причем в каждом ряду будет находиться более одной монетки. Выиграть можно и в том случае, если в первом ряду останется одна, во втором — две и в третьем — три монетки. Тот, кто открывает игру, наверняка побеждает, если первым ходом он забирает две монетки из верхнего ряда, а затем рационально продолжает игру.

Казалось, что анализ столь простой игры не может привести к каким-либо неожиданностям, однако в начале века было сделано удивительное открытие. Обнаружилось, что ним допускает обобщение на любое число рядов с любым числом фишек в каждом ряду и что с помощью до смешного простой стратегии, используя двоичную систему счисления, любой желающий может стать непобедимым игроком. Полный анализ и доказательство существования оптимальной стратегии впервые опубликовал в 1901 году Чарлз Л. Бутон, профессор математики Гарвардского университета. Бутон и назвал игру «ним» от устаревшей формы английских глаголов «стянуть», «украсть».

Каждую комбинацию фишек в обобщенной игре Бутон назвал либо «опасной», либо «безопасной». Если позиция, создавшаяся после очередного хода игрока, гарантирует ему выигрыш, она называется безопасной; в противном случае позиция называется опасной.

Так, при игре в ним по описанной выше схеме «3, 4, 5» (рис. 84) первый игрок окажется в безопасной позиции, взяв две монетки из верхнего ряда. Любую опасную позицию, сделав соответствующий ход, всегда можно превратить в безопасную. Каждая безопасная позиция становится опасной после любого хода. Следовательно, рациональная игра заключается в том, чтобы каждый раз превращать опасную позицию в безопасную.

Чтобы определить, опасна или безопасна данная позиция, число фишек в каждом ряду нужно записать в двоичной системе. Если сумма чисел в каждом столбце (разряде) равна нулю или четна, то позиция безопасна. Если же сумма нечетна хотя бы в одном разряде, то позиция опасна.

В двоичной системе нет ничего сверхъестественного. Это всего лишь способ записи чисел в виде суммы степеней двойки. В помещенной здесь таблице приведена двоичная запись чисел от 1 до 20.

Двоичные числа для игры в ним

Обратите внимание на то, что, двигаясь справа налево, вы каждый раз попадаете в столбец, отвечающий большей степени двойки, чем предыдущий (то есть переходите ко все более старшим двоичным разрядам). Так, двоичная запись 10 101 говорит нам, что к 16 нужно прибавить 4 и 1, а это дает десятичное число 21. Записывая в двоичной системе число фишек в каждом ряду, расставленных по схеме «3, 4, 5», мы получим

Сумма цифр в среднем столбце равна 1 — нечетному числу, что свидетельствует об опасности данной позиции. Поэтому первый игрок может сделать ее безопасной. Как уже объяснялось, именно это он и делает, когда забирает из верхнего ряда две монетки. В результате в верхнем ряду остается лишь 1 монетка (двоичное число также 1) и нечетное число в последовательности сумм чисел по столбцам пропадает. Перепробовав остальные ходы, читатель убедится в том, что только указанный ход может сделать исходную позицию безопасной.