Исследовательская работа по математике "Математические загадки НИМ"

Районная конференция «Шаг в науку»

Секция «математические науки и ИКТ»

 (направление – математика)

Математические загадки игры «Ним»

Грязных Кристина Николаевна

МБОУ Софпорогская ОШ, 9  класс,п. Софпорог,

Лоухского района

Е-mail: tropki@mail.ru; тел. +7(921)461-74-59

Руководитель: Лобова Анна Владимировна,

учитель математики МБОУ Софпорогская ОШ,

Е-mail: tropki@mail.ru;  тел. +7(921)623-17-38.

Лоухи, 2016 год

Введение.

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

Возникают вопросы:         

•  Как же играть, чтобы не проиграть?
•  Как найти выигрышные стратегии игры математическими методами?
•  Победа в игре – это закономерность или случайность?

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

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

Область исследования: математическая теория комбинаторных игр.

Объект исследования: поиск выигрышных стратегий игровых комбинаторных задач.

Предмет моего исследования: математическая игра «Ним».

Цели исследования: Изучение выигрышных стратегий математической игры «Ним» или доказательство того, что их нет, а результат игры – это лишь случайность.

Задачи исследования:

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

Методы исследования:

• поиск информации с целью получения новых знаний об объекте исследования, дальнейший анализ и систематизация полученных знаний.
• Наблюдение за объектом исследования в различных ситуациях.
• Моделирование различных игровых ситуаций для постановки игрового эксперимента.
• Эксперимент с целью выявления математических закономерностей или обоснования их отсутствия.
• Математические методы: статистические с целью проведения статистики результатов игры, методы теории графов, метод математической индукции и  дедукции.

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

Свое знакомство с математическими особенностями игры «Ним»,  и с правилами игры я начала со статьи в журнале Квант «Две игры со спичками». [1].  Именно эта статья дала старт всему моему исследованию.

В моей работе также оказалась полезной работа со статьей Ворожцова А.В., Шульмана Т., опубликованного в познавательном журнале для старшеклассников «Потенциал». Тема статьи: «Игра «Ним», или как математики играют в игры». [2]. Работая с данной статьей, у  меня родилась мысль проведения игрового эксперимента с моими одноклассниками, с целью выявления и дальнейшего обоснования математических закономерностей, я решила ряд предложенных в статье задач для самостоятельной работы и получила общую стратегию многих вариаций игры в «Ним».

Серьезное теоретическое обоснование математических особенностей различных комбинаторных игр я подчеркнула, работая с учебным пособием для студентов и разработчиков компьютерных  игр «Введение в теорию комбинаторных игр» Фролова И. Самарского государственного университета.[3].  С помощью данного учебного пособия я также познакомилась с новыми для себя математическими методами доказательства.

Интересно, что первый анализ выигрышных стратегий игры «Ним» был дан в 1902 году математиком Гарвардского университета Чарльзом Леонардом Боутоном. Именно ему и приписывают название этой игры.

А корни этой игры уходят в древний Китай и в нее любили играть китайские императоры, а всем кто у них выигрывал, отрубали головы. Вот и задумаешься, легко ли было проиграть императору?

Какие же математические загадки  таит в себе эта комбинаторная игра? Или  выигрыш в игре – это случайность. Об этом можно прочитать в основной части моего исследования.

Основная часть исследовательской работы.

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

В данной теории не изучаются случайные игры. В данном виде игр заранее известны обоим игрокам все возможные позиции и все возможные ходы.

Игра «Ним» - это классическая комбинаторная игра, в которой нет скрытой информации для обоих игроков. Игроки по очереди делают ходы. Игра всегда заканчивается выигрышем или проигрышем, а победителя в большинстве игр определяет последний ход.

Правила классической игры «Ним» просты: Два игрока поочередно берут предметы:  камушки, спички, монеты  и другие из кучек, рядов, коробок.

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

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

Игрок, взявший последний предмет выигрывает.^[1]

В игре «Ним» позиции записываются путем перечисления размеров имеющихся кучек. Так запись (a,b,c) – соответствует трем кучкам с данным количеством предметом.

В данных задачах – играх, позиции называются выигрышными, если выигрывает тот, кто ходит первым и проигрышными, если выигрывает  второй.

Если игрок имеет возможность ходить так, чтобы у него выиграть, независимо от того, как он будет ходить, значит, игрок «выигрывает» в данной позиции.

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

В различных учебных пособиях и статьях можно найти основные идеи решения игровых задач и описание поиска этих самых выигрышных стратегий. Среди них, выделим: игры – шутки, метод симметрии, дополнение до фиксированного числа и метод выигрышных позиций.

Остановимся на применении этих методов к решению задач «Ним». А чтобы понять их суть в действии и попробовать выявить закономерность, проведем игровой эксперимент, моделируя различные игровые ситуации «Ним».

Для проведения игрового эксперимента я познакомила своих друзей с правилами игры и приготовила разные варианты условий задачи «Ним».

Первая стратегия, на которой мы остановились, это игры – шутки. Это такие игры, где для построения выигрышной позиции можно ничего не знать, так как результат в данных играх зависит не от игры соперников, а от начальных условий.  Единственное, надо заметить, что это игра не на поиск выигрышной стратегии, а «шутка». Почему такое название? Потому что нас хотят обмануть, что стратегия выигрыша есть. Просто в этих играх, как бы ты не ходила, выигрывает всегда либо первый, либо второй и ты не сможешь повлиять на ход игры, так как это определено условиями игры. Для доказательства того, кто выигрывает, обычно используется какая – то величина, которая понятно чему равна в начале игры и в конце ее, а также понятно, как она изменяется на каждом ходу. Обычно в таких играх можно подсчитать даже число ходов. Это число называется инвариантом.^[2]

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

Многие задачи легко решаются, если заметить, что некоторая величина имеет определенную четность. Иногда эту величину надо сконструировать, например, рассмотреть четность суммы или произведения.

Очень часто в решении таких задач можно использовать «метод маленьких чисел», начинать поиск решения с небольших чисел.

Приведу пример одной задачи – шутки «Ним».

Задача – шутка.

Имеется три кучки камней: в первой – 10, во второй – 15, в третьей – 20. За ход можно разбить любую кучку на две меньшие. Проигрывает тот, кто не может сделать ход. Кто выиграет?

Решение: Можно подсчитать количество возможных ходов для раскладывания кучек: их будет 42. Это четное число. Поэтому, как бы ни ходил первый игрок, количество кучек после его хода будет всегда четно, а после хода второго – нечетно. Значит, победит всегда первый, так как по завершении игры всегда останется ровно 45 кучек по одному камню и последним сделает ход игрок с нечетным номером, то есть – первый.

Следующий метод решения для многих стратегических задач – это симметрия.

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

Разберем решение одной из задач «Ним» методом симметрии.

Задача: Имеется две кучки камней по 7 штук в каждой. За ход можно взять любое количество камней, но только из одной кучки. Проигрывает тот, кто не сможет сделать ход. Кто выиграет?

Решение: В решении используем метод «малых» задач и предположим, что в наших двух кучках по одному камню. Очевидно, что при любой игре первого выиграет – второй игрок. А если мы добавим в одну из кучек еще камушек, то первый при правильной игре – выиграет, так как он может взять из кучки, где два камня – один и попадет в позицию, описанную выше, в которой только что был победитель – второй.

Если в кучках будет 3 и 1 камень соответственно, то снова победит первый, взяв из первой кучки два камушка.

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

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

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

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

Следующая задача «Ним»  - дополнение до фиксированного числа.

Суть данной стратегии в том, чтобы уменьшить каждым «совместным» ходом общее число элементов на одно и тоже фиксированное число, что сводит игру к меньшему числу элементов и делает ее простой.

Задача (дополнение до фиксированного числа): Двое играют в игру. Ходы, которые делаются, по очереди, заключаются в том, что из кучки в 50 камней убирается от 1 до 5 штук. Выигрывает тот, кто возьмет последний камень. Кто выигрывает в игре?

Решение: В этой задаче также применим метод малых задач. Предположим, что в нашей кучке менее 6-ти предметов. Заметим, что выигрывает первый игрок, забрав все камни первым ходом. А если в кучке будет ровно 6 камней, то выигрывает второй. Так как первый может забрать только до пяти таких предметов, а значит еще один останется для второго.

Если камней  - 9, то первому можно просчитать свой ход таким образом, чтобы забрав свои камни, второму можно было взять свои пять по максимуму, и  хотя бы  один камушек оставить первому. А именно, в этой ситуации первому надо взять3 камня, тогда второй, взяв 5 камушков, один оставит первому.

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

А если камней 12? Тогда выигрывает второй. Почему?

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

Увеличим число камней до 36. Снова выигрывает второй, так как, как бы ни играл первый, у второго снова будет возможность довести число камней до шести и он  - победитель.

Возьмем другое число камней – 21. И снова, убирая необходимое  количество камней, первый игрок доводит игру ровно до 6-ти камней и выигрывает. Нетрудно заметить, опираясь на выше сказанное, что здесь 3 «лишних» камня для первого игрока.

Возникает вопрос, а как высчитать это число камней, которое надо убрать.

Мы заметили, что решение данных задач находится вокруг одного и того же числа – 6. Так как максимальное число камней, которое можно убрать – 5 и один камень мы оставляем для дальнейшего своего хода.

Поэтому мы можем предположить, что в условиях данной задачи, если число камней в кучке делится на 6 без остатка, то выигрывает второй. В противном случае – выиграет первый.

Это предположение нетрудно доказать.

Пусть у нас в кучке кратное шести число камней, то есть - 6n камней. После любого хода первого игрока второй делает ход, уменьшая число камней в кучке на 6, тем самым оставляя в ней: (6n – 6) камней.

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

Допустим, что количество камней в кучке не делится на 6 без остатка. То есть количество камней: 6n + mod, где  mod – остаток от деления на 6 (от 1 до 5 камней).  Тогда число камней, равное mod первый игрок имеет возможность убрать своим первым ходом и сводет игру к случаю 6n, тем самым выигрывает.

Напомним, что в нашей задаче было 50 камней. Данное число не делится на 6 без остатка, а значит,  выигрывает первый игрок, после того, как уберет 2 «лишних» для себя камня и, сведя игру к случаю: 6n.

Опираясь на последнюю задачу, попробуем получить общее решение задач игры «Ним».

Пусть в кучке лежат S камней. Играют двое, ходят по очереди. За один ход можно взять любое количество камней в пределах от 1 до Z. Проигрывает тот, кто не может сделать ход. Кто выигрывает в данной игре?

Решение: Найдем остаток от деления S на Z и обозначим его за mod.

Рассмотрим случай, когда mod≠0. В этом случае, первый игрок забирает число камней, равное остатку mod. Второй игрок сможет забрать от 1 до Z камней, а первый должен дополнить своим ходом ходы соперника до Z + 1, чтобы обязательно забрать последний камень и выиграть. В самом деле, если из исходного количества камней вычесть остаток, то полученная разность будет делиться нацело на максимальное количество допустимых камней, которые можно забрать  плюс еще один камень. И этот последний добавочный камень и останется первому игроку.

Теперь о случае mod=0. В случае, когда количество камней кучки делится без остатка на число допустимых для взятия камней + еще один, опираясь на предыдущие обоснования, сразу получаем выигрыш  второго игрока.

На практике, решая задачи игры «Ним», мы заметили, что методы симметрии и дополнения до фиксированного числа являются эффективными в решении данных задач и работают в решении большого класса задач.^[3]

Следующее направление моей работы – поиск выигрышных и проигрышных позиций игры с помощью теории графов и сведение к заведомо известной выигрышной или проигрышной позиции.

Важно понимать, что в игре «Ним» кроме проигрышных и выигрышных позиций никаких других нет. Это довольно сложно объяснить, хотя кажется очевидным.

Составим граф игры «Ним» при условии, что у нас имеется 3 кучки камней (3,2,1), играющие по очереди могут забрать любое количество камней из одной кучки.

 С помощью данного графа докажем существование выигрышной стратегии для второго игрока.

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

Граф игры (3,2,1) выглядит так:

Рис.1.

Из графа на рис.1. видно, какие позиции ведут к выигрышу второго, а именно к позиции (1,1) и какие позиции ведут к выигрышу первого, то есть к позициям (1), (1,1,1).

Подобным методом можно установить проигрышные и выигрышные позиции в игре «Ним» в поддавки, условия которой таковы: тот, кто взял последний камень, наоборот, проигрывает. (Решение данной задачи можно увидеть на сайте моего проекта).

Связь проигрышных позиций с четностью суммы в двоичной системе счисления.

Решая разные игровые задачи «Ним» я не раз сталкивалась с идеей четности для определения выигрышной и проигрышной позиции.

Заметим, что самый простой способ проследить четность, это представить числа, выражающие количество камней в кучках в двоичной системе счисления. Данная система счисления – самая простая для записи целой чисел, в ней все десятичные числа представляются в виде суммы степеней числа 2.

Проследив за двоичным представлением чисел, выражающих игровые позиции, мы заметили, что проигрышные позиции в игре «Ним»  - это те позиции, где сумма цифр каждого разряда в двоичной записи чисел (а, в, с) четна.

Решив задачи, предложенные для самостоятельной работы в журнале «Квант», докажем это утверждение. [1].

Во-первых, докажем, что если позиция (а, в, с) в игре «Ним»  не является проигрышной, то есть не удовлетворяет условиям четности, описанным выше, то играющий может сделать ее проигрышной.

Пусть в игре рассматривается какая – то позиция, например,  (101, 234, 282). Переведя данные числа в двоичную систему счисления, мы увидим, что сумма двоичных разрядов данных чисел – нечетна.

В самом деле, после перевода мы получим (1100101, 11101010, 100011010). После нехитрого вычисления суммы двоичных разрядов мы получим нечетный результат. А из того, что сумма данных цифр нечетна, следует, что хотя бы одна и данных разрядных цифр – это 1.

Изменим теперь игровым ходом количество камней в третьей кучке, где самое большое количество разрядов, так как именно последний больший разряд и определяет результат суммы, на другое число так, чтобы изменились цифры, соответствующие 1-му, 3 – му, 5 – му, 8-му и 9 – му разряду. То есть, заменим число 100011010 на 010001111. И новая позиция будет уже являться проигрышной. А так как первоначальное число камней  в  третьей кучке больше, чем в измененной. То игрок в нее легко может перейти.

Это правило применимо для любой выигрышной позиции игры «Ним». Так как двоичные разряды – это цифры: либо 1, либо 0. Изменяя игровую позицию, 1 тоже определенным ходом можно всегда заменить на 0. А значит, если позиция проигрышной не является,  ее можно сделать такой.

Теперь докажем, что если позиция (a, b, c) является проигрышной, то после любого хода игрока  она перестает быть такой.

Это утверждение базируется на том, что любой ход меняет хоть одну цифру в двоичной записи чисел (a, b, c). То есть меняет 0 на 1 или 1 на 0. При этом в нужном разряде изменение касается лишь одной цифры.

Все выше сказанное подтверждает предположение о том, что в игре «Ним» проигрышными являются те и только те позиции (a, b, c), для которых суммы всех цифр, отвечающих одному разряду в записи чисел (a, b, c) в двоичной системе счисления, для всех разрядов четны.

Обобщив полученные данные, можно выделить некоторую общую стратегию игру «Ним».

В большинстве игр «Ним» работает симметрия. То есть после каждого хода соперника вы можете сделать «симметричный» ответный ход. И выигрывает второй.

Двоичное представление чисел, представляющих игровые позиции,  позволило нам доказать связь  четности суммы всех цифр  и проигрышной позиции в игре.

Полученные закономерности и  идеи решения задач комбинаторной игры «Ним» будут полезны в различных версиях игры.

Заключение.

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

Гипотеза о том, что игра «Ним» имеет свою выигрышную стратегию, которую можно установить, подтвердилась. А миф о том, что результат игры всего лишь случайность развеялся.

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

Математические игры – это интересный и увлекательный раздел строгой науки математики.

Игровые задачи интересно решать, поиск стратегии занимает порой много времени, но это стоит того.

Игровой эксперимент позволил выявить интересные математические  закономерности.

По итогам работы был создан сайт проекта «Математические загадки игры «Ним»», на страницах этого сайта собраны различные идеи решения задач «Ним», общие стратегии игры и различные вариации задач игры с решением. Некоторые из них авторские, подобранные на каждый изученный мной метод ее решения.

Данный материал будет полезен всем, кто увлекается математикой, теорией игр.

Следующее направление моей работы – программирование игры «Ним» на компьютере и дальнейшее знакомство с теорией комбинаторных игр, а затем и игр со случайным исходом.

Список использованных источников и литературы.

1. И. М. Яглом «Две игры со спичками»/Квант № 2, 1971 г.
2. http://potential.org.ru – Образовательный журнал для старшеклассников и учителей. Статья «Игра «Ним или как математики играют в игры»».
3. И. Фролов «Введение в теорию игр»/Учебное пособие для студентов/Самарский государственный университет. 2010г.
4.  Л.М.Лихтарников. «Занимательные задачи по математике», М.,1996г.
5.  Е.В.Галкин. «Нестандартные задачи по математике», М., 1996г.
6.  А.Я.Кононов. «Математическая мозаика», М., 2004 г.
7.  Б.П.Гейдман. «Подготовка к математической олимпиаде», М., 2007 г.
8.  Т.Д.Гаврилова. «Занимательная математика», изд. Учитель, 2005 г.
9. Е.В.Галкин. «Нестандартные задачи по математике, 5-11 классы», М., 1969 г.
10. «Ума палата» - игры, головоломки, загадки, лабиринты. М., 1996г.
11. https://ru.wikipedia.org/ - Вики – статья об игре «Ним»
12. http://pikabu.ru/story/strategicheskie_igryi_i_reshenie_zadach_igra_nim_i_ey_podobnyie_3932848 - Стратегические игры и решение задач. Игра «Ним» и им подобные.
13. http://mat.1september.ru/view_article.php?ID=200901011 – Системы счисления и их применение.
14. http://nenuda.ru/ - Статья о методах решения задач – игр.