ГОРОДСКОЙ КЛАССИЧЕСКИЙ ЛИЦЕЙ РЕФЕРАТ Математические игры и головоломки
    Подготовил:
    Петров А. А., 10Б класс (физ-мат) г. Кемерово - 1999
     Математические игры и головоломки очень популярны, как, впрочем, и все игры. И далеко не всегда более сложная игра - более интересная. Часто миллионы людей с неугасаемым интересом играют в самые простые игры, и именно эти игры больше всего ценят, именно они входят в историю математики и прославляют своих создателей. Наиболее приближенными к математике являются головоломки, но много головоломок образовалось из когда-то существовавших (а некоторые из ещё существующих) игр. Большинство таких основополагающих игр было придумано древнегреческими математиками. В последнее время математическим играм внимание уделяется, в основном, для нахождения выигрышных стратегий, на что сильно повлияло распространение программирования: составить алгоритм, по которому в игру смог бы играть компьютер, часто бывает сложнее и интереснее, нежели самому научиться играть в неё, при этом глубже вникаешь в суть игры, после чего выиграть в неё можешь уже практически любого. Игры Простейшие математические игры часто используют как задачи, в которых нужно найти выигрышную стратегию, либо одно положение перевести в другое. Иногда задачи бывают весьма простыми, когда они решаются известными методами, такими как инвариант и раскраска, но есть и весьма простые, но до сих пор неразрешённые задачи, связанные с математическими играми. Примером может являться популярная игра крестики-нолики на бесконечном поле (рендзю). Она, как известно, при правильной стратегии обоих игроков бесконечна, но выигрышную стратегию при этом никто не знает. В настоящее время придумано множество алгоритмов этой игры, основанных, прежде всего, на переборе различных вариантов и анализе игры на следующие несколько ходов, которые очень близки к выигрышной стратегии, но лишь при их реализации на компьютере - человек же им следовать практически не может. Существуют простейшие приёмы этой игры, которыми пользуются игроки, но решающей чаще всего бывает внимательность. Игра ним и другие аналогичные игры Существует несколько игр, в которых двое играющих A и B, руководствуясь определёнными правилами, по очереди вынимают то или иное число фишек из одной или нескольких кучек - побеждает тот, кто берёт последнюю фишку. Простейшая такая игра - это игра с одной кучкой фишек, и сделать ход в ней - значит взять из кучки любое число фишек от 1 до m включительно. Многие подобные игры поддаются исследованию с помощью числа Шпрага-Гранди G(C). Пустой позиции O, не содержащей фишек, отвечает G(O)=0. Комбинацию кучек, состоящих соответственно из x, y, ... фишек, обозначим C=(x, y, ...) и предположим, что допустимые ходы переводят C в другие комбинации: D, E, ... Тогда G(C) есть наименьшее неотрицательное число, отличное от G(D), G(E), ... Это позволяет по индукции определить G(C) для любой комбинации C, разрешённой правилами игры. Так, в упомянутой задаче G(x)=x mod (m+1). Если G(C)>0, то игрок, делающий следующий ход, допустим, это игрок A, может обеспечить себе выигрыш, если ему удастся перейти к "безопасной" комбинации S с G(S)=0. Действительно, по определению G(S) в этом случае либо S - пустая позиция, и тогда A уже выиграл, либо B следующим ходом должен перейти к "опасной" позиции U с G(U)>0 - и тогда всё повторяется снова. ............