Теория игр: Петя выигрывает вторым ходом

Два игрока, Петя и Ваня, играют в следующую игру. Перед игроками лежит куча камней. Игроки ходят по очереди, первый ход делает Петя. За один ход игрок может:
– убрать из кучи 1 камень;
– убрать из кучи 7 камней;
– уменьшить количество камней в куче в 2 раза (количество камней, полученное при делении, округляется до меньшего).
Например, из кучи в 45 камней за один ход можно получить кучу из 44, 38, 22 камней. Игра завершается, когда количество камней в куче становится не более 25. Победителем считается игрок, сделавший последний ход, то есть первым получивший кучу из 25 или менее камней. В начальный момент в куче было S камней, S ≥ 26.

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

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

def f(s, m):
    if s <= 25:
        return m % 2 == 0
    if m == 0:
        return False
    h = [f(x, m - 1) for x in (s - 1, s - 7, s // 2)]
    return any(h) if m % 2 != 0 else all(h)

res = [s for s in range(26, 425) if f(s, 3) and not f(s, 1)]
print(res[0], res[1])

Два игрока, Петя и Ваня, играют в следующую игру. Перед игроками лежит куча камней. Игроки ходят по очереди, первый ход делает Петя. За один ход игрок может:
– добавить в кучу 2 камня;
– добавить в кучу 4 камня;
– увеличить количество камней в куче в 3 раза.
Например, из кучи в 10 камней за один ход можно получить кучу из 12, 14, 30 камней. Игра завершается, когда количество камней в куче становится не менее 119. Победителем считается игрок, сделавший последний ход, то есть первым получивший кучу из 119 или более камней. В начальный момент в куче было S камней, 1 ≤ S ≤ 118.

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

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

def f(s, m):
    if s >= 119:
        return m % 2 == 0
    if m == 0:
        return False
    h = [f(x, m - 1) for x in (s + 2, s + 4, s * 3)]
    return any(h) if m % 2 != 0 else all(h)

res = [s for s in range(1, 119) if f(s, 3) and not f(s, 1)]
print(res[0], res[1])

Два игрока, Петя и Ваня, играют в следующую игру. Перед игроками лежат две кучи камней. Игроки ходят по очереди, первый ход делает Петя. За один ход игрок может:
– добавить в одну из куч 1 камень;
– увеличить количество камней в одной из куч в 3 раза.
Например, пусть в одной куче 10 камней, а в другой — 7; такую позицию обозначим (10, 7). За один ход из неё можно получить любую из позиций: (10, 8), (10, 21), (11, 7), (30, 7). Игра завершается, когда суммарное количество камней в кучах становится не менее 94. Победителем считается игрок, сделавший последний ход. В начальный момент в первой куче было 9 камней, во второй — S камней, 1 ≤ S ≤ 84.

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

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

def f(a, b, m):
    if a + b >= 94:
        return m % 2 == 0
    if m == 0:
        return False
    h = [f(x, y, m - 1) for x, y in ((a + 1, b), (a * 3, b), (a, b + 1), (a, b * 3))]
    return any(h) if m % 2 != 0 else all(h)

res = [s for s in range(1, 85) if f(9, s, 3) and not f(9, s, 1)]
print(res[0], res[1])

Два игрока, Петя и Ваня, играют в следующую игру. Перед игроками лежит куча камней. Игроки ходят по очереди, первый ход делает Петя. За один ход игрок может:
– добавить в кучу 1 камень;
– добавить в кучу 4 камня;
– увеличить количество камней в куче в 3 раза.
Например, из кучи в 10 камней за один ход можно получить кучу из 11, 14, 30 камней. Игра завершается, когда количество камней в куче становится не менее 66. Победителем считается игрок, сделавший последний ход, то есть первым получивший кучу из 66 или более камней. В начальный момент в куче было S камней, 1 ≤ S ≤ 65.

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

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

def f(s, m):
    if s >= 66:
        return m % 2 == 0
    if m == 0:
        return False
    h = [f(x, m - 1) for x in (s + 1, s + 4, s * 3)]
    return any(h) if m % 2 != 0 else all(h)

res = [s for s in range(1, 66) if f(s, 3) and not f(s, 1)]
print(res[0], res[1])

Два игрока, Петя и Ваня, играют в следующую игру. Перед игроками лежит куча камней. Игроки ходят по очереди, первый ход делает Петя. За один ход игрок может:
– убрать из кучи 1 камень;
– убрать из кучи 6 камней;
– уменьшить количество камней в куче в 3 раза (количество камней, полученное при делении, округляется до меньшего).
Например, из кучи в 40 камней за один ход можно получить кучу из 39, 34, 13 камней. Игра завершается, когда количество камней в куче становится не более 20. Победителем считается игрок, сделавший последний ход, то есть первым получивший кучу из 20 или менее камней. В начальный момент в куче было S камней, S ≥ 21.

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

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

def f(s, m):
    if s <= 20:
        return m % 2 == 0
    if m == 0:
        return False
    h = [f(x, m - 1) for x in (s - 1, s - 6, s // 3)]
    return any(h) if m % 2 != 0 else all(h)

res = [s for s in range(21, 420) if f(s, 3) and not f(s, 1)]
print(res[0], res[1])

Два игрока, Петя и Ваня, играют в следующую игру. Перед игроками лежат две кучи камней. Игроки ходят по очереди, первый ход делает Петя. За один ход игрок может:
– добавить в одну из куч 1 камень;
– увеличить количество камней в одной из куч в 2 раза.
Например, пусть в одной куче 10 камней, а в другой — 7; такую позицию обозначим (10, 7). За один ход из неё можно получить любую из позиций: (10, 8), (10, 14), (11, 7), (20, 7). Игра завершается, когда суммарное количество камней в кучах становится не менее 77. Победителем считается игрок, сделавший последний ход. В начальный момент в первой куче было 5 камней, во второй — S камней, 1 ≤ S ≤ 71.

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

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

def f(a, b, m):
    if a + b >= 77:
        return m % 2 == 0
    if m == 0:
        return False
    h = [f(x, y, m - 1) for x, y in ((a + 1, b), (a * 2, b), (a, b + 1), (a, b * 2))]
    return any(h) if m % 2 != 0 else all(h)

res = [s for s in range(1, 72) if f(5, s, 3) and not f(5, s, 1)]
print(res[0], res[1])

Два игрока, Петя и Ваня, играют в следующую игру. Перед игроками лежит куча камней. Игроки ходят по очереди, первый ход делает Петя. За один ход игрок может:
– убрать из кучи 2 камня;
– убрать из кучи 6 камней;
– уменьшить количество камней в куче в 3 раза (количество камней, полученное при делении, округляется до меньшего).
Например, из кучи в 45 камней за один ход можно получить кучу из 43, 39, 15 камней. Игра завершается, когда количество камней в куче становится не более 25. Победителем считается игрок, сделавший последний ход, то есть первым получивший кучу из 25 или менее камней. В начальный момент в куче было S камней, S ≥ 26.

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

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

def f(s, m):
    if s <= 25:
        return m % 2 == 0
    if m == 0:
        return False
    h = [f(x, m - 1) for x in (s - 2, s - 6, s // 3)]
    return any(h) if m % 2 != 0 else all(h)

res = [s for s in range(26, 425) if f(s, 3) and not f(s, 1)]
print(res[0], res[1])

Два игрока, Петя и Ваня, играют в следующую игру. Перед игроками лежит куча камней. Игроки ходят по очереди, первый ход делает Петя. За один ход игрок может:
– добавить в кучу 1 камень;
– добавить в кучу 4 камня;
– увеличить количество камней в куче в 3 раза.
Например, из кучи в 10 камней за один ход можно получить кучу из 11, 14, 30 камней. Игра завершается, когда количество камней в куче становится не менее 117. Победителем считается игрок, сделавший последний ход, то есть первым получивший кучу из 117 или более камней. В начальный момент в куче было S камней, 1 ≤ S ≤ 116.

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

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

def f(s, m):
    if s >= 117:
        return m % 2 == 0
    if m == 0:
        return False
    h = [f(x, m - 1) for x in (s + 1, s + 4, s * 3)]
    return any(h) if m % 2 != 0 else all(h)

res = [s for s in range(1, 117) if f(s, 3) and not f(s, 1)]
print(res[0], res[1])

Два игрока, Петя и Ваня, играют в следующую игру. Перед игроками лежат две кучи камней. Игроки ходят по очереди, первый ход делает Петя. За один ход игрок может:
– добавить в одну из куч 2 камня;
– увеличить количество камней в одной из куч в 2 раза.
Например, пусть в одной куче 10 камней, а в другой — 7; такую позицию обозначим (10, 7). За один ход из неё можно получить любую из позиций: (10, 9), (10, 14), (12, 7), (20, 7). Игра завершается, когда суммарное количество камней в кучах становится не менее 58. Победителем считается игрок, сделавший последний ход. В начальный момент в первой куче было 12 камней, во второй — S камней, 1 ≤ S ≤ 45.

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

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

def f(a, b, m):
    if a + b >= 58:
        return m % 2 == 0
    if m == 0:
        return False
    h = [f(x, y, m - 1) for x, y in ((a + 2, b), (a * 2, b), (a, b + 2), (a, b * 2))]
    return any(h) if m % 2 != 0 else all(h)

res = [s for s in range(1, 46) if f(12, s, 3) and not f(12, s, 1)]
print(res[0], res[1])

Два игрока, Петя и Ваня, играют в следующую игру. Перед игроками лежит куча камней. Игроки ходят по очереди, первый ход делает Петя. За один ход игрок может:
– убрать из кучи 1 камень;
– убрать из кучи 4 камня;
– уменьшить количество камней в куче в 2 раза (количество камней, полученное при делении, округляется до меньшего).
Например, из кучи в 40 камней за один ход можно получить кучу из 39, 36, 20 камней. Игра завершается, когда количество камней в куче становится не более 20. Победителем считается игрок, сделавший последний ход, то есть первым получивший кучу из 20 или менее камней. В начальный момент в куче было S камней, S ≥ 21.

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

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

def f(s, m):
    if s <= 20:
        return m % 2 == 0
    if m == 0:
        return False
    h = [f(x, m - 1) for x in (s - 1, s - 4, s // 2)]
    return any(h) if m % 2 != 0 else all(h)

res = [s for s in range(21, 420) if f(s, 3) and not f(s, 1)]
print(res[0], res[1])

Два игрока, Петя и Ваня, играют в следующую игру. Перед игроками лежит куча камней. Игроки ходят по очереди, первый ход делает Петя. За один ход игрок может:
– добавить в кучу 1 камень;
– добавить в кучу 4 камня;
– увеличить количество камней в куче в 3 раза.
Например, из кучи в 10 камней за один ход можно получить кучу из 11, 14, 30 камней. Игра завершается, когда количество камней в куче становится не менее 103. Победителем считается игрок, сделавший последний ход, то есть первым получивший кучу из 103 или более камней. В начальный момент в куче было S камней, 1 ≤ S ≤ 102.

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

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

Два игрока, Петя и Ваня, играют в следующую игру. Перед игроками лежит куча камней. Игроки ходят по очереди, первый ход делает Петя. За один ход игрок может:
– убрать из кучи 1 камень;
– убрать из кучи 4 камня;
– уменьшить количество камней в куче в 3 раза (количество камней, полученное при делении, округляется до меньшего).
Например, из кучи в 60 камней за один ход можно получить кучу из 59, 56, 20 камней. Игра завершается, когда количество камней в куче становится не более 40. Победителем считается игрок, сделавший последний ход, то есть первым получивший кучу из 40 или менее камней. В начальный момент в куче было S камней, S ≥ 41.

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

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

Два игрока, Петя и Ваня, играют в следующую игру. Перед игроками лежат две кучи камней. Игроки ходят по очереди, первый ход делает Петя. За один ход игрок может:
– добавить в одну из куч 1 камень;
– увеличить количество камней в одной из куч в 2 раза.
Например, пусть в одной куче 10 камней, а в другой — 7; такую позицию обозначим (10, 7). За один ход из неё можно получить любую из позиций: (10, 8), (10, 14), (11, 7), (20, 7). Игра завершается, когда суммарное количество камней в кучах становится не менее 97. Победителем считается игрок, сделавший последний ход. В начальный момент в первой куче было 10 камней, во второй — S камней, 1 ≤ S ≤ 86.

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

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

Два игрока, Петя и Ваня, играют в следующую игру. Перед игроками лежит куча камней. Игроки ходят по очереди, первый ход делает Петя. За один ход игрок может:
– добавить в кучу 1 камень;
– добавить в кучу 2 камня;
– увеличить количество камней в куче в 2 раза.
Например, из кучи в 10 камней за один ход можно получить кучу из 11, 12, 20 камней. Игра завершается, когда количество камней в куче становится не менее 103. Победителем считается игрок, сделавший последний ход, то есть первым получивший кучу из 103 или более камней. В начальный момент в куче было S камней, 1 ≤ S ≤ 102.

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

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

Два игрока, Петя и Ваня, играют в следующую игру. Перед игроками лежит куча камней. Игроки ходят по очереди, первый ход делает Петя. За один ход игрок может:
– убрать из кучи 2 камня;
– убрать из кучи 6 камней;
– уменьшить количество камней в куче в 3 раза (количество камней, полученное при делении, округляется до меньшего).
Например, из кучи в 60 камней за один ход можно получить кучу из 58, 54, 20 камней. Игра завершается, когда количество камней в куче становится не более 40. Победителем считается игрок, сделавший последний ход, то есть первым получивший кучу из 40 или менее камней. В начальный момент в куче было S камней, S ≥ 41.

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

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