Дерево (ЕГЭ С3) Выигрышные игровые стратегии

ЕГЭ С3_ Два игрока играют в следующую игру. Имеются три кучи камней, содержащих соответственно 2, 3, 4 камня. За один ход разрешается или удвоить количество камней в какой-нибудь куче, или добавить по два камня в каждую из трех куч. Предполагается, что у каждого игрока имеется неограниченный запас камней. Выигрывает тот игрок, после чьего хода в какой- нибудь куче становится > 15 камней или во всех трех кучах суммарно становится > 25 камней. Игроки ходят по очереди. Выяснить, кто выигрывает при правильной игре, - первый или второй игрок.

Решение: cтарт 2, 3, 4 4, 3, 4 2, 6, 42, 3, 84, 5, 6 I II 8, 3, 4 4, 6, 4 4, 3, 8 6, 5, 6 4, 6, 4 2,12, 4 2, 6, 8 4, 8, 6 4, 3, 8 2, 6, 8 2, 3,16 4, 5, 10 8, 5, 6 4, 10, 6 4, 5, 12 6, 7, 8 При ходе (4, 6, 4) II игрока I проигрывает Ход (2, 3, 8) ошибочный для I игрока I игрок выигрывает при любом ходе II Ответ: I игрок выигрывает при ходе (2, 3, 4)->(4, 5, 6)

ЕГЭ С3_3_ 2006 Два игрока играют в следующую игру. Перед ними лежат две кучки камней, в первой из которых 5, а во второй - 3 камня. У каждого игрока неограниченно много камней. Игроки ходят по очереди. Ход состоит в том, что игрок или удваивает число камней в какой-то куче, или добавляет 4 камня в какую-то кучу. Выигрывает игрок, после хода которого в одной из куч становится не менее 22 камней. Кто выигрывает при безошибочной игре обоих игроков -игрок, делающий первый ход, или игрок, делающий второй ход? Как должен ходить выигрывающий игрок? Ответ обоснуйте.

ЕГЭ С3_2_ 2006 Два игрока играют в следующую игру. Перед ними лежат две кучки камней, в первой из которых 4, а во второй - 3 камня. У каждого игрока неограниченно много камней. Игроки ходят по очереди. Ход состоит в том, что игрок или увеличивает в 3 раза число камней в какой-то куче или добавляет 2 камня в какую-то кучу. Выигрывает игрок, после хода которого общее число камней в двух кучах становится не менее 24 камней. Кто выигрывает при безошибочной игре обоих игроков - игрок, делающий первый ход или игрок, делающий второй ход? Каким должен быть первый ход выигрывающего игрока? Ответ обоснуйте.

Демо 2008

ЕГЭ С3_ Два игрока играют в следующую игру. Перед ними лежат две кучки камней, в первой из которых 6, а во второй - 5 камней. У каждого игрока неограниченно много камней. Игроки ходят по очереди. Ход состоит в том, что игрок увеличивает или в 2 раза, или в 3 раза число камней в какой-то куче. Выигрывает игрок, после хода которого общее число камней в двух кучах становится не менее 48 камней. Кто выигрывает при безошибочной игре обоих игроков - игрок, делающий первый ход, или игрок, делающий второй ход? Каким должен быть первый ход выигрывающего игрока? Ответ обоснуйте.

ЕГЭ С3_ Два игрока играют в следующую игру. Перед ними лежат две кучки камней, в первой из которых 3, а во второй - 6 камней. У каждого игрока неограниченно много камней. Игроки ходят по очереди. Ход состоит в том, что игрок или удваивает число камней в какой-то куче, или добавляет 2 камня в какую-то кучу. Выигрывает игрок, после хода которого общее число камней в двух кучах становится не менее 24 камней. Кто выигрывает при безошибочной игре обоих игроков - игрок, делающий первый ход, или игрок, делающий второй ход? Каким должен быть первый ход выигрывающего игрока? Ответ обоснуйте.

1.Два игрока играют в следующую игру. На координатной плоскости стоит фишка. Игроки ходят по очереди. В начале игры фишка находится в точке с координатами (5,2). Ход состоит в том, что игрок перемещает фишку из точки с координатами (x,y) в одну из трех точек: или в точку с координатами (x+3,y), или в точку с координатами (x,y+3), или в точку с координатами (x,y+4). Выигрывает игрок, после хода которого расстояние по прямой от фишки до точки с координатами (0,0) не меньше 13 единиц. Кто выигрывает при безошибочной игре обоих игроков – игрок, делающий первый ход, или игрок, делающий второй ход? Каким должен быть первый ход выигрывающего игрока? Ответ обоснуйте Примеры заданий:

1 игрок (5,2) 29 (8,2) 68 (5,5) 50 (5,6) 61 1) из каждой ситуации в этой игре возможно три продолжения, поэтому дерево получается троичным 2) по теореме Пифагора расстояние L от точки с координатами (x,y) до начала координат – это квадратный корень из суммы квадратов координат: Решение (вариант 1, ручная прокрутка): чтобы избавиться от вычисления квадратного корня, нужно перейти от заданного условия к равносильному условию в целых числах: 3) первый игрок имеет три варианта хода, запишем их в таблицу, указывая для каждого положения координаты (в скобках) и значение (мелким шрифтом);

4) ход второго игрока: 1 игрок2 игрок (5,2) 29 (8,2) 68 (11,2) 125 (8,5) 89 (8,6) 100 (5,5) 50 (8,5) 89 (5,8) 89 (5,9) 106 (5,6) 61 (8,6) 100 (5,9) 106 (5,10) 125 второй игрок тут тоже никак не может выиграть 5) обратите внимание на варианты, выделенные в таблице серым фоном: они уже встречались выше в этом же столбце (хотя получены в результате другой последовательности ходов), поэтому дальше не стоит их рассматривать отдельно

6) строим таблицу для третьего хода (игрок 1); для сокращения записи не будем выписывать все возможные ходы, если мы нашли выигрышный ход из этой позиции (выделен синим фоном): 1 игрок2 игрок1 игрок (5,2) 29 (8,2) 68 (11,2) 125 (14,2) 200 (8,5) 89 (11,5) 146 (8,8) 128 (8,9) 145 (8,6) 100 (11,6) 157 (8,9) 145 (8,10) 164 (5,5) 50 (8,5) 89 (5,8) 89 (5,12) 169 (5,9) 106 (5,12) 169 (5,6) 61 (8,6) 100 (5,9) 106 (5,10) 125 (5,13) 196 видим, что в некоторых случаях первый игрок может выиграть уже на втором ходу, однако это не гарантирует ся, значит, нельзя утверждать, что первый игрок всегда выиграет

7) легко проверить, что во всех оставшихся позициях (если первый не выиграл) второй игрок выигрывает своим следующим ходом: 1 игрок2 игрок1 игрок2 игрок (5,2) 29 (8,2) 68 (11,2) 125 (14,2) 200 (8,5) 89 (11,5) 146 (14,5) 221 (8,8) 128 (11,8) 185 (8,9) 145 (11,9) 202 (8,6) 100 (11,6) 157 (14,6) 232 (8,9) 145 (8,10) 164 (11,10) 221 (5,5) 50 (8,5) 89 (5,8) 89 (5,12) 169 (5,9) 106 (5,12) 169 (5,6) 61 (8,6) 100 (5,9) 106 (5,10) 125 (5,13) 196

8) из таблицы следует, что второй игрок выигрывает (своим вторым ходом), если ему удастся свести ситуацию к положению (8,5) или (8,6) 9)далее замечаем, что при любом ходе первого игрока второй может добиться нужной ему позиции (показаны варианты в зависимости от первого хода): (8,2)(8,5) (8,2)(8,6)или (5,5)(8,5) или (5,6)(8,6) и выиграть вторым ходом 10) таким образом, при правильной игре выиграет второй игрок, для этого при любом ходе первого игрока ему достаточно свести ситуацию к положению (8,5) или (8,6); такая возможность у него есть.

Возможные ловушки и проблемы: нужно уметь правильно считать, часто в работах встречаются арифметические ошибки, которые приводят к неверному решению таблица получается довольно громоздкой, чтобы не запутаться, лучше оставлять в ней только те данные, которые действительно влияют на решение (как мы делали выше) обнаружив, что первый игрок выигрывает в некоторых вариантах на 2-ом ходу, можно (напрасно!) обрадоваться и записать неверный ответ (помните, что факт выигрыша в каких-то случаях, еще не означает, что этот игрок выиграет всегда) необходимо проверить, при любом ли ходе первого игрока второй игрок (в нашей задаче) может получить нужную для себя ситуацию; например, мог быть вариант, когда для первого хода (5,5) при любом ходе второго игрока выигрывал первый, это означало бы, что при правильной игре первый всегда победит известные примеры задач ЕГЭ этого типа показывают, что второй игрок почему-то выигрывает чаще, но на это нельзя рассчитывать, именно в вашем варианте может быть все по-другому

Как правильно оформить решение: нужно обязательно написать ответ СЛОВАМИ, например, «Выиграет игрок, который делает второй ход» нужно обязательно привести ВСЕ варианты ходов первого игрока и доказать, что во всех случаях у второго (в данной задаче!) есть выигрышный ход в решении должна быть СЛОВАМИ описана стратегия игры второго игрока «как он должен играть, чтобы выиграть) За что снимают баллы: если вы правильно указали выигрывающего игрока, но не привели никакого обоснования, эксперт поставит 0 баллов не описана стратегия выигрывающего игрока (как именно ему нужно ходить) не проведен полный анализ возможных ходов обоих игроков (рассмотрены не все случаи ответных ходов)

ЕГЭ 2009

Решите самостоятельно: 1) Два игрока играют в следующую игру. На координатной плоскости в точке с координатами (2;3) стоит фишка. Игроки ходят по очереди. Ход состоит в том, что игрок перемещает фишку из точки с координатами (x,y) в одну из трех точек: (2x;y), (x,2y) или (x,y+2). Выигрывает тот игрок, после хода которого расстояние по прямой от фишки до начала координат (0,0) больше 13 единиц. Кто выигрывает – игрок, делающий ход первым, или игрок, делающий ход вторым? Ответ: Выигрывает второй игрок. Своим первым ходом ему нужно получить одну из ситуаций: (4,5) или (4,6), после этого он выигрывает через 1 ход.

2) Даны три кучи камней, содержащие соответственно 3, 4 и 5 камней. За один ход разрешается или удвоить количество камней в меньшей куче (если таких две – то лишь в одной из них), или добавить 2 камня в большую из куч (если таких две – то лишь в одну из них). Выигрывает тот игрок, после хода которого во всех трех кучах суммарно становится не менее 23 камней. Игроки ходят по очереди. Выяснить, кто выигрывает при правильной игре – первый или второй игрок. Ответ: Выигрывает второй игрок. Своим первым ходом ему нужно получить одну из ситуаций: (8,4,5) или (6,4,7) – здесь числа в скобках обозначают количество камней в первой, второй и третьей кучках соответственно. Он выигрывает через 1 ход.