Теория игр: Ваня выигрывает первым или вторым ходом

Два игрока, Петя и Ваня, играют в следующую игру. Перед игроками лежит куча камней. Игроки ходят по очереди, первый ход делает Петя. За один ход игрок может:
– убрать из кучи 2 камня;
– убрать из кучи 6 камней;
– уменьшить количество камней в куче в 4 раза (количество камней, полученное при делении, округляется до меньшего).
Например, из кучи в 30 камней за один ход можно получить кучу из 28, 24, 7 камней. Игра завершается, когда количество камней в куче становится не более 10. Победителем считается игрок, сделавший последний ход, то есть первым получивший кучу из 10 или менее камней. В начальный момент в куче было S камней, S ≥ 11.

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

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

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

print(min(s for s in range(11, 410) if f(s, 4) and not f(s, 2)))

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

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

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

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

print(min(s for s in range(1, 67) if f(s, 4) and not f(s, 2)))

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

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

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

def f(a, b, m):
    if a + b >= 63:
        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)

print(min(s for s in range(1, 55) if f(8, s, 4) and not f(8, s, 2)))

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

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

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

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

print(max(s for s in range(1, 63) if f(s, 4) and not f(s, 2)))

Два игрока, Петя и Ваня, играют в следующую игру. Перед игроками лежит куча камней. Игроки ходят по очереди, первый ход делает Петя. За один ход игрок может:
– убрать из кучи 3 камня;
– убрать из кучи 7 камней;
– уменьшить количество камней в куче в 2 раза (количество камней, полученное при делении, округляется до меньшего).
Например, из кучи в 40 камней за один ход можно получить кучу из 37, 33, 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 - 3, s - 7, s // 2)]
    return any(h) if m % 2 != 0 else all(h)

print(min(s for s in range(21, 420) if f(s, 4) and not f(s, 2)))

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

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

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

def f(a, b, m):
    if a + b >= 67:
        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)

print(min(s for s in range(1, 62) if f(5, s, 4) and not f(5, s, 2)))

Два игрока, Петя и Ваня, играют в следующую игру. Перед игроками лежит куча камней. Игроки ходят по очереди, первый ход делает Петя. За один ход игрок может:
– убрать из кучи 2 камня;
– убрать из кучи 4 камня;
– уменьшить количество камней в куче в 3 раза (количество камней, полученное при делении, округляется до меньшего).
Например, из кучи в 50 камней за один ход можно получить кучу из 48, 46, 16 камней. Игра завершается, когда количество камней в куче становится не более 30. Победителем считается игрок, сделавший последний ход, то есть первым получивший кучу из 30 или менее камней. В начальный момент в куче было S камней, S ≥ 31.

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

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

def f(s, m):
    if s <= 30:
        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)

print(min(s for s in range(31, 430) if f(s, 4) and not f(s, 2)))

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

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

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

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

print(max(s for s in range(1, 89) if f(s, 4) and not f(s, 2)))

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

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

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

def f(a, b, m):
    if a + b >= 41:
        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)

print(min(s for s in range(1, 29) if f(12, s, 4) and not f(12, s, 2)))

Два игрока, Петя и Ваня, играют в следующую игру. Перед игроками лежит куча камней. Игроки ходят по очереди, первый ход делает Петя. За один ход игрок может:
– убрать из кучи 1 камень;
– убрать из кучи 7 камней;
– уменьшить количество камней в куче в 3 раза (количество камней, полученное при делении, округляется до меньшего).
Например, из кучи в 40 камней за один ход можно получить кучу из 39, 33, 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 - 7, s // 3)]
    return any(h) if m % 2 != 0 else all(h)

print(min(s for s in range(21, 420) if f(s, 4) and not f(s, 2)))

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

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

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

Два игрока, Петя и Ваня, играют в следующую игру. Перед игроками лежит куча камней. Игроки ходят по очереди, первый ход делает Петя. За один ход игрок может:
– убрать из кучи 2 камня;
– убрать из кучи 6 камней;
– уменьшить количество камней в куче в 4 раза (количество камней, полученное при делении, округляется до меньшего).
Например, из кучи в 30 камней за один ход можно получить кучу из 28, 24, 7 камней. Игра завершается, когда количество камней в куче становится не более 10. Победителем считается игрок, сделавший последний ход, то есть первым получивший кучу из 10 или менее камней. В начальный момент в куче было S камней, S ≥ 11.

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

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

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

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

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

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

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

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

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

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

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