2015-10-14
1285Тема: Дерево игры. Поиск выигрышной стратегии.
Что нужно знать:
· в простых играх можно найти выигрышную стратегию, просто перебрав все возможные варианты ходов соперников
· для примера рассмотрим такую игру: сначала в кучке лежит 5 спичек; два игрока убирают спички по очереди, причем за 1 ход можно убрать 1 или 2 спички; выигрывает тот, кто оставит в кучке 1 спичку
· первый игрок может убрать одну спичку (в этом случае их останется 4), или сразу 2 (останется 3), эти два варианта можно показать на схеме:
· если первый игрок оставил 4 спички, второй может своим ходом оставить 3 или 2; а если после первого хода осталось 3 спички, второй игрок может выиграть, взяв две спички и оставив одну:
· если осталось 3 или 2 спички, то 1-ый игрок (в обеих ситуациях) выиграет своим ходом:
· простроенная схема называется «деревом игры», она показывает все возможные варианты, начиная с некоторого начального положения (для того, чтобы не загромождать схему, мы не рисовали другие варианты, если из какого-то положения есть выигрышный ход)
|
|
|
· в любой ситуации у игрока есть два возможных хода, поэтому от каждого узла этого дерева отходят две «ветки», такое дерево называется двоичным (если из каждого положения есть три варианта продолжения, дерево будет троичным)
· проанализируем эту схему; если первый игрок своим первым ходом взял две спички, то второй сразу выигрывает; если же он взял одну спичку, то своим вторым ходом он может выиграть, независимо от хода второго игрока
· кто же выиграет при правильной игре? для этого нужно ответить на вопросы: 1) «Может ли первый игрок выиграть, независимо от действий второго?», и 2) «Может ли второй игрок выиграть, независимо от действий первого?»
· ответ на первый вопрос – «да»; действительно, убрав всего одну спичку первым ходом, 1-ый игрок всегда может выиграть на следующем ходу
· ответ на второй вопрос – «нет», потому что если первый игрок сначала убрал одну спичку, второй всегда проиграет, если первый не ошибется
· таким образом, при правильной игре выиграет первый игрок; для этого ему достаточно первым ходом убрать всего одну спичку
· в некоторых играх, например, в рэндзю (крестики-нолики на бесконечном поле) нет выигрышной стратегии, то есть, при абсолютно правильной игре обоих противников игра бесконечна (или заканчивается ничьей); кто-то может выиграть только тогда, когда его соперник по невнимательности сделает ошибку
· полный перебор вариантов реально выполнить только для очень простых игр; например, в шахматах сделать это за приемлемое время не удается (дерево игры очень сильно разветвляется, порождая огромное количество вариантов)
|
|
|
· в демо-вариантах ЕГЭ рекомендуется записывать дерево в виде таблицы (фактически, повернув его «на бок»), так получается более компактно:
| 1 игрок | 2 игрок | 1 игрок | |
Пример задания:
Два игрока играют в следующую игру. На координатной плоскости стоит фишка. Игроки ходят по очереди. В начале игры фишка находится в точке с координатами (5,2). Ход состоит в том, что игрок перемещает фишку из точки с координатами (x,y) в одну из трех точек: или в точку с координатами (x+3,y), или в точку с координатами (x,y+3), или в точку с координатами (x,y+4). Выигрывает игрок, после хода которого расстояние по прямой от фишки до точки с координатами (0,0) не меньше 13 единиц. Кто выигрывает при безошибочной игре обоих игроков – игрок, делающий первый ход, или игрок, делающий второй ход? Каким должен быть первый ход выигрывающего игрока? Ответ обоснуйте.
Решение (вариант 1, полное дерево игры, «поиск в ширину»):
1) из каждой ситуации в этой игре возможно три продолжения, поэтому дерево получается троичным
2) по теореме Пифагора расстояние L от точки с координатами (x,y) до начала координат – это квадратный корень из суммы квадратов координат: 
; чтобы избавиться от вычисления квадратного корня, нужно перейти от заданного условия 
к равносильному условию в целых числах: 
3) в начальный момент 
, условие не выполнено
4) первый игрок имеет три варианта хода, запишем их в таблицу, указывая для каждого положения координаты (в скобках) и значение 
(мелким шрифтом);
| I игрок | |
| (5,2) 29 | (8,2) 68 |
| (5,5) 50 | |
| (5,6) 61 |
5) видим, что одним ходом первый игрок никак не может выиграть (для всех вариантов 
)
6) построим следующий столбец таблицы (ход второго игрока):
второй игрок тут тоже никак не может выиграть (для всех вариантов );
7) обратите внимание на варианты, выделенные в таблице серым фоном: они уже встречались выше в этом же столбце (хотя получены в результате другой последовательности ходов), поэтому дальше не стоит их рассматривать отдельно
8) строим таблицу для третьего хода (I-й игрок); для сокращения записи не будем выписывать все возможные ходы, если мы нашли выигрышный ход из этой позиции (выделен синим фоном):
| I игрок | II игрок | I игрок | |
| (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 |
9) видим, что в некоторых случаях первый игрок может выиграть уже на втором ходу, однако это не гарантируется, значит, нельзя утверждать, что первый игрок всегда выиграет
10) легко проверить, что во всех оставшихся позициях (если первый не выиграл) второй игрок выигрывает своим следующим ходом:
| I игрок | II игрок | I игрок | II игрок | |
| (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 |
11) теперь осталось выполнить самое главное – сделать анализ этой таблицы и определить, кто же выиграет, если оба играют лучшим для себя образом
12) из таблицы следует, что второй игрок выигрывает (своим вторым ходом), если ему удастся свести ситуацию к положению (8,5) или (8,6)
13) далее замечаем, что при любом ходе первого игрока второй может добиться нужной ему позиции (показаны варианты в зависимости от первого хода):
| (8,2)→(8,5) (8,2)→(8,6) | или | (5,5)→(8,5) | или | (5,6)→(8,6) |
и выиграть вторым ходом
14) таким образом, при правильной игре выиграет второй игрок, для этого при любом ходе первого игрока ему достаточно свести ситуацию к положению (8,5) или (8,6); такая возможность у него есть.
|
|
|
| Возможные ловушки и проблемы: · нужно уметь правильно считать, часто в работах встречаются арифметические ошибки, которые приводят к неверному решению · таблица получается довольно громоздкой, чтобы не запутаться, лучше оставлять в ней только те данные, которые действительно влияют на решение (как мы делали выше) · обнаружив, что первый игрок выигрывает в некоторых вариантах на 2-ом ходу, можно (напрасно!) обрадоваться и записать неверный ответ (помните, что факт выигрыша в каких-то случаях, еще не означает, что этот игрок выиграет всегда) · необходимо проверить, при любом ли ходе первого игрока второй игрок (в нашей задаче) может получить нужную для себя ситуацию; например, мог быть вариант, когда для первого хода (5,5) при любом ходе второго игрока выигрывал первый, это означало бы, что при правильной игре первый всегда победит · известные примеры задач ЕГЭ этого типа показывают, что второй игрок почему-то выигрывает чаще J, но на это нельзя рассчитывать, именно в вашем варианте может быть все по-другому |
| Как правильно оформить решение: · нужно обязательно написать ответ СЛОВАМИ, например, «Выиграет игрок, который делает второй ход» · нужно обязательно привести ВСЕ варианты ходов первого игрока и доказать, что во всех случаях у второго (в данной задаче!) есть выигрышный ход · в решении должна быть СЛОВАМИ описана стратегия игры второго игрока «как он должен играть, чтобы выиграть) · рекомендуется записывать ходы в таблицу, точно совпадающую с той, которая приводится в официальном решении демо-варианта; для эксперта этот вариант будет гарантированно понятен и привычен |
Итак, у нас получилось, что выигрывает второй игрок. В ответе на каждом ходу нужно привести все возможные ходы первого игрока, и на каждый из этих ходов дать выигрышный ответ второго. В первом столбце стандартной таблицы записываем начальную позицию. Из этого положения у I-ого игрока есть 3 варианта хода, записываем их во второй столбец:
| 1-й ход | 2-й ход | 3-й ход | 4-й ход | |
| стартовая позиция | I-й игрок (все варианты хода) | II-ой игрок, выигрышный ход | I-й игрок (все варианты хода) | II-ой игрок, выигрышный ход |
| (5,2) 29 | (8,2) 68 | |||
| (5,5) 50 | ||||
| (5,6) 61 |
Обратите внимание, что мы перечислили все возможные ходы I-ого игрока, как и требуется.
|
|
|
Теперь на каждый возможный ход I-ого игрока во втором столбце записываем выигрышный ответ II-ого, то есть, такой ответ, который приводит второго к выигрышу, и подчеркиваем его (или как-то выделяем по-другому, чтобы показать, что это выигрышный ход):
| 1-й ход | 2-й ход | 3-й ход | 4-й ход | |
| стартовая позиция | I-й игрок (все варианты хода) | II-ой игрок, выигрышный ход | I-й игрок (все варианты хода) | II-ой игрок, выигрышный ход |
| (5,2) 29 | (8,2) 68 | (8,5) 89 | ||
| (5,5) 50 | (8,5) 89 | |||
| (5,6) 61 | (8,6) 100 |
В четвертом столбце нужно перечислить все варианты (обязательно все!) второго хода I-ого игрока в ответ на указанный выигрышный ход второго:
| 1-й ход | 2-й ход | 3-й ход | 4-й ход | |
| стартовая позиция | I-й игрок (все варианты хода) | II-ой игрок, выигрышный ход | I-й игрок (все варианты хода) | II-ой игрок, выигрышный ход |
| (5,2) 29 | (8,2) 68 | (8,5) 89 | (11,5) 146 | |
| (8,8) 128 | ||||
| (8,9) 145 | ||||
| (5,5) 50 | (8,5) 89 | (11,5) 146 | ||
| (8,8) 128 | ||||
| (8,9) 145 | ||||
| (5,6) 61 | (8,6) 100 | (11,6) 157 | ||
| (8,9) 145 | ||||
| (8,10) 164 |
Остается добавить в последний столбец (один!) выигрышный ход II-ого игрока. Обратите внимание, что для выигрывающего игрока достаточно указать только один выигрышный ход, а для проигравшего нужно рассмотреть все ходы на каждом шаге.
| 1-й ход | 2-й ход | 3-й ход | 4-й ход | |
| стартовая позиция | I-й игрок (все варианты хода) | II-ой игрок, выигрышный ход | I-й игрок (все варианты хода) | II-ой игрок, выигрышный ход |
| (5,2) 29 | (8,2) 68 | (8,5) 89 | (11,5) 146 | (14,5) 221 |
| (8,8) 128 | (11,8) 185 | |||
| (8,9) 145 | (11,9) 202 | |||
| (5,5) 50 | (8,5) 89 | (11,5) 146 | (14,5) 221 | |
| (8,8) 128 | (11,8) 185 | |||
| (8,9) 145 | (11,9) 202 | |||
| (5,6) 61 | (8,6) 100 | (11,6) 157 | (14,6) 232 | |
| (8,9) 145 | (11,9) 202 | |||
| (8,10) 164 | (11,10) 221 |
После таблицы обязательно опишите стратегию игры словами:
«Выигрывает игрок, который делает второй ход. Таблица содержит все варианты хода первого игрока. Из нее видно, что при любом ходе первого игрока у второго есть ход, приводящий к победе».
| За что снимают баллы: · если вы правильно указали выигрывающего игрока, но не привели никакого обоснования, эксперт поставит 0 баллов · не описана стратегия выигрывающего игрока (как именно ему нужно ходить) · не проведен полный анализ возможных ходов обоих игроков (рассмотрены не все случаи ответных ходов) |
Решение (вариант 2, неполное дерево игры, «поиск в глубину»):
1) в отличие от предыдущего способа, будем строить дерево «в глубину», то есть доходить до выигрыша одного из игроков, и только потом переходить к следующей ветке
2) рассмотрим первый ход первого игрока:
| I игрок | |
| (5,2) 29 | (8,2) 68 |
3) теперь рассматриваем первый возможный ответ второго игрока (увеличение x на 3):
| I игрок | II игрок | |
| (5,2) 29 | (8,2) 68 | (11,2) 125 |
4) видим, что в этой ситуации следующим ходом I-й игрок выигрывает:
| I игрок | II игрок | I игрок | |
| (5,2) 29 | (8,2) 68 | (11,2) 125 | (14,2) 200 |
таким образом, эту ветку дерева мы рассмотрели до конца
5) теперь анализируем второй возможный ответ II-ого игрока:
| I игрок | II игрок | I игрок | |
| (5,2) 29 | (8,2) 68 | (11,2) 125 | (14,2) 200 |
| (8,5) 89 |
6) перебор вариантов показывает, что следующим ходом первый игрок никак не может выиграть, таблице перечислены все его возможные ходы:
| I игрок | II игрок | I игрок | |
| (5,2) 29 | (8,2) 68 | (11,2) 125 | (14,2) 200 |
| (8,5) 89 | (11,5) 146 | ||
| (8,8) 128 | |||
| (8,9) 145 |
7) в то же время своим следующим ходом II-й игрок выигрывает при любом ответе I-ого, увеличивая координату x на 3:
| I игрок | II игрок | I игрок | II игрок | |
| (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 |
таким образом, если II-й игрок свел ситуацию к позиции (8,5), он выиграет, потому что при любом ответе I-го игрока у второго есть выигрышный ход; поэтому (8,5) – это выигрышный ход второго игрока в том случае, когда первый игрок походил (8,2)
заметим, что в позиции (8,2) у второго игрока есть еще один ход – (8,6), но его уже можно не рассматривать, поскольку мы уже нашли один выигрышный ход – (8,5), этого достаточно
8) теперь рассматриваем второй возможный ход первого игрока в исходной позиции:
| I игрок | |
| (5,2) 29 | (5,5) 50 |
9) сразу замечаем, что второй игрок, увеличив y на 3, может своим ходом сразу свести игру к позиции (8,5), которая обеспечивает его выигрыш (см. выше), поэтому дальше эту ветку можно не рассматривать
| I игрок | II игрок | |
| (5,2) 29 | (5,5) 50 |  (8,5) 89
|
10) остается третий возможный ход первого игрока из начального положения: (5,6)
| I игрок | |
| (5,2) 29 | (5,6) 61 |
11) видим, что из положения (5,6) не удается свести игру к уже рассмотренной выигрышной позиции (8,5), поэтому нужно проверить все возможные ответы второго игрока и попытаться найти среди них выигрышный ход
12) чтобы максимально сократить перебор, сначала рассмотрим вариант хода второго игрока, который ближе всего к известной выигрышной позиции (8,5) – это ход (8,6):
| I игрок | II игрок | |
| (5,2) 29 | (5,6) 61 | (8,6) 100 |
13) проверяем все возможные ответы первого игрока и выясняем, что он не может выиграть сразу, одним ходом:
| I игрок | II игрок | I игрок | |
| (5,2) 29 | (5,6) 61 | (8,6) 100 | (11,6) 157 |
| (8,9) 145 | |||
| (8,10) 164 |
14) а второй игрок своим следующим ходом всегда выигрывает, увеличивая x на 3:
| I игрок | II игрок | I игрок | II игрок | |
| (5,2) 29 | (5,6) 61 |  (8,6) 100
| (11,6) 157 | (14,6) 232 |
| (8,9) 145 | (11,9) 202 | |||
| (8,10) 164 | (11,10) 221 |
поэтому (8,6) – это выигрышный ход второго игрока в ответ на первый ход (5,6)
15) таким образом, при правильной игре выиграет второй игрок, для этого при любом ходе первого игрока ему достаточно свести ситуацию к положению (8,5) или (8,6); такая возможность у него есть
16) остается только записать ответ в виде таблицы и текстового пояснения, как показано выше
Рекомендации:
· этот способ решения позволяет очень удобно записывать промежуточные результаты на листике, даже не строя громоздкую таблицу
0 I игрок II игрок I игрок II игрок
(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
(5,5) 50 (8,5) 89
(5,5) 50 (8,6) 100 (11,6) 157 (14,6) 232
(8,9) 145 (8,9) 202
(8,10) 164 (8,10) 221
· тем не менее, окончательный ответ для эксперта желательно записать в виде «стандартной» таблицы и (обязательно!) следующего за ней текстового комментария
|
Решение (вариант 3, графический):
1) в задачах на движение фишки можно применить графический метод [1], немного измененный и упрощенный, в сравнении с оригинальным вариантом
2) обозначим начальное положение точки на плоскости белым кружком:
поскольку при каждом ходе координаты увеличиваются, можно рассматривать только первый квадрант плоскости; задача – очередным ходом выйти за границу, обозначенную красной линией
3) нанесем на плоскость точки, куда можно попасть за один ход, и обозначим их черными кружками:
4) дальше отметим все точки, в которые можно «допрыгнуть» за два хода; некоторые из этих точек позволяют следующим ходом «выпрыгнуть» за красную границу (или хотя бы на красную линию, например, в точку (12,5)), такие точки обозначим кружками с двойной границей – это выигрышные позиции
5) теперь отмечаем все новые (неотмеченные) точки, куда можно «допрыгнуть» за один ход из черных точек; все эти позиции выигрышные, то есть, следующим ходом очередной игрок выигрывает
6) ключевой момент: находим на плоскости черные точки, из которых ВСЕ ходы ведут к выигрышным позициям; в данном случае это точки (8,5) и (8,6) – это проигрышные позиции, поскольку ЛЮБОЙ очередной ход приводит в выигрышную позицию; обводим эти точки на рисунке рамкой:
7) теперь отмечаем двойной линией все точки, из которых можно сразу (за 1 ход) перейти (перевести игру) в одну из проигрышных (для соперника) позиций, это точки (5,5), (5,6) и (8,2)
8) все черные точки использованы, и получилось так, что ВСЕ возможные ходы первого игрока в начальной ситуации ведут в выигрышные позиции, то есть начальная позиция (5,2) – проигрышная, ее тоже можно обвести в красную рамку
9) таким образом, при правильной игре выиграет второй игрок, для этого при любом ходе первого игрока ему достаточно свести ситуацию к положению (8,5) или (8,6); такая возможность у него есть
10) теперь для каждого хода первого игрока нужно указать выигрышный ход второго, который переводит игру в проигрышную позицию
| I игрок | II игрок | |
| (5,2) | (8,2) | (8,5) |
| (5,5) | (8,5) | |
| (5,6) | (8,6) |
11) дальше, как и в предыдущих способах решения, обязательно нужно расписать все возможные ответы первого игрока (3-й ход) и выигрышные ходы второго игрока для этих вариантов
| Возможные проблемы: · нужна клетчатая бумага · у вас может не быть циркуля, поэтому строить окружность придется по точкам · легко ошибиться, если есть точки на самой окружности или очень близко к ней · неудобно использовать при большом радиусе окружности (например, 35) · неудобно отмечать точки разными значками, легко запутаться |
Еще пример задания:
Два игрока играют в следующую игру. Перед ними лежат две кучки камней, в первой из которых 3, а во второй – 4 камня. У каждого игрока неограниченно много камней. Игроки ходят по очереди. Ход состоит в том, что игрок или увеличивает в 2 раза число камней в какой-то куче, или увеличивает на 4 число камней в одной из куч. Игрок, после хода которого общее число камней в двух кучах становится не менее 25, проигрывает. Кто выигрывает при безошибочной игре обоих игроков – игрок, делающий первый ход, или игрок, делающий второй ход? Каким должен быть первый ход выигрывающего игрока? Ответ обоснуйте.
Решение:
1) обратите внимание на выделенное слово в условии задачи – тот, кто получил 25 или больше камней в обоих кучках, проигрывает
2) как вынудить противника набрать 25 камней или больше? за 1 ход число камней увеличивается по меньшей мере на 3 (если в первой кучке еще 3 камня) или даже на 4, поэтому требуется своим очередным ходом сделать в двух кучках количество камней 22, 23 или 24 (если первая кучка уже содержит более 3-х камней, то можно и 21!)
3) применим «поиск в глубины», будем рассматривать возможные ходы, начиная с тех, при которых получается бóльшая сумма (чтобы ветка быстрее закончилась)
4) рассмотрим первый ход первого игрока:
| I игрок | |
| (3,4) 7 | (7,4) 11 |
5) теперь рассматриваем первый возможный ответ второго игрока:
| I игрок | II игрок | |
| (3,4) 7 | (7,4) 11 | (14,4) 18 |
6) в этой ситуации у I-го игрока есть выигрышный ход – такой, при котором все ответы II-го приводят к его проигрышу:
| I игрок | II игрок | I игрок | II игрок | |
| (3,4) 7 | (7,4) 11 | (14,4) 18 | (14,8) 22 | (28,8) 36 ´ (18,8) 26 ´ (14,16) 30 ´ (14,12) 26 ´ |
таким образом, эту ветку дерева мы рассмотрели до конца
7) теперь анализируем второй возможный ответ II-ого игрока и все ответы I-ого:
| I игрок | II игрок | I игрок | |
| (3,4) 7 | (7,4) 11 | (14,4) 18 | (14,8) 22 |
| (11,4) 15 | (22,4) 26 ´ (15,4) 19 (11,8) 19 |
8) из таблицы видим, что при ответе (22,4) игрок I проигрывает сразу; однако на два других хода II-й игрок может ответить так, что сам он не проиграет (сумма равна 23), а I-й игрок проиграет следующим ходом:
| I игрок | II игрок | I игрок | II игрок | I игрок | |
| (3,4) 7 | (7,4) 11 | (14,4) 18 | (14,8) 22 | ||
| (11,4) 15 | (22,4) 26 ´ | ||||
| (15,4) 19 | (15,8) 23 | (30,8) 38 ´ (19,8) 27 ´ (15,16) 31 ´ (15,12) 27 ´ | |||
| (11,8) 19 | (11,12) 23 | (11,24) 35 ´ (22,12) 34 ´ (11,16) 27 ´ (15,12) 27 ´ |
9) из приведенной таблицы следует, что при первом ходе I-ого игрока (7,4) выиграет II-й – у него есть ход (11,4), который приводит к выигрышу (остальные возможные ответы можно уже не рассматривать!)
10) итак, I-й игрок не может ходить (7,4), поскольку при этом он проиграет; посмотрим, что будет при первом ходе (6,4): II-й может ответить (12,4), при одном из вариантов I-й проиграет сразу же:
| I игрок | II игрок | I игрок | |
| (3,4) 7 | (6,4) 10 | (12,4) 16 | (24,4) 28 ´ (16,4) 20 (12,8) 20 |
11) на оставшиеся два варианта ответа I-го игрока у II-го есть ход (16,8), который вынуждает I-го проиграть на следующем ходу
| I игрок | II игрок | I игрок | II игрок | I игрок | |
| (3,4) 7 | (6,4) 10 | (12,4) 16 | (24,4) 28 ´ | ||
| (16,4) 20 | (16,8) 24 | (32,8) 40 ´ (20,8) 28 ´ (16,16) 32 ´ (16,12) 26 ´ | |||
| (12,8) 20 |
таким образом, при первом ходе (6,4) также выигрывает II-й игрок
12) у I-го игрока остался еще один возможный первый ход – (3,8), проверим его; если этот ход окажется выигрышным, то в игре победит I-й игрок, если нет – то второй
13) если на (3,8) второй отвечает (3,16), I-й игрок может получить 23 камня в обеих кучах ходом (3,20) и выиграет:
| I игрок | II игрок | I игрок | II игрок | |
| (3,4) 7 | (3,8) 11 | (3,16) 19 | (3,20) 23 | (3,40) 43 ´ (3,24) 27 ´ (7,20) 27 ´ (6,20) 26 ´ |
14) однако, ответ II-ого (3,12) приводит к тому, что при любом ответе I-ого он проигрывает сразу или через один ход:
| I игрок | II игрок | I игрок | II игрок | I игрок | |
| (3,4) 7 | (3,8) 11 | (3,16) 19 | (3,20) 23 | ||
| (3,12) 15 | (3,24) 27 ´ | ||||
| (3,16) 19 | (6,16) 22 | (6,32) 38 ´ (6,20) 26 ´ (12,16) 28 ´ (10,16) 26 ´ | |||
| (6,12) 18 | (12,12) 24 | (12,24) 36 ´ (12,16) 28 ´ (24,12) 36 ´ (16,12) 28 ´ | |||
| (7,12) 19 | (11,12) 23 | (11,24) 35 ´ (11,16) 27 ´ (22,12) 34 ´ (15,12) 27 ´ |
15) таким образом, выигрывает II-й игрок; своим первым ходом ему нужно свести игру к позиции (11,4), (12,4) или (3,12), а вторым ходом – к одной из позиций (15,8), (16,8), (11,12), (12,12) или (6,16).
16) итоговая таблица, в которой указаны выигрышные ходы II-го игрока и все возможные ответы I-го игрока:
| I игрок | II игрок | I игрок | II игрок | I игрок | |
| (3,4) 7 | (3,8) 11 | (3,12) 15 | (3,24) 27 ´ | ||
| (3,16) 19 | (6,16) 22 | (6,32) 38 ´ (6,20) 26 ´ (12,16) 28 ´ (10,16) 26 ´ | |||
| (6,12) 18 | (12,12) 24 | (12,24) 36 ´ (12,16) 28 ´ (24,12) 36 ´ (16,12) 28 ´ | |||
| (7,12) 19 | (11,12) 23 | (11,24) 35 ´ (11,16) 27 ´ (22,12) 34 ´ (15,12) 27 ´ | |||
| (7,4) 11 | (11,4) 15 | (22,4) 26 ´ | |||
| (15,4) 19 | (15,8) 23 | (30,8) 38 ´ (19,8) 27 ´ (15,16) 31 ´ (15,12) 27 ´ | |||
| (11,8) 19 | (11,12) 23 | (11,24) 35 ´ (22,12) 34 ´ (11,16) 27 ´ (15,12) 27 ´ | |||
| (6,4) 10 | (12,4) 16 | (24,4) 28 ´ | |||
| (16,4) 20 | (16,8) 24 | (32,8) 40 ´ (20,8) 28 ´ (16,16) 32 ´ (16,12) 28 ´ | |||
| (12,8) 20 |
Еще пример задания:
Два игрока, Петя и Ваня, играют в следующую игру. Перед ними лежат две кучки камней, в первой из которых 3, а во второй – 4 камня. У каждого игрока неограниченно много камней. Игроки ходят по очереди. Ход состоит в том, что игрок или увеличивает в 2 раза число камней в какой-то куче, или увеличивает на 3 число камней в одной из куч. Игра завершается, когда количество камней в одной из куч становится не менее 15. Если в момент завершения игры общее число камней в двух кучах не менее 26, то выиграл Петя, в противном случае – Ваня. Кто выигрывает при безошибочной игре обоих игроков – Петя или Ваня? Каким должен быть первый ход выигрывающего игрока? Ответ обоснуйте.
Решение:
1) обратите внимание на то, что в этой задаче игра останавливается по одному критерию (15 камней в одной из куч), а выигравший игрок определяется по другому (количество камней в обоих кучах)
2) из п. 1 следует, что тот, кто закончил игру, может как выиграть, так и проиграть; в остальном отличий от предыдущих задач нет, принцип решения тот же
3) рассмотрим первый ход первого игрока и возможные ответы второго игрока:
| I игрок | II игрок | |
| (3,4) 7 | (6,4) 10 | (9,4) 13 (6,7) 13 (12,4) 16 (6,8) 14 |
4) игра еще не закончилась, потому что ни в одной куче нет 15 камней;
5) если второй игрок походил (12,4), то своим следующим ходом (24,4) первый игрок может закончить игру и выиграть (поскольку сумма будет равна 28 ≥ 26):
| I игрок | II игрок | I игрок | |
| (3,4) 7 | (6,4) 10 | (12,4) 16 | (24,4) 28 |
| (9,4) 13 (6,7) 13 (6,8) 14 |
здесь и далее финальные позиции, в которых выигрывает первый, будем обозначать синим фоном, а позиции, в которых выигрывает второй – красным фоном
6) проверяем следующий вариант ответа второго, (9,4):
| I игрок | II игрок | I игрок | |
| (3,4) 7 | (6,4) 10 | (12,4) 16 | (24,4) 28 |
| (9,4) 13 | (18,4) 22 | ||
| (9,8) 17 | |||
| (12,4) 16 | |||
| (9,7) 16 | |||
| (6,7) 13 (6,8) 14 |
7) первый может закончить игру ходом (18,4), то это ему не выгодно, потому что сумма 22 меньше 26 и он, согласно правилам игры, проиграет!
8) в остальных случаях игра продолжается, причем у второго всегда находится выигрышный ход:
| I игрок | II игрок | I игрок | II игрок | |
| (3,4) 7 | (6,4) 10 | (12,4) 16 | (24,4) 28 | |
| (9,4) 13 | (18,4) 22 | |||
| (9,8) 17 | (9,16) 23 | |||
| (9,7) 16 | (18,7) 25 | |||
| (12,4) 16 | (15,4) 19 | |||
| (6,7) 13 (6,8) 14 |
9) таким образом, если первый игрок сначала походит (6,4), то второй всегда выиграет так:
| I игрок | II игрок | I игрок | II игрок | |
| (3,4) 7 | (6,4) 10 | (9,4) 13 | (18,4) 22 | |
| (9,8) 17 | (9,16) 23 | |||
| (9,7) 16 | (18,7) 25 | |||
| (12,4) 16 | (15,4) 19 |
10) рассматриваем второй возможный ход первого игрока и возможные ответы второго:
| I игрок | II игрок | |
| (3,4) 7 | (3,7) 10 | (6,7) 13 (3,10) 13 (3,14) 17 |
11) при ответе (3,14) первый может сразу закончить игру и выиграть:
| I игрок | II игрок | I игрок | |
| (3,4) 7 | (3,7) 10 | (3,14) 17 | (3,28) 31 |
| (6,7) 13 (3,10) 13 |
12) проверяем возможные ответы на ход (6,7):
| I игрок | II игрок | I игрок | |
| (3,4) 7 | (3,7) 10 | (3,14) 17 | (3,28) 31 |
| (6,7) 13 | (9,7) 16 | ||
| (6,10) 16 | |||
| (12,7) 19 | |||
| (6,14) 20 | |||
| (3,10) 13 |
13) при ходе (9,7) второй может завершить игру ходом (18,7) в свою пользу (сумма = 25); при остальных ответах второй не заканчивает игру, а у первого появляется возможность выиграть:
| I игрок | II игрок | I игрок | II игрок | I игрок | |
| (3,4) 7 | (3,7) 10 | (3,14) 17 | (3,28) 31 | ||
| (6,7) 13 | (9,7) 16 | (18,7) 25 | |||
| (9,14) 23 | (9,28) 37 | ||||
| (12,7) 19 | (24,7) 31 | ||||
| (9,10) 19 | (9,20) 29 | ||||
| (6,10) 16 | |||||
| (12,7) 19 | |||||
| (6,14) 20 | |||||
| (3,10) 13 |
14) проверяем ход первого (6,10); при ответе второго (6,20) он заканчивает игру, но первый выигрывает (сумма 26); при остальных ответах первый выигрывает на следующем ходу, завершая игру с суммой более 26:
| I игрок | II игрок | I игрок | II игрок | I игрок | |
| (3,4) 7 | (3,7) 10 | (3,14) 17 | (3,28) 31 | ||
| (6,7) 13 | (9,7) 16 | (18,7) 25 | |||
| (9,14) 23 | (9,28) 37 | ||||
| (12,7) 19 | (24,7) 31 | ||||
| (9,10) 19 | (9,20) 29 | ||||
| (6,10) 16 | (6,20) 26 | ||||
| (12,10) 22 | (24,10) 34 | ||||
| (6,13) 19 | (6,26) 32 | ||||
| (9,10) 19 | (9,20) 29 | ||||
| (12,7) 19 | |||||
| (6,14) 20 | |||||
| (3,10) 13 |
15) таким образом, при ответе второго (6,7) при правильной игре всегда выигрывает первый – ему нужно походить (6,10):
| I игрок | II игрок | I игрок | II игрок | I игрок | |
| (3,4) 7 | (3,7) 10 | (3,14) 17 | (3,28) 31 | ||
| (6,7) 13 | (6,10) 16 | (6,20) 26 | |||
| (12,10) 22 | (24,10) 34 | ||||
| (6,13) 19 | (6,26) 32 | ||||
| (9,10) 19 | (9,20) 29 | ||||
| (3,10) 13 |
16) остается проверить ответ второго (3,10) – если он тоже приведет к победе первого, то мы сделаем вывод, что своим первым ходом (3,7) первый выигрывает при правильной игре
17) замечаем, что из (3,10) первый игрок может легко получить (6,10), то есть свести игру к предыдущему варианту, в котором он выигрывает
17) таким образом, таким образом, выигрывает I-й игрок (Петя); его первый ход должен быть (3,7), а второй – (3,28) или (6,10); в первом случае он выиграет сразу, во втором – через один ход
18) итоговая таблица, в которой указаны выигрышные ходы I-го игрока (Пети) и все возможные ответы II-го игрока (Вани):
| I игрок | II игрок | I игрок | II игрок | I игрок | |
| (3,4) 7 | (3,7) 10 | (3,14) 17 | (3,28) 31 | ||
| (6,7) 13 или (3,10) 13 | (6,10) 16 | (6,20) 26 | |||
| (12,10) 22 | (24,10) 34 | ||||
| (6,13) 19 | (6,26) 32 | ||||
| (9,10) 19 | (9,20) 29 |
Задачи для тренировки [2]:
1) Два игрока играют в следующую игру. Перед ними лежат две кучки камней, в первой из которых 1, а во второй – 2 камня. У каждого игрока неограниченно много камней. Игроки ходят по очереди. Ход состоит в том, что игрок или увеличивает в 3 раза число камней в какой-то куче, или добавляет 2 камня в какую-то кучу. Выигрывает игрок, после хода которого общее число камней в двух кучах становится не менее 17 камней. Кто выигрывает при безошибочной игре обоих игроков – игрок, делающий первый ход, или игрок, делающий второй ход? Каким должен быть первый ход выигрывающего игрока? Ответ обоснуйте.
2) Два игрока играют в следующую игру. Перед ними лежат две кучки камней, в первой из которых 3, а во второй – 2 камня. У каждого игрока неограниченно много камней. Игроки ходят по очереди. Ход состоит в том, что игрок или увеличивает в 3 раза число камней в какой-то куче, или добавляет 1 камень в какую-то кучу. Выигрывает игрок, после хода которого общее число камней в двух кучах становится не менее 16 камней. Кто выигрывает при безошибочной игре – игрок, делающий первый ход, или игрок, делающий второй ход? Каким должен быть первый ход выигрывающего игрока? Ответ обоснуйте.
3) Два игрока играют в следующую игру. Перед ними лежат две кучки камней, в первой из которых 4, а во второй – 3 камня. У каждого игрока неограниченно много камней. Игроки ходят по очереди. Ход состоит в том, что игрок или увеличивает в 3 раза число камней в какой-то куче или добавляет 2 камня в какую-то кучу. Выигрывает игрок, после хода которого общее число камней в двух кучах становится не менее 24 камней. Кто выигрывает при безошибочной игре обоих игроков – игрок, делающий первый ход или игрок, делающий второй ход? Каким должен быть первый ход выигрывающего игрока? Ответ обоснуйте.
4) Два игрока играют в следующую игру. Перед ними лежат три кучки камней, в первой из которых 2, во второй – 3, в третьей – 4 камня. У каждого игрока неограниченно много камней. Игроки ходят по очереди. Ход состоит в том, что игрок или удваивает число камней в какой-то куче или добавляет по два камня в каждую из куч. Выигрывает игрок, после хода которого либо в одной из куч становится не менее 15 камней, либо общее число камней во всех трех кучах становится не менее 25. Кто выигрывает при безошибочной игре обоих игроков – игрок, делающий первый ход или игрок, делающий второй ход? Каким должен быть первый ход выигрывающего игрока? Ответ обоснуйте.
5) Даны три кучи камней, содержащих соответственно 2,3 и 4 камня. За один ход разрешается или удвоить количество камней в меньшей куче (если их две – то в каждой из них), или добавить по 1 камню в каждую из трех куч. Выигрывает тот игрок, после хода которого во всех трех кучах суммарно становится не менее 23 камней. Игроки ходят по очереди. Выяснить, кто выигрывает при правильной игре – первый или второй игрок.
6) Два игрока играют в следующую игру. Перед ними лежат две кучки камней, в первой из которых 3, а во второй – 4 камня. У каждого игрока неограниченно много камней. Ходят игроки по очереди. Делая очередной ход, игрок или увеличивает в какой-то кучке число камней в 2 раза, или добавляет в какую-то кучку 3 камня. Выигрывает тот игрок, после хода которого общее число камней в двух кучках становится не менее 23. Кто выиграет – игрок, делающий ход первым, или игрок, делающий второй ход?
7) Два игрока играют в следующую игру. Перед ними лежат две кучки камней, в первой из которых 2, во второй – 3 камня. У каждого игрока неограниченное количество камней. Игроки ходят по очереди. Ход состоит в том, что игрок или увеличивает число камней в какой-то куче в 3 раза, или добавляет 3 камня в любую из куч. Выигрывает игрок, после хода которого общее число камней в двух кучах становится не менее 33. Кто выигрывает – игрок, делающий ход первым, или игрок, делающий ход вторым?
8) Даны две горки фишек, содержащих соответственно 2 и 4 фишки. За один ход разрешается или удвоить количество фишек в какой-нибудь горке, или добавить по две фишки в каждую из двух горок. Выигрывает тот игрок, после чьего хода в двух горках суммарно становится не менее 24 фишек. Игроки ходят по очереди. Кто выигрывает – игрок, делающий ход первым, или игрок, делающий ход вторым?
9) Два игрока играют в следующую игру. Перед ними лежат две кучки фишек, в первой из которых 3, а во второй – 5 фишек. У каждого игрока неограниченно много фишек. Ходят игроки по очереди. Делая очередной ход, игрок или увеличивает в какой-то кучке число фишек в 2 раза, или добавляет в какую-то кучку 2 фишки. Выигрывает тот игрок, после хода которого общее число фишек в двух кучках становится не менее 21. Кто выиграет – игрок, делающий ход первым, или игрок, делающий второй ход?
10) Даны три кучи камней, содержащие соответственно 3, 4 и 5 камней. За один ход разрешается или удвоить количество камней в меньшей куче (если таких две – то лишь в одной из них), или добавить 2 камня в большую из куч (если таких две – то лишь в одну из них). Выигрывает тот игрок, после хода которого во всех трех кучах суммарно становится не менее 23 камней. Игроки ходят по очереди. Выяснить, кто выигрывает при правильной игре – первый или второй игрок.
11) Два игрока играют в следующую игру. На координатной плоскости в точке с координатами (0;1) стоит фишка. Игроки ходят по очереди. Ход состоит в том, что игрок перемещает фишку из точки с координатами (x,y) в одну из трех точек: (x+3;y), (x,y+3) или (x,y+4). Выигрывает тот игрок, после хода которого расстояние по прямой от фишки до начала координат (0,0) больше 10 единиц. Кто выигрывает – игрок, делающий ход первым, или игрок, делающий ход вторым?
12) Два игрока играют в следующую игру. На координатной плоскости в точке с координатами
(-2;-1) стоит фишка. Игроки ходят по очереди. Ход состоит в том, что игрок перемещает фишку из точки с координатами (x,y) в одну из трех точек: (x+3;y), (x,y+4) или (x+2,y+2). Выигрывает тот игрок, после хода которого расстояние по прямой от фишки до начала координат (0,0) больше 9 единиц. Кто выигрывает – игрок, делающий ход первым, или игрок, делающий ход вторым?
13) Два игрока играют в следующую игру. На координатной плоскости в точке с координатами
(3;-5) стоит фишка. Игроки ходят по очереди. Ход состоит в том, что игрок перемещает фишку из точки с координатами (x,y) в одну из трех точек: (x+3;y), (x,y+4) или (x,y+5). Выигрывает тот игрок, после хода которого расстояние по прямой от фишки до начала координат (0,0) не меньше 10 единиц. Кто выигрывает – игрок, делающий ход первым, или игрок, делающий ход вторым?
14) Два игрока играют в следующую игру. На координатной плоскости в точке с координатами
(-3;2) стоит фишка. Игроки ходят по очереди. Ход состоит в том, что игрок перемещает фишку из точки с координатами (x,y) в одну из трех точек: (x+5;y), (x,y+4) или (x+3,y+3). Выигрывает тот игрок, после хода которого расстояние по прямой от фишки до начала координат (0,0) больше 12 единиц. Кто выигрывает – игрок, делающий ход первым, или игрок, делающий ход вторым?
15) Два игрока играют в следующую игру. На координатной плоскости в точке с координатами
(0;-4) стоит фишка. Игроки ходят по очереди. Ход состоит в том, что игрок перемещает фишку из точки с координатами (x,y) в одну из трех точек: (x+4;y), (x,y+4) или (x+4,y+4). Выигрывает тот игрок, после хода которого расстояние по прямой от фишки до начала координат (0,0) больше 12 единиц. Кто выигрывает – игрок, делающий ход первым, или игрок, делающий ход вторым?
16) Два игрока играют в следующую игру. На координатной плоскости в точке с координатами
(2;3) стоит фишка. Игроки ходят по очереди. Ход состоит в том, что игрок перемещает фишку из точки с координатами (x,y) в одну из трех точек: (2x;y), (x,2y) или (x,y+2). Выигрывает тот игрок, после хода которого расстояние по прямой от фишки до начала координат (0,0) больше 13 единиц. Кто выигрывает – игрок, делающий ход первым, или игрок, делающий ход вторым?
17) Два игрока играют в следующую игру. Перед ними лежат две кучки камней, в первой из которых 1, а во второй – 2 камня. У каждого игрока неограниченно много камней. Игроки ходят по очереди. Ход состоит в том, что игрок или увеличивает в 3 раза число камней в какой-то куче, или добавляет 3 камня в какую-то кучу. Выигрывает игрок, после хода которого в одной из куч становится не менее 24 камней. Кто выигрывает при безошибочной игре обоих игроков – игрок, делающий первый ход, или игрок, делающий второй ход? Каким должен быть первый ход выигрывающего игрока? Ответ обоснуйте.
18) Два игрока играют в следующую игру. Перед ними лежат две кучки камней, в первой из которых 5, а во второй – 3 камня. У каждого игрока неограниченно много камней. Игроки ходят по очереди. Ход состоит в том, что игрок или увеличивает в 2 раза число камней в какой-то куче, или добавляет 4 камня в какую-то кучу. Выигрывает игрок, после хода которого в одной из куч становится не менее 22 камней. Кто выигрывает при безошибочной игре обоих игроков – игрок, делающий первый ход, или игрок, делающий второй ход? Каким должен быть первый ход выигрывающего игрока? Ответ обоснуйте.
19) Два игрока играют в следующую игру. На координатной плоскости в точке с координатами (1;0) стоит фишка. Игроки ходят по очереди. Ход состоит в том, что игрок перемещает фишку из точки с координатами (x,y) в одну из трех точек: (x+3;y), (x,y+3) или (x,y+4). Выигрывает тот игрок, после хода которого расстояние по прямой от фишки до начала координат (0,0) больше 13 единиц. Кто выигрывает – игрок, делающий ход первым, или игрок, делающий ход вторым?
20) Два игрока играют в следующую игру. На координатной плоскости в точке с координатами (1;2) стоит фишка. Игроки ходят по очереди. Ход состоит в том, что игрок перемещает фишку из точки с координатами (x,y) в одну из трех точек: (x+3;y), (x,y+3) или (x,y+4). Выигрывает тот игрок, после хода которого расстояние по прямой от фишки до начала координат (0,0) больше 13 единиц. Кто выигрывает – игрок, делающий ход первым, или игрок, делающий ход вторым?
21) Два игрока играют в следующую игру. На координатной плоскости в точке с координатами (1;0) стоит фишка. Игроки ходят по очереди. Ход состоит в том, что игрок перемещает фишку из точки с координатами (x,y) в одну из трех точек: (x+4;y), (x,y+4) или (x+4,y+4). Выигрывает тот игрок, после хода которого расстояние по прямой от фишки до начала координат (0,0) больше 13 единиц. Кто выигрывает – игрок, делающий ход первым, или игрок, делающий ход вторым?
22) Два игрока играют в следующую игру. На координатной плоскости в точке с координатами
(-3;2) стоит фишка. Игроки ходят по очереди. Ход состоит в том, что игрок перемещает фишку из точки с координатами (x,y) в одну из трех точек: (x–1;y+3), (x+3,y–1) или (x+2,y+2). Выигрывает тот игрок, после хода которого расстояние по прямой от фишки до начала координат (0,0) больше 8 единиц. Кто выигрывает – игрок, делающий ход первым, или игрок, делающий ход вторым?
23) Два игрока играют в следующую игру. На координатной плоскости в точке с координатами
(-1;2) стоит фишка. Игроки ходят по очереди. Ход состоит в том, что игрок перемещает фишку из точки с координатами (x,y) в одну из трех точек: (x–1;y+4), (x+3,y–1) или (x+2,y+3). Выигрывает тот игрок, после хода которого расстояние по прямой от фишки до начала координат (0,0) больше 11 единиц. Кто выигрывает – игрок, делающий ход первым, или игрок, делающий ход вторым?
24) Два игрока играют в следующую игру. Перед ними лежат две кучки камней, в первой из которых 3, а во второй – 6 камней. У каждого игрока неограниченно много камней. Игроки ходят по очереди. Ход состоит в том, что игрок или увеличивает в 2 раза число камней в какой-то куче, или добавляет 2 камня в какую-то кучу. Выигрывает игрок, после хода которого общее число камней в двух кучах становится не менее 24. Кто выигрывает при безошибочной игре обоих игроков – игрок, делающий первый ход, или игрок, делающий второй ход? Каким должен быть первый ход выигрывающего игрока? Ответ обоснуйте.
25) Два игрока играют в следующую игру. Перед ними лежат две кучки камней, в первой из которых 1, а во второй – 4 камня. У каждого игрока неограниченно много камней. Игроки ходят по очереди. Ход состоит в том, что игрок или увеличивает в 3 раза число камней в какой-то куче, или добавляет 3 камня в какую-то кучу. Выигрывает игрок, после хода которого общее число камней в двух кучах становится не менее 22. Кто выигрывает при безошибочной игре обоих игроков – игрок, делающий первый ход, или игрок, делающий второй ход? Каким должен быть первый ход выигрывающего игрока? Ответ обоснуйте.
26) Два игрока играют в следующую игру. Перед ними лежат две кучки камней, в первой из которых 6, а во второй – 5 камней. У каждого игрока неограниченно много камней. Игроки ходят по очереди. Ход состоит в том, что игрок увеличивает в 2 раза или в 3 раза число камней в какой-то куче. Выигрывает игрок, после хода которого общее число камней в двух кучах становится не менее 48. Кто выигрывает при безошибочной игре обоих игроков – игрок, делающий первый ход, или игрок, делающий второй ход? Каким должен быть первый ход выигрывающего игрока? Ответ обоснуйте.
27) Два игрока играют в следующую игру. Перед ними лежат две кучки камней, в первой из которых 2, а во второй – 3 камня. У каждого игрока неограниченно много камней. Игроки ходят по очереди. Ход состоит в том, что игрок увеличивает в 2 раза или в 3 раза число камней в какой-то куче. Выигрывает игрок, после хода которого в одной из куч становится не менее 20 камней. Кто выигрывает при безошибочной игре обоих игроков – игрок, делающий первый ход, или игрок, делающий второй ход? Каким должен быть первый ход выигрывающего игрока? Ответ обоснуйте.
28) Два игрока играют в следующую игру. Перед ними лежат две кучки камней, в первой из которых 1, а во второй – 2 камня. У каждого игрока неограниченно много камней. Игроки ходят по очереди. Ход состоит в том, что игрок или увеличивает в 3 раза число камней в какой-то куче, или добавляет 4 камня в какую-то кучу. Выигрывает игрок, после хода которого в одной из куч становится не менее 20 камней. Кто выигрывает при безошибочной игре обоих игроков – игрок, делающий первый ход, или игрок, делающий второй ход? Каким должен быть первый ход выигрывающего игрока? Ответ обоснуйте.
29) Два игрока играют в следующую игру. Перед ними лежат две кучки камней, в первой из которых 2, а во второй – 3 камня. У каждого игрока неограниченно много камней. Игроки ходят по очереди. Ход состоит в том, что игрок или увеличивает в 2 раза число камней в какой-то куче, или увеличивает на 3 число камней в одной из куч. Выигрывает игрок, после хода которого общее число камней в двух кучах становится не менее 17. Кто выигрывает при безошибочной игре обоих игроков – игрок, делающий первый ход, или игрок, делающий второй ход? Каким должен быть первый ход выигрывающего игрока? Ответ обоснуйте.
30) Два игрока играют в следующую игру. На координатной плоскости в точке с координатами
(3;2) стоит фишка. Игроки ходят по очереди. Ход состоит в том, что игрок перемещает фишку из точки с координатами (x,y) в одну из трех точек: (x+3;y), (x,y+2) или (x,y+4). Выигрывает тот игрок, после хода которого расстояние по прямой от фишки до начала координат (0,0) больше 12 единиц. Кто выигрывает – игрок, делающий ход первым, или игрок, делающий ход вторым?
31) Два игрока играют в следующую игру. На координатной плоскости в точке с координатами
(2;3) стоит фишка. Игроки ходят по очереди. Ход состоит в том, что игрок перемещает фишку из точки с координатами (x,y) в одну из трех точек: (2x;y), (x,y+3) или (x,y+4). Выигрывает тот игрок, после хода которого расстояние по прямой от фишки до начала координат (0,0) больше 14 единиц. Кто выигрывает – игрок, делающий ход первым, или игрок, делающий ход вторым?
32) Два игрока играют в следующую игру. На координатной плоскости в точке с координатами
(3;3) стоит фишка. Игроки ходят по очереди. Ход состоит в том, что игрок перемещает фишку из точки с координатами (x,y) в одну из трех
