Математические игры и стратегии.
На этом занятии мы познакомимся с математическими играми и стратегиями.
Что такое математическая задача-игра? Это игра, в которой:
- принимают участие двое или более игроков;
- есть правила, которые задают начальные условия и возможные действия игроков;
- игра состоит из поочередных шагов (ходов) игроков, ходы не зависят от случайности (например, от бросания кубика или монеты);
- правила определяют условия выигрыша или ничьей, выиграть игру может только один игрок, остальным игрокам засчитывается проигрыш;
- каждый игрок стремится выиграть, не поддается и играет только за себя.
Стратегия игрока – это его план действий в игре. Игрок планирует, как он будет действовать в каждый свой ход. Если есть стратегия, которая приводит игрока к выигрышу, несмотря на действия противников, то она называется выигрышной.
Решить задачу-игру – значит найти выигрышную стратегию для одного из игроков. При этом нужно доказать, что выбранная стратения приводик игрока к выигрышу. Если удалось найти выигрышную стратегию для одного игрока, то для остальных игроков выигрышной стратегии не существует, так как в игре возможен только один победитель.
Иногда в задаче стоит вопрос: «Кто победит при правильной игре?». Говорят, что игрок играет правильно, если он не ошибается, не поддается, и, если у него в данный момент есть выигрывающий ход, то он его делает. То есть, если игроку известна его выигрышная стратегия, то он применяет именно ее и не делает глупых и ошибочных шагов. Ответить на вопрос задачи – это то же самое, что найти выигрышную стратегию одного из игроков.
Обычно, несколько раз сыграв в игру, мы уже можем заметить, в каком случае мы выигрываем или проигрываем. То есть, играя, мы постепенно находим выигрышную стратегию. И когда требуется решить математическую задачу-игру, то лучше всего сначала несколько раз в нее сыграть. Но можно пойти и другим путем: внимательно проанализировать правила игры и найти решение математически.
Дальше рассмотрим, какие виды выигрышных стратегий встречаются в математических играх.
Игры-шутки.
Игра-шутка – это такая математическая игра, в которой выигрыш не зависит от ходов игроков. Как бы они ни играли, результат заранее определен условиями задачи.
Задача 1.
Саша и Маша по очереди ломают шоколадку размером 4 х 4 дольки. За один ход можно разломить любой имеющийся кусок шоколадки вдоль прямой линии. Первый ход делает Саша. Проигрывает тот, кто не может сделать ход. Кто выиграет?
Решение.
Игрок не может сделать ход в том случае, если все имеющиеся куски шоколадки состоят ровно из одной дольки (значит, никакой кусок больше нелья разломить). Таким образом, игра закончится, когда получится 16 кусков.
За каждый ход количество кусков, на которые разломана шоколадка, увеличивается на один. Значит, чтобы получилось 16 кусков шоколадки, нужно сделать 15 ходов. И если Саша делает 1-й ход, то он же делает и 15-й ход. После этого у Маши нет хода, и она проигрывает.
Ответ.
Выиграет Саша.
Симметричные стратегии.
В некоторых задачах-играх можно добиться выигрыша, если «копировать», повторять ходы противника. Такая стратегия называется симметричной.
Задача 2.
Аня и Таня по очереди раскрашивают клетчатый коврик размером 9 х 9 клеток. За один ход можно раскрасить только одну клетку. Клетку можно раскрасить, если она не соприкасается ни одной стороной с уже раскрашенными клетками. Проигрывает тот, кто не может сделать ход. Первой ходит Аня. Кто из девочек выиграет? Как она должна ходить, чтобы точно выиграть?
Решение.
В этой игре есть выигрышная стратегия для Ани. Первым ходом ей нужно раскрасить центральную клетку коврика. Затем в каждом следующем ходе «копировать» ход Тани симметрично относительно центра. Если перед ходом Тани на коврике есть клетка, которую можно раскрасить, то значит найдется и симметричная ей клетка для Ани. Если же перед ходом Тани не осталось ни одной клетки, которую можно раскрасить, то она не сможет сделать ход, а значит, проиграет.
Ответ.
Выиграет Аня. В свой первый ход она закрашивает центральную клетку, в следующие ходы симметрично «копирует» ходы Тани.
Задача 3.
У Оли и Коли есть три кучки из 5, 5 и 7 конфет. За один ход можно взять любое количество конфет, но только из одной кучки. Первой ходит Оля. Выигрывает тот, кто возьмет последнюю конфету. Кто выиграет? Как он должен ходить, чтобы точно выиграть?
Решение.
В этой задаче есть выигрышная стратегия для Оли. В первый ход ей нужно взять полностью кучку из 7 конфет. После хода Оли мы получаем две кучки по 5 конфет, и ходит Коля. Оля выиграет, если будет повторять ходы Коли: брать столько же конфет, сколько взял Коля перед ней, только из другой кучки. Поэтому после хода Оли в кучках всегда будет поровну конфет. И если Коля сможет взять конфету из какой-то кучки, то и Оля после него сможет взять конфету из другой кучки. Получается, что последняя конфета в любом случае достанется Оле, и она выиграет.
Ответ.
Выиграет Оля. В свой первый ход она должна забрать кучку из 7 конфет, а в следующие ходы брать столько же конфет, сколько и Коля, но из другой кучки.
Стратегии дополнения.
Еще один вид выигрышных стратегий – это стратегии дополнения. В этом случае игру можно разбить на несколько частей, в каждой из которых ход одного игрока «дополняет» ход другого игрока.
Задача 4.
Пончик и Сиропчик купили в кондитерской набор из 6 пирожных и решили сыграть в игру. За один ход можно съесть 1 или 2 пирожных. Условие выигрыша:
- Выигрывает тот, кто съест последнее пирожное.
- Проигрывает тот, кто съест последнее пирожное.
Первым ходит Пончик. Кто выиграет? Как он должен ходить, чтобы выиграть?
Решение.
а) Рассмотрим ситуацию, когда выигрывает тот, кто съест последнее пирожное.
Сначала посмотрим, кто выиграет, если в наборе будет 3 пирожных. В этом случае последнее пирожное съест тот, кто будет ходить вторым. Если первый игрок съест 1 пирожное, то второй съест оставшиеся 2. Если первый игрок съест 2 пирожных, то второй съест оставшееся 1.
То есть, если к ходу игрока осталось 3 пирожных, то он проиграет.
Разобьем набор из 6 пирожных на 2 части по 3 пирожных. Первым ходит Пончик. Если он берет 1 пирожное, то Сиропчик должен взять 2 оставшихся пирожных из этой части. Если Пончик берет 2 пирожных, то Сиропчик должен взять оставшееся 1 пирожное из этой части.
Таким образом, если Сиропчик в каждый свой ход будет «дополнять» ход Пончика до 3 пирожных, то Сиропчику достанется последнее пирожное в каждой из 3 частей и во всей игре в целом. Сиропчик выиграет.
б) Рассмотрим ситуацию, когда проигрывает тот, кто съест последнее пирожное.
В задаче изменилось условие выигрыша, и это существенно влияет на результат. Если использовать ту же стратегию дополнения, что и случае а), то она не будет выигрышной для Сиропчика, ведь он съест последнее пирожное и проиграет.
Зато в этом случае стратегию дополнения может использовать Пончик. В первый ход он должен съесть 2 пирожных. К ходу Сиропчика останется 4 пирожных. Сиропчик ходит, а Пончик «дополняет» его ход до 3 пирожных, и к следующему ходу Сиропчика остается 1 пирожное. Сиропчик его съедает и проигрывает.
Ответ.
а) Выиграет Сиропчик. В каждый свой ход он должен «дополнять» предыдущий ход Пончика до 3 пирожных.
б) Выиграет Пончик. В первый ход он должен съесть 2 пирожных, затем в каждый свой ход он должен «дополнять» предыдущий ход Сиропчика до 3 пирожных.
Задача 5.
Пончик и Сиропчик купили в кондитерской набор из 7 пирожных и решили сыграть в игру. За один ход можно съесть 1 или 2 пирожных. Выигрывает тот, кто съест последнее пирожное. Первым ходит Пончик. Кто выиграет? Как он должен ходить, чтобы выиграть?
Решение.
Условия задачи те же самые, что и в предыдущей задаче (а), лишь количество пирожных на 1 больше. Но это существенно влияет на результат.
В этом случае выиграет Пончик. Первым ходом ему нужно съесть 1 пирожное. После этого хода мы возвращаемся к предыдущей задаче с 6 пирожными. Но теперь следующий ход у Сиропчика, а Пончик должен «дополнять» его ходы до 3 пирожных.
Ответ.
Выиграет Пончик. В первый ход он должен съесть 1 пирожное, в каждый слеюдущий свой ход он должен «дополнять» предыдущий ход Сиропчика до 3 пирожных.
Игры с известной стратегией одного из игроков.
В некоторых задачах стратегия одного из игроков задана условиями задачи, то есть четко определена последовательность его ходов. При этих условиях требуется найти выигрышную стратегию для второго игрока или доказать, что ее нет.
Задача 6.
Винтик и Шпунтик изобрели автомат по продаже сладостей. В нем есть приемник (для приема монет и конфет), кнопки выбора конфет (леденец, карамелька или шоколадная) и окно выдачи конфет. Работает автомат так:
- если в автомат бросить 1 монету, то он выдаст леденец или карамельку или шоколадную конфету (по выбору покупателя);
- если в автомат бросить карамельку, то он выдаст 2 леденца;
- если в автомат бросить леденец, то он выдаст 1 шоколадную конфету.
Сможет ли Незнайка купить в автомате 5 шоколадных конфет, если у него есть 3 монеты? А если у него только 2 монеты?
Решение.
Тут в качестве «противника» Незнайки выступает автомат, стратегия которого строго определена. Попробуем найти выигрышную стратегию для Незнайки.
За 1 монету Незнайка может получить либо 1 шоколадную конфету, либо 2 шоколадных конфеты. 2 шоколадных конфеты он сможет получить, выполнив такие ходы:
- бросить 1 монету, выбрать и получить 1 карамельку;
- бросить 1 карамельку, получить 2 леденца;
- бросить 1 леденец, получить 1 шоколадную конфету;
- бросить 1 леденец, получить 1 шоколадную конфету.
Чтобы получить 5 шокладных конфет, Незнайке нужно на 1 монету купить 1 шоколадную конфету, а на оставшиеся 2 монеты получить по 2 шоколадных конфеты (то есть всего 4) по указанному выше плану.
А если у Незнайки всего 2 монеты, то 5 шоколадных конфет получить он не сможет.
Ответ.
За 3 монеты Незнайка сможет получить 5 шоколадных конфет, а за 2 монеты не сможет.