Задание 21. Теория Игр. Задание 3. ЕГЭ 2026 по информатике
Средний процент выполнения: 67.8%
Ответом к заданию 21 по информатике может быть цифра (число) или слово.
Подпишись на суперполезные материалы
Задачи для практики
Задача 1
Два игрока, Паша и Влад, играют в увлекательную игру. Перед ними лежат две кучи камней. Игроки ходят по очереди, первый ход делает Паша. За один ход игрок может:
Добавить один камень в одну из куч;
Увеличить количество камней в любой куче в два раза.
Например, пусть в одной куче 10 камней, а в другой 6 камней. Обозначим такую позицию (10; 6). За один ход из позиции (10; 6) можно получить любую из четырёх позиций: (11; 6), (20; 6), (10; 7), (10; 12). У игроков есть неограниченное количество камней, чтобы делать ходы.
Игра завершается в тот момент, когда суммарное количество камней в двух кучах становится не менее 499. Победителем считается игрок, сделавший последний ход, то есть первым получивший позицию, в которой в двух кучах будет 499 или больше камней.
В начальный момент в первой куче было 5 камней, а во второй куче - S камней, где 1 ≤ S ≤ 493.
Будет говорить, что игрок имеет выигрышную стратегию, если он может победить при любых ходах соперника.
Найдите минимальное значения S, при которых у Влада есть выигрышная стратегия, причём одновременно выполняются два условия:
У Влада есть выигрышная стратегия, позволяющая ему выиграть первым или вторым ходом при любой игра Паши.
У Влада нет стратегии, которая позволит ему гарантированно выиграть первым ходом.
Решение
Напишем код для решения №21:
def F21(x, y, pos):
global summ, turn1, turn2
if pos == 0:
return (F21(x+turn1,y, pos+1) and F21(x*turn2,y, pos+1) and
F21(x,y+turn1, pos+1) and F21(x,y*turn2, pos+1))
elif pos == 1:
if x+y >= summ:
return False
else:
return (F21(x+turn1,y, pos+1) or F21(x*turn2,y, pos+1) or
F21(x,y+turn1, pos+1) or F21(x,y*turn2, pos+1))
elif pos == 2:
if x+y >= summ:
return True
else:
#return False
return (F21(x+turn1,y, pos+1) and F21(x*turn2,y, pos+1) and
F21(x,y+turn1, pos+1) and F21(x,y*turn2, pos+1))
elif pos == 3:
if x+y >= summ:
return False
else:
return (F21(x+turn1,y, pos+1) or F21(x*turn2,y, pos+1) or
F21(x,y+turn1, pos+1) or F21(x,y*turn2, pos+1))
elif pos == 4:
if x+y >= summ:
return True
else:
return False
summ = 499
turn1 = 1
turn2 = 2
for S in range(1, 493):
if F21(5, S, 0):
print(S)
Не забудем внести изменения в код, чтобы вывести значения гарантированной победы за один ход:
elif pos == 2:
if x+y >= summ:
return True
else:
return False
Наименьшее итоговое подходящее значение, выведенное в консоль: 243.
Ответ: 243.
Задача 2
Два игрока, Паша и Влад, играют в увлекательную игру. Перед ними лежат две кучи камней. Игроки ходят по очереди, первый ход делает Паша. За один ход игрок может:
Добавить пять камней в одну из куч;
Увеличить количество камней в любой куче в четыре раза.
Например, пусть в одной куче 10 камней, а в другой 6 камней. Обозначим такую позицию (10; 6). За один ход из позиции (10; 6) можно получить любую из четырёх позиций: (15; 6), (40; 6), (10; 11), (10; 24). У игроков есть неограниченное количество камней, чтобы делать ходы.
Игра завершается в тот момент, когда суммарное количество камней в двух кучах становится не менее 740. Победителем считается игрок, сделавший последний ход, то есть первым получивший позицию, в которой в двух кучах будет 740 или больше камней.
В начальный момент в первой куче было 34 камней, а во второй куче - S камней, где 1 ≤ S ≤ 705.
Будет говорить, что игрок имеет выигрышную стратегию, если он может победить при любых ходах соперника.
Найдите минимальное значения S, при которых у Влада есть выигрышная стратегия, причём одновременно выполняются два условия:
У Влада есть выигрышная стратегия, позволяющая ему выиграть первым или вторым ходом при любой игра Паши.
У Влада нет стратегии, которая позволит ему гарантированно выиграть первым ходом.
Решение
Напишем код для решения №21:
def F(x, y, pos):
if pos == 0:
return (F(x+1,y, pos+1) and F(x*2,y, pos+1) and
F(x,y+1, pos+1) and F(x,y*2, pos+1))
elif pos == 1:
if x+y >= 231:
return False
else:
return (F(x+1,y, pos+1) or F(x*2,y, pos+1) or
F(x,y+1, pos+1) or F(x,y*2, pos+1))
elif pos == 2:
if x+y >= 231:
return True
else:
return (F(x+1,y, pos+1) and F(x*2,y, pos+1) and
F(x,y+1, pos+1) and F(x,y*2, pos+1))
elif pos == 3:
if x+y >= 231:
return False
else:
return (F(x+1,y, pos+1) or F(x*2,y, pos+1) or
F(x,y+1, pos+1) or F(x,y*2, pos+1))
elif pos == 4:
if x+y >= 231:
return True
else:
return False
for S in range(1, 214):
if F(17, S, 0):
print(S)
Не забудем внести изменения в код, чтобы вывести значения гарантированной победы за один ход:
elif pos == 2:
if x+y >= 231:
return True
else:
return False
Наименьшее итоговое подходящее значение, выведенное в консоль: 97.
Ответ: 97.
Задача 3
Паша и Влад играют в увлекательную игру. Перед ними лежат две кучи камней, игроки ходят по очереди, первый ход делает Паша. За один ход каждый игрок может по выбору сделать одно из двух действий:
1. Прибавить к одной (любой) куче один камень.
2. Увеличить количество камней в одной (любой) куче в два раза.
Например, если в одной куче лежит 5 камней, а во второй 7. Обозначим эту ситуацию (5;7). Из этой позиции за один ход можно получить 4 варианта: (6; 7), (10; 7), (5, 8) и (5, 14).
Игра завершается, когда сумма камней в двух кучах становится не менее 61. Побеждает тот игрок, который сделал последний ход, то есть тот игрок, после хода которого сумма камней в двух кучах стала не менее 61. У игроков неограниченное количество камней для ходов.
В начальный момент времени в первой куче было 6 камней, а во второй S, где 1 ≤ S ≤ 54.
Будет говорить, что игрок имеет выигрышную стратегию, если он может победить при любых ходах соперника.
Для игры, описанной в 19-ом задании, найдите минимальное значение S во второй кучке, если в первой 6 камней. При котором Влад имеет выигрышную стратегию, при которой одновременно выполняется два условия:
-Влад не может гарантированно выиграть в первый ход;
-Влад выигрывает своим первым или вторым ходом, независимо от ходов Паши.
Решение
Подходящее значение: 23.
Если начальная позиция (6; 23), Паша может получить одну из четырёх позиций: (7; 23), (12, 23), (6, 24), (6, 46).
Из позиции (6; 46) Влад побеждает за один ход, получив позицию (6; 92).
Из позиций (7; 23), (12, 23), (6, 24) Влад делает позиции (14; 23), (12, 24), (12, 24), соответственно.
Из позиции (14, 23) Паша получает одну из четырёх позиций, ни в одной из которых не выигрывает: (15, 23), (28, 23), (14, 24), (14, 46).
Для каждой из этих четырёх позиций Влад может выиграть в один ход: (15, 46), (28, 46), (14, 48), (14, 92).
Из позиции (12, 24) Паша получает одну из четырёх позиций, ни в одной из которых не выигрывает: (13, 24), (24, 24), (12, 25), (12, 48).
Для каждой из этих четырёх позиций Влад может выиграть в один ход: (13, 48), (24, 48), (12, 50), (12, 96).
Ответ: 23.
Задача 4
Паша и Влад играют в увлекательную игру. Перед ними лежит куча камней, игроки ходят по очереди, первый ход делает Паша. За один ход каждый игрок может по выбору сделать одно из трёх действий:
1. Прибавить к куче один камень.
2. Прибавить к куче два камня.
3. Увеличить количество камней в куче в два раза.
Например, если в куче лежит 5 камней, из этой позиции за один ход можно получить 6, 7 или 10 камней.
Игра завершается, когда количество камней в куче становится не менее 41. Побеждает тот игрок, который сделал последний ход, то есть тот игрок, после хода которого количество камней в куче стало не менее 41. У игроков неограниченное количество камней для ходов.
В начальный момент времени в куче было S камней, где 1 ≤ S ≤ 40.
Будет говорить, что игрок имеет выигрышную стратегию, если он может победить при любых ходах соперника.
Для игры, описанной в 19-ом задании, найдите минимальное значение S, при котором Влад имеет выигрышную стратегию, при которой одновременно выполняется два условия:
-Влад не может гарантированно выиграть в первый ход;
-Влад выигрывает своим первым или вторым ходом, независимо от ходов Паши.
Решение
Подходящее значение S: 17. После первого хода Паши камней в куче будет или 18, или 19, или 34. Если в куче станет 34 камня, Влад удвоит количество камней и выиграет первым ходом. Ситуация, когда в куче 18 или 19 камней, разобрана в 20 задании. В этой ситуации игрок, который будет ходить (теперь это Влад), выигрывает своим вторым ходом.
В таблице изображено дерево возможных партий при описанной стратегии Влада. Заключительные позиции (в них выигрывает Влад) подчёркнуты.
| И. п. | Положение после очередных ходов | |||
| 1-й ход Паши (разобраны все ходы) | 1-й ход Влада (только ход по стратегии) | 2-й ход Паши (разобраны все ходы) | 2-й ход Влада (только ход по стратегии) | |
| 17 | 17 + 1 = 18 | 18 + 2 = 20 | 20 + 1 = 21 | 21 · 2 = 42 |
| 20 + 2 = 22 | 22 · 2 = 44 | |||
| 20 · 2 = 40 | 40 · 2 = 80 | |||
| 17 + 2 = 19 | 19 + 1 = 20 | 20 + 1 = 21 | 21 · 2 = 42 | |
| 20 + 2 = 22 | 22 · 2 = 44 | |||
| 20 · 2 = 40 | 40 · 2 = 80 | |||
| 17 · 2 = 34 | 34 · 2 = 68 | |||
Задача 5
Паша и Влад играют в увлекательную игру. Перед ними лежит куча камней, игроки ходят по очереди, первый ход делает Паша. За один ход каждый игрок может по выбору сделать одно из двух действий:
1. Прибавить к куче один камень.
2. Увеличить количество камней в куче в три раза.
Например, если в куче лежит 5 камней, то из этой позиции за один ход можно получить 6 или 15 камней.
Игра завершается, когда количество камней в куче становится не менее 109. Побеждает тот игрок, который сделал последний ход, то есть тот игрок, после хода которого количество камней в куче превысит 108 камней. У игроков неограниченное количество камней для ходов.
В начальный момент времени в куче было S камней, где 1 ≤ S ≤ 108.
Будет говорить, что игрок имеет выигрышную стратегию, если он может победить при любых ходах соперника.
Для игры, описанной в 19-ом задании, найдите минимальное значение S, при котором Влад имеет выигрышную стратегию, при которой одновременно выполняется два условия:
-Влад не может гарантированно выиграть в первый ход;
-Влад выигрывает своим первым или вторым ходом, независимо от ходов Паши.
Решение
Подходящее число - 34.
При таком начальном значении Паша может получить 35 или 102. Из 102 Влад выиграет первым ходом, а значение 35, можно свести в значение 36.
Паша может получить 37 или 108. Из этих двух значений выиграет Влад.
Задача 6
Паша и Влад играют в увлекательную игру. Перед ними лежит куча камней, игроки ходят по очереди, первый ход делает Паша. За один ход каждый игрок может по выбору сделать одно из двух действий:
1. Прибавить к куче два камня.
2. Увеличить количество камней в куче в два раза.
Например, если в куче лежит 5 камней, из этой позиции за один ход можно получить 7 или 10 камней.
Игра завершается, когда количество камней в куче становится не менее 32. Побеждает тот игрок, который сделал последний ход, то есть тот игрок, после хода которого количество камней в куче стало не менее 32. У игроков неограниченное количество камней для ходов.
В начальный момент времени в куче было S камней, где 1 ≤ S ≤ 28.
Будет говорить, что игрок имеет выигрышную стратегию, если он может победить при любых ходах соперника.
Для игры, описанной в 19-ом задании, найдите минимальное значение S, при котором Влад имеет выигрышную стратегию, при которой одновременно выполняется два условия:
-Влад не может гарантированно выиграть в первый ход;
-Влад выигрывает своим первым или вторым ходом, независимо от ходов Паши.
Решение
Подходящее значение S: 10. После первого хода Паши камней в куче будет или 12, или 20. Если в куче станет 20 камней, Влад удвоит количество камней и выиграет первым ходом. Ситуация, когда в куче 12 камней, разобрана в 20 задании. В этой ситуации игрок, который будет ходить (теперь это Влад), выигрывает своим вторым ходом.
Задача 7
Паша и Влад играют в увлекательную игру. Перед ними лежат две кучи камней, игроки ходят по очереди, первый ход делает Паша. За один ход каждый игрок может по выбору сделать одно из двух действий:
1. Прибавить к одной (любой) куче один камень.
2. Увеличить количество камней в одной (любой) куче в два раза.
Например, если в одной куче лежит 5 камней, а во второй 7. Обозначим эту ситуацию (5;7). Из этой позиции за один ход можно получить 4 варианта: (6; 7), (10; 7), (5, 8) и (5, 14).
Игра завершается, когда сумма камней в двух кучах становится не менее 77. Побеждает тот игрок, который сделал последний ход, то есть тот игрок, после хода которого сумма камней в двух кучах стала не менее 77. У игроков неограниченное количество камней для ходов.
В начальный момент времени в первой куче было 7 камней, а во второй S, где 1 ≤ S ≤ 69.
Будет говорить, что игрок имеет выигрышную стратегию, если он может победить при любых ходах соперника.
Для игры, описанной в 19-ом задании, найдите минимальное значение S, при котором Влад имеет выигрышную стратегию, при которой одновременно выполняется два условия:
-Влад не может гарантированно выиграть в первый ход;
-Влад выигрывает своим первым или вторым ходом, независимо от ходов Паши.
Решение
Подходящее значение: 30.
Если начальная позиция (7; 30), Паша может получить одну из четырёх позиций: (8; 30), (14, 30), (7, 31), (7, 60).
Из позиции (7; 60) Влад побеждает за один ход, получив позицию (7; 120).
Из позиций (8; 30), (14, 30), (7, 31) Влад делает позиции (16; 30), (14, 31), соответственно.
Из позиции (16, 30) Паша получает одну из четырёх позиций, ни в одной из которых не выигрывает: (17, 30), (32, 30), (16, 31), (16, 60).
Для каждой из этих четырёх позиций Влад может выиграть в один ход: (17, 60), (64, 60), (16, 62), (16, 120).
Из позиции (14, 31) Паша получает одну из четырёх позиций, ни в одной из которых не выигрывает: (15, 31), (28, 31), (14, 32), (14, 62).
Для каждой из этих четырёх позиций Влад может выиграть в один ход: (15, 62), (28, 62), (14, 64), (14, 124).
Ответ: 30.
Задача 8
Два игрока, Петя и Ваня, играют в следующую игру. Перед ними лежит набор слов, составленных из букв русского алфавита, при этом одно слово не является началом другого слова. Под словом подразумевается просто набор букв русского языка. Игра состоит в том, что игроки составляют слово из набора, приписывая по очереди буквы к концу составляемого слова, т.е. справа. При этом каждое промежуточное слово должно быть началом одного из заданных слов. Выигрывает тот, кто получит одно из заданных слов целиком. Первый ход делает Петя, т.е. Петя пишет первую букву составляемого слова.
Пример. Заданный набор слов: {АНАКОНДА, АПЕЛЬСИН, БОБ, БАКЛАЖАН, БАР}.
Первым ходом Петя пишет Б (он мог написать Б или А).
Ваня в ответ дописывает А и получает БА (он мог ещё получить БО).
Вторым ходом Петя получает БАР и выигрывает.
Одну букву поменяйте местами с другой буквой в более коротком слове так, чтобы теперь выигрышная стратегия была у другого игрока {КУХГНКУХГНХ, НГХУКНГХУН, КУХГНКУХГНЮЖ}. В ответе укажите изменённое слово
Решение
Самое короткое слово НГХУКНГХУН, нужно поменять местами первую букву с буквой К, тогда получим слово: КГХУННГХУН
Задача 9
Два игрока, Паша и Влад, играют в увлекательную игру. Перед ними лежат две кучи камней. Игроки ходят по очереди, первый ход делает Паша. За один ход игрок может:
Добавить два камня в одну из куч;
Увеличить количество камней в любой куче в четыре раза.
Например, пусть в одной куче 10 камней, а в другой 6 камней. Обозначим такую позицию (10; 6). За один ход из позиции (10; 6) можно получить любую из четырёх позиций: (12; 6), (40; 6), (10; 8), (10; 24). У игроков есть неограниченное количество камней, чтобы делать ходы.
Игра завершается в тот момент, когда суммарное количество камней в двух кучах становится не менее 791. Победителем считается игрок, сделавший последний ход, то есть первым получивший позицию, в которой в двух кучах будет 791 или больше камней.
В начальный момент в первой куче было 42 камня, а во второй куче - S камней, где 1 ≤ S ≤ 748.
Будет говорить, что игрок имеет выигрышную стратегию, если он может победить при любых ходах соперника.
Найдите минимальное значения S, при которых у Влада есть выигрышная стратегия, причём одновременно выполняются два условия:
У Влада есть выигрышная стратегия, позволяющая ему выиграть первым или вторым ходом при любой игра Паши.
У Влада нет стратегии, которая позволит ему гарантированно выиграть первым ходом.
Решение
Напишем код для решения №21:
def F21(x, y, pos):
global summ, turn1, turn2
if pos == 0:
return (F21(x+turn1, y, pos+1) and F21(x*turn2, y, pos+1) and
F21(x, y+turn1, pos+1) and F21(x, y*turn2, pos+1))
elif pos == 1:
if x+y >= summ:
return False
else:
return (F21(x+turn1, y, pos+1) or F21(x*turn2, y, pos+1) or
F21(x, y+turn1, pos+1) or F21(x, y*turn2, pos+1))
elif pos == 2:
if x+y >= summ:
return True
else:
#return False
return (F21(x+turn1, y, pos+1) and F21(x*turn2, y, pos+1) and
F21(x, y+turn1, pos+1) and F21(x, y*turn2, pos+1))
elif pos == 3:
if x+y >= summ:
return False
else:
return (F21(x+turn1, y, pos+1) or F21(x*turn2, y, pos+1) or
F21(x, y+turn1, pos+1) or F21(x, y*turn2, pos+1))
elif pos == 4:
if x+y >= summ:
return True
else:
return False
summ = 791
turn1 = 2
turn2 = 4
for S in range(1, 749):
if F21(42, S, 0):
print(S)
Не забудем внести изменения в код, чтобы вывести значения гарантированной победы за один ход:
elif pos == 2:
if x+y >= summ:
return True
else:
return False
Наименьшее итоговое подходящее значение, выведенное в консоль: 186.
Ответ: 186.
Задача 10
Паша и Влад играют в увлекательную игру. Перед ними лежит куча камней, игроки ходят по очереди, первый ход делает Паша. За один ход каждый игрок может по выбору сделать одно из трёх действий:
1. Прибавить к куче один камень.
2. Прибавить к куче два камня.
3. Увеличить количество камней в куче в два раза.
Например, если в куче лежит 5 камней, из этой позиции за один ход можно получить 6, 7 или 10 камней.
Игра завершается, когда количество камней в куче становится не менее 23. Побеждает тот игрок, который сделал последний ход, то есть тот игрок, после хода которого количество камней в куче стало не менее 23. У игроков неограниченное количество камней для ходов.
В начальный момент времени в куче было S камней, где 1 ≤ S ≤ 22.
Будет говорить, что игрок имеет выигрышную стратегию, если он может победить при любых ходах соперника.
Для игры, описанной в 19-ом задании, найдите минимальное значение S, при котором Влад имеет выигрышную стратегию, при которой одновременно выполняется два условия:
-Влад не может гарантированно выиграть в первый ход;
-Влад выигрывает своим первым или вторым ходом, независимо от ходов Паши.
Решение
Подходящее значение S: 8. После первого хода Паши в куче будет или 9, или 10, или 16 камней. Если в куче станет 16 камней, Влад удвоит количество камней и выиграет первым ходом. Ситуация, когда в куче 10 или 9 камней, разобрана в 20-ом задании. В этой ситуации игрок, который будет ходить (теперь это Влад), выигрывает своим вторым ходом. В таблице изображено дерево возможных партий при описанной стратегии Влада. Заключительные позиции (в них выигрывает Влад) подчёркнуты.
| И. п. | Положение после очередных ходов | |||
| 1-й ход Паши (разобраны все ходы) | 1-й ход Влада (только ход по стратегии) | 2-й ход Паши (разобраны все ходы) | 2-й ход Влада (только ход по стратегии) | |
| 8 | 8+1=9 | 9 + 2 = 11 | 11 + 1 = 12 | 12 · 2 = 24 |
| 11 + 2 = 13 | 13 · 2 = 26 | |||
| 11 · 2 = 22 | 22 · 2 = 44 | |||
| 8 + 2 = 10 | 10 + 1 = 11 | 11 + 1 = 12 | 12 · 2 = 24 | |
| 11 + 2 = 13 | 13 · 2 = 26 | |||
| 11 · 2 = 22 | 22 · 2 = 44 | |||
| 8 · 2 = 16 | 16 · 2 = 32 | |||
Задача 11
Два игрока, Петя и Ваня, играют в следующую игру. Перед игроками лежит несколько фишек. Игроки ходят по очереди, первый ход делает Петя и он просто кладёт фишку на игровое поле. За любой следующий один ход игрок может положить фишку на игровое поле справа от уже лежавшей на нём, при этом последняя цифра числа на фишке, которая уже лежит на столе, должна совпадать с первой цифрой числа фишки, которую собираются положить. Фишки нельзя поворачивать. Игра завершается в тот момент, когда нельзя будет положить фишку на игровое поле. Победителем считается игрок, сделавший последний ход.
Например, имея фишки 11, 14, 22, 23, 24 и 42, может быть следующая игра:
Петя кидает число 11, тогда Ваня выложит фишку 14, тогда Петя может положить фишку 42, а Ваня выложит 23 или 24 и выиграет, т.к. больше нет фишек, которые начинаются с 3 или 4.
Дан набор фишек: 11, 12, 13, 21, 22, 23, 31, 33
Будем говорить, что игрок имеет выигрышную стратегию, если он может выиграть при любых ходах противника. Описать стратегию игрока — значит описать, какой ход он должен сделать в любой ситуации, которая ему может встретиться при различной игре противника. В описание выигрышной стратегии не следует включать ходы играющего по этой стратегии игрока, не являющиеся для него безусловно выигрышными, т. е. не являющиеся выигрышными независимо от игры противника.
Сколько существует фишек, начиная с которых выигрывает Петя?
Решение
Из фишки 33 выигрывает Петя.
Из 13 Ваня.
Если в начале игры Петя выложит 11, то у Вани есть ходы 12 и 13. Число 12 Петя сведёт в 21 и выиграет через 1 ход. А 13 в 31 и тоже выиграет через 1 ход.
Мы нашли 2 фишки. 11 и 33.
Если в начале игры Петя выложил 12, то у Вани есть ходы: 21, 22, 23. Ваня походит 22, то Петя пойдёт 21 или 23, тогда Ваня сведёт всё к 11 или 33 и выиграет через 1 ход.
Если в начале Петя выложит 21, то Ваня сможет походить в 11, 12 или 13. Но Ваня сведёт игру в число 11 и выиграет через 3 хода.
Если Петя выложит 22, то у Вани есть ходы 21 и 23. 21 Петя сводит в 12, тогда Ваня пойдёт 23, а Петя 33. У Вани останется только ход 31 и Петя выиграет ходом 13.
23 Петя сводит в 33, тогда у Вани есть только ход 31, и Петя выиграет числом 13.
Мы нашли уже 3 фишки: 11, 22 и 33.
Проверим 23. Но тут выиграет Ваня. Как и с числом 13. 23 - 33 - 31 - 13
Задача 12
Два игрока, Паша и Влад, играют в увлекательную игру. Перед ними лежат две кучи камней. Игроки ходят по очереди, первый ход делает Паша. За один ход игрок может:
Добавить два камня в одну из куч;
Увеличить количество камней в любой куче в два раза.
Например, пусть в одной куче 10 камней, а в другой 6 камней. Обозначим такую позицию (10; 6). За один ход из позиции (10; 6) можно получить любую из четырёх позиций: (12; 6), (20; 6), (10; 8), (10; 12). У игроков есть неограниченное количество камней, чтобы делать ходы.
Игра завершается в тот момент, когда суммарное количество камней в двух кучах становится не менее 468. Победителем считается игрок, сделавший последний ход, то есть первым получивший позицию, в которой в двух кучах будет 468 или больше камней.
В начальный момент в первой куче было 7 камней, а во второй куче - S камней, где 1 ≤ S ≤ 460.
Будет говорить, что игрок имеет выигрышную стратегию, если он может победить при любых ходах соперника.
Найдите минимальное значения S, при которых у Влада есть выигрышная стратегия, причём одновременно выполняются два условия:
У Влада есть выигрышная стратегия, позволяющая ему выиграть первым или вторым ходом при любой игра Паши.
У Влада нет стратегии, которая позволит ему гарантированно выиграть первым ходом.
Решение
Напишем код для решения №21:
def F21(x, y, pos):
global summ, turn1, turn2
if pos == 0:
return (F21(x+turn1,y, pos+1) and F21(x*turn2,y, pos+1) and
F21(x,y+turn1, pos+1) and F21(x,y*turn2, pos+1))
elif pos == 1:
if x+y >= summ:
return False
else:
return (F21(x+turn1,y, pos+1) or F21(x*turn2,y, pos+1) or
F21(x,y+turn1, pos+1) or F21(x,y*turn2, pos+1))
elif pos == 2:
if x+y >= summ:
return True
else:
#return False
return (F21(x+turn1,y, pos+1) and F21(x*turn2,y, pos+1) and
F21(x,y+turn1, pos+1) and F21(x,y*turn2, pos+1))
elif pos == 3:
if x+y >= summ:
return False
else:
return (F21(x+turn1,y, pos+1) or F21(x*turn2,y, pos+1) or
F21(x,y+turn1, pos+1) or F21(x,y*turn2, pos+1))
elif pos == 4:
if x+y >= summ:
return True
else:
return False
summ = 468
turn1 = 2
turn2 = 2
for S in range(1, 461):
if F21(7, S, 0):
print(S)
Не забудем внести изменения в код, чтобы вывести значения гарантированной победы за один ход:
elif pos == 2:
if x+y >= summ:
return True
else:
return False
Наименьшее итоговое подходящее значение, выведенное в консоль: 224.
Ответ: 224.
Задача 13
Два игрока, Паша и Влад, играют в увлекательную игру. Перед ними лежат две кучи камней. Игроки ходят по очереди, первый ход делает Паша. За один ход игрок может:
Добавить один камень в одну из куч;
Увеличить количество камней в любой куче в два раза.
Например, пусть в одной куче 10 камней, а в другой 6 камней. Обозначим такую позицию (10; 6). За один ход из позиции (10; 6) можно получить любую из четырёх позиций: (11; 6), (20; 6), (10; 7), (10; 12). У игроков есть неограниченное количество камней, чтобы делать ходы.
Игра завершается в тот момент, когда суммарное количество камней в двух кучах становится не менее 417. Победителем считается игрок, сделавший последний ход, то есть первым получивший позицию, в которой в двух кучах будет 417 или больше камней.
В начальный момент в первой куче было 46 камней, а во второй куче - S камней, где 1 ≤ S ≤ 370.
Будет говорить, что игрок имеет выигрышную стратегию, если он может победить при любых ходах соперника.
Найдите минимальное значения S, при которых у Влада есть выигрышная стратегия, причём одновременно выполняются два условия:
У Влада есть выигрышная стратегия, позволяющая ему выиграть первым или вторым ходом при любой игра Паши.
У Влада нет стратегии, которая позволит ему гарантированно выиграть первым ходом.
Решение
Напишем код для решения №21:
def F21(x, y, pos):
global summ, turn1, turn2
if pos == 0:
return (F21(x + turn1, y, pos + 1) and F21(x * turn2, y, pos + 1) and
F21(x, y + turn1, pos + 1) and F21(x, y * turn2, pos + 1))
elif pos == 1:
if x+y >= summ:
return False
else:
return (F21(x + turn1, y, pos + 1) or F21(x * turn2, y, pos + 1) or
F21(x, y + turn1, pos + 1) or F21(x, y * turn2, pos + 1))
elif pos == 2:
if x+y >= summ:
return True
else:
#return False
return (F21(x + turn1, y, pos + 1) and F21(x * turn2, y, pos + 1) and
F21(x, y + turn1, pos + 1) and F21(x, y * turn2, pos + 1))
elif pos == 3:
if x+y >= summ:
return False
else:
return (F21(x + turn1, y, pos + 1) or F21(x * turn2, y, pos + 1) or
F21(x, y + turn1, pos + 1) or F21(x, y * turn2, pos + 1))
elif pos == 4:
if x+y >= summ:
return True
else:
return False
summ = 417
turn1 = 1
turn2 = 2
for S in range(1, 371):
if F21(46, S, 0):
print(S)
Не забудем внести изменения в код, чтобы вывести значения гарантированной победы за один ход:
elif pos == 2:
if x+y >= summ:
return True
else:
return False
Наименьшее итоговое подходящее значение, выведенное в консоль: 161.
Ответ: 161.
Задача 14
Два игрока, Паша и Влад, играют в увлекательную игру. Перед ними лежат две кучи камней. Игроки ходят по очереди, первый ход делает Паша. За один ход игрок может:
Добавить пять камней в одну из куч;
Увеличить количество камней в любой куче в четыре раза.
Например, пусть в одной куче 10 камней, а в другой 6 камней. Обозначим такую позицию (10; 6). За один ход из позиции (10; 6) можно получить любую из четырёх позиций: (15; 6), (40; 6), (10; 11), (10; 24). У игроков есть неограниченное количество камней, чтобы делать ходы.
Игра завершается в тот момент, когда суммарное количество камней в двух кучах становится не менее 740. Победителем считается игрок, сделавший последний ход, то есть первым получивший позицию, в которой в двух кучах будет 740 или больше камней.
В начальный момент в первой куче было 34 камней, а во второй куче - S камней, где 1 ≤ S ≤ 705.
Будет говорить, что игрок имеет выигрышную стратегию, если он может победить при любых ходах соперника.
Найдите минимальное значения S, при которых у Влада есть выигрышная стратегия, причём одновременно выполняются два условия:
У Влада есть выигрышная стратегия, позволяющая ему выиграть первым или вторым ходом при любой игра Паши.
У Влада нет стратегии, которая позволит ему гарантированно выиграть первым ходом.
Решение
Напишем код для решения №21:
def F21(x, y, pos):
global summ, turn1, turn2
if pos == 0:
return (F21(x+5,y, pos+1) and F21(x*4,y, pos+1) and
F21(x,y+5, pos+1) and F21(x,y*4, pos+1))
elif pos == 1:
if x+y >= summ:
return False
else:
return (F21(x+5,y, pos+1) or F21(x*4,y, pos+1) or
F21(x,y+5, pos+1) or F21(x,y*4, pos+1))
elif pos == 2:
if x+y >= summ:
return True
else:
#return False
return (F21(x+5,y, pos+1) and F21(x*4,y, pos+1) and
F21(x,y+5, pos+1) and F21(x,y*4, pos+1))
elif pos == 3:
if x+y >= summ:
return False
else:
return (F21(x+5,y, pos+1) or F21(x*4,y, pos+1) or
F21(x,y+5, pos+1) or F21(x,y*4, pos+1))
elif pos == 4:
if x+y >= summ:
return True
else:
return False
summ = 740
for S in range(1, 706):
if F21(34, S, 0):
print(S)
Не забудем внести изменения в код, чтобы вывести значения гарантированной победы за один ход:
elif pos == 2:
if x+y >= summ:
return True
else:
return False
Наименьшее итоговое подходящее значение, выведенное в консоль: 169.
Ответ: 169.
Задача 15
Два игрока, Паша и Валя, играют в следующую игру. Перед игроками лежит куча камней. Игроки ходят по очереди, первый ход делает Паша. За один ход игрок может добавить в кучу один или четыре камня либо увеличить количество камней в куче в пять раз. Например, имея кучу из 10 камней, за один ход можно получить кучу из 11, 14 или 50 камней. У каждого игрока, чтобы делать ходы, есть неограниченное количество камней. Игра завершается в тот момент, когда количество камней в куче становится не менее 84.
Победителем считается игрок, сделавший последний ход, т. е. первым получивший кучу, в которой будет 84 или больше камней. В начальный момент в куче было S камней; 1 ≤ S ≤ 72.
Будем говорить, что игрок имеет выигрышную стратегию, если он может выиграть при любых ходах противника. Описать стратегию игрока — значит описать, какой ход он должен сделать в любой ситуации, которая ему может встретиться при различной игре противника. В описание выигрышной стратегии не следует включать ходы играющего по этой стратегии игрока, не являющиеся для него безусловно выигрышными, т. е. не являющиеся выигрышными независимо от игры противника.
Найдите минимальное значение S, при котором одновременно выполняются два условия:
— у Вали есть выигрышная стратегия, позволяющая ему выиграть первым или вторым ходом при любой игре Паши;
— у Вали нет стратегии, которая позволит ему гарантированно выиграть первым ходом.
Решение
Решение при помощи программы на С++:
bool comp(int a, int b) {return a < b;};
int main() {
int S[84]; // тут задаётся мин. значение для выигрыша
for (int i = 0; i < 84; ++i)
if (i < 17) // при каком наим. S можно выиграть за один ход? 84/5
S[i] = 0;
else
S[i] = 1; // выигрыш за один ход
for (int z = 0; z < 50; ++z)
for (int i = 0; i < 84; ++i) {
// если ещё не обработана позиция
if (S[i] == 0)
// если любым ходом попадает в выигрышную позицию для второго игрока
if (S[i + 1] > 0 && S[i + 4] > 0 && S[i * 5] > 0)
S[i] = max({S[i + 1], S[i + 4], S[i * 5]}, comp) * -1;
// если одним из ходов может перевести в проигрышную позицию для второго игрока
else if (S[i + 1] < 0 || S[i + 4] < 0 || S[i * 5] < 0)
S[i] = max({abs(S[i + 1]), abs(S[i + 4]), abs(S[i * 5])}, comp) + 1;
}
return 0;
}
Нас интересуют позиции, в которых находится значение -2, что означает: игрок, ходящий вторым, выигрывает за 2 хода. Позиции со значением -1 нам не подходят, поскольку из них второй игрок будет гарантированно выигрывать первым ходом, что не соответствует второму условию задания. Для этого запускаем цикл:
for (int i = 0; i < 84; ++i)
if (S[i] == -2)
cout << i << " ";
Программа выдаст ответ: 11 14. Минимальное: 11
Задача 16
Паша и Влад играют в увлекательную игру. Перед ними лежат две кучи камней, игроки ходят по очереди, первый ход делает Паша. За один ход каждый игрок может по выбору сделать одно из двух действий:
1. Прибавить к одной (любой) куче один камень.
2. Увеличить количество камней в одной (любой) куче в два раза.
Например, если в одной куче лежит 5 камней, а во второй 7. Обозначим эту ситуацию (5;7). Из этой позиции за один ход можно получить 4 варианта: (6; 7), (10; 7), (5, 8) и (5, 14).
Игра завершается, когда сумма камней в двух кучах становится не менее 69. Побеждает тот игрок, который сделал последний ход, то есть тот игрок, после хода которого сумма камней в двух кучах стала не менее 69. У игроков неограниченное количество камней для ходов.
В начальный момент времени в первой куче было 6 камней, а во второй S, где 1 ≤ S ≤ 62.
Будет говорить, что игрок имеет выигрышную стратегию, если он может победить при любых ходах соперника.
Для игры, описанной в 19-ом задании, найдите минимальное значение S, при котором Влад имеет выигрышную стратегию, при которой одновременно выполняется два условия:
-Влад не может гарантированно выиграть в первый ход;
-Влад выигрывает своим первым или вторым ходом, независимо от ходов Паши.
Решение
Подходящее значение: 27.
Если начальная позиция (6; 27), Паша может получить одну из четырёх позиций: (7; 27), (12, 27), (6, 28), (6, 54).
Из позиции (6; 54) Влад побеждает за один ход, получив позицию (6; 108).
Из позиций (7; 27), (12, 27), (6, 28) Влад делает позиции (14; 27), (12, 28), (12, 28), соответственно.
Из позиции (14, 27) Паша получает одну из четырёх позиций, ни в одной из которых не выигрывает: (15, 27), (28, 27), (14, 28), (14, 54).
Для каждой из этих четырёх позиций Влад может выиграть в один ход: (15, 54), (28, 54), (14, 56), (14, 108).
Из позиции (12, 28) Паша получает одну из четырёх позиций, ни в одной из которых не выигрывает: (13, 28), (24, 28), (12, 29), (12, 56).
Для каждой из этих четырёх позиций Влад может выиграть в один ход: (13, 56), (24, 56), (12, 58), (12, 112).
Ответ: 27.
Задача 17
Паша и Влад играют в увлекательную игру. Перед ними лежат две кучи камней, игроки ходят по очереди, первый ход делает Паша. За один ход каждый игрок может по выбору сделать одно из двух действий:
1. Прибавить к одной (любой) куче один камень.
2. Увеличить количество камней в одной (любой) куче в два раза.
Например, если в одной куче лежит 5 камней, а во второй 7. Обозначим эту ситуацию (5;7). Из этой позиции за один ход можно получить 4 варианта: (6; 7), (10; 7), (5, 8) и (5, 14).
Игра завершается, когда сумма камней в двух кучах становится не менее 61. Побеждает тот игрок, который сделал последний ход, то есть тот игрок, после хода которого сумма камней в двух кучах стала не менее 61. У игроков неограниченное количество камней для ходов.
В начальный момент времени в первой куче было 6 камней, а во второй S, где 1 ≤ S ≤ 54.
Будет говорить, что игрок имеет выигрышную стратегию, если он может победить при любых ходах соперника.
Для игры, описанной в 19-ом задании, найдите минимальное значение S, при котором Влад имеет выигрышную стратегию, при которой одновременно выполняется два условия:
-Влад не может гарантированно выиграть в первый ход;
-Влад выигрывает своим первым или вторым ходом, независимо от ходов Паши.
Решение
Подходящее значение: 23.
Если начальная позиция (6; 23), Паша может получить одну из четырёх позиций: (7; 23), (12, 23), (6, 24), (6, 46).
Из позиции (6; 46) Влад побеждает за один ход, получив позицию (6; 92).
Из позиций (7; 23), (12, 23), (6, 24) Влад делает позиции (14; 23), (12, 24), (12, 24), соответственно.
Из позиции (14, 23) Паша получает одну из четырёх позиций, ни в одной из которых не выигрывает: (15, 23), (28, 23), (14, 24), (14, 46).
Для каждой из этих четырёх позиций Влад может выиграть в один ход: (15, 46), (28, 46), (14, 48), (14, 92).
Из позиции (12, 24) Паша получает одну из четырёх позиций, ни в одной из которых не выигрывает: (13, 24), (24, 24), (12, 25), (12, 48).
Для каждой из этих четырёх позиций Влад может выиграть в один ход: (13, 48), (24, 48), (12, 50), (12, 96).
Решение при помощи программы на С++
int main() {
int S[100][100]; // тут задаётся мин. значение для выигрыша
for (int i = 0; i < 100; ++i)
for (int j = 0; j < 100; ++j)
// при каком наим. S можно выиграть за один ход? 84/5
if (i*2 + j >= 61 || i + j*2 >= 61) // выигрыш за один ход
S[i][j] = 1;
else
S[i][j] = 0;
for (int z = 0; z < 50; ++z)
for (int i = 0; i < 100; ++i)
for (int j = 0; j < 100; ++j) {
// если ещё не обработана позиция
if (S[i][j] == 0)
// если любым ходом попадает в выигрышную позицию для второго игрока
if (S[i + 1][j] > 0 && S[i * 2][j] > 0
&& S[i][j + 1] > 0 && S[i][j * 2] > 0)
S[i][j] = max({S[i + 1][j], S[i * 2][j], S[i][j + 1], S[i][j * 2]}, comp) * -1;
// если одним из ходов может перевести в проигрышную позицию для второго игрока
else if (S[i + 1][j] < 0 || S[i * 2][j] < 0 || S[i][j + 1] < 0 || S[i][j * 2] < 0)
S[i][j] = abs(min({S[i + 1][j], S[i * 2][j], S[i][j + 1], S[i][j * 2]}, comp)) + 1;
}
cout << "№20) ";
for (int i = 1; i < 54; ++i) {
if (S[6][i] == 2)
cout << i << " ";
}
cout << endl << "№21) ";
for (int i = 1; i < 54; ++i) {
if (S[6][i] == -2)
cout << i << " ";
}
return 0;
}
Программа выведет:
№20) 24 26
№21) 23
Ответ: 23.
Задача 18
Паша и Влад играют в увлекательную игру. Перед ними лежат две кучи камней, игроки ходят по очереди, первый ход делает Паша. За один ход каждый игрок может по выбору сделать одно из двух действий:
1. Прибавить к одной (любой) куче один камень.
2. Увеличить количество камней в одной (любой) куче в два раза.
Например, если в одной куче лежит 5 камней, а во второй 7. Обозначим эту ситуацию (5;7). Из этой позиции за один ход можно получить 4 варианта: (6; 7), (10; 7), (5, 8) и (5, 14).
Игра завершается, когда сумма камней в двух кучах становится не менее 83. Побеждает тот игрок, который сделал последний ход, то есть тот игрок, после хода которого сумма камней в двух кучах стала не менее 83. У игроков неограниченное количество камней для ходов.
В начальный момент времени в первой куче было 9 камней, а во второй S, где 1 ≤ S ≤ 73.
Будет говорить, что игрок имеет выигрышную стратегию, если он может победить при любых ходах соперника.
Для игры, описанной в 19-ом задании, найдите минимальное значение S. При котором Влад имеет выигрышную стратегию, при которой одновременно выполняется два условия:
-Влад не может гарантированно выиграть в первый ход;
-Влад выигрывает своим первым или вторым ходом, независимо от ходов Паши.
Решение
Подходящее значение: 31.
Если начальная позиция (9; 31), Паша может получить одну из четырёх позиций: (10; 31), (18, 31), (9, 32), (9, 62).
Из позиции (9; 62) Влад побеждает за один ход, получив позицию (9; 124).
Из позиций (10; 31), (18, 31), (9, 32) Влад делает позиции (20; 31), (18, 32), (18, 32), соответственно.
Из позиции (20, 31) Паша получает одну из четырёх позиций, ни в одной из которых не выигрывает: (21, 31), (40, 31), (20, 32), (20, 62).
Для каждой из этих четырёх позиций Влад может выиграть в один ход: (21, 62), (40, 62), (20, 64), (20, 144).
Из позиции (18, 32) Паша получает одну из четырёх позиций, ни в одной из которых не выигрывает: (19, 32), (36, 32), (18, 33), (18, 64).
Для каждой из этих четырёх позиций Влад может выиграть в один ход: (19, 64), (36, 64), (18, 66), (18, 128).
Ответ: 31.
Задача 19
Паша и Влад играют в увлекательную игру. Перед ними лежат две кучи камней, игроки ходят по очереди, первый ход делает Паша. За один ход каждый игрок может по выбору сделать одно из двух действий:
1. Прибавить к одной (любой) куче один камень.
2. Увеличить количество камней в одной (любой) куче в два раза.
Например, если в одной куче лежит 5 камней, а во второй 7. Обозначим эту ситуацию (5;7). Из этой позиции за один ход можно получить 4 варианта: (6; 7), (10; 7), (5, 8) и (5, 14).
Игра завершается, когда сумма камней в двух кучах становится не менее 57. Побеждает тот игрок, который сделал последний ход, то есть тот игрок, после хода которого сумма камней в двух кучах стала не менее 57. У игроков неограниченное количество камней для ходов.
В начальный момент времени в первой куче было 5 камней, а во второй S, где 1 ≤ S ≤ 51.
Будет говорить, что игрок имеет выигрышную стратегию, если он может победить при любых ходах соперника.
Для игры, описанной в 19-ом задании, найдите минимальное значение S, при котором Влад имеет выигрышную стратегию, при которой одновременно выполняется два условия:
-Влад не может гарантированно выиграть в первый ход;
-Влад выигрывает своим первым или вторым ходом, независимо от ходов Паши.
Решение
Подходящее значение: 22.
Если начальная позиция (5; 22), Паша может получить одну из четырёх позиций: (6; 22), (10, 22), (5, 23), (5, 44).
Из позиции (5; 44) Влад побеждает за один ход, получив позицию (5; 88).
Из позиций (6; 22), (10, 22), (5, 23) Влад делает позиции (12; 22), (10, 23), (10, 23), соответственно.
Из позиции (12, 22) Паша получает одну из четырёх позиций, ни в одной из которых не выигрывает: (13, 22), (24, 22), (12, 23), (12, 44).
Для каждой из этих четырёх позиций Влад может выиграть в один ход: (13, 44), (24, 44), (12, 46), (12, 88).
Из позиции (10, 23) Паша получает одну из четырёх позиций, ни в одной из которых не выигрывает: (11, 23), (20, 23), (10, 24), (10, 46).
Для каждой из этих четырёх позиций Влад может выиграть в один ход: (11, 46), (20, 46), (10, 48), (10, 92).
Ответ: 22.
Задача 20
Паша и Влад играют в увлекательную игру. Перед ними лежат две кучи камней, игроки ходят по очереди, первый ход делает Паша. За один ход каждый игрок может по выбору сделать одно из двух действий:
1. Прибавить к одной (любой) куче один камень.
2. Увеличить количество камней в одной (любой) куче в два раза.
Например, если в одной куче лежит 5 камней, а во второй 7. Обозначим эту ситуацию (5;7). Из этой позиции за один ход можно получить 4 варианта: (6; 7), (10; 7), (5, 8) и (5, 14).
Игра завершается, когда сумма камней в двух кучах становится не менее 77. Побеждает тот игрок, который сделал последний ход, то есть тот игрок, после хода которого сумма камней в двух кучах стала не менее 77. У игроков неограниченное количество камней для ходов.
В начальный момент времени в первой куче было 7 камней, а во второй S, где 1 ≤ S ≤ 69.
Будет говорить, что игрок имеет выигрышную стратегию, если он может победить при любых ходах соперника.
Для игры, описанной в 19-ом задании, найдите минимальное значение S, при котором Влад имеет выигрышную стратегию, при которой одновременно выполняется два условия:
-Влад не может гарантированно выиграть в первый ход;
-Влад выигрывает своим первым или вторым ходом, независимо от ходов Паши.
Решение
Подходящее значение: 30.
Если начальная позиция (7; 30), Паша может получить одну из четырёх позиций: (8; 30), (14, 30), (7, 31), (7, 60).
Из позиции (7; 60) Влад побеждает за один ход, получив позицию (7; 120).
Из позиций (8; 30), (14, 30), (7, 31) Влад делает позиции (16; 30), (14, 31), (14, 31), соответственно.
Из позиции (16, 30) Паша получает одну из четырёх позиций, ни в одной из которых не выигрывает: (17, 30), (32, 30), (16, 31), (16, 60).
Для каждой из этих четырёх позиций Влад может выиграть в один ход: (17, 60), (32, 60), (16, 62), (16, 120).
Из позиции (14, 31) Паша получает одну из четырёх позиций, ни в одной из которых не выигрывает: (15, 31), (28, 31), (14, 32), (14, 62).
Для каждой из этих четырёх позиций Влад может выиграть в один ход: (15, 62), (28, 62), (14, 64), (14, 144).
Ответ: 30.
Рекомендуемые курсы подготовки
- Узнаешь всё про кодирование: что это такое и как происходит
- Познакомишься с Условием Фано: как оно примняется и почему важно
- Научишься считать колиечтсво информации и сколько под неё нужно выделить памяти
на бесплатном курсе Турбо ЕГЭ
