Автор статьи: Антонио Грамши, педагог, математик и автор логических игр.
Другие названия игр этого обширного семейства – хватательные (М. Гарднер) и игры на вычитание (И. С. Фролов).
В них противники по очереди забирают подмножества из некоторого исходного множества. Тот, кто забирает последнее подмножество, считается победителем в нормальной игре или проигравшим в мизере.
Понятно, что если исходное множество конечно, то конечна и сама игра.
Типичный представитель – ним. Правила игры предельно просты.
Имеется несколько кучек однородных предметов (на приведенном ниже рисунке – три ряда спичек).
Противники поочередно забирают из них по одному или нескольку предметов, причем каждым ходом можно забирать предметы только из одной кучки. Выигрывает (или, наоборот, проигрывает) тот, кто своим очередным ходом забирает последние предметы.
Число кучек и предметов в каждой из них можно варьировать произвольным образом. Можно также ограничивать число забираемых предметов.
Ниму и аналогичным играм посвящена обширная литература, в частности, большая глава в книге Мартина Гарднера “Математические головоломки и развлечения” (М.: Мир, 1971, стр. 132-151). Там же описан алгоритм для нима, основанный на представлении позиций в виде двоичного кода.
Более сложные игры на исчерпание множеств – так-тикс, квадратобоязнь (квадратура), топологические игры хакенбуш, рассада, блэк и ползунок. Так-тикс, квадратобоязнь, блэк и ползунок описаны в книге Гика Е. Я. и Сухарева А. В. “Интеллектуальные игры и развлечения” (М.: ФАИР-ПРЕСС, 1999) на стр. 130-131, 132, 75- 77 и 77-78 соответственно. Описание хакенбуша приведено в книге Гарднера М. “Крестики-нолики” (М.: “Мир”, 1988) на стр. 201-209. Рассада описана в книге того же автора “Математические новеллы” (М.: “Мир”, 1974) на стр. 281-287. Информацию по всем упомянутым играм легко также найти в интернете.
Важная особенность игр на исчерпание множеств состоит в том, что для них не имеет смысла говорить о врéменном преимуществе того или иного игрока, поскольку игровой материал общий. В случае если с самого начала выигрышная стратегия не известна, партия делится на две четко разграниченные по времени стадии.
На первой стадии противники совершают нейтральные ходы, не ведущие к немедленному проигрышу, пока кто-то первым не увидит выигрышную комбинацию. Наступает вторая стадия: игрок, оказавшийся более проницательным, реализует выигрыш (если он, конечно, не ошибся в расчетах). О плавном переходе от первой стадии ко второй, с накоплением преимущества, не может идти и речи. Именно по этой причине к играм на исчерпание множеств более склонны математики, чем любители логических игр. По сути, они являются в большей степени головоломками – часто очень занимательными, – начальная конфигурация которых создается обоими игроками.
Игры на исчерпание множеств очень легко придумать самим, и они служат превосходным конструктором для разнообразных задач. Простор для творчества здесь очень велик.
Ниже приводятся три игры, изобретенные автором. Заложенные в них идеи настолько просты и очевидны, что было бы удивительно, если аналогичные игры не изобрел и кто-то другой.
Прямоугольный ним
Игровым полем является совокупность нескольких (не менее двух) квадратов разной величины, разделенных на клетки. Пример такого поля приведен на рис. 1
Играют двое соперников (хотя игру можно без труда обобщить для произвольного числа лиц). Ходят по очереди. Каждым ходом игрок выбирает квадрат и вычерчивает в нем произвольный прямоугольник (в частности, квадрат), стороны которого совпадают со сторонами клеток. При этом он не должен пересекаться с другими прямоугольниками, уже вычерченными в этом квадрате (см. рис. 2).
Игроки сделали первые четыре хода.
Проигрывает тот, кто очередным ходом не может вычертить прямоугольник (см. рис. 3).
Игрок В (делающий ход вторым) выиграл на восьмом ходу.
Анализ этой игры представляется довольно сложным, хотя сама игра доступна младшим школьникам. Кроме того, на ее основе можно придумывать разнообразные задачи, развивающие комбинаторно-геометрическое мышление. Приведем несложную задачу.
Игрок А (делающий ход первым) своим ходом вычертил квадратик 1 (рис. 4). Найдите выигрыш для игрока В.
Ответ: игрок В своим ходом вычерчивает квадрат, совпадающий с малым квадратом поля, а потом на каждый прямоугольник игрока А в большом квадрате поля вычерчивает симметричный ему относительно квадратика 1 прямоугольник.
Подчеркнем, что идея симметрии вообще является важным элементом стратегии в играх на исчерпание множеств.
Читатель сам без труда придумает бесчисленные вариации этой игры.
Растущие ломаные
Игра разработана в соавторстве с М. Чернышевым.
Поле для игры – квадрат произвольных размеров, например, 1010 на бумаге в клетку (рис. 5).
Играют двое. Ходы совершаются поочередно. Первым ходом вычерчивается отрезок, проходящий по одной из сторон произвольной клетки поля. Вторым ходом вычерчивается ломаная, состоящая из двух таких отрезков, третьим ходом – из трех и т.д. (рис. 6).
Противники сделали первые пять ходов.
Ломаные не должны ветвиться, касаться друг друга и краев поля, а также пересекать друг друга и самих себя (рис. 7).
Ходы №№ 6, 7, 8, 9 сделаны не по правилам: ломаная № 6 касается края поля, № 7 касается № 3, № 8 ветвится, № 9 пересекает саму себя.
Проигрывает тот, кто очередным ходом не может начертить свою ломаную (рис. 8).
РисИгрок А выиграл на девятом ходу, поскольку игрок B следующим ходом не может начертить ломаную длиной 10.
Игра в квадраты
Эта игра аналогична предыдущей. Только здесь противники поочередно вычерчивают квадраты, сторона которых с каждым ходом возрастает на единицу. Партия начинается с единичного квадрата. Квадраты могут касаться друг друга и краев поля (но не пересекаться). Проигрывает тот, кто своим очередным ходом не может вычертить квадрат (рис. 9).
Игрок А, делающий ход первым, выиграл на пятом ходу, так как игрок B следующим ходом не может поставить квадрат 66.
Т. к. в процессе партии квадраты очень быстро увеличиваются (и, соответственно, число ходов невелико), целесообразно увеличить размеры поля, например, до 2020. Но начинать лучше все же с поля 100.