Четвёртая открытая интернет-олимпиада по математике

======= 136 ========

Оценка за решение задачи ММ136 учитывается дважды: в основном Марафоне
и в тематическом конкурсе.

ММ136 (МИ3) (5 баллов)

На столе в открытую лежит 16 карт: 4 туза (считаются за 1 очко), 4 двойки, 4 тройки и 4 четвёрки. Петя и Вася по очереди берут оттуда по одной карте и складывают в отдельную стопку (общую). Выигрывает тот, после чьего хода сумма очков в этой стопке составит 21 очко (или заставивший соперника своим ходом превысить это значение). Петя начинает игру. Кто победит в игре и какой стратегии он должен придерживаться (как реагировать на ходы соперника)?


Решение

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

Для того, чтобы проанализировать эту игру, неплохо бы как-то разложить этот гиперкуб на плоскость. Это можно сделать в виде такой таблицы, состоящей из 25-ти секторов. Тогда взятие единицы или двойки соответствует сдвигу вниз или влево в пределах одного сектора, а взятие тройки или четвёрки - смене сектора на нижний или правый.



В позициях, соответствующих перебору, стоят единицы, ведь игрок, пришедший в них, проиграл, значит тот, к кому в данный момент перешла очередь хода - выиграл. В позициях, где сумма a+2b+3c+4d=21, стоят нули, т.к. пришедший туда выигрывает, значит, тот, кому очередь ход перешла, проиграл. Остальные ячейки заполняем рекурсивно по правилу: Если из ячейки можно хотя
одним ходом попасть в проигрышную, она - выигрышная, а если же все ходы ведут в выигрышные позиции, она - проигрышная.

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

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

Проведя компьютерный анализ игры для других позиций, Сергей Половинкин установил, что Петя выиграет для любого N, не делящегося на 5, кроме N=27.

Награды

За правильное решение задачи Дмитрий Пашуткин, Алексей Волошин, Кирилл Веденский, Анатолий Казмерчук, Евгений Гужавин, Александр Ларин и Владислав Франк получают по 5 призовых баллов. Сергей Половинкин получает 5+2=7 призовых баллов. Николай Дерюгин получает 3 призовых балла.

Эстетическая оценка задачи 4 балла

Разбор задачи ММ137 подготовил Алексей Извалов