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