Дошкольникам
1 класс
2 класс
3 класс
4 класс
5 класс
6 класс
7 класс
8 класс
9 класс
10 класс
11 класс
ОГЭ
ЕГЭ
ВУЗ
Для всех
Назад

ЕГЭ, Информатика: 20. Выигрышная стратегия: часть 2: все задания

21. Задание #295291
Решено верно
Решено неверно
Сообщить о проблеме

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

За один ход игрок может добавить в кучу $2$ камня или увеличить количество камней в куче в $3$ раза. Для того чтобы делать ходы, у каждого игрока есть неограниченное количество камней.

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

В начальный момент в куче было $S$ камней; $1 \leq S \leq 78$.

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

Для игры, описанной в задании $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]$.

Показать
Очки опыта 20
Спросить Зави
22. Задание #295294
Решено верно
Решено неверно
Сообщить о проблеме

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

За один ход игрок может добавить в кучу $3$ камня или увеличить количество камней в куче в $2$ раза. Для того чтобы делать ходы, у каждого игрока есть неограниченное количество камней.

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

В начальный момент в куче было $S$ камней; $1 \leq S \leq 72$.

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

Для игры, описанной в задании $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]$.

Показать
Очки опыта 20
Спросить Зави
23. Задание #295298
Решено верно
Решено неверно
Сообщить о проблеме

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

За один ход игрок может:
– добавить в одну из куч (по своему выбору) $2$ камня;
– увеличить количество камней в одной из куч (по своему выбору) в $2$ раза.

Например, пусть в одной куче $20$ камней, а в другой $30$ камней; такую позицию в игре обозначим $(20, 30)$. Тогда за один ход можно получить любую из четырёх позиций: $(22, 30)$, $(20, 32)$, $(40, 30)$, $(20, 60)$.

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

В начальный момент в первой куче было $7$ камней, во второй куче – $S$ камней; $1 \leq S \leq 93$.

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

Известно, что Ваня выиграл своим первым ходом после неудачного первого хода Пети.

Для игры, описанной в задании $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]$.

Показать
Очки опыта 20
Спросить Зави
24. Задание #295302
Решено верно
Решено неверно
Сообщить о проблеме

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

За один ход игрок может:
– добавить в одну из куч (по своему выбору) $3$ камня;
– увеличить количество камней в одной из куч (по своему выбору) в $2$ раза.

Например, пусть в одной куче $20$ камней, а в другой $30$ камней; такую позицию в игре обозначим $(20, 30)$. Тогда за один ход можно получить любую из четырёх позиций: $(23, 30)$, $(20, 33)$, $(40, 30)$, $(20, 60)$.

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

В начальный момент в первой куче было $9$ камней, во второй куче – $S$ камней; $1 \leq S \leq 119$.

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

Известно, что Ваня выиграл своим первым ходом после неудачного хода Пети.

Для игры, описанной в задании $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]$.

Показать
Очки опыта 20
Спросить Зави
25. Задание #295309
Решено верно
Решено неверно
Сообщить о проблеме

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

За один ход игрок может:
– добавить в одну из куч (по своему выбору) $2$ камня;
– увеличить количество камней в одной из куч (по своему выбору) в $3$ раза.

Например, пусть в одной куче $20$ камней, а в другой $30$ камней; такую позицию в игре обозначим $(20, 30)$. Тогда за один ход можно получить любую из четырёх позиций: $(22, 30)$, $(20, 32)$, $(60, 30)$, $(20, 90)$.

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

В начальный момент в первой куче было $8$ камней, во второй куче – $S$ камней; $1 \leq S \leq 88$.

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

Известно, что Ваня выиграл своим первым ходом после неудачного первого хода Пети.

Для игры, описанной в задании $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]$.

Показать
Очки опыта 20
Спросить Зави
26. Задание #295312
Решено верно
Решено неверно
Сообщить о проблеме

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

За один ход игрок может добавить в кучу $2$ или $5$ камней либо увеличить количество камней в куче в $2$ раза. У каждого игрока есть неограниченное количество камней, чтобы делать ходы.

Игра завершается в тот момент, когда количество камней в куче становится не менее $61$.

Победителем считается игрок, сделавший последний ход, т.е. первым получивший кучу, в которой находится $61$ камень или больше.

В начальный момент в куче было $S$ камней; $1 \leq S \leq 60$.

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

Для игры, описанной в задании $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]$.

Показать
Очки опыта 20
Спросить Зави
27. Задание #295339
Решено верно
Решено неверно
Сообщить о проблеме

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

За один ход игрок может добавить в кучу $2$ или $5$ камней либо увеличить количество камней в куче в $3$ раза. У каждого игрока есть неограниченное количество камней, чтобы делать ходы.

Игра завершается в тот момент, когда количество камней в куче становится не менее $83$.

Победителем считается игрок, сделавший последний ход, т.е. первым получивший кучу, в которой находится $83$ камня или больше.

В начальный момент в куче было $S$ камней; $1 \leq S \leq 82$.

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

Для игры, описанной в задании $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]$.

Показать
Очки опыта 20
Спросить Зави
28. Задание #295351
Решено верно
Решено неверно
Сообщить о проблеме

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

За один ход игрок может добавить в кучу один или три камня либо увеличить количество камней в куче в два раза. У каждого игрока есть неограниченное количество камней, чтобы делать ходы.

Игра завершается в тот момент, когда количество камней в куче становится не менее $57$.

Победителем считается игрок, сделавший последний ход, т.е. первым получивший кучу, в которой находится $57$ камней или больше.

В начальный момент в куче было $S$ камней; $1 \leq S \leq 56$.

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

Для игры, описанной в задании $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]$.

Показать
Очки опыта 20
Спросить Зави
29. Задание #295365
Решено верно
Решено неверно
Сообщить о проблеме

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

За один ход игрок может добавить в кучу $2$ или $5$ камней либо увеличить количество камней в куче в $2$ раза. У каждого игрока есть неограниченное количество камней, чтобы делать ходы.

Игра завершается в тот момент, когда количество камней в куче становится не менее $72$.

Победителем считается игрок, сделавший последний ход, т.е. первым получивший кучу, в которой находится $72$ камня или больше.

В начальный момент в куче было $S$ камней; $1 \leq S \leq 71$.

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

Для игры, описанной в задании $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]$.

Показать
Очки опыта 20
Спросить Зави
30. Задание #295369
Решено верно
Решено неверно
Сообщить о проблеме

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

За один ход игрок может добавить в кучу один или четыре камня либо увеличить количество камней в куче в три раза. У каждого игрока есть неограниченное количество камней, чтобы делать ходы.

Игра завершается в тот момент, когда количество камней в куче становится не менее $79$.

Победителем считается игрок, сделавший последний ход, т.е. первым получивший кучу, в которой находится $79$ камней или больше.

В начальный момент в куче было $S$ камней; $1 \leq S \leq 78$.

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

Для игры, описанной в задании $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]$.

Показать
Очки опыта 20
Спросить Зави
03:50:00
Решено заданий: 0 из
0 заданий сегодня

Предложить улучшение