Решение (через таблицу, А.Н. Носкин)

1) По сути, это та же самая задача с двумя камнями, в которой буквы Ю – это первая куча камней, а буквы Я – вторая. Поэтому данную задачу удобно решать с помощью таблицы, в которой строки примем за количество букв Ю, а столбцы – за букву Я.

2) Анализируя количество букв в условии задачи видим, что наименьшее количество букв – Ю (5 штук). Добавить букву заменим на команду +1, а удвоить на команду *2.

3) Составим таблицу, в которой строки начинаются с числа 5, а столбцы заканчиваются числом 30. Данное число получается из условия достижения победы: (65-5)/2=30.

(Ю,Я)	27	28	29	30
5
6
7
8
9
10
11

Закрасим ячейки, из которых игрок, делающий ход одерживает победу, например:

30*2 + 5 = 65

29*2 + 7 = 65

28*2 + 9 = 65

4) Задание 1. Рассмотрим все возможные ходы из позиции (6, 29), красная точка.

(Ю,Я)	27	28	29	30
5
6
7
8
9
10
11

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

Аналогично рассматриваем все ходы из позиции (8, 28):

(Ю,Я)	27	28	29	30
5
6
7
8
9
10
11

Эта позиция тоже проигрышная, по рассуждениям приведенных выше для позиции (6,29).

Задание 1. В каждой из начальных позиций (6, 29), (8, 28)  выигрышную стратегию имеет Ваня. При любом ходе Пети ему нужно удвоить количество букв Б. Во всех случаях он выигрывает своим первым ходом, так как в результате его хода получается слово длиной не менее 65 символов.

5) Задание 2. В каждой из начальных позиций (6, 28), (7, 28), (8, 27) выигрышную стратегию имеет Петя. Своим первым ходом ему нужно перевести игру в позицию (6, 29) в первом случае или (8, 28) во втором и третьем случаях. Выше было доказано, что это позиции проигрышные для Вани. Таким ходом Петя «загоняет» Ваню в ячейку из которой он не сможет выиграть, но своим ходом создаст условие (попадет в закрашенную область) из которой Петя достигает победу.

(Ю,Я)	27	28	29	30
5
6
7
8
9
10
11

6) Задание 3. Рассмотрим позицию (5, 28).

(Ю,Я)	27	28	29	30
5
6
7
8
9
10
11

 

Если из этой позиции Петя (красный круг) добавит любую букву (ход +1), то Ваня (зеленый круг) переведет игру в позицию (6,29), из которой у Пети нет выигрышной стратегии – см. результат выполнения задания 1, поэтому это выигрышная позиция для Вани.

Если из этой позиции Петя (красный круг) удвоит любую букву (ход *2), то попадает в закрашенную область и победу одержит Ваня первым ходом.

(Ю,Я)	27	28	29	30
5
6
7
8
9
10
11

7) Остается нарисовать неполное дерево игры. Для выигрывающего игрока на каждом ходу выбираем только один вариант, который ведёт к выигрышу, а для проигрывающего (Пети) рассматриваем все возможные ходы, чтобы доказать, что ему не уйти от проигрыша (см. выше).

Ещё пример задания:

P-06. Два игрока,Петя и Ваня по очереди стирают буквы из слова или фразы. Первым ходит Петя. За один ход разрешается стереть или ровно одну букву, или все одинаковые буквы. Выигрывает тот, кто сотрёт последнюю букву.   

Задание 1. Укажите все слова из списка ниже, начиная с которых выигрывает Петя.   

ДА, АГА, СТО, МАМА, СССР, ОГОГО, ТАРТАР, ТОРТ, РОКОКО, РЕННЕР, АВАТАР, КАРАКУРТ, КАСКАД, АНАТАНА, НЯННЯН, НАГАН.   

Задание 2. Укажите все слова из представленных, начиная с которых Ваня не может гарантированно выиграть своим первым ходом, но может выиграть либо своим первым или вторым ходом, в зависимости от хода Пети. Для всех выбранных слов укажите его выигрышную стратегию.   

Задание 3. Дана фраза: ИНФОРМАТИКА ЭТО НАУКА. Кто выиграет в этой игре, и какой будет выигрышная стратегия этого игрока?

1) Разберём задачу в общем виде. Когда в слове (фразе) не осталось ни одной буквы, по условию эта позиция – проигрышная. Тогда позиция, в которой осталась одна буква или только одинаковые буквы – выигрышная.

2) Сначала для простоты предположим, что все буквы в заданной фразе разные. Если их чётное число, то их можно разбить на две группы равного размера. Например, для слова КУРА можно использовать такую разбивку: КУ-РА. Теперь, когда Петя вычеркивает какую-то букву (например, У), Ване нужно вычеркнуть одну букву в другой половине (например, А) для того, чтобы восстановить симметрию. Таким образом, на каком-то шаге Ваня получит пустую строку и выиграет. Поэтому

Любая симметричная позиция – проигрышная (выигрышная для соперника).

3) Если начальная позиция несимметричная, Петя может своим первым ходом сделать её симметричной и Ваня оказывается в проигрышной позиции. Выигрышная стратегия Пети состоит в том, чтобы на каждом шаге восстанавливать симметрию.

Любая позиция, из которой можно одним ходом получить симметричную позицию – выигрышная.

В общем случае при правильной игре выиграет тот, кто первым построит симметричную позицию.

4) Если в слове есть парные буквы, ситуация несколько осложняется. Одинаковые буквы нужно при разбиении располагать в одной и той же половине. Например, слово КАА представляет собой несимметричную (выигрышную) позицию, так как, убрав одну букву А, получаем симметричную позицию К-А. Слово МАМА – это симметричная (проигрышная) позиция ММ-АА, поэтому при правильной игре выиграет Ваня.

5) Рассмотрим ещё один вариант, когда одна буква встречается 3 раза, а вторая – один, например, АААБ. Если Петя стёр все буквы А или одну букву Б, Ваня стирает все оставшиеся буквы и сразу выигрывает. Если Петя стёр одну букву А, Ваня должен стереть ещё одну букву А и получает симметричную (проигрышную для Пети) позицию А-Б. Поэтому позиция АААБ – проигрышная. Будем также называть её симметричной.

6) Рассмотрим ещё один вариант, когда одна буква встречается 4 раза, а вторая – два, например, ААААББ. Если Петя стёр все буквы одной группы (все А или все Б), Ваня стирает все буквы второй группы и сразу выигрывает. Если Петя стёр одну букву А, Ваня должен стереть ещё одну букву А и получает симметричную (проигрышную для Пети) позицию АА-ББ.
Если Петя стер одну букву Б, Ваня стирает одну букву А, получая позицию АААБ, в которой он выиграет в любом случае (см. предыдущий пункт). Поэтому позиция ААААББ – проигрышная. Будем также называть её симметричной.

7) Рассмотрим слова, приведённые в задании.

ДА ® Д-А – симметричная (проигрышная для Пети) позиция, выиграет Ваня своим первым ходом.

АГА – убрав одну букву А, Петя получает (проигрышную для Вани) симметричную позицию А-Г; выиграет Петя своим вторым ходом;

СТО – убрав любую букву, Петя получает симметричную (проигрышную для Вани) позицию и  выиграет своим вторым ходом;

МАМА ® ММ-АА – симметричная проигрышная позиция, выиграет Ваня своим первым или ходом;

СССР ® симметричная (проигрышная для Пети) позиция (см. п. 5), поэтому Петя проиграет, а Ваня выиграет своим первым или вторым ходом;

ОГОГО – убрав одну букву О, Петя получает симметричную позицию ОО-ГГ и выиграет своим вторым ходом или третьим ходом;

 ТАРТАР – убрав любую пару одинаковых букв, Петя получает симметричную позицию (например, ТТ-АА) и выигрывает своим вторым или третьим ходом;

ТОРТ – убрав две буквы Т, Петя получает симметричную позицию О-Р и выигрывает своим вторым ходом;

РОКОКО – убрав две буквы К, Петя получаем проигрышную (для Вани) позицию ООО-Р (см. п. 5) и выигрывает;

РЕННЕР – убрав любую пару одинаковых букв, Петя получает симметричную позицию (например, ЕЕ-НН) и выигрывает своим вторым или третьим ходом;

АВАТАР – все возможные ходы ведут в выигрышные позиции ААВТР, ВТР, ААВР, ААТР или АААВТ (каждую из них можно свести одним ходом к симметричной позиции); это проигрышная позиция, выиграет Ваня;

КАРАКУРТ – убрав любую пару букв, Петя получает симметричную (проигрышную для Вани) позицию (например, УКК-РРТ) и выигрывает своим третьим или четвертым ходом;

КАСКАД – симметричная (проигрышная) позиция СКК-ААД, выиграет Ваня своим вторым или третьим ходом;

АНАТАНА – убрав одну букву Т, Петя получает симметричную (проигрышную для Вани) позицию ААААНН (см. п. 6) и выигрывает;

НЯННЯН – симметричная (проигрышная для Пети) позиция ННННЯЯ (см. п. 6), выиграет Ваня;

НАГАН – убрав букву Г, Петя получает симметричную (проигрышную для Вани) позицию НН-АА и выигрывает своим вторым или третьим ходом.

8) Таким образом, ответы на первые два вопроса следующие:

1. Петя выигрывает, если игра начинается со слов

АГА, СТО, ОГОГО, ТАРТАР, ТОРТ, РОКОКО, РЕННЕР, КАРАКУРТ, АНАТАНА, НАГАН.

2. Если игра начинается со слов МАМА или СССР, выигрывает Ваня своим первым или вторым ходом в зависимости от ходов Пети; во всех случаях Ваня должен восстанавливать симметрию позиции.

9) Теперь рассмотрим фразу ИНФОРМАТИКА ЭТО НАУКА. Расставим буквы с учётом повторений: (АААА ИИ) (КК НН ОО ТТ) (МРУФЭ). В первой скобке позиция симметричная (см. п. 6), во второй – тоже симметричная, а в третьей – несимметричная. Поэтому вся позиция несимметричная, то есть выигрышная. Убрав любую одиночную букву из последней скобки Петя может свести игру к симметричной (проигрышной для Вани) позиции.

10) Таким образом,

3. Если игра начинается с фразы ИНФОРМАТИКА ЭТО НАУКА, выигрывает Петя. Сначала ему нужно стереть одну из букв, которая встречается только один раз, а затем своими ходами поддерживать симметрию позиции.

Ещё пример задания:

P-05. Два игрока, Петя и Ваня, играют в следующую игру. Перед игроками лежит куча камней. Игроки ходят по очереди, первый ход делает Петя. За один ход игрок может

а) добавить в кучу один камень или

б) увеличить количество камней в куче в два раза.

Игра завершается в тот момент, когда количество камней в куче становится не менее 24. Если при этом в куче оказалось не более 38 камней, то победителем считается игрок, сделавший последний ход. В противном случае победителем становится его противник. Например, если в куче был 21 камень и Петя удвоит количество камней в куче, то игра закончится и победителем будет Ваня. В начальный момент в куче было S камней, 1 <S£ 23.

Задание 1. а) При каких значениях числа S Петя может выиграть в один ход? Укажите все такие значения и соответствующие ходы Пети.

б) У кого из игроков есть выигрышная стратегия при S = 22, 21, 20? Опишите выигрышные стратегии для этих случаев.

Задание 2. У кого из игроков есть выигрышная стратегия при S = 11, 10? Опишите соответствующие выигрышные стратегии.

Задание 3. У кого из игроков есть выигрышная стратегия при S = 9? Постройте дерево всех партий, возможных при этой выигрышной стратегии (в виде рисунка или таблицы). На рёбрах дерева указывайте, кто делает ход; в узлах – количество камней в позиции.

Решение:

1) Задание 1а. Сложность состоит в том, что Петя проиграет, если в результате его хода количество камней станет больше, чем 38. Он может сделать ход «+1» или «*2». Ходом «+1» он сможет получить 24 камня в куче (и таким образом выиграет!) из позиции S = 23.

Теперь проверим ход «*2». Для выигрыша Пети количество камней в результате этого хода должно стать от 24 до 38, поэтому Петя выиграет этим ходом при S от 12 до 19.

2) Задание 1б. При S = 22 возможные ходы дают кучи в 23 и 44 камня. В первом случае (S = 23) противник оказывается в выигрышной позиции (см. предыдущий пункт), во втором случае тот, кто ходит, проигрывает, потому что 44 > 38. Поэтому позиция S = 22 – проигрышная, Петя проиграет, у Вани есть выигрышная стратегия: в случае S = 23 сделать ход «+1».

При S = 21 Петя может перевести игру в позицию S = 22, она, как мы только что показали, проигрышная для Вани. Поэтому у Пети есть выигрышная стратегия.

При S = 20 ходом «+1» Петя переведет игру в выигрышную (для Вани) позицию, а при ходе «*3» он сразу проиграет, получив 40 > 38 камней. Поэтому выигрышная стратегия есть у Вани.

3) Задание 2. При S = 11 или S = 10 Петя может ходом «*2» перевести игру в позиции S = 22 и S = 20, обе они, как мы показали в предыдущем пункте, проигрышные. Поэтому выигрышную стратегию имеет Петя.

4) Задание 3. При S = 9 возможно 2 хода: ход «+1» приводит к позиции S = 10, она выигрышная (см. предыдущий пункт); ход «*2» приводит к позиции S = 18, она тоже выигрышная (см. первый пункт). Таким образом, все возможные ходы ведут в выигрышные для соперника позиции, и позиция S = 9 – проигрышная (для Пети). Выигрышную стратегию имеет Ваня. При построении дерева для проигрывающего (Пети) указываем все возможные ходы, а для выигрывающего (Вани) – только один выигрышный ход. Дерево можно нарисовать так:

или записать в виде таблицы

	Петя	Ваня	Петя	Ваня	Петя	Ваня
9	9*2=18	18*2=36
	9+1=10	10*2=20	20*2=40
			20+1=21	21+1=22	22+1=23	23+1=24
					22*2=44

Ещё пример задания:

Р-04.   Два игрока, Петя и Ваня, играют в следующую игру. Перед игроками лежат две кучи камней. Игроки ходят по очереди, первый ход делает Петя. За один ход игрок может добавить в одну из куч (по своему выбору) один камень или увеличить количество камней в куче в два раза. Например, пусть в одной куче 10 камней, а в другой 7 камней; такую позицию в игре будем обозначать (10, 7). Тогда за один ход можно получить любую из четырёх позиций: (11, 7), (20, 7), (10, 8), (10, 14). Для того чтобы делать ходы, у каждого игрока есть неограниченное количество камней.

Игра завершается в тот момент, когда суммарное количество камней в кучах становится не менее 73. Победителем считается игрок, сделавший последний ход, т.е. первым получивший такую позицию, что в кучах всего будет 73 камня или больше.

Будем говорить, что игрок имеет выигрышную стратегию, если он может выиграть при любых ходах противника. Описать стратегию игрока – значит описать, какой ход он должен сделать в любой ситуации, которая ему может встретиться при различной игре противника. Например, при начальных позициях (6, 34), (7, 33), (9, 32) выигрышная стратегия есть у Пети. Чтобы выиграть, ему достаточно удвоить количество камней во второй куче.

Задание 1

Для каждой из начальных позиций (6, 33), (8, 32) укажите, кто из игроков имеет выигрышную стратегию. В каждом случае опишите выигрышную стратегию; объясните, почему эта стратегия ведёт к выигрышу, и укажите, какое наибольшее количество ходов может потребоваться победителю для выигрыша при этой стратегии.

Задание 2

Для каждой из начальных позиций (6, 32), (7, 32), (8, 31) укажите, кто из игроков имеет выигрышную стратегию. В каждом случае опишите выигрышную стратегию; объясните, почему эта стратегия ведёт к выигрышу, и укажите, какое наибольшее количество ходов может потребоваться победителю для выигрыша при этой стратегии.

Задание 3

Для начальной позиции (7, 31) укажите, кто из игроков имеет выигрышную стратегию. Опишите выигрышную стратегию; объясните, почему эта стратегия ведёт к выигрышу, и укажите, какое наибольшее количество ходов может потребоваться победителю для выигрыша при этой стратегии. Постройте дерево всех партий, возможных при указанной Вами выигрышной стратегии. Представьте дерево в виде рисунка или таблицы.

Решение:

5) Задание 1. Из всех заданных начальных позиций минимальное количество камней в первой куче – 6. Если во второй куче было S камней, то после первого хода Пети количество камней в двух кучах может стать равным

7+S(после добавления 1 камня в любую кучу)

12+S(после удвоения первой кучи)

6+2S(после удвоения второй кучи)

Выписываем условия выигрыша на первом ходу для всех трёх вариантов

  7 + S ³ 73  Þ   S ³ 66

  12 + S ³ 73 Þ   S ³ 61

  6 + 2S ³ 73 Þ   S ³ 34

Отсюда следует, что при S ³ 34 Петя выиграет первым же ходом, удвоив число камней во второй куче.

6) Составим таблицу выигрышных и проигрышных позиций. По вертикали будем откладывать количество камней в первой куче, а по горизонтали – во второй (там больше!). Зеленым фоном отметим выигрышные позиции:

	31	32	33	34	35	36
6

7) аналогично для 7 камней в первой куче цепочка выигрышных позиций начинается с (7,33):

  7 + 2S ³ 73 Þ   S ³ 33

	31	32	33	34	35	36
6
7

для 8 камней – тоже с 33, а для 9 – с 32:

	31	32	33	34	35	36
6
7
8
9

8) Теперь рассмотрим «угловые» клетки: (6,33) и (8,32)

9) Все возможные ходы из (6,33) ведут в выигрышные позиции (выделены зеленым фоном):

(7,33) (6,34) (14,33) и (6,66)

Поэтому позиция (6,33) – проигрышная.

10) Все возможные ходы из (8,32) ведут в выигрышные позиции (выделены зеленым фоном):

(9,32) (8,33) (18,32) и (8,64)

Поэтому позиция (8,32) – проигрышная.

Получается такая таблица:

	31	32	33	34	35	36
6
7
8
9

11) Таким образом, ответ на задание 1: в позициях (6,33) и (8,32) Петя (ходящий первым) проигрывает, а Ваня (второй) имеет выигрышную стратегию: при любом первом ходе Пети удвоить количество камней во второй куче. Обоснование приведено в пп. 5 и 6 выше.

12) Задание 2. В каждой из начальных позиций (6, 32), (7, 32), (8, 31) есть ход в проигрышную позицию:

(6,32) ® (6,33)          (7,32) ® (8,32)          (8,31) ® (8,32)

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

Получается такая таблица:

	31	32	33	34	35	36
6
7
8
9

13) Задание 3. В позиции (7,31) существует 4 возможных хода:

(8,31) (7,32) (14,31) (7,62) 

все эти позиции – выигрышные, поэтому Петя (первый ходящий) проиграет, а Ваня имеет выигрышную стратегию. Она заключается в том, чтобы своим первым ходом перевести игру в проигрышную (для Пети) позицию (8,32):

(8,31) ® (8,32)           (7,32) ® (8,32)               

или вообще сразу выиграть:

(14,31) ® (14,62)      (7,62) ® (14,62)             

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

То же решение в виде таблицы

Начало	Петя	Ваня	Петя	Ваня
(7,31)	(8,31)	(8,32)	(9,32)	(9,64)
			(8,33)	(8,66)
	(7,32)		(16,32)	(16,64)
			(8,64)
	(14,31)	(14,62)
	(7,62)

Ещё пример задания:

Р-03.   Два игрока, Петя и Ваня, играют в следующую игру. Перед игроками лежат две кучи камней. Игроки ходят по очереди, первый ход делает Петя. За один ход игрок может добавить в одну из куч (по своему выбору) один камень или увеличить количество камней в куче в два раза. Например, пусть в одной куче 10 камней, а в другой 7 камней; такую позицию в игре будем обозначать (10, 7). Тогда за один ход можно получить любую из четырёх позиций: (11, 7), (20, 7), (10, 8), (10, 14). Для того чтобы делать ходы, у каждого игрока есть неограниченное количество камней.

Игра завершается в тот момент, когда суммарное количество камней в кучах становится не менее 55. Победителем считается игрок, сделавший последний ход, то есть первым получивший такую позицию, что в кучах всего будет 55 или больше камней.

В начальный момент в первой куче было 5 камней, во второй куче – S камней; 1 ≤ S ≤ 49.

Будем говорить, что игрок имеет выигрышную стратегию, если он может выиграть при любых ходах противника. Описать стратегию игрока – значит, описать, какой ход он должен сделать в любой ситуации, которая ему может встретиться при различной игре противника.

Выполните следующие задания. Во всех случаях обосновывайте свой ответ.

Задание 1

а) Укажите все такие значения числа S, при которых Петя может выиграть за один ход, и соответствующие выигрывающие ходы. Если при некотором значении S Петя может выиграть несколькими способами, достаточно указать один выигрывающий ход.

б) Сколько существует значений S, при которых Петя не может выиграть за один ход, но при любом ходе Пети Ваня может выиграть своим первым ходом?

Задание 2

Укажите такое значение S, при котором у Пети есть выигрышная стратегия, причём одновременно выполняются два условия:

− Петя не может выиграть за один ход;

− Петя может выиграть своим вторым ходом независимо от того, как будет ходить Ваня.

Для указанного значения S опишите выигрышную стратегию Пети.

Задание 3

Укажите значение S, при котором одновременно выполняются два условия:

− у Вани есть выигрышная стратегия, позволяющая ему выиграть первым или вторым ходом при любой игре Пети;

− у Вани нет стратегии, которая позволит ему гарантированно выиграть первым ходом.

Для указанного значения S опишите выигрышную стратегию Вани.

Постройте дерево всех партий, возможных при этой выигрышной стратегии Вани (в виде рисунка или таблицы). На рисунке на рёбрах дерева указывайте, кто делает ход; в узлах – количество камней в позиции.

Решение:

15) Задание 1а. В этом задании начальная позиция – (5, S), и у Пети есть один ход. После этого хода количество камней в двух кучах может стать равным

6+S(после добавления 1 камня в любую кучу)

10+S(после удвоения первой кучи)

5+2S(после удвоения второй кучи)

Выписываем условия выигрыша на первом ходу для всех трёх вариантов

  6 + S ³ 55  Þ   S ³ 49

  10 + S ³ 55 Þ   S ³ 45

  5 + 2S ³ 55 Þ   S ³ 25

Отсюда следует, что при S ³ 25 Петя выиграет первым же ходом, удвоив число камней во второй куче.

Для дальнейшего анализа составим таблицу, где по вертикали будем отмечать количество камней в первой куче, а по горизонтали – во второй:

	...	20	21	22	23	24	25	26	27
5							А

Например, ячейка, отмеченная буквой А, соответствует позиции (5,25). Это выигрышная позиция, все выигрышные позиции отмечены зелёным цветом. Если во второй куче 6 камней (вторая строка), выигрышная позиция определяется условием

  6 + 2S ³ 55 Þ   2S ³ 49                  Þ   S ³ 25 (так же, как и для (5,S)!)

	...	20	21	22	23	24	25	26	27
5
6

Если во второй куче 7 камней (третья строка), получаем

  7 + 2S ³ 55 Þ   2S ³ 48                  Þ   S ³ 24

и так далее:

	...	20	21	22	23	24	25	26	27
5
6
7
8
9
10
11
12
13

Теперь попробуем найти проигрышные позиции –  такие позиции, из которых все ходы ведут в выигрышные позиции (отмеченные зелёным фоном). Ход «+1» смещает позицию в таблице на одну клетку вправо или вниз, а ход «*2» – на соответствующее число клеток вправо или вниз. Очевидно, что все позиции в углах зелёной лесенки – проигрышные. На рисунке показаны все ходы из позиции (6,24), все они ведут в зелёные ячейки:

	...	20	21	22	23	24	25	26	27
5
6
7
8
9
10
11
12
13

Далее: выигрышными (за 2 хода) будут все позиции, из которых есть ход хотя бы в одну проигрышную позицию:

	...	20	21	22	23	24	25	26	27
5				2		2
6			2		2
7		2			2
8	2			2
9				2
10			2
11			2
12		2
13		2

 

16) Задание 1б. Как мы уже знаем, после первого хода Петя может получить количество камней 6+S, 10+S и 5+2S, но выиграть он не должен, то есть

  6 + S < 55  Þ   S < 49

  10 + S < 55 Þ   S < 45

  5 + 2S < 55 Þ   S < 25

Самое сильное условие – S < 25. Теперь ходит Ваня, у него на каждый ход Пети есть 4 варианта ответа. Рассмотрим первый возможный ход Пети и все возможные ответы Вани:

  (6, S) ® (7,S) или (6,S+1) или (12,S) или (6,2S)

На каждый ход Пети у Вани должен быть выигрышный ход. Для хода Пети (6, S) получаем условия

  7 + S ³ 55  Þ   S ³ 48

  12 + S ³ 55 Þ   S ³ 43

  6 + 2S ³ 55 Þ   S ³ 25

 Таким образом, при ходе Пети (6, S) Ваня может гарантированно выиграть только при S ³ 25, но в этом случае Петя и сам может выиграть своим первым ходом! Поэтому значений S, удовлетворяющих условию 1б, нет! Остальные варианты первого хода Пети можно уже не проверять.

Заметим, что позиция (6,24) – проигрышная, потому что выиграть одним ходом из неё нельзя (лучший ход – удвоение второй кучи – дает в сумме 54 камня!), но любой ход из неё ведёт к выигрышной позиции.

Если смотреть на построенную таблицу, в первой строке (для позиций, в которых в первой куче 5 камней) нет чёрной клетки между выигрышем в один ход (позиция (5,25)) и выигрышем в 2 хода (позиция (5,24)). Заметим, что это произошло потому, что в позиции (5,24) возможен «выжидающий» ход в проигрышную позицию (6,24).

17) Задание 2. Поскольку Петя не может выиграть за 1 ход, имеем S < 25. Как мы выяснили в предыдущем пункте, позиция (6,24) – проигрышная. Поэтому ответ на это задание – такое значение S, что у Пети есть ход, который переводит игру в позицию (6,24).

Действительно, начав с позиции (5,24), Петя может перевести игру в проигрышную позицию (6,24), в которой Ваня не может выиграть одним ходом, но всегда создаст Пете выигрышную позицию на втором ходу.

При S = 24 Петя не может выиграть за один ход, но может выиграть за два. Для этого ему нужно добавить 1 камень в первую кучу, получив позицию (6,24), которая является проигрышной. Для любого хода Вани в этой позиции есть выигрышный второй ход Пети  – удвоение второй кучи:

  (6, 24) ® Ваня: (7,24) ®  Петя: (7,48)

  (6, 24) ® Ваня: (6,25) ®  Петя: (6,50)

  (6, 24) ® Ваня: (12,24) ®  Петя: (12,48)

  (6, 24) ® Ваня: (6,48) ®  Петя: (6,96)

Возможен и другой ответ на этот вопрос. Дело в том, что при S = 22 Петя своим первым ходом тоже может получить проигрышную (для Вани) позицию, только другую: (10,22).

При S = 22 Петя не может выиграть за один ход, но может выиграть за два. Для этого ему нужно удвоить число камней в первой куче, получив позицию (10,22), которая является проигрышной. Для любого хода Вани в этой позиции есть выигрышный второй ход Пети  – удвоение второй кучи:

  (10, 22) ® Ваня: (11,22) ®  Петя: (11,44)

  (10, 22) ® Ваня: (10,23) ®  Петя: (10,46)

  (10, 22) ® Ваня: (20,22) ®  Петя: (20,44)

  (10, 22) ® Ваня: (10,44) ®  Петя: (10,88)

18) Задание 3. Нам нужно найти такое значение S, что из начальной позиции (5,S) ЛЮБОЙ ход Пети ведёт в выигрышную (для Вани) позицию. Попробуем первое нерассмотренное значение, S = 23. Возможные ходы Пети:

(6,23), (5,24), (10,23) и (5,46)

В первых двух случаях Ваня своим ходом сведет игру в проигрышную (для Пети) позицию (6,24) и выиграет своим вторым ходом, а в последних двух случаях выиграет на первом же ходу, удвоив число камней во второй куче.

Ещё легче определить нужный ход по таблице. Все клетки в углах новой лесенки – это проигрышные позиции, потому что все ходы из них ведут на зелёные клетки:

	...	20	21	22	23	24	25	26	27
5			2	2	2	2
6		2	2		2
7	2	2		2	2
8	2			2
9			2	2
10			2
11		2	2
12		2
13	2	2

На этом можно остановиться, потому что по условию задачи нас интересуют только позиции с выигрышем в 1 или 2 хода (позиции в остальных клетках требуют для выигрыша больше двух ходов). Смотрим на верхнюю строку: при S=21 и S=23 позиция проигрышная за 2 хода, это и есть два возможных ответа на вопрос 3.

Для S = 23 у Вани есть выигрышная стратегия, позволяющая ему выиграть первым или вторым ходом при любой игре Пети, но у него нет стратегии, которая позволит ему гарантированно выиграть первым ходом. Все возможные ходы Пети и выигрышные ответы Вани приведены в таблице:

Начало	Петя	Ваня	Петя	Ваня
(5,23)	(6,23)	(6,24)	(7,24)	(7,48)
			(6,25)	(6,50)
	(5,24)		(12,24)	(12,48)
			(6,48)	(6,96)
	(10,23)	(10,46)
	(5,46)

Вместо таблицы можно построить аналогичное дерево (конечно, это не совсем дерево, но для упрощения схемы можно объединить две ветки к узлу (6,24), а также две ветки к узлу (10,46)):

Возможен и другой ответ на этот вопрос. При S=21 у Вани тоже есть выигрышная стратегия, он выигрывает на первом или на втором ходу.

Начало	Петя	Ваня	Петя	Ваня
(5,21)	(10,21)	(10,22)	(11,22)	(11,44)
			(10,23)	(10,46)
	(5,22)		(20,22)	(20,44)
			(10,44)	(10,88)
	(6,21)	(12,21)	(13,21)	(13,42)
			(12,22)	(12,44)
			(24,21)	(24,42)
			(12,42)	(12,84)
	(5,42)	(5,84)

Ещё пример задания:

Р-02. Два игрока, Петя и Ваня, играют в следующую игру. Перед игроками лежит куча камней. Игроки ходят по очереди, первый ход делает Петя. За один ход игрок может добавить в кучу один или три камня или увеличить количество камней в куче в два раза. Например, имея кучу из 15 камней, за один ход можно получить кучу из 16, 18 или 30 камней. У каждого игрока, чтобы делать ходы, есть неограниченное количество камней. Игра завершается в тот момент, когда количество камней в куче становится не менее 35. Победителем считается игрок, сделавший последний ход, т.е. первым получивший кучу, в которой будет 35 или больше камней. В начальный момент в куче было S камней; 1 ≤ S ≤ 34.

Будем говорить, что игрок имеет выигрышную стратегию, если он может выиграть при любых ходах противника. Описать стратегию игрока – значит описать, какой ход он должен сделать в любой ситуации, которая ему может встретиться при различной игре противника. Выполните следующие задания. Во всех случаях обосновывайте свой ответ.

Задание 1

а) Укажите все такие значения числа S, при которых Петя может выиграть в один ход. Обоснуйте, что найдены все нужные значения S, и укажите выигрывающие ходы.

б) Укажите такое значение S, при котором Петя не может выиграть за один ход, но при любом ходе Пети Ваня может выиграть своим первым ходом. Опишите выигрышную стратегию Вани.

Задание 2

Укажите два таких значения S, при которых у Пети есть выигрышная стратегия, причём одновременно выполняются два условия:

− Петя не может выиграть за один ход;

− Петя может выиграть своим вторым ходом независимо от того, как будет ходить Ваня.

Для каждого указанного значения S опишите выигрышную стратегию Пети.

Задание 3

Укажите значение S, при котором одновременно выполняются два условия:

− у Вани есть выигрышная стратегия, позволяющая ему выиграть первым или вторым ходом при любой игре Пети;

− у Вани нет стратегии, которая позволит ему гарантированно выиграть первым ходом.

Для указанного значения S опишите выигрышную стратегию Вани.

Постройте дерево всех партий, возможных при этой выигрышной стратегии Вани (в виде рисунка или таблицы). На рисунке на рёбрах дерева указывайте, кто делает ход; в узлах – количество камней в позиции.

Решение (способ 1, таблица):

1) Задание 1а. Последним ходом может быть «+1», «+3» или «*2». Выиграть последним ходом «+1» можно, если S = 34. Ходом «+2» можно выиграть при S=32, S=33 и S=34. Ходом «*2» можно выиграть из любой позиции при S > 17. Можно составить таблицу, в которой «В₁» обозначает выигрыш за один ход:

S	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17	18	19	…	34
																		В1	В1	…	В1

Поэтому ответ должен быть такой:

Задание 1а. Петя может выиграть за один ход при любом S > 17. Он должен увеличить вдвое число камней, при этом в куче всегда получится не менее 36 камней.

2) Задание 1б. Ваня может выиграть в один ход тогда, когда все ходы Пети из текущей позиции ведут в выигрышные позиции. Это будет при S = 17:

Задание 1б. Ваня может гарантированно выиграть своим первым ходом при S = 17. В этом случае Петя своим первым ходом может получить в куче 18, 19 или 34 камня, то есть, выиграть за один ход не может. В любой из этих позиций Ваня выигрывает своим первым ходом, удваивая количество камней.

Позицию S = 17 отмечаем в таблице как проигрышную (за 1 ход):

S	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17	18	19	…	34
																	П1	В1	В1	…	В1

3) Для того, чтобы Петя смог выиграть своим вторым ходом, ему нужно своим первым ходом перевести игру в проигрышную (для Вани) позицию, то есть, получить 17 камней. Он может сделать это при S = 14 (ходом «+3») или при S = 16 (ходом «+1»).

Задание 2. При S = 14 или S = 16 Петя своим первым ходом может получить 17 камней, переведя игру в проигрышную (для Вани) позицию. Поэтому своим вторым ходом Петя всегда выиграет.

В таблице обозначим эти позиции как выигрышные (за 2 хода):

S	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17	18	19	…	34
														В2		В2	П1	В1	В1	…	В1

4) для выполнения задания № 3 нужно найти такие позиции, из которых все возможные ходы ведут в выигрышные позиции, помеченные как В₁ или В₂; это позиции S = 13 и S = 15: при S = 13 можно получить 14, 16 или 26 камней, все эти позиции выигрышные; при S = 15 можно получить 16, 18 или 30 камней, это так же выигрышные позиции

5) В задании требуется найти только одну подходящую позицию, выбираем S = 13.

Задание 3. При S = 13 после первого хода Пети в куче будет 14, 16, или 26 камней. Если в куче получилось 14 или 16 камней, Ваня выиграет своим вторым ходом (см. задание 2). Если получилось 26 камней, Ваня выигрывает первым ходом, удвоив количество камней.

Строим дерево игры, рассматривая на каждом шаге все возможные ходы Пети и только выигрышный ход Вани:

У нас получилось не совсем дерево, потому что на первом ходу Ваня из двух позиций (S=14 и S=16) приводит игру к проигрышной для Пети позиции S=17. Для сокращения записи можно привести стрелки в один узел. Зелёные прямоугольники обозначают выигрыш Вани.

Ещё пример задания:

Здесь и в задачах для тренировки условие записано в сокращенном виде для экономии места. Полную форму записи условия см. в первой разобранной задаче.

Р-01. Два игрока, Петя и Ваня, играют в следующую игру. Перед игроками лежит куча камней. Игроки ходят по очереди, первый ход делает Петя. За один ход игрок может добавить в кучу один камень, добавить в кучу три камня или увеличить количество камней в куче в два  раза. Например, имея кучу из 15 камней, за один ход можно получить кучу из 16, 18 или 30 камней. У каждого игрока, чтобы делать ходы, есть неограниченное количество камней. Игра завершается в тот момент, когда количество камней в куче становится не менее 30.
В начальный момент в куче было S камней, 1 ≤ S ≤ 29.

1. При каких S: 1а) Петя выигрывает первым ходом; 1б) Ваня выигрывает первым ходом?

2. Назовите три значения S, при которых Петя может выиграть своим вторым ходом?

3. При каких S Ваня выигрывает своим первым или вторым ходом?

Решение (способ 2, математический, Г. Сергеев, г. Москва ):

1) Вопрос 1а. Петя выигрывает первым ходом:

 

Петя должен правильно выбрать один из трёх возможных вариантов действий
(+1 ИЛИ +3 ИЛИ *2), которое переведет кучу камней к состоянию ≥30. Таким образом, получаем совокупность неравенств:

2) Вопрос 1б. Ваня выигрывает первым ходом

Любое действие Пети (И +1 И +3 И *2) должно привести кучу камней к состоянию
. Только это может обеспечить выигрыш Вани на следующем ходу. Таким образом, получаем систему:

3) Назовите три значения S, при которых Петя может выиграть своим вторым ходом?

 

Петя должен выиграть, а это значит, он должен правильно выбрать один из трёх возможных вариантов действий (+1 ИЛИ +3 ИЛИ *2), которое переведет кучу камней к состоянию . Только это может обеспечить ему выигрыш при любом действии его противника Вани. Таким образом, получаем совокупность:

4) Вопрос 3. При каком S Ваня выигрывает своим первым или вторым ходом?

Сначала найдем, при каком S Ваня выигрывает своим вторым ходом.

Таким образом, получаем, что нет такого количества камней S, которые гарантировали бы выигрыш Вани именно после его второго хода при любых действиях Пети.

5) Найдем, при каких значениях S любое действие Пети приведет кучу камней к такому состоянию, при котором Ваня сможет выиграть после 1 или после второго хода:

 

6) Составим систему на основе следующих условий:

a. любой ход Пети ведет в позицию выигрыша в два хода () или в один ход ()

b. текущая позиция не совпадает с проигрышной позицией в один ход (), иначе, кроме нужных значений S, мы здесь получим ещё ответ на вопрос 1б

7) итак, ответ на вопрос 3: S = 10 или 12.

8) Построим дерево игры для S = 10. Обратите внимание, что после ходов Пети +1 и +3 Ваня своим следующим ходом сводит игру к одной и той же проигрышной (для Пети) позиции
S = 14.

 

Ещё пример задания:

Р-00. Два игрока, Петя и Ваня, играют в следующую игру. Перед игроками лежит куча камней. Игроки ходят по очереди, первый ход делает Петя. За один ход игрок может добавить в кучу один камень или увеличить количество камней в куче в два раза. Например, имея кучу из 15 камней, за один ход можно получить кучу из 16 или 30 камней. У каждого игрока, чтобы делать ходы, есть неограниченное количество камней. Игра завершается в тот момент, когда количество камней в куче становится не менее 22. Победителем считается игрок, сделавший последний ход, то есть первым получивший кучу, в которой будет 22 или больше камней.

В начальный момент в куче было S камней, 1 ≤ S ≤ 21. Будем говорить, что игрок имеет выигрышную стратегию, если он может выиграть при любых ходах противника. Описать стратегию игрока – значит описать, какой ход он должен сделать в любой ситуации, которая ему может встретиться при различной игре противника.

Выполните следующие задания. Во всех случаях обосновывайте свой ответ.

1. а) Укажите все такие значения числа S, при которых Петя может выиграть в один ход. Обоснуйте, что найдены все нужные значения S, и укажите выигрывающий ход для каждого указанного значения S.

б) Укажите такое значение S, при котором Петя не может выиграть за один ход, но при любом ходе Пети Ваня может выиграть своим первым ходом. Опишите выигрышную стратегию Вани.

2. Укажите два таких значения S, при которых у Пети есть выигрышная стратегия, причём
– Петя не может выиграть за один ход, и
– Петя может выиграть своим вторым ходом, независимо от того, как будет ходить Ваня.

Для каждого указанного значения S опишите выигрышную стратегию Пети.

3. Укажите значение S, при котором:
– у Вани есть выигрышная стратегия, позволяющая ему выиграть первым или вторым ходом при любой игре Пети, и
– у Вани нет стратегии, которая позволит ему гарантированно выиграть первым ходом.

---

---