Математические головоломки и развлечения
Шрифт:
Подробное объяснение софизма с треугольником и некоторые другие головоломки можно найти в двух главах «Исчезновение фигур» моей книги «Математические чудеса и тайны». [25] Софизм с галстуком подробно разобран у М. Крайчика. [26]
Заключительное «доказательство» того, что неинтересных чисел не существует, вызвало следующую телеграмму читателя:
Немедленно прекратите вылавливать неинтересные числа и превращать их в интересные. Для интереса оставьте хоть одно неинтересное число!
25
Гарднер
26
Kraitchik M. Mathematical Recreations. — 1942.
Глава 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) и нечетное число в последовательности сумм чисел по столбцам пропадает. Перепробовав остальные ходы, читатель убедится в том, что только указанный ход может сделать исходную позицию безопасной.
Если в каждом ряду стоит не более 31 фишки, то любую позицию легко проанализировать, использовав в качестве вычислительной машины (работающей в двоичной системе!) пальцы левой руки. Предположим, что в начальной позиции в первом ряду стоит 7, во втором 13, в третьем —24 и в четвертом —30 фишек. Вы должны сделать первый ход. Опасна или безопасна исходная позиция? Поверните левую руку с растопыренными пальцами ладонью к себе. Большой палец будет означать коэффициент при 16, указательный—коэффициент при 8, средний — при 4, безымянный — при 2 и мизинец — коэффициент при 1. Для того чтобы ввести в вашу вычислительную машину число 7, прежде всего нужно загнуть палец, соответствующий наибольшей степени двойки, входящей в 7.
Такой степенью является 4, поэтому вы загибаете средний палец.
Продолжая двигаться направо, добавляйте степени двойки до тех пор, пока вы в сумме не получите 7. Для этого вам придется загнуть средний, безымянный пальцы и мизинец. Три остальных числа —13, 24 и 30 — вводятся в вашу вычислительную машину точно так же, но, поскольку вам требуется вычислить сумму чисел, стоящих в столбцах при одной и той же степени двойки, вы, дойдя до согнутого пальца, который вам нужно согнуть еще раз, просто разгибаете его.
Независимо от количества рядов позиция безопасна, если по окончании работы вашей вычислительной машины на левой руке не останется ни одного загнутого пальца. Это означает, что любым ходом вы наверняка сделаете положение опасным и заведомо проиграете, если ваш противник знает о ниме столько же, сколько и вы. В приведенном нами примере большой и указательный пальцы останутся согнутыми. Это говорит о том, что позиция опасна и что, сделав правильный ход, вы сможете выиграть. Поскольку опасных позиций больше, чем безопасных, у первого игрока при случайном выборе начальной позиции гораздо больше шансов выиграть, чем проиграть.