Кто выиграет при правильной игре

Кто выиграет при правильной игре

Вернёмся к примеру 5 и зададимся вопросом: кто выиграет?

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

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

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

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

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

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

Идея доказательства этого утверждения в частном случае будет рассмотрена при решении задач методом анализа с конца (см. § 3).

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

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

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

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

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

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

Кто выиграет при правильной игре

«Игра — высшая форма исследования».

Стратегия задач про игры

Задачи про игры — весьма популярный вид олимпиадных задач, особенно в младших классах. Как показывает опыт, наиболее общая проблема у начинающих — понять, «что вообще от нас хотят», какие рассуждения являются правильным решением задачи, а какие — нет.
Обычно предполагается (и мы не будем в дальнейшем это специально указывать!), что играют двое, делая ходы по очереди (пропускать свой ход нельзя!), а в задаче спрашивают «кто выиграет при правильной игре?» Стандартная ошибка, по сути — понимать слова «при правильной игре» так, как будто оба противника играют оптимальным для себя образом (тем более, что решающий задачу часто неправильно понимает, что такое «оптимальным образом»!). Тогда придумывается выигрышная стратегия, дающая ответ только на оптимальный ход противника (обычно еще «оптимальным» считается такой ход, когда противник следует придуманной нами же стратегии — хотя для другого игрока такая стратегия может быть, наоборот, совсем никудышной. ). На самом деле, надо уметь придумывать ответ на любой ход противника, каким бы идиотским он нам не казался. Обычно правильная стратегия, в отличие от липы, не имеет случаев разной сложности, а с одинаковой легкостью находит достойный ответ на любой ход!

Основные методы решения игровых задач

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

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

Итак, если выиграет первый, тогда в решении игровой задачи нужно записать:

I) его первый ход;

II) алгоритм его ходов в ответ на каждый ход соперника, т.е. стра­тегию победы;

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

Если же выиграет второй, тогда в решение нужно записать:

I) алгоритм его ходов в ответ на каждый ход соперника, т.е. стра­тегию победы;

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

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

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

В своей работе я рассмотрел следующие идеи стратегий:

· Игры, использующие симметрию.

· Игры, в которых стратегия — дополнение до фиксированного числа.

· Игры, использующие метод выигрышных позиций

Остановимся на каждой идее более подробно.

Игры, использующие симметрию

Сейчас мы познакомимся с мощным и красивым, но очень простым методом решения игровых задач — симметричной стратегией. Суть его — делать каждый раз ход, симметричный ходу противника или дополняющий его до чего-либо. Доказательство правильности нашей стратегии будет пользоваться тем, что после каждого нашего хода позиция симметрична: раз так, то если противник сумел сделать свой ход, то и мы сможем сделать ход, симметричный ему. Неправильно думать что симметрии — стратегия только для второго игрока. Если исходная позиция — несимметрична, то обычно первый игрок может ее как-то сделать симметричной, а потом играть по симметрии, отвечая на ходы второго.

Задача 1: Соты имеют форму квадрата 9×9. Все квадратики, кроме центрального, заполнены мёдом. В центре — дёготь. За один ход разрешено разломить соты вдоль любой вертикальной или горизонтальной линии и съесть ту часть, где нет дёгтя. Проигрывает тот, кому остался только дёготь. Кто выиграет при правильной игре?

Ответ. Выигрышная стратегия есть у второго игрока.

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

Игры, в которых стратегия — дополнение до фиксированного числа

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

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

Решение: Остаток от деления числа 15 на 3 + 1 = 4 равен 3. Начинающему надо, добиться того, чтобы последний карандаш взял противник, поэтому первым ходом он должен взять не 3 карандаша (остаток от деления), а 2 (1 карандаш – противнику!) Затем каждым последующим ходом будет дополнять количество карандашей, взятых вторым игроком, до 4.

После первого хода 1 -го игрока на столе останется 13 карандашей, после второго хода — 9, после третьего — 5, после четвертого — 1. Следовательно, последний карандаш берет второй игрок.

Метод выигрышных позиций

Бесспорно, самый мощный и универсальный способ решения задач на игры — поиск выигрышных позиций. Здесь мы будем называть выигрышной ту позицию, которую выгодно оставлять после своего хода, а проигрышной, соответственно, ту, которую невыгодно (в согласии с одной половиной методической литературы и в противоположность другой половине 🙂 Тогда финальная позиция, из которой уже нельзя сделать ход — выигрышная. Основные свойства позиций таковы:
1.) каждая позиция — либо выигрышная, либо проигрышная (промежуточных вариантов нет!);
2.) из выигрышной позиции можно пойти только на проигрышную;
3.) из любой проигрышной позиции можно пойти на выигрышную.
Тогда, если начальная позиция — проигрышная, выигрывает первый, если выигрышная — второй. Стратегия одинакова: каждый раз ходить на выигрышную позицию. Тогда противник должен будет походить на проигрышную позицию (свойство 2), а мы опять сможем пойти на выигрышную (свойство 3).

Суть метода: делим всю доску (или все возможные ходы) на два вида полей — выигрываю­ щие и проигрывающие (причем под это определение попадают все рассматриваемые клетки или ходы). После этого стратегия играющего заключается в том, чтобы делать свой ход на выигрывающие клетки (или делать выигрывающие ходы). Данный метод пригоден почти для всех игровых задач.

Рассмотрим применение данного метода на конкретной задаче.

Задача 3: Имеются две кучки конфет: в одной — 20, в другой — 21. За ход нужно съесть все конфеты в одной из кучек, а вторую разделить на две необязательно равные кучки. Проигрывает тот, кто не может сделать ход. Кто выиграет?

Решение: Если мы решили использовать метод выигрышных пози­ций, то нам нужно найти эти выигрышные позиции. Чтобы их найти, рассмотрим простейшие случаи.

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

Очевидно, что позиция 2 и 1 выигрышная для первого и проигрыш­ная для второго.

Если 3 и 1, тогда второй вновь с победой, как несложно убедиться простой проверкой, так как есть ровно два хода.

Когда в кучках 3 и 2, победа у первого (убираем 3, делим 2).

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

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

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

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

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

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

Стратегия победителя заключается в том, что он делает ход на «вы­игрышные» поля. Так как первый может сделать ход на «выигрышное» поле, а хода с одного «выигрышного» поля на другое нет, и с любого «проигрышного» поля за один ход можно попасть на «выигрышное», то побеждает начинающий. Своим первым ходом он может съест куч­ку из 21 конфеты, а кучу с 20 конфетами разделить на две, в которых нечетное количество конфет в обеих кучках (например, 19 и 1). За­метим, что последняя позиция, когда две кучки, по одной конфете в каждой, выигрышная, т.е. последний ход сделает первый.

Самый первый и простой класс игр — игры-шутки, в которых, на самом деле, нет никакой стратегии (а нас хотят обмануть, что она якобы есть!). Просто. как бы кто ни ходил, либо всегда выиграет первый игрок (тот, кто начинает игру), либо всегда второй. Задача — в том, чтобы математически доказать такую закономерность (а заметить ее можно, сыграв самому с собой раза 3-4). Для доказательства обычно находится какая-то величина, которая понятно чему равна в начале и конце и понятно как изменяется на каждом ходу — тут даже частенько число ходов до конца однозначно посчитать можно. Либо какой-то инвариант (т.е. что-то, не меняющееся ни при какой ходе), однозначно зависящий от начальной позиции (чаще всего — от четности) и определяющий выигравшего в конце.

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

Задача 4: Двое по очереди ломают шоколадку 5×8. За ход можно разломать любой кусок по прямой линии между дольками. Проигрывает тот, кто не может сделать ход (И это такое стандартное условие, что мы его будем подразумевать, если не сказано обратное. Вопрос «кто выиграет при правильной игре?» тоже подразумевается.)
Решение: Что значит, что игра закончилась? Конечно, что шоколадка уже вся разломана на отдельные дольки. Долек всегда будет 5×8=40 штук, а шоколадка в начале была одна. Заметим, что на каждом ходу один кусок шоколадки всегда разламывается на 2, т.е. количество различных кусков шоколадки увеличивается на 1. В начале это кол-во было равно 1, а в конце, как мы заметили, 40. Значит, игра продолжалась ровно 39 ходов («ходом» мы называем ход одного игрока, а не пару «ход — ответный ход»). Поэтому последний (39-й) ход был обязательно ходом первого (его ходы — первый, третий и все с нечетными номерами) — и первый выиграл.
Вот такая получилась шутка — как ни ходи, первый всегда выигрывает 😉

Кто выиграет при правильной игре

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

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

Игры-шутки (исход игры не зависит от ходов противников)

Симметричные стратегии

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

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

Другие стратегии (удачное соответствие, решение с конца)

а) Выигрышная стратегия для Маляки: если Каляка берет a карандашей, то следующим ходом Маляка берет (5− a ) карандашей. Так как после каждой пары ходов количество карандашей в кучке уменьшается на 5, а 20 делится на 5, то через 4 пары ходов Маляка выиграет.

б) Выигрышная стратегия для Каляки: первым ходом взять 2 карандаша, чтобы оставшееся количество карандашей делилось на 6. Следующие ходы Каляка делает по правилу: если Маляка берет a карандашей, то следующим ходом Каляка берет (6− a карандашей).

Кто выиграет при правильной игре

1. Введение.

Математические науки выделили собственную дисциплину, которая исключительно исследует игровые явления как явления, поддающиеся обработке математическим аппаратом. Истоки теоретико-игровых рассуждений восходят с работам Баше де Мезирака (середина 17 века). Сама же идея создания математической теории конфликта — теории игр — формируется с начала 20 века, о чем свидетельствуют труды К. Бутона, Э. Ласкера, Е. Мура, Э. Цермело, Э. Бореля, Г. Штейнгауза.

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

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

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

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

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

Что такое игровая, стратегическая задача? Это не совсем обычная математическая задача, так как, во-первых, в ней часто нет ничего числового, то есть непо­нятно, а что, собственно говоря, нужно решать или точнее, что писать в решении таких задач?

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

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

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

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

2. Основные идеи решения игровых задач

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

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

Так как же правильно записать решение игровой задачи?

В решении игровой задачи нужно записать:

I) ход первого игрока;

II) алгоритм ходов в ответ на каждый ход соперника, т. е. стра­тегию победы;

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

В работе рассмотрены следующие идеи стратегий:

Игры-шутки.

Игры, использующие симметрию.

Игры, в которых стратегия — дополнение до фиксированного числа.

Игры, использующие метод выигрышных позиций

Остановимся на каждой идее более подробно.

3. Игровые задачи.

1. Игры-шутки.

Игры – шутки – это такие игры, где для построения вы­игрышного алгоритма можно ничего и не знать, так как в них результат будет зависеть не от игры партнеров, а от начальных условий. Однако для этого в решении нужно заметить, что это игра-шутка, а не какая-то другая, в которой нужно искать выигрышную стратегию. На самом деле, нет никакой стратегии (а нас хотят обмануть, что она якобы есть!) Просто. как бы кто ни ходил, либо всегда выиграет первый игрок (тот, кто начинает игру), либо всегда второй. Задача — в том, чтобы математически доказать такую закономерность. Для доказательства обычно находится какая-то величина, которая понятно чему равна в начале и конце и понятно как изменяется на каждом ходу — тут даже частенько число ходов до конца однозначно посчитать можно. Это величина называется инвариантом (четность – самый известный инвариант в математике).

Инвариант (от лат. invarians — неизменяющийся), в математике — величина, остающаяся неизменяемой при тех или иных преобразованиях.

1. В ряде задач встречается следующая ситуация. Некоторая система последовательно изменяет своё состояние, и требуется выяснить нечто о её конечном состоянии. Полностью проследить за всеми переходами может оказаться делом сложным, но иногда ответить на требуемый вопрос помогает вычисление некоторой величины, характеризующей состояние системы и сохраняющейся при всех переходах (такую величину называют инвариантом для рассматриваемой системы). Ясно, что тогда в конечном состоянии значение инварианта будет то же самое, что и в начальном, т.е. система не может оказаться в состоянии с другим значением инварианта.

2. На практике этот метод сводится к тому, что некоторая величина вычисляется двумя способами: сначала она просто вычисляется в начальном и конечном состояниях, а затем прослеживается её изменение при последовательных мелких переходах.

3. Наиболее простым и часто встречающимся инвариантом является четность числа; инвариантом может быть также и остаток от деления не только на 2, но и на какое-нибудь другое число. Для построения инвариантов иногда бывают полезны вспомогательные раскраски, т.е. разбиения рассматриваемых объектов на несколько групп (каждая группа состоит из объектов одного цвета).

Многие задачи легко решаются, если заметить, что некоторая величина имеет определённую чётность. Из этого следует, что ситуации, в которых эта величина имеет другую чётность, невозможны. Иногда эту величину (функцию) надо сконструировать, например, рассмотреть чётность суммы или произведения, разбить объекты на пары, заметить чередование состояний, раскрасить объекты в 2 цвета.

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

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

Решение: Долек всегда будет 5×8=40 штук, а шоколадка в начале была одна. Заметим, что на каждом ходу один кусок шоколадки всегда разламывается на 2, т.е. количество различных кусков шоколадки увеличивается на 1. В начале это кол-во было равно 1, а в конце, как мы заметили, 40. Значит, игра продолжалась ровно 39 ходов. Поэтому последний (39-й) ход был обязательно ходом первого (его ходы — первый, третий и все с нечетными номерами) — и первый выиграл.Вот такая получилась шутка — как ни ходи, первый всегда выигрывает.

Решить ту же задачу в общем виде, про шоколадку MxN.

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

Задача – игра Ним.

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

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

2.Симметрия.Очень простой, но мощный и красивый метод решения игровых задач — симметричная стратегия. Суть его — делать каждый раз ход, симметричный ходу противника или дополняющий его до чего-либо. Доказательство правильности нашей стратегии будет пользоваться тем, что после каждого нашего хода позиция симметрична: раз так, то если противник сумел сделать свой ход, то и мы сможемсделать ход, симметричный ему.

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

Решение: Нам нужно найти такую последовательность ходов, которая позволила бы, глядя на ходы сопер­ника, делать ходы, которые привели бы к победе. Как же ходить после хода соперника? Стол круглый, поэтому первый ход так и просится — положить пятак в центр доски. А дальше? А дальше — по симметрии, относительно центра стола! И понятно, что первый выиграет.

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

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

Задача 2. Двое по очереди ставят слонов в клетки шахматной доски 8×8 так, чтобы слоны не били друг друга. Проигрывает тот, кто не может сделать ход. Кто выиграет?

Решение: Здесь нет центральной клетки. А если бы и была, по­ставить симметрично относительно нее слона мы не можем, так как тогда слон вставал на поле, которое бьется слоном, который поставил соперник.

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

3. Игры, в которых стратегия — дополнение до фиксированного числа.

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

Рассмотрим пример такой стратегии на конкретной задаче.

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

Решение: И опять выработку стратегии лучше начинать с небольшого числа камеш­ков. Понятно, что если в нашей кучке меньше шести камней, тогда выиграет первый игрок: он первым своим ходом заберет все камни.

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

Если камней семь? Что делать тогда первому? Ему нужно забрать один камень и свести задачу к предыдущему случаю. Аналогично надо выработать стратегию игры и для 7, 8, 9,10,11 камней.

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

Итак, если число камней делится на 6, то выигрывает второй, если не делится, то первый. Докажем это.

Пусть у нас 6tкамней. После первого хода игрока, начинающего игру, второй делает ход, после которого остается 6t — 6 камней, т. е. число камней в кучке уменьшилось на 6. Несложно понять, что послед­ний камень возьмет игрок, делающий второй ход, и также понятно, что у него всегда есть возможность сделать ход.

Пусть у нас 6t+a, где 1 < а < 5, камней. Тогда начинающий первым своим ходом убирает все, что «мешает», т. е. а камней, и остается всего 6t камней, т. е. сводит игру к рассматриваемому выше случаю, где он уже второй игрок. Значит в этом случае побеждает игрок, делающий первый ход.

В нашей задаче 50 камней. Поэтому вы­игрывает первый, беря из кучки два камня и оставляя 48 камней. Далее после его последующих ходов в кучке будет оставаться соответствен­но 42, 36, 30, 24, 18, 12, 6, 0, таким образом, последний камень забирает первый игрок.

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

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

Начинающий первым ходом говорит число 2, и при каждом следу­ющем ходе будет говорить число, которое больше предыдущего (т. е. сказанному им на предыдущем ходу) ровно на 6. Итак, на втором ходу он говорит число 8, на третьем — 14, . на девятом — 50.

Второй игрок не сможет помешать начинающему, так как макси­мальное число, которое он может прибавить к сказанному первым иг­роком — это 5, а минимальное — это 1 (а разность между числами, произносимыми первым, — 6).

5. Метод выигрышных позиций

Задача 1.Имеются две кучки конфет: в одной — 20, в другой — 21. За ход нужно съесть все конфеты в одной из кучек, а вторую разделить на две необязательно равные кучки. Проигрывает тот, кто не может сделать ход. Кто выиграет?

Решение: Если мы решили использовать метод выигрышных пози­ций, то нам нужно найти эти выигрышные позиции. Чтобы их найти, рассмотрим простейшие случаи.

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

Очевидно, что позиция 2 и 1 выигрышная для первого и проигрыш­ная для второго.

Если 3 и 1, тогда второй вновь с победой, как несложно убедиться простой проверкой, так как есть ровно два хода.

Когда в кучках 3 и 2, победа у первого (убираем 3, делим 2).

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

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

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

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

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

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

Стратегия победителя заключается в том, что он делает ход на «вы­игрышные» поля. Так как первый может сделать ход на «выигрышное» поле, а хода с одного «выигрышного» поля на другое нет, и с любого «проигрышного» поля за один ход можно попасть на «выигрышное», то побеждает начинающий. Своим первым ходом он может съест куч­ку из 21 конфеты, а кучу с 20 конфетами разделить на две, в которых нечетное количество конфет в обеих кучках (например, 19 и 1). За­метим, что последняя позиция, когда две кучки, по одной конфете в каждой, выигрышная, т. е. последний ход сделает первый.

3. Заключение.

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

Наша дальнейшая работа над этой темой кажется нам еще перспективой, потому что именно теории игр посвящено задание № 26 из ЕГЭ по информатике.

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

Используемая литература:

Генкин С.А., Итенберг И.В., Фомин Д.В. Ленинградские математические кружки. Киров: АСА, 1994.

Гусев В.А., Орлов И.А., Розенталь А.Л. Внеклассная работа по математике в 6-8 классах. М.: Просвещение, 1984.

Петров Н.Н. Математические игры. Ижевск: УдГУ, (1 изд.) 1994.

Гарднер. Математические чудеса и тайны. 1985 г.

Шень А. Ш47 Игры и стратегии с точки зрения математики. | 2-е изд., стерео- типное. | М.: МЦНМО, 2008. | 40 с.: ил.