Потенциал Образовательный журнал
для старшеклассников и учителей

<< К разделам
Информатика
Алгоритмы
Теория информации
Теория программирования
Все статьи
Журнал
Подписка
Интернет-Журнал «Потенциал» External link mark
Авторам
Печатные номера
Полезные сайты
ЗФТШ External link mark
МЦНМО External link mark
Журнал "Квант" External link mark
"Открытый Колледж" External link mark
Союз образовательных сайтов External link mark
Интернет-портал "Абитуриент" External link mark
Другие ссылки...

WOlist.ru - каталог качественных сайтов Рунета Союз образовательных сайтов Rambler's Top100 Портал ВСЕОБУЧ. Все образование Москвы и регионов РФ.

Главная Подписка Архив Авторы Фотоальбом Подготовка в вуз Магазин

Игра "Ним", или как математики играют в игры

Это статья не о компьютерных играх, и не о подкидном дураке, и, конечно, не о футболе. Речь пойдет о играх математических, а точнее, комбинаторных. Игра Ним, крестики-нолики, шахматы, Го, шашки, реверси — это известные примеры комбинаторных игр. Оказывается есть один удивительный способ быстро находить выйгрышную стратегию для большого класса комбинаторных игр.

Ворожцов А.В., Шульман Т.


Что такое Игра?

Нет, мы сегодня будем говорить не о компьютерных играх, и не о подкидном дураке, и, конечно, не о футболе. Речь пойдет об играх математических, а точнее, комбинаторных.

Оказывается, математики, кроме синусов и косинусов, изучают также игры. Этот факт школьные учебники по математике почему-то скрывают от учеников. Многие математические теории можно рассматривать как игры с определёнными правилами. А часто и наоборот — игры порождают сложные математические теории.

Крестики-нолики, шахматы, Го, шашки, реверси — это известные примеры комбинаторных игр. Можно сказать, что комбинаторные игры — это игры, где нет элементов случайности, все правила чётко описаны, и игроки имеют полную информацию о текущей ситуации. Строгое определение звучит так:

Комбинаторная игра — это множество игровых позиций, про каждую из которых игрокам известно, как (в какие другие позиции) может ходить каждый из них.

Какие вы знаете комбинаторные игры кроме перечисленных?

Рассмотрим простую комбинаторную игру ''Конфета''.

Игра ''Конфета''

Игра "Конфета": Есть натуральное число N — "конфета". Игроки по очереди ''откусывают'' не больше половины от имеющегося кусочка. Проигрывает тот, кто не сможет откусить от оставшегося единственного ''кванта конфеты''.

Давайте разберёмся, как в неё играть. ''Конфета'' величиной в один квант — {1} — проигрышная позиция для того, кто ходит первым. ''Конфета'' {2} — выигрышная: мы ходим в {1} и выигрываем. Далее: {3} — проигрышная, потому что из неё можно сходить только в конфету {2}. Из {4} можно сходить в {3}, а значит поставить соперника в плохую ситуацию. То есть {4} — выигрышная позиция.

Задача: Поиграйте в игру ''Конфета'' {20} сами с собой или с другом. Попробуйте поиграть первым и вторым игроком.

Задача: Докажите, что ``Конфета'' {15} является проигрышной позицией, то есть проигрывает тот, кто ходит первым (при правильной игре второго). В чём заключается ``правильная игра'' второго, то есть какова его выигрышная стратегия?

Опишем все проигрышные позиции игры "Конфета". Для этого построим таблицу прогрышных и выигрышных позиций:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25
+ + - + + + - + + + + + + + - + + + + + + + + + +

Здесь ''+'' означает выигрышную, а ''-'' — проигрышную позицию.

Задача: Докажите методом математической индукции, что проигрышные "конфеты" — это "конфеты" {2^n-1}.

Вариации игры "Конфета": Игроки по очереди ''откусывают''
  • a) 3, 5 или 8 квантов;
  • б) 2n квантов, где n=0,1,2...;
  • в) n2 квантов, где n=1,2....
Проигрывает тот, кто не может ничего откусить от ''конфеты''.

Задача: Нарисуйте табличку проигрышных-выигрышных позиций и попытайтесь угадать закономерность для этих трёх случаев.

Игра Ним

Это древняя китайская игра. В неё любили играть китайские императоры. Тем, кто у них выигрывал, отрубали голову.

Игра Ним: Есть три кучки камней с числом камней — 3, 2, и 1. Играющие по очереди забирают любое количество камней из любой кучки. Проигрывает тот, кому нечего забирать.

Как нужно играть, чтобы выиграть в Ним?

Задача: Поиграйте в Ним друг с другом. Есть ли выигрышная стратегия у первого? А у второго?

%DIV{HiddenAnswer}% Есть у второго. %ENDDIV%

Для того, чтобы разобраться с этим, давайте рассмотрим различные игровые позиции. Во-первых, сколько игровых позиций? Перечислим все (в фигурных скобках мы будем писать число камней в кучках): {1}, {2}, {3}, {1,1}, {2,1}, {3,1}, {2,2}, {3, 2}, {1,1,1}, {2,1,1}, {3,1,1}, {2,2,1}, {3,2,1} . Это позиции, в которые мы можем попасть через некоторое число ходов. Далее. Очевидно, что в позиции {1,1} выигрывает второй, а в позициях {1}, {1,1,1} выигрывает первый.

Задача: Докажите, что позиции {2,1}, {3,1}, {2,1,1} — выигрышные.

Решение: Они выигрышные, потому что из них можно сходить в позицию {1,1}.

Задача: Докажите, что позиция {2,2} — проигрышная.

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

Что такое выигрышная стратегия?

Позиции, в которых выигрывает тот, кто ходит первым, назовём выигрышными, а в которых выигрывает второй — проигрышными.

Игрок ''выигрывает'' в данной позиции значит, что он имеет возможность ходить так, и так отвечать на ходы противника, чтобы выиграть у него, независимо от того, как противник будет ходить. Эта возможность + описание того, как нужно отвечать на ходы соперника, называется выигрышной стратегией. Другими словами, если игрок умный и ходит первым из выигрышной позиции, то он выиграет. Но как бы ни был умён игрок, он может проиграть, если будет ходить первым из проигрышной позиции.

Задача: Докажите существование выигрышной стратегии для игрока, который ходит вторым в игре Ним {3,2,1}.

Граф Игры

Важно понять, что в игре Ним кроме проигрышных и выигрышных позиций никаких других позиций нет. Это довольно сложно объяснить, хотя кажется очевидным. В шахматах это не так — там возможны ``ничейные'' позиции. Другое важное отличие шахмат от игры Nim заключается в том, что в шахматах, множества ходов, которые могут сделать игроки из одной и той же позиции, разные (играющий черными, не может двигать белые фигуры, и наоборот). Здесь рассматривали только те игры, в которых множества ходов, которые могут сделать игроки из одной позиции, совпадают (у игроков нет цвета). Такие игры называются нейтральными.

На рисунке 1 показана схема ходов в игре Ним {3,2,1}. Она называется графом игры.

Рис.1 граф игры Ним

Граф игры — это множество точек, соединённых стрелочками (направленными рёбрами). Точки (вершины графа) – это множество всех игровых ситуаций, которые могут возникнуть в данной игре. Каждая точка (вершина графа) соответствует одной из возможных игровых ситуаций. То, что из точки A ведёт стрелочка в точку B, означает, что из позиции A можно сходить в позицию B.

Чтобы освоиться с понятием ''граф игры'', решите две задачи:

Задача: Кто выигрывает при правильной игре в Ним {2,2}? Нарисуйте граф этой игры.

Задача: Кто выигрывает при правильной игре в ''Конфету'' {5}? Нарисуйте граф игры.

Давайте рассмотрим игру Ним {3,2,1} в поддавки, условия которой таковы: тот, кто взял последний камень, тот и проиграл.

Задача: Кто выигрывает при правильной игре в ''Ним в поддавки''? Нарисуйте граф игры.

Решение: {1} — проигрышная позиция. Значит, все позиции, из которых в неё можно сходить, будут выигрышными. Это позиции: {2}, {3}, {1,1}, {2,1}, {3,1}. Дальше мы должны найти позицию, из которой можно сходить только в эти выигрышные позиции. Это будет {2,2} — проигрышная позиция, так как из неё нельзя сходить в проигрышную позицию (поставить своего соперника в проигрышную позицию). Позиции, из которых можно сходить в {2,2}, есть выигрышные. Это {3,2} и {2,2,1}. Теперь из оставшихся позиций {1,1,1}, {2,2,1}, {3,1,1} нужно найти такую, из которой можно сходить только в хорошие позиции (выигрышные позиции). Это {1,1,1} — плохая, проигрышная позиция. Значит {2,1,1} и {3,1,1} — хорошие. Смотрим на {3,2,1}. Из неё нельзя сходить ни в одну из проигрышных позиций {1},{1,1,1},{2,2}, а значит, она сама проигрышная. Как видите, и в поддавки и в обычный Ним позиция {3,2,1} является проигрышной. В этом нет никакого противоречия. Граф игры показан на рисунке 2.

Рис.2 граф игры ''Ним в поддавки''

В левом столбце этой таблицы выписаны проигрышные позиции, в правом — выигрышные.

Есть естественное обобщение игры Ним на произвольное количество кучек и камней в каждой кучке.

Игра Ним: Есть кучки камней {n1, n2,... ,nl}, ni — число камней в i-ой кучке. Играющие по очереди забирают любое количество камней из любой кучки. Проигрывает тот, кому нечего забирать.

Надо ответить на вопрос: кто выиграет при правильной игре? Начнем по порядку. Первая идея, которая у нас есть — это идея симметрии.

Задача: Докажите, что в игре {3,3,1,1} выигрывает второй.

Решение: Действительно, разобьем кучки на две одинаковые группы: {3,1} и {3,1}. Тогда, как бы ни сходил первый, мы (второй игрок) будем делать аналогичный ход, только в другой группе. И так далее. Симметричный ход всегда будет существовать и нам всегда будет куда ходить. Поэтому мы не проиграем, а значит, выиграем.

Во всех симметричных играх выигрывает второй.

Ним {3,2,1} — несимметричная игра. Но в ней все равно выигрывает второй.

Задача: Позиция {3,3,1} выигрышная или проигрышная?

%DIV{HiddenAnswer}% Выигрышная. Ход в {3,3}. %ENDDIV%

Задача: Позиция {4,3,1} выигрышная или проигрышная?

%DIV{HiddenAnswer}% Выигрышная. Ход в {3,2,1}. %ENDDIV%

Задача: Позиция {100,100,1} выигрышная или проигрышная?

%DIV{HiddenAnswer}% Выигрышная. Ход в {100,100}. %ENDDIV%

Задача: Докажите, что позиция {n,n,1} при любом натуральном n является выигрышной.

Следующая идея: если из имеющегося набора кучек выбросить симметричную составляющую, то характеристика позиции не изменится (если была проигрышная позиция, то и останется проигрышной, если была выигрышная, то и останется выигрышной). Например, в предыдущей задаче можно было выкинуть {100,100}. Позиция {1} – выигрышная, значит и {100,100,1} – тоже выигрышная.

Проигрышные позиции будем называть нулевыми. {3,2,1}, {7,7}, {2,1,2,1} — нулевые. Откуда взялось такое название, станет ясно из следующего утверждения.

Утверждение. Если к позиции добавить или отнять нулевую позицию, то характеристика позиции не изменится.

Доказательство: Докажем, что при сложении выигрышной позиции A с нулевой позицией B получается выигрышная позиция. Итак, мы играем одновременно в 2 игры. Играя первыми, будем делать ходы ''на доске'' A и выиграем там. Всякий раз, когда соперник будет делать ход в часть B, мы сможем успешно отвечать ходом в ту же часть, поскольку по условию в части B есть выигрышная стратегия для второго.

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

Задача: Докажите, что {3,2,1,100,100} является нулевой позицией.

Итак, сложение любой позиции с нулевой позицией не меняет её характеристику.

ВОПРОС: Когда в игре Ним {m1,m2,... , mk} есть выигрышная стратегия для первого игрока?

Для ответа на этот вопрос нам понадобится операция XOR. Чтобы осуществить операцию XOR набора натуральных чисел, нужно перевести их в двоичную систему счисления и записать друг под другом, ровняя по младшему разряду. Затем подсчитать чётность числа единиц в каждом столбце, и записать под столбцом 1, если нечётно, и 0, если чётно. Осталось перевести результат — нижнюю строчку — из двоичной системы в привычную нам десятичную.

Примеры операции XOR:

Определим для игры Ним {m1,m2,... , mk} число Nimber как Nimber=XOR(m1,m2,... , mk)

Итак, для каждой игры Ним мы можем подсчитать число Nimber.

ОТВЕТ на ВОПРОС: В игре Ним {m1,m2,... , mk} есть выигрышная стратегия для первого игрока тогда и только тогда, когда Nimber=XOR(m1,m2,... , mk)≠ 0. Иначе есть выигрышная стратегия для второго.

Для доказательства мы предъявим выигрышную Стратегию:

Если в текущий момент набор кучек таков, что их Nimber не равен 0,то вы должны сходить так, чтоб он стал равен 0. Второй из позиции с нулевым Nimber -ом сможет сходить только в позицию с ненулевым Nimber -ом. Вы после его хода снова сходите в позицию с нулевым Nimber -ом, и так далее. Конечная позиция – полное отсутствие камней – имеет нулевой Nimber, а значит, когда-нибудь именно вы в неё сходите и выиграете.

Задача: Докажите, что если в позиции {m1, ..., mk} игры Ним {XOR(m1, ..., mk)≠ 0}, то вы сможете сходить в новую позицию (уменьшив одно из чисел { m1, ..., mk}), для которой XOR=0.

Задача: Докажите, что если в позиции { m1, ..., mk} игры Ним XOR( m1, ..., mk)=0, то вы сможете сходить только в позиции, в которых XOR≠ 0.

Решив эти две задачи, вы докажите, что предложенная стратегия — действительно выигрышная.

Примеры. Nimber игры Ним из одной кучки с n камнями есть n: Nimber(Ним{n})=n

Значит, в случае одной кучки всегда выигрывает первый.

Nimber(Ним{2,1})=3, значит в игре Ним{2,1} выигрывает первый. Зато Nimber(Ним{3,2,1})=0, и в ситуации {3,2,1} есть выигрышная стратегия у второго. Какова она?

Задача: Найдите Nimber для Ним {5,1} и Ним {9,8,1}.

%DIV{HiddenAnswer}% 4 и 0. %ENDDIV%

Давайте поиграем

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

1. Двое по очереди кладут пятаки на круглый стол, причем так, чтобы они не накладывались друг на друга. Проигрывает тот, кто не может сделать ход.

2. Двое по очереди ставят слонов в клетки шахматной доски так, чтобы слоны не били друг друга (цвет слонов значения не имеет). Проигрывает тот, кто не может сделать ход.

3. Двое по очереди ставят королей в клетки доски так, чтобы короли не били друг друга. Проигрывает тот, кто не может сделать ход.

4. Дана клетчатая доска
  • а) 9* 10;
  • б) 9* 11;
  • с) 12* 10.
За ход разрешается покрыть любые 2 соседние клетки доминошкой (прямоугольником 2*1 или 2*1) так, чтобы доминошки не перекрывались. Проигрывает тот, кто не может сделать ход.

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

6. На окружности расставлено 10 точек. За ход разрешается соединить любые две из них отрезком, который не пересекает отрезков, проведенных ранее. Проигрывает тот, кто не может сделать ход.

7. У ромашки
  • а) 12 лепестков;
  • б) 11 лепестков.
За ход разрешается оторвать либо один лепесток, либо два рядом растущих лепестка. Проигрывает тот, кто не может сделать хода.

8. Дан прямоугольный параллелепипед размерами 4*4*4, составленный из единичных кубиков. За ход разрешается проткнуть спицей любой ряд, если в нем есть хотя бы один непроткнутый кубик. Проигрывает тот, кто не может сделать ход.

9. Двое по очереди разламывают шоколадку 5*10. За ход разрешается сделать прямолинейный разлом любого из имеющихся кусков вдоль углубления. Выигрывает тот, кто первым отломит дольку 1*1.

10. Двое по очереди ставят крестики и нолики в клетки доски n*n. Начинающий ставит крестики, его соперник — нолики. В конце подсчитывается, сколько имеется строчек и столбцов, в которых крестиков больше, чем ноликов — это очки, набранные первым игроком. Количество строчек и столбцов, где ноликов больше — очки второго. Побеждает тот из игроков, кто наберёт больше очков.

11. На доске два числа — 7 и 8. Игрок за ход стирает наибольшее (если наибольших несколько, то любое из них) и пишет вместо него любое меньшее натуральное число. Кто сходит в позицию {1,1}, тот
  • а) выиграл;
  • б) проиграл.

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

13. Рассмотрим прямоугольник n*m, разделённый на единичные квадратики. Игроки по очереди выбирают одну из вершин, являющуюся общей для двух или более квадратиков, и убирают все квадратики, которые выше и правее этой вершины. Можно еще ходить в самую нижнюю левую, но тот, кто туда сходит, проигрывает.

Задачи

Задача: Какой ход нужно сделать первому игроку в игре ''Конфета'' {33}?

%DIV{HiddenAnswer}% Нужно сходить в {31} %ENDDIV%

Задача: Кто выигрывает в игре 6?

Задача: Поиграйте в Ним {5,4,1}. Кто выигрывает при правильной игре?

Задача: Поиграйте в Ним {5,5,2,2}. Кто выигрывает при правильной игре?

Задача: Поиграйте в игру ''Конфета'' случай в). Кто выигрывает при правильной игре, если размер конфеты равен
  • a)20;
  • б)n?

Задача: Кто выигрывает в игре ''Ним в поддавки'' в ситуации {5,1,1}?

%DIV{HiddenAnswer}% Первый. Ход в {1,1,1}. %ENDDIV%

Задача: Кто выигрывает в игре ''Ним в поддавки'' в ситуации {8,4,1}?

Задача: Нарисуйте граф игры ''Конфета''{6}.

Задача: Докажите, что в игре 13 независимо от значений m>1 и n>1 выигрывает первый.

%DIV{HiddenAnswer}% Пусть есть выигрышная стратегия у второго. Пусть первый игрок первым ходом стирает угловой верхний правый единичный квадратик. У второго должен быть ход, который ставит первого в проигрышную позицию. Но в эту же самую позицию мог бы сходить и первый игрок первым ходом. Значит выигрышной стратегии у второго нет. Следовательно она есть у первого. %ENDDIV%

Игра Реверси

Show attachmentsHide attachments
Topic attachments
I Attachment Action Size Date Who Comment
jpgJPG table1.JPG manage 7.8 K 29 Sep 2006 - 12:13 OlgaButygina  
jpgJPG table2.JPG manage 10.4 K 29 Sep 2006 - 12:17 OlgaButygina  

© Журнал "Потенциал", 2005-2017. Все права защищены. Воспроизведение материалов сайта и журнала "Потенциал" в любом виде, полностью или частично, допускается только с письменного разрешения редакции.
Отзывы и пожелания шлите почтой.
Подготовка к ЕГЭ
ЕГЭ по математике
login