Задание 20. Теория Игр. Задание 2. ЕГЭ 2026 по информатике
Средний процент выполнения: 51.9%
Ответом к заданию 20 по информатике может быть цифра (число) или слово.
Подпишись на суперполезные материалы
Задачи для практики
Задача 1
Паша и Влад играют в увлекательную игру. Перед ними лежат две кучи камней, игроки ходят по очереди, первый ход делает Паша. За один ход каждый игрок может по выбору сделать одно из двух действий:
1. Прибавить к одной (любой) куче один камень.
2. Увеличить количество камней в одной (любой) куче в два раза.
Например, если в одной куче лежит 5 камней, а во второй 7. Обозначим эту ситуацию (5;7). Из этой позиции за один ход можно получить 4 варианта: (6; 7), (10; 7), (5, 8) и (5, 14).
Игра завершается, когда сумма камней в двух кучах становится не менее 61. Побеждает тот игрок, который сделал последний ход, то есть тот игрок, после хода которого сумма камней в двух кучах стала не менее 61. У игроков неограниченное количество камней для ходов.
В начальный момент времени в первой куче было 6 камней, а во второй S, где 1 ≤ S ≤ 54.
Будет говорить, что игрок имеет выигрышную стратегию, если он может победить при любых ходах соперника.
Для игры, описанной в задании 19, найдите два наименьших значения S, при которых у Паши есть выигрышная стратегия, причём одновременно выполняются два условия:
– Паша не может выиграть за один ход;
– Паша может выиграть своим вторым ходом независимо от того, как будет ходить Влад
Найденные значения запишите в ответе в порядке возрастания.
Решение
Напишем код для решения №20:
def F(x, y, pos):
if pos > 3:
return False
if x + y >= 61 and pos != 3:
return False
if x + y >= 61 and pos == 3:
return True
else:
if pos % 2 == 0:
return F(x+1, y, pos+1) or F(x, y+1, pos+1) \
or F(x*2, y, pos+1) or F(x, y*2, pos+1)
else:
return F(x+1, y, pos+1) and F(x, y+1, pos+1) \
and F(x*2, y, pos+1) and F(x, y*2, pos+1)
for S in range(1, 55):
if F(6, S, 0):
print(S)
В консоль вывелось: 24 26. В ответ запишем их без разделителей в порядке возрастания.
Задача 2
Два игрока, Паша и Влад, играют в увлекательную игру. Перед ними лежат две кучи камней. Игроки ходят по очереди, первый ход делает Паша. За один ход игрок может:
Добавить пять камней в одну из куч;
Увеличить количество камней в любой куче в четыре раза.
Например, пусть в одной куче 10 камней, а в другой 6 камней. Обозначим такую позицию (10; 6). За один ход из позиции (10; 6) можно получить любую из четырёх позиций: (15; 6), (40; 6), (10; 11), (10; 24). У игроков есть неограниченное количество камней, чтобы делать ходы.
Игра завершается в тот момент, когда суммарное количество камней в двух кучах становится не менее 740. Победителем считается игрок, сделавший последний ход, то есть первым получивший позицию, в которой в двух кучах будет 740 или больше камней.
В начальный момент в первой куче было 34 камней, а во второй куче - S камней, где 1 ≤ S ≤ 705.
Будет говорить, что игрок имеет выигрышную стратегию, если он может победить при любых ходах соперника.
Найдите два наименьших значения S, при которых у Паши есть выигрышная стратегия, причём одновременно выполняются два условия:
Паша не может выиграть за один ход;
Паша может выиграть своим вторым ходом независимо от того, как будет ходить Влад.
В ответе запишите два числа в порядке возрастания без пробелов и разделителей.
Решение
Напишем код для решения №20:
def F(x, y, pos):
if pos == 0:
return (F(x+5,y, pos+1) or F(x*4,y, pos+1) or
F(x,y+5, pos+1) or F(x,y*4, pos+1))
elif pos == 1:
if x+y >= 740:
return False
else:
return (F(x+5,y, pos+1) and F(x*4,y, pos+1) and
F(x,y+5, pos+1) and F(x,y*4, pos+1))
elif pos == 2:
if x+y >= 740:
return False
else:
return (F(x+5,y, pos+1) or F(x*4,y, pos+1) or
F(x,y+5, pos+1) or F(x,y*4, pos+1))
elif pos == 3:
if x+y >= 740:
return True
else:
return False
for S in range(1, 706):
if F(34, S, 0):
print(S)
Два наименьших значений, выведенных в консоль: 44 и 150.
Ответ: 44150.
Задача 3
Паша и Влад играют в увлекательную игру. Перед ними лежит куча камней, игроки ходят по очереди, первый ход делает Паша. За один ход каждый игрок может по выбору сделать одно из трёх действий:
1. Прибавить к куче один камень.
2. Прибавить к куче два камня.
3. Увеличить количество камней в куче в два раза.
Например, если в куче лежит 5 камней, из этой позиции за один ход можно получить 6, 7 или 10 камней.
Игра завершается, когда количество камней в куче становится не менее 41. Побеждает тот игрок, который сделал последний ход, то есть тот игрок, после хода которого количество камней в куче стало не менее 41. У игроков неограниченное количество камней для ходов.
В начальный момент времени в куче было S камней, где 1 ≤ S ≤ 40.
Будет говорить, что игрок имеет выигрышную стратегию, если он может победить при любых ходах соперника.
Для игры, описанной в 19-ом задании, найдите два наибольших значения S, при которых Паша имеет выигрышную стратегию. При которой одновременно выполняется два условия:
-Паша не выигрывает в первый ход;
-Паша выигрывает своим вторым ходом, независимо от хода Влада.
В качестве ответа укажите два числа в порядке возрастания слитно без запятых и разделителей.
Решение
Подходящие значения S: 19 и 18. В этих случаях Паша, очевидно, не может выиграть первым ходом. Однако, добавив в кучу 1 или 2 камня, он может получить кучу из 20 камней. Эта позиция разобрана в 19 задании. Если в куче 20 камней, то игрок, который будет ходить (теперь это Влад), выиграть не может, а его противник (то есть Паша) следующим ходом выиграет.
Задача 4
Паша и Влад играют в увлекательную игру. Перед ними лежит куча камней, игроки ходят по очереди, первый ход делает Паша. За один ход каждый игрок может по выбору сделать одно из двух действий:
1. Прибавить к куче один камень.
2. Увеличить количество камней в куче в три раза.
Например, если в куче лежит 5 камней, то из этой позиции за один ход можно получить 6 или 15 камней.
Игра завершается, когда количество камней в куче становится не менее 109. Побеждает тот игрок, который сделал последний ход, то есть тот игрок, после хода которого количество камней в куче превысит 108 камней. У игроков неограниченное количество камней для ходов.
В начальный момент времени в куче было S камней, где 1 ≤ S ≤ 108.
Будет говорить, что игрок имеет выигрышную стратегию, если он может победить при любых ходах соперника.
Для игры, описанной в 19-ом задании, найдите два значения S, при которых Паша имеет выигрышную стратегию, при которой одновременно выполняется два условия:
-Паша не выигрывает в первый ход;
-Паша выигрывает своим вторым ходом, независимо от хода Влада.
В качестве ответа укажите два числа в порядке возрастания слитно без запятых и разделителей.
Решение
Подходящие значения S: 12 и 35. В этих случаях Паша, очевидно, не может выиграть первым ходом. Однако, добавив в кучу с 35 камнями 1 камень или утроив кучу из 12 камней, он может получить кучу из 36 камней. Эта позиция разобрана в задании 19. Если в куче 36 камней, то игрок, который будет ходить (теперь это Влад), выиграть не может, а его противник (то есть Паша) следующим ходом выиграет.
Задача 5
Два игрока, Паша и Влад, играют в увлекательную игру. Перед ними лежат две кучи камней. Игроки ходят по очереди, первый ход делает Паша. За один ход игрок может:
Добавить два камня в одну из куч;
Увеличить количество камней в любой куче в два раза.
Например, пусть в одной куче 10 камней, а в другой 6 камней. Обозначим такую позицию (10; 6). За один ход из позиции (10; 6) можно получить любую из четырёх позиций: (12; 6), (20; 6), (10; 8), (10; 12). У игроков есть неограниченное количество камней, чтобы делать ходы.
Игра завершается в тот момент, когда суммарное количество камней в двух кучах становится не менее 468. Победителем считается игрок, сделавший последний ход, то есть первым получивший позицию, в которой в двух кучах будет 468 или больше камней.
В начальный момент в первой куче было 7 камней, а во второй куче - S камней, где 1 ≤ S ≤ 460.
Будет говорить, что игрок имеет выигрышную стратегию, если он может победить при любых ходах соперника.
Найдите два наименьших значения S, при которых у Паши есть выигрышная стратегия, причём одновременно выполняются два условия:
Паша не может выиграть за один ход;
Паша может выиграть своим вторым ходом независимо от того, как будет ходить Влад.
В ответе запишите два числа в порядке возрастания без пробелов и разделителей.
Решение
Напишем код для решения №20:
def F(x, y, pos):
if pos == 0:
return (F(x+2,y, pos+1) or F(x*2,y, pos+1) or
F(x,y+2, pos+1) or F(x,y*2, pos+1))
elif pos == 1:
if x+y >= 468:
return False
else:
return (F(x+2,y, pos+1) and F(x*2,y, pos+1) and
F(x,y+2, pos+1) and F(x,y*2, pos+1))
elif pos == 2:
if x+y >= 468:
return False
else:
return (F(x+2,y, pos+1) or F(x*2,y, pos+1) or
F(x,y+2, pos+1) or F(x,y*2, pos+1))
elif pos == 3:
if x+y >= 468:
return True
else:
return False
for S in range(1, 461):
if F(7, S, 0):
print(S)
Два наименьших значений, выведенных в консоль: 115 и 226.
Ответ: 115226.
Задача 6
Паша и Влад играют в увлекательную игру. Перед ними лежат две кучи камней, игроки ходят по очереди, первый ход делает Паша. За один ход каждый игрок может по выбору сделать одно из двух действий:
1. Прибавить к одной (любой) куче два камня.
2. Увеличить количество камней в одной (любой) куче в два раза.
Например, если в одной куче лежит 5 камней, а во второй 7. Обозначим эту ситуацию (5;7). Из этой позиции за один ход можно получить 4 варианта: (10; 7), (7; 7), (5, 9) и (5, 14).
Игра завершается, когда сумма камней в двух кучах становится не менее 100. Побеждает тот игрок, который сделал последний ход, то есть тот игрок, после хода которого сумма камней в двух кучах стала не менее 100. У игроков неограниченное количество камней для ходов.
Будет говорить, что игрок имеет выигрышную стратегию, если он может победить при любых ходах соперника.
Для игры, описанной в 19-ом задании, для начальной позиции (10; 42) укажите, кто из игроков имеет выигрышную стратегию. Укажите, какое наибольшее количество ходов может потребоваться победителю для выигрыша при этой стратегии. В ответе укажите имя игрока и количество ходов без пробелов и разделителей, например, "Влад3".
Решение
Для начальной позиции (10; 42) выигрывает Паша своим вторым ходом.
Чтобы выиграть, Паша должен после своего хода получить позицию (10; 44). Для этого он должен увеличить на 2 число камней либо во второй куче. Считая позицию (10; 44) начальной, мы приходим к рассмотрению ситуации задания 19.
Как уже было показано ранее, в этом случае выигрывает тот, кто ходит вторым. Значит, выиграет Паша своим вторым ходом.
Задача 7
Паша и Влад играют в увлекательную игру. Перед ними лежит куча камней, игроки ходят по очереди, первый ход делает Паша. За один ход каждый игрок может по выбору сделать одно из трёх действий:
1. Прибавить к куче один камень.
2. Прибавить к куче два камня.
3. Увеличить количество камней в куче в два раза.
Например, если в куче лежит 5 камней, из этой позиции за один ход можно получить 6, 7 или 10 камней.
Игра завершается, когда количество камней в куче становится не менее 23. Побеждает тот игрок, который сделал последний ход, то есть тот игрок, после хода которого количество камней в куче стало не менее 23. У игроков неограниченное количество камней для ходов.
В начальный момент времени в куче было S камней, где 1 ≤ S ≤ 22.
Будет говорить, что игрок имеет выигрышную стратегию, если он может победить при любых ходах соперника.
Для игры, описанной в 19-ом задании, найдите два значения S, при которых Паша имеет выигрышную стратегию, при которой одновременно выполняется два условия:
-Паша не выигрывает в первый ход;
-Паша выигрывает своим вторым ходом, независимо от хода Влада.
В качестве ответа укажите два числа в порядке возрастания слитно без запятых и разделителей.
Решение
Подходящие значения S: 10 и 9. В этих случаях Паша, очевидно, не может выиграть первым ходом. Однако, добавив в кучу 1 или 2 камня, он может получить кучу из 11 камней. Эта позиция разобрана в 19-ом задании. Если в куче 11 камней, то игрок, который будет ходить (теперь это Влад), выиграть не может, а его противник (то есть Паша) следующим ходом выиграет.
Задача 8
Паша и Влад играют в увлекательную игру. Перед ними лежат две кучи камней, игроки ходят по очереди, первый ход делает Паша. За один ход каждый игрок может по выбору сделать одно из двух действий:
1. Прибавить к одной (любой) куче один камень.
2. Увеличить количество камней в одной (любой) куче в два раза.
Например, если в одной куче лежит 5 камней, а во второй 7. Обозначим эту ситуацию (5;7). Из этой позиции за один ход можно получить 4 варианта: (6; 7), (10; 7), (5, 8) и (5, 14).
Игра завершается, когда сумма камней в двух кучах становится не менее 77. Побеждает тот игрок, который сделал последний ход, то есть тот игрок, после хода которого сумма камней в двух кучах стала не менее 77. У игроков неограниченное количество камней для ходов.
В начальный момент времени в первой куче было 7 камней, а во второй S, где 1 ≤ S ≤ 69.
Будет говорить, что игрок имеет выигрышную стратегию, если он может победить при любых ходах соперника.
Для игры, описанной в 19-ом задании, найдите два значения S, при которых Паша имеет выигрышную стратегию, при которой одновременно выполняется два условия:
-Паша не выигрывает в первый ход;
-Паша выигрывает своим вторым ходом, независимо от хода Влада.
В качестве ответа укажите два числа в порядке возрастания слитно без запятых и разделителей.
Решение
Подходящие значения: 31 и 34.
Если начальная позиция (7; 31), Паша увеличивает количество камней в первой куче в два раза и получает позицию (14; 31).
Из позиции (14; 31) Влад может получить четыре различные позиции, ни в одной из которых он не побеждает: (15; 31), (28, 31), (14, 32), (14, 62).
В каждой из этих позиций Паша может выиграть своим вторым ходом: (15; 62), (28, 62), (14, 63), (14, 124).
Если начальная позиция (7; 34), Паша увеличивает количество камней в первой куче на один и получает позицию (8; 34).
Из позиции (8; 34) Влад может получить четыре различные позиции, ни в одной из которых он не побеждает: (9; 34), (16, 34), (8, 35), (8, 68).
В каждой из этих позиций Паша может выиграть своим вторым ходом: (9; 68), (16, 68), (8, 70), (8, 136).
Ответ: 3134.
Задача 9
Два игрока, Петя и Ваня, играют в следующую игру. Перед ними лежит набор слов, составленных из букв русского алфавита, при этом одно слово не является началом другого слова. Под словом подразумевается просто набор букв русского языка. Игра состоит в том, что игроки составляют слово из набора, приписывая по очереди буквы к концу составляемого слова, т.е. справа. При этом каждое промежуточное слово должно быть началом одного из заданных слов. Выигрывает тот, кто получит одно из заданных слов целиком. Первый ход делает Петя, т.е. Петя пишет первую букву составляемого слова.
Пример. Заданный набор слов: {АНАКОНДА, АПЕЛЬСИН, БОБ, БАКЛАЖАН, БАР}.
Первым ходом Петя пишет Б (он мог написать Б или А).
Ваня в ответ дописывает А и получает БА (он мог ещё получить БО).
Вторым ходом Петя получает БАР и выигрывает.
Укажите имя, у кого есть выигрышная стратегия при исходном наборе слов {КУХГНКУХГНХ, НГХУКНГХУК, КУХГНКУХГНЮЖ}.
Решение
Если двигаться по слову: КУХГНКУХГНХ, то Петя выиграет.
Задача 10
Два игрока, Петя и Ваня, играют в следующую игру. Перед игроками лежит несколько фишек. Игроки ходят по очереди, первый ход делает Петя и он просто кладёт фишку на игровое поле. За любой следующий один ход игрок может положить фишку на игровое поле справа от уже лежавшей на нём, при этом последняя цифра числа на фишке, которая уже лежит на столе, должна совпадать с первой цифрой числа фишки, которую собираются положить. Фишки нельзя поворачивать. Игра завершается в тот момент, когда нельзя будет положить фишку на игровое поле. Победителем считается игрок, сделавший последний ход.
Например, имея фишки 11, 14, 22, 23, 24 и 42, может быть следующая игра:
Петя кидает число 11, тогда Ваня выложит фишку 14, тогда Петя может положить фишку 42, а Ваня выложит 23 или 24 и выиграет, т.к. больше нет фишек, которые начинаются с 3 или 4.
Дан набор фишек: 11, 12, 13, 21, 22, 23, 31, 33
Будем говорить, что игрок имеет выигрышную стратегию, если он может выиграть при любых ходах противника. Описать стратегию игрока — значит описать, какой ход он должен сделать в любой ситуации, которая ему может встретиться при различной игре противника. В описание выигрышной стратегии не следует включать ходы играющего по этой стратегии игрока, не являющиеся для него безусловно выигрышными, т. е. не являющиеся выигрышными независимо от игры противника.
Если Петя в начале выложит фишку с номером 13, у кого из игроков есть выигрышная стратегия и сколько всего фишек будет лежать на столе? В ответе укажите имя игрока и количество фишек без пробелов.
Если выигрышных стратегий несколько, укажите наибольшую длину.
Ответ запишите в виде: Петя9
Решение
Для начального значения 13, партия может выглядеть следующим образом:
13 (Петя) - 33 (Ваня) - 31 (П) - 11 (В) - 12 (П) - 23 (В)
Задача 11
Два игрока, Паша и Влад, играют в увлекательную игру. Перед ними лежат две кучи камней. Игроки ходят по очереди, первый ход делает Паша. За один ход игрок может:
Добавить один камень в одну из куч;
Увеличить количество камней в любой куче в два раза.
Например, пусть в одной куче 10 камней, а в другой 6 камней. Обозначим такую позицию (10; 6). За один ход из позиции (10; 6) можно получить любую из четырёх позиций: (11; 6), (20; 6), (10; 7), (10; 12). У игроков есть неограниченное количество камней, чтобы делать ходы.
Игра завершается в тот момент, когда суммарное количество камней в двух кучах становится не менее 417. Победителем считается игрок, сделавший последний ход, то есть первым получивший позицию, в которой в двух кучах будет 417 или больше камней.
В начальный момент в первой куче было 46 камней, а во второй куче - S камней, где 1 ≤ S ≤ 370.
Будет говорить, что игрок имеет выигрышную стратегию, если он может победить при любых ходах соперника.
Найдите два наименьших значения S, при которых у Паши есть выигрышная стратегия, причём одновременно выполняются два условия:
Паша не может выиграть за один ход;
Паша может выиграть своим вторым ходом независимо от того, как будет ходить Влад.
В ответе запишите два числа в порядке возрастания без пробелов и разделителей.
Решение
Напишем код для решения №20:
def F(x, y, pos):
if pos == 0:
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 == 1:
if x+y >= 417:
return False
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 == 2:
if x+y >= 417:
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 == 3:
if x+y >= 417:
return True
else:
return False
for S in range(1, 371):
if F(46, S, 0):
print(S)
Два наименьших значений, выведенных в консоль: 162 и 184.
Ответ: 162184.
Задача 12
Два игрока, Паша и Влад, играют в увлекательную игру. Перед ними лежат две кучи камней. Игроки ходят по очереди, первый ход делает Паша. За один ход игрок может:
Добавить один камень в одну из куч;
Увеличить количество камней в любой куче в два раза.
Например, пусть в одной куче 10 камней, а в другой 6 камней. Обозначим такую позицию (10; 6). За один ход из позиции (10; 6) можно получить любую из четырёх позиций: (11; 6), (20; 6), (10; 7), (10; 12). У игроков есть неограниченное количество камней, чтобы делать ходы.
Игра завершается в тот момент, когда суммарное количество камней в двух кучах становится не менее 499. Победителем считается игрок, сделавший последний ход, то есть первым получивший позицию, в которой в двух кучах будет 499 или больше камней.
В начальный момент в первой куче было 5 камней, а во второй куче - S камней, где 1 ≤ S ≤ 493.
Будет говорить, что игрок имеет выигрышную стратегию, если он может победить при любых ходах соперника.
Найдите два наименьших значения S, при которых у Паши есть выигрышная стратегия, причём одновременно выполняются два условия:
Паша не может выиграть за один ход;
Паша может выиграть своим вторым ходом независимо от того, как будет ходить Влад.
В ответе запишите два числа в порядке возрастания без пробелов и разделителей.
Решение
Напишем код для решения №20:
def F(x, y, pos):
if pos == 0:
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 == 1:
if x+y >= 499:
return False
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 == 2:
if x+y >= 499:
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 == 3:
if x+y >= 499:
return True
else:
return False
for S in range(1, 493):
if F(5, S, 0):
print(S)
Два наименьших значений, выведенных в консоль: 244 и 246.
Ответ: 244246.
Задача 13
Два игрока, Паша и Влад, играют в увлекательную игру. Перед ними лежат две кучи камней. Игроки ходят по очереди, первый ход делает Паша. За один ход игрок может:
Добавить два камня в одну из куч;
Увеличить количество камней в любой куче в четыре раза.
Например, пусть в одной куче 10 камней, а в другой 6 камней. Обозначим такую позицию (10; 6). За один ход из позиции (10; 6) можно получить любую из четырёх позиций: (12; 6), (40; 6), (10; 8), (10; 24). У игроков есть неограниченное количество камней, чтобы делать ходы.
Игра завершается в тот момент, когда суммарное количество камней в двух кучах становится не менее 791. Победителем считается игрок, сделавший последний ход, то есть первым получивший позицию, в которой в двух кучах будет 791 или больше камней.
В начальный момент в первой куче было 42 камня, а во второй куче - S камней, где 1 ≤ S ≤ 748.
Будет говорить, что игрок имеет выигрышную стратегию, если он может победить при любых ходах соперника.
Найдите два наименьших значения S, при которых у Паши есть выигрышная стратегия, причём одновременно выполняются два условия:
Паша не может выиграть за один ход;
Паша может выиграть своим вторым ходом независимо от того, как будет ходить Влад.
В ответе запишите два числа в порядке возрастания без пробелов и разделителей.
Решение
Напишем код для решения №20:
def F(x, y, pos):
if pos == 0:
return (F(x+2,y, pos+1) or F(x*4,y, pos+1) or
F(x,y+2, pos+1) or F(x,y*4, pos+1))
elif pos == 1:
if x+y >= 791:
return False
else:
return (F(x+2,y, pos+1) and F(x*4,y, pos+1) and
F(x,y+2, pos+1) and F(x,y*4, pos+1))
elif pos == 2:
if x+y >= 791:
return False
else:
return (F(x+2,y, pos+1) or F(x*4,y, pos+1) or
F(x,y+2, pos+1) or F(x,y*4, pos+1))
elif pos == 3:
if x+y >= 791:
return True
else:
return False
for S in range(1, 749):
if F(42, S, 0):
print(S)
Два наименьших значений, выведенных в консоль: 117 и 118.
Ответ: 117118.
Задача 14
Два игрока, Паша и Влад, играют в увлекательную игру. Перед ними лежат две кучи камней. Игроки ходят по очереди, первый ход делает Паша. За один ход игрок может:
Добавить один камень в одну из куч;
Увеличить количество камней в любой куче в два раза.
Например, пусть в одной куче 10 камней, а в другой 6 камней. Обозначим такую позицию (10; 6). За один ход из позиции (10; 6) можно получить любую из четырёх позиций: (15; 6), (40; 6), (10; 11), (10; 24). У игроков есть неограниченное количество камней, чтобы делать ходы.
Игра завершается в тот момент, когда суммарное количество камней в двух кучах становится не менее 231. Победителем считается игрок, сделавший последний ход, то есть первым получивший позицию, в которой в двух кучах будет 740 или больше камней.
В начальный момент в первой куче было 17 камней, а во второй куче - S камней, где 1 ≤ S ≤ 214.
Будет говорить, что игрок имеет выигрышную стратегию, если он может победить при любых ходах соперника.
Найдите два наименьших значения S, при которых у Паши есть выигрышная стратегия, причём одновременно выполняются два условия:
Паша не может выиграть за один ход;
Паша может выиграть своим вторым ходом независимо от того, как будет ходить Влад.
В ответе запишите два числа в порядке возрастания без пробелов и разделителей.
Решение
Напишем код для решения №20:
def F(x, y, pos):
if pos == 0:
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 == 1:
if x+y >= 231:
return False
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 == 2:
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 == 3:
if x+y >= 231:
return True
else:
return False
for S in range(1, 214):
if F(17, S, 0):
print(S)
Два наименьших значений, выведенных в консоль: 98 и 106.
Ответ: 98106.
Задача 15
Паша и Влад играют в увлекательную игру. Перед ними лежит куча камней, игроки ходят по очереди, первый ход делает Паша. За один ход каждый игрок может по выбору сделать одно из двух действий:
1. Прибавить к куче два камня.
2. Увеличить количество камней в куче в два раза.
Например, если в куче лежит 5 камней, из этой позиции за один ход можно получить 7 или 10 камней.
Игра завершается, когда количество камней в куче становится не менее 32. Побеждает тот игрок, который сделал последний ход, то есть тот игрок, после хода которого количество камней в куче стало не менее 32. У игроков неограниченное количество камней для ходов.
В начальный момент времени в куче было S камней, где 1 ≤ S ≤ 28.
Будет говорить, что игрок имеет выигрышную стратегию, если он может победить при любых ходах соперника.
Для игры, описанной в 19-ом задании, найдите два наименьших значения S, при которых Паша имеет выигрышную стратегию, при которой одновременно выполняется два условия:
-Паша не выигрывает в первый ход;
-Паша выигрывает своим вторым ходом, независимо от хода Влада.
В качестве ответа укажите два числа в порядке возрастания слитно без запятых и разделителей.
Решение
Подходящие значения S: 12 и 7. В этих случаях Паша, очевидно, не может выиграть первым ходом. Однако, добавив в кучу с 12 камнями 2 камня или удвоив кучу из 7 камней, он может получить кучу из 14 камней. Эта позиция разобрана в задании 19.
Если в куче 14 камней, то игрок, который будет ходить (теперь это Влад), выиграть не может, а его противник (то есть Паша) следующим ходом выиграет.
Задача 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, при которых Паша имеет выигрышную стратегию, при которой одновременно выполняется два условия:
-Паша не выигрывает в первый ход;
-Паша выигрывает своим вторым ходом, независимо от хода Влада.
В качестве ответа укажите два числа в порядке возрастания слитно без запятых и разделителей.
Решение
Подходящие значения: 28 и 30.
Если начальная позиция (6; 28), Паша увеличивает количество камней в первой куче в два раза и получает позицию (12; 28).
Из позиции (12; 28) Влад может получить четыре различные позиции, ни в одной из которых он не побеждает: (13; 28), (24, 28), (12, 29), (12, 56).
В каждой из этих позиций Паша может выиграть своим вторым ходом: (13; 56), (24, 56), (12, 58), (12, 112).
Если начальная позиция (6; 30), Паша увеличивает количество камней во второй куче на один и получает позицию (6; 31).
Из позиции (6; 31) Влад может получить четыре различные позиции, ни в одной из которых он не побеждает: (7; 31), (12, 31), (6, 32), (6, 62).
В каждой из этих позиций Паша может выиграть своим вторым ходом: (7; 62), (12, 62), (6, 64), (6, 124).
Ответ: 2830.
Задача 17
Паша и Влад играют в увлекательную игру. Перед ними лежат две кучи камней, игроки ходят по очереди, первый ход делает Паша. За один ход каждый игрок может по выбору сделать одно из двух действий:
1. Прибавить к одной (любой) куче один камень.
2. Увеличить количество камней в одной (любой) куче в два раза.
Например, если в одной куче лежит 5 камней, а во второй 7. Обозначим эту ситуацию (5;7). Из этой позиции за один ход можно получить 4 варианта: (6; 7), (10; 7), (5, 8) и (5, 14).
Игра завершается, когда сумма камней в двух кучах становится не менее 83. Побеждает тот игрок, который сделал последний ход, то есть тот игрок, после хода которого сумма камней в двух кучах стала не менее 83. У игроков неограниченное количество камней для ходов.
В начальный момент времени в первой куче было 9 камней, а во второй S, где 1 ≤ S ≤ 73.
Будет говорить, что игрок имеет выигрышную стратегию, если он может победить при любых ходах соперника.
Для игры, описанной в 19-ом задании, найдите два значения S, при которых Паша имеет выигрышную стратегию, при которой одновременно выполняется два условия:
-Паша не выигрывает в первый ход;
-Паша выигрывает своим вторым ходом, независимо от хода Влада.
В качестве ответа укажите два числа в порядке возрастания слитно без запятых и разделителей.
Решение
Подходящие значения: 32 и 36.
Если начальная позиция (9; 32), Паша увеличивает количество камней в первой куче в два раза и получает позицию (18; 32).
Из позиции (18; 32) Влад может получить четыре различные позиции, ни в одной из которых он не побеждает: (19; 32), (36, 32), (18, 33), (18, 64).
В каждой из этих позиций Паша может выиграть своим вторым ходом: (19; 64), (36, 64), (18, 66), (18, 128).
Если начальная позиция (9; 36), Паша увеличивает количество камней в первой куче на один и получает позицию (10; 36).
Из позиции (10; 36) Влад может получить четыре различные позиции, ни в одной из которых он не побеждает: (11; 36), (20, 36), (10, 37), (10, 72).
В каждой из этих позиций Паша может выиграть своим вторым ходом: (11; 72), (20, 72), (10, 74), (10, 144).
Ответ: 3236.
Задача 18
Паша и Влад играют в увлекательную игру. Перед ними лежат две кучи камней, игроки ходят по очереди, первый ход делает Паша. За один ход каждый игрок может по выбору сделать одно из двух действий:
1. Прибавить к одной (любой) куче один камень.
2. Увеличить количество камней в одной (любой) куче в два раза.
Например, если в одной куче лежит 5 камней, а во второй 7. Обозначим эту ситуацию (5;7). Из этой позиции за один ход можно получить 4 варианта: (6; 7), (10; 7), (5, 8) и (5, 14).
Игра завершается, когда сумма камней в двух кучах становится не менее 77. Побеждает тот игрок, который сделал последний ход, то есть тот игрок, после хода которого сумма камней в двух кучах стала не менее 77. У игроков неограниченное количество камней для ходов.
В начальный момент времени в первой куче было 7 камней, а во второй S, где 1 ≤ S ≤ 69.
Будет говорить, что игрок имеет выигрышную стратегию, если он может победить при любых ходах соперника.
Для игры, описанной в 19-ом задании, найдите два значения S, при которых Паша имеет выигрышную стратегию, при которой одновременно выполняется два условия:
-Паша не выигрывает в первый ход;
-Паша выигрывает своим вторым ходом, независимо от хода Влада.
В качестве ответа укажите два числа в порядке возрастания слитно без запятых и разделителей.
Решение
Подходящие значения: 31 и 34.
Если начальная позиция (7; 31), Паша увеличивает количество камней в первой куче в два раза и получает позицию (14; 31).
Из позиции (14; 31) Влад может получить четыре различные позиции, ни в одной из которых он не побеждает: (15; 31), (28, 31), (14, 32), (14, 62).
В каждой из этих позиций Паша может выиграть своим вторым ходом: (15; 62), (28, 62), (14, 63), (14, 124).
Если начальная позиция (7; 34), Паша увеличивает количество камней в первой куче на один и получает позицию (8; 34).
Из позиции (8; 34) Влад может получить четыре различные позиции, ни в одной из которых он не побеждает: (9; 34), (16, 34), (8, 35), (8, 68).
В каждой из этих позиций Паша может выиграть своим вторым ходом: (9; 68), (16, 68), (8, 70), (8, 136).
Ответ: 3134.
Задача 19
Паша и Влад играют в увлекательную игру. Перед ними лежат две кучи камней, игроки ходят по очереди, первый ход делает Паша. За один ход каждый игрок может по выбору сделать одно из двух действий:
1. Прибавить к одной (любой) куче один камень.
2. Увеличить количество камней в одной (любой) куче в два раза.
Например, если в одной куче лежит 5 камней, а во второй 7. Обозначим эту ситуацию (5;7). Из этой позиции за один ход можно получить 4 варианта: (6; 7), (10; 7), (5, 8) и (5, 14).
Игра завершается, когда сумма камней в двух кучах становится не менее 61. Побеждает тот игрок, который сделал последний ход, то есть тот игрок, после хода которого сумма камней в двух кучах стала не менее 61. У игроков неограниченное количество камней для ходов.
В начальный момент времени в первой куче было 6 камней, а во второй S, где 1 ≤ S ≤ 54.
Будет говорить, что игрок имеет выигрышную стратегию, если он может победить при любых ходах соперника.
Для игры, описанной в 19-ом задании, найдите два значения S, при которых Паша имеет выигрышную стратегию и одновременно выполняется два условия:
-Паша не выигрывает в первый ход;
-Паша выигрывает своим вторым ходом, независимо от хода Влада.
В качестве ответа укажите два числа в порядке возрастания слитно без запятых и разделителей.
Решение
Подходящие значения: 24 и 26.
Если начальная позиция (6; 24), Паша увеличивает количество камней в первой куче в два раза и получает позицию (12; 24).
Из позиции (12; 24) Влад может получить четыре различные позиции, ни в одной из которых он не побеждает: (13; 24), (24, 24), (12, 25), (12, 48).
В каждой из этих позиций Паша может выиграть своим вторым ходом: (13; 48), (24, 48), (12, 50), (12, 96).
Если начальная позиция (6; 26), Паша увеличивает количество камней во второй куче на один и получает позицию (6; 27).
Из позиции (6; 27) Влад может получить четыре различные позиции, ни в одной из которых он не побеждает: (7; 27), (12, 27), (6, 28), (6, 54).
В каждой из этих позиций Паша может выиграть своим вторым ходом: (7; 54), (12, 54), (6, 56), (6, 108).
Решение при помощи программы на С++
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
Ответ: 2426.
Задача 20
Два игрока, Паша и Валя, играют в следующую игру. Перед игроками лежит куча камней. Игроки ходят по очереди, первый ход делает Паша. За один ход игрок может добавить в кучу один или четыре камня либо увеличить количество камней в куче в пять раз. Например, имея кучу из 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 хода. Для этого запускаем цикл:
for (int i = 0; i < 84; ++i)
if (S[i] == 2)
cout << i << " ";
Программа выдаст ответ: 12 15
Рекомендуемые курсы подготовки
- Узнаешь всё про кодирование: что это такое и как происходит
- Познакомишься с Условием Фано: как оно примняется и почему важно
- Научишься считать колиечтсво информации и сколько под неё нужно выделить памяти
на бесплатном курсе Турбо ЕГЭ
