ЕГЭ, Информатика: 20. Выигрышная стратегия: часть 2: все задания
Два игрока, Петя и Ваня, играют в следующую игру. Перед игроками лежит куча камней. Игроки ходят по очереди, первый ход делает Петя.
Для игры, описанной в задании $19$, найдите два наименьших значения $S$, при которых у Пети есть выигрышная стратегия, причём одновременно выполняются два условия:
- Петя не может выиграть за один ход;
- Петя может выиграть своим вторым ходом независимо от того, как будет ходить Ваня.
Найденные значения запишите в ответе в порядке возрастания без пробелов.
Первый способ – математическое решение
Петя не должен выигрывать первым ходом, поэтому $3S<79$, откуда $S\leq26$.
Чтобы Петя гарантированно выиграл вторым ходом, первым ходом ему нужно получить $25$ или $26$ камней.
При $25$ камнях Ваня может получить: $25\rightarrow27$ или $25\rightarrow75$.
Из обеих позиций Петя выигрывает следующим ходом:
$27\rightarrow81$;
$75\rightarrow225$.
При $26$ камнях: $26\rightarrow28$ или $26\rightarrow78$, и Петя также выигрывает следующим ходом:
$28\rightarrow84$;
$78\rightarrow80$.
Получить эти позиции можно так:
$23\rightarrow25$;
$24\rightarrow26$.
Второй способ – решение с помощью Python
def moves(x):
return [x + 2, x * 3]
def win1(x):
return x < 79 and any(
y >= 79 for y in moves(x)
)
ans = []
for S in range(1, 79):
if not win1(S):
if any(
x < 79 and all(
y < 79 and win1(y)
for y in moves(x)
)
for x in moves(S)
):
ans.append(S)
print(ans[:2])
Программа проверяет, что Петя не может выиграть первым ходом, а затем ищет такой его ход, после которого при любом ходе Вани Петя выигрывает следующим ходом.
Программа выведет: $[23,\ 24]$.
Два игрока, Петя и Ваня, играют в следующую игру. Перед игроками лежит куча камней. Игроки ходят по очереди, первый ход делает Петя.
Для игры, описанной в задании $19$, найдите два наименьших значения $S$, при которых у Пети есть выигрышная стратегия, причём одновременно выполняются два условия:
- Петя не может выиграть за один ход;
- Петя может выиграть своим вторым ходом независимо от того, как будет ходить Ваня.
Найденные значения запишите в ответе в порядке возрастания без пробелов.
Первый способ – математическое решение
Петя не должен выигрывать первым ходом, поэтому $S\leq36$.
Первое подходящее значение: $S=17$. Петя удваивает количество камней: $17\rightarrow34$.
Ваня может получить:
$34\rightarrow37$;
$34\rightarrow68$.
Из обеих позиций Петя выигрывает следующим ходом:
$37\rightarrow74$;
$68\rightarrow136$.
Второе подходящее значение: $S=18$. Петя получает: $18\rightarrow36$.
Ваня может получить:
$36\rightarrow39$;
$36\rightarrow72$.
Из обеих позиций Петя выигрывает:
$39\rightarrow78$;
$72\rightarrow75$.
Второй способ – решение с помощью Python
def moves(x):
return [x + 3, x * 2]
def win1(x):
return x < 73 and any(
y >= 73 for y in moves(x)
)
ans = []
for S in range(1, 73):
if not win1(S):
if any(
x < 73 and all(
y < 73 and win1(y)
for y in moves(x)
)
for x in moves(S)
):
ans.append(S)
print(ans[:2])
Программа проверяет, что Петя не может выиграть первым ходом, а затем ищет такой его ход, после которого при любом ходе Вани Петя выигрывает следующим ходом.
Программа выведет: $[17,\ 18]$.
Два игрока, Петя и Ваня, играют в следующую игру. Перед игроками лежат две кучи камней. Игроки ходят по очереди, первый ход делает Петя.
Известно, что Ваня выиграл своим первым ходом после неудачного первого хода Пети.
Для игры, описанной в задании $19$, найдите два наименьших значения $S$, при которых у Пети есть выигрышная стратегия, причём одновременно выполняются два условия:
- Петя не может выиграть за один ход;
- Петя может выиграть своим вторым ходом независимо от того, как будет ходить Ваня.
Найденные значения запишите в ответе в порядке возрастания без пробелов.
Первый способ – математическое решение
Петя не должен выигрывать первым ходом, поэтому:
$7+2S<101$,
$S\leq46$.
Первое подходящее значение: $S=23$. Петя удваивает вторую кучу: $(7;23)\rightarrow(7;46)$.
Ваня может получить: $(9;46),\ (7;48),\ (14;46),\ (7;92)$.
Из каждой такой позиции Петя выигрывает следующим ходом:
- $(9;46)\rightarrow(9;92)$, сумма $101$;
- $(7;48)\rightarrow(7;96)$, сумма $103$;
- $(14;46)\rightarrow(14;92)$, сумма $106$;
- $(7;92)\rightarrow(9;92)$, сумма $101$.
Второе подходящее значение: $S=43$. Петя удваивает первую кучу: $(7;43)\rightarrow(14;43)$.
Ваня может получить: $(16;43),\ (14;45),\ (28;43),\ (14;86)$.
Из каждой такой позиции Петя также выигрывает следующим ходом.
Второй способ – решение с помощью Python
def moves(a, b):
return [(a + 2, b), (a, b + 2),
(a * 2, b), (a, b * 2)]
def win1(a, b):
return a + b < 101 and any(
x + y >= 101 for x, y in moves(a, b)
)
ans = []
for S in range(1, 94):
if not win1(7, S):
if any(
all(
x + y < 101 and win1(x, y)
for x, y in moves(a, b)
)
for a, b in moves(7, S)
):
ans.append(S)
print(ans[:2])
Программа проверяет, что Петя не может выиграть первым ходом, а затем ищет такой его ход, после которого при любом ходе Вани Петя выигрывает следующим ходом.
Программа выведет: $[23,\ 43]$.
Два игрока, Петя и Ваня, играют в следующую игру. Перед игроками лежат две кучи камней. Игроки ходят по очереди, первый ход делает Петя.
Известно, что Ваня выиграл своим первым ходом после неудачного хода Пети.
Для игры, описанной в задании $19$, найдите два наименьших значения $S$, при которых у Пети есть выигрышная стратегия, причём одновременно выполняются два условия:
- Петя не может выиграть за один ход;
- Петя может выиграть своим вторым ходом независимо от того, как будет ходить Ваня.
Найденные значения запишите в ответе в порядке возрастания без пробелов.
Первый способ – математическое решение
Петя не должен выигрывать первым ходом, поэтому:
$9+2S<129$,
$S\leq59$.
Первое подходящее значение: $S=54$. Петя удваивает первую кучу: $(9;54)\rightarrow(18;54)$.
Ваня может получить: $(21;54),\ (18;57),\ (36;54),\ (18;108)$.
Из каждой такой позиции Петя выигрывает следующим ходом:
- $(21;54)\rightarrow(21;108)$, сумма $129$;
- $(18;57)\rightarrow(18;114)$, сумма $132$;
- $(36;54)\rightarrow(36;108)$, сумма $144$;
- $(18;108)\rightarrow(21;108)$, сумма $129$.
При $S=55$ Петя действует так же: $(9;55)\rightarrow(18;55)$, и после любого хода Вани выигрывает следующим ходом.
Для $S<54$ гарантированной победы вторым ходом у Пети нет.
Второй способ – решение с помощью Python
def moves(a, b):
return [(a + 3, b), (a, b + 3),
(a * 2, b), (a, b * 2)]
def win1(a, b):
return a + b < 129 and any(
x + y >= 129 for x, y in moves(a, b)
)
ans = []
for S in range(1, 120):
if not win1(9, S):
if any(
all(
x + y < 129 and win1(x, y)
for x, y in moves(a, b)
)
for a, b in moves(9, S)
):
ans.append(S)
print(ans[:2])
Программа проверяет, что Петя не может выиграть первым ходом, а затем ищет такой его ход, после которого при любом ходе Вани Петя выигрывает следующим ходом.
Программа выведет: $[54,\ 55]$.
Два игрока, Петя и Ваня, играют в следующую игру. Перед игроками лежат две кучи камней. Игроки ходят по очереди, первый ход делает Петя.
Известно, что Ваня выиграл своим первым ходом после неудачного первого хода Пети.
Для игры, описанной в задании $19$, найдите два наименьших значения $S$, при которых у Пети есть выигрышная стратегия, причём одновременно выполняются два условия:
- Петя не может выиграть за один ход;
- Петя может выиграть своим вторым ходом независимо от того, как будет ходить Ваня.
Найденные значения запишите в ответе в порядке возрастания без пробелов.
Первый способ – математическое решение
Петя не должен выигрывать первым ходом, поэтому:
$8+3S<97$,
$S\leq29$.
Первое подходящее значение: $S=23$. Петя утраивает первую кучу: $(8;23)\rightarrow(24;23)$.
Ваня может получить: $(26;23),\ (24;25),\ (72;23),\ (24;69)$.
Из каждой такой позиции Петя выигрывает следующим ходом:
- $(26;23)\rightarrow(78;23)$, сумма $101$;
- $(24;25)\rightarrow(72;25)$, сумма $97$;
- $(72;23)\rightarrow(74;23)$, сумма $97$;
- $(24;69)\rightarrow(26;69)$, сумма $95$ — этот ход не выигрывает, поэтому Петя утраивает первую кучу: $(72;69)$, сумма $141$.
При $S=24$ Петя действует аналогично: $(8;24)\rightarrow(24;24)$, и после любого хода Вани выигрывает следующим ходом.
Для $S<23$ гарантированной победы вторым ходом у Пети нет.
Второй способ – решение с помощью Python
def moves(a, b):
return [(a + 2, b), (a, b + 2),
(a * 3, b), (a, b * 3)]
def win1(a, b):
return a + b < 97 and any(
x + y >= 97 for x, y in moves(a, b)
)
ans = []
for S in range(1, 89):
if not win1(8, S):
if any(
all(
x + y < 97 and win1(x, y)
for x, y in moves(a, b)
)
for a, b in moves(8, S)
):
ans.append(S)
print(ans[:2])
Программа проверяет, что Петя не может выиграть первым ходом, а затем ищет такой его ход, после которого при любом ходе Вани Петя выигрывает следующим ходом.
Программа выведет: $[23,\ 24]$.
Два игрока, Петя и Ваня, играют в следующую игру. Перед игроками лежит куча камней. Игроки ходят по очереди, первый ход делает Петя.
Для игры, описанной в задании $19$, найдите два наименьших значения $S$, при которых у Пети есть выигрышная стратегия, причём одновременно выполняются два условия:
- Петя не может выиграть за один ход;
- Петя может выиграть своим вторым ходом независимо от того, как будет ходить Ваня.
Найденные значения запишите в ответе в порядке возрастания.
Первый способ – математическое решение
Подходящими промежуточными позициями являются $29$ и $30$ камней. Если Петя получает $30$ камней, Ваня может сделать ходы: $30\rightarrow32,\ 35,\ 60$.
Из каждой позиции Петя выигрывает следующим ходом:
$32\rightarrow64$;
$35\rightarrow70$;
$60\rightarrow62$.
Аналогично для $29$ камней: $29\rightarrow31,\ 34,\ 58$, после чего Петя также выигрывает следующим ходом.
Два наименьших начальных значения, из которых Петя может получить $29$ или $30$:
$15\rightarrow30$;
$24\rightarrow29$.
Второй способ – решение с помощью Python
def moves(x):
return [x + 2, x + 5, x * 2]
def win1(x):
return x < 61 and any(
y >= 61 for y in moves(x)
)
ans = []
for S in range(1, 61):
if not win1(S):
if any(
x < 61 and all(
y < 61 and win1(y)
for y in moves(x)
)
for x in moves(S)
):
ans.append(S)
print(ans[:2])
Программа проверяет, что Петя не может выиграть первым ходом, а затем ищет такой его ход, после которого при любом ходе Вани Петя выигрывает следующим ходом.
Программа выведет: $[15,\ 24]$.
Два игрока, Петя и Ваня, играют в следующую игру. Перед игроками лежит куча камней. Игроки ходят по очереди, первый ход делает Петя.
Для игры, описанной в задании $19$, найдите два наименьших значения $S$, при которых у Пети есть выигрышная стратегия, причём одновременно выполняются два условия:
- Петя не может выиграть за один ход;
- Петя может выиграть своим вторым ходом независимо от того, как будет ходить Ваня.
Найденные значения запишите в ответе в порядке возрастания без пробела.
Первый способ – математическое решение
Пете первым ходом нужно получить $26$ или $27$ камней.
Если получено $26$: $26\rightarrow28,\ 31,\ 78$.
Из каждой позиции Петя выигрывает следующим ходом:
$28\rightarrow84$;
$31\rightarrow93$;
$78\rightarrow83$.
Если получено $27$: $27\rightarrow29,\ 32,\ 81$, и Петя также выигрывает следующим ходом.
Два наименьших начальных значения:
$9\rightarrow27$;
$21\rightarrow26$.
Второй способ – решение с помощью Python
def moves(x):
return [x + 2, x + 5, x * 3]
def win1(x):
return x < 83 and any(
y >= 83 for y in moves(x)
)
ans = []
for S in range(1, 83):
if not win1(S):
if any(
x < 83 and all(
y < 83 and win1(y)
for y in moves(x)
)
for x in moves(S)
):
ans.append(S)
print(ans[:2])
Программа проверяет, что Петя не может выиграть первым ходом, а затем ищет такой его ход, после которого при любом ходе Вани Петя выигрывает следующим ходом.
Программа выведет: $[9,\ 21]$.
Два игрока, Петя и Ваня, играют в следующую игру. Перед игроками лежит куча камней. Игроки ходят по очереди, первый ход делает Петя.
Для игры, описанной в задании $19$, найдите два наименьших значения $S$, при которых у Пети есть выигрышная стратегия, причём одновременно выполняются два условия:
- Петя не может выиграть за один ход;
- Петя может выиграть своим вторым ходом независимо от того, как будет ходить Ваня.
Найденные значения запишите в ответе в порядке возрастания без пробелов.
Первый способ – математическое решение
Петя первым ходом должен получить $28$ камней.
После этого Ваня может получить: $28\rightarrow29,\ 31,\ 56$.
Из каждой такой позиции Петя выигрывает следующим ходом:
$29\rightarrow58$;
$31\rightarrow62$;
$56\rightarrow57$.
Получить $28$ камней Петя может так:
$14\rightarrow28$;
$25\rightarrow28$;
$27\rightarrow28$.
Два наименьших значения: $S=14$ и $S=25$.
Второй способ – решение с помощью Python
def moves(x):
return [x + 1, x + 3, x * 2]
def win1(x):
return x < 57 and any(
y >= 57 for y in moves(x)
)
ans = []
for S in range(1, 57):
if not win1(S):
if any(
x < 57 and all(
y < 57 and win1(y)
for y in moves(x)
)
for x in moves(S)
):
ans.append(S)
print(ans[:2])
Программа проверяет, что Петя не может выиграть первым ходом, а затем ищет такой его ход, после которого при любом ходе Вани Петя выигрывает следующим ходом.
Программа выведет: $[14,\ 25]$.
Два игрока, Петя и Ваня, играют в следующую игру. Перед игроками лежит куча камней. Игроки ходят по очереди, первый ход делает Петя.
Для игры, описанной в задании $19$, найдите два наименьших значения $S$, при которых у Пети есть выигрышная стратегия, причём одновременно выполняются два условия:
- Петя не может выиграть за один ход;
- Петя может выиграть своим вторым ходом независимо от того, как будет ходить Ваня.
Найденные значения запишите в ответе в порядке возрастания.
Первый способ – математическое решение
Пете первым ходом нужно получить $34$ камня.
После этого Ваня может получить: $34\rightarrow36,\ 39,\ 68$.
Из каждой такой позиции Петя выигрывает следующим ходом:
$36\rightarrow72$;
$39\rightarrow78$;
$68\rightarrow73$.
Получить $34$ камня Петя может так:
$17\rightarrow34$;
$29\rightarrow34$;
$32\rightarrow34$.
Два наименьших значения: $S=17$ и $S=29$.
Второй способ – решение с помощью Python
def moves(x):
return [x + 2, x + 5, x * 2]
def win1(x):
return x < 72 and any(
y >= 72 for y in moves(x)
)
ans = []
for S in range(1, 72):
if not win1(S):
if any(
x < 72 and all(
y < 72 and win1(y)
for y in moves(x)
)
for x in moves(S)
):
ans.append(S)
print(ans[:2])
Программа проверяет, что Петя не может выиграть первым ходом, а затем ищет такой его ход, после которого при любом ходе Вани Петя выигрывает следующим ходом.
Программа выведет: $[17,\ 29]$.
Два игрока, Петя и Ваня, играют в следующую игру. Перед игроками лежит куча камней. Игроки ходят по очереди, первый ход делает Петя.
Для игры, описанной в задании $19$, найдите два наименьших значения $S$, при которых у Пети есть выигрышная стратегия, причём одновременно выполняются два условия:
- Петя не может выиграть за один ход;
- Петя может выиграть своим вторым ходом независимо от того, как будет ходить Ваня.
Найденные значения запишите в ответе в порядке возрастания без пробелов.
Первый способ – математическое решение
Пете первым ходом нужно получить $26$ камней.
После этого Ваня может получить: $26\rightarrow27,\ 30,\ 78$.
Из каждой такой позиции Петя выигрывает следующим ходом:
$27\rightarrow81$;
$30\rightarrow90$;
$78\rightarrow79$.
Получить $26$ камней Петя может двумя минимальными способами:
$22\rightarrow26$;
$25\rightarrow26$.
Второй способ – решение с помощью Python
def moves(x):
return [x + 1, x + 4, x * 3]
def win1(x):
return x < 79 and any(
y >= 79 for y in moves(x)
)
ans = []
for S in range(1, 79):
if not win1(S):
if any(
x < 79 and all(
y < 79 and win1(y)
for y in moves(x)
)
for x in moves(S)
):
ans.append(S)
print(ans[:2])
Программа проверяет, что Петя не может выиграть первым ходом, а затем ищет такой его ход, после которого при любом ходе Вани Петя выигрывает следующим ходом.
Программа выведет: $[22,\ 25]$.