Разбор задачи C3 (демо ЕГЭ 2011)
Два игрока играют в следующую игру. Перед ними лежат две кучки камней, в первой из которых 3, а во второй 4 камня. У каждого игрока неограниченно много камней. Игроки ходят по очереди. Ход состоит в том, что игрок или удваивает число камней в какой-то куче или добавляет 4 камня в какую-то кучу. Игрок, после хода которого общее число камней в двух кучах становится больше 25, проигрывает. Кто выигрывает при безошибочной игре обоих игроков – игрок, делающий первый ход, или игрок, делающий второй ход? Каким должен быть первый ход выигрывающего игрока? Ответ обоснуйте.
Введем обозначения: х-первая куча, у-вторая куча. Старт: (х,у). Варианты хода игроков: (х*2,у), (х,у*2), (х+4,у), (х, у+4). Игрок проиграет, когда число камней в 2-х кучах станет 25 (х+у=25). Изобразим ход игры в виде дерева решений. Необходимо ветвить дерево до того момента, когда все варианты последнего хода станут пройгрышными.
После первого хода дерево будет выглядеть так:
На дереве изображены все возможные варианты ходов. Одним цветом в строке подчертнуты одинаковые значения количества камней в кучах. По ходу игры будем ветвить только разные координаты.
После первых 2-х ходов дерево будет выглядеть так:
Последующие рисунки большие по длине и поэтому не умещаются. Чтобы просмотреть рисунки полностью, нажмите на ссылку:"Полный вид изображения",размещенной под рисунком. Кликните по открывшемуся изображению, чтобы его увеличить.
После первых 3-х ходов дерево будет выглядеть так:
Когда 1-й игрок совершает 3-й ход, он проигрывает, когда (х,у) равны: 24,4, 3,32, 3,24, 28,4, 22,4 т.к. сумма х и у в этих случаях больше 25. На рисунке пройгрышные позиции 1-го игрока выделены сплошной рамкой:
Каждый игрок играет безошибочно, поэтому 1-й игрок не пойдет в пройгрышную позицию. Позиции: 24,4, 3,32, 3,24, 28,4, 22,4 ветвить не будем.
Найдем в последней строке позиции, где сумма х и у близка к 25-и. При прибавлении 4-х количество камней увеличится минимум на 4. Поэтому позиции, где х+у принадлежит [22,25] на следующем ходу дадут только пройгрыш при любом ходе игрока. Это правило касается тех позиций, где х и у больше 3-х (если х или у равны 3-м, то х+у принадлежит [23,25]). Найдем такие позиции: 6,16, 20,4 , 7,16, 14,8, 18,4. На следующем рисунке они выделены розовым. Эти позиции на 4-м ходу ветвить не будем.
На рисунке пройгрышные позиции 2-го игрока выделены сплошной рамкой:
В последней строке видно, что минимальное значение х и у равно 4-м, поэтому позиции, где х+у принадлежит [22,25] на следующем ходу дадут только пройгрыш при любом ходе игрока. На рисунке они выделены розовым в последней строке (4-й ход):
На 5-м ходу получаются только пройгрышные позиции (символом "П" обозначены пройгрышные позиции):
Поэтому 1-й игрок проигрывает. Выигрывает 2-й игрок.
Найдем выйгрышные позиции 2-го игрока на 4-м ходе. Это те позиции, что выделены розовым на 4-м ходе.
Рассмотрим позиции 2-го игрока на 2-м ходе. Пройгрышные позиции:
Если 2-й игрок пойдет в позицию 3,16, то при ходе 1-го игрока в позицию 6,16 или 7,16 на 3-м ходе 2-й игрок не может попасть в свои выйгрышные позиции на 4-м ходе.
Если 2-й игрок пойдет в позицию 10,4, то при ходе 1-го игрока в позицию 20,4 на 3-м ходе 2-й игрок не может попасть в свои выйгрышные позиции на 4-м ходе.
Если 2-й игрок пойдет в позицию 6,8, то при ходе 1-го игрока в позицию 6,16 на 3-м ходе 2-й игрок не может попасть в свои выйгрышные позиции на 4-м ходе.
Если 2-й игрок пойдет в позицию 7,8, то при ходе 1-го игрока в позицию 14,8 или 7,16 на 3-м ходе 2-й игрок не может попасть в свои выйгрышные позиции на 4-м ходе.
Если 2-й игрок пойдет в позицию 14,4, то при ходе 1-го игрока в позицию 14,8 или 18,4 на 3-м ходе 2-й игрок не может попасть в свои выйгрышные позиции на 4-м ходе.
Выйгрышные позиции: 12,4, 3,12, 11,4. При любом ходе 1-го игрока на 3-м ходу 2-й игрок может попасть в свои выйгрышные позиции на 4-м ходу. Выйгрышные позиции 2-го игрока на 2-м ходе выделены зеленым:
Представим решение также в виде таблицы (выйгрышные ходы выделены розовым):
Старт |
1-й ход | 2-й ход | 3-й ход | 4-й ход | 5-й ход |
---|---|---|---|---|---|
1-й игрок (все ходы) |
2-й игрок (выйгрышный ход) |
1-й игрок (все ходы) |
2-й игрок (выйгрышный ход) |
1-й игрок (все ходы) | |
3,4 |
6,4 | 12,4 | 12,8 | 16,8, 12,12 |
пройгрыш |
16,4 | 16,8, 20,4 |
||||
3,8 | 3,12 | 6,12 | 12,12, 10,12, 6,16 |
||
7,12 | 11,12, 7,16 |
||||
3,16 | 6,16, 7,16, 3,20 |
||||
7,4 |
11,4 |
11,8 |
15,8, 11,12 | ||
15,4 | 15,8, 19,4 |
Выигрывает 2-й игрок. Варианты его первого хода представлены в таблице выше, в столбце, выделенном розовым.