20. Теория игр

Решение руками

Из предыдущего задания мы знаем, что в значении Ваня гарантированно выигрывает своим первым ходом. Значение, из которого ХОТЯ БЫ ОДИН ход ведет в – это значение, в котором Петя выигрывает вторым ходом. Распишем значение и стратегии, при которых Петя побеждает своим вторым ходом:

Петя может увеличить количество камней до ходом .

Петя может увеличить количество камней до ходом .

Ответ:

Решение БУ

from functools import lru_cache
@lru_cache(None)
def game(first_heap): # функция игры
    if first_heap >= 50: # если камней в куче стало больше 49
        return 0 # прекращаем игру
    moves = [game(first_heap+1),game(first_heap+2),game(first_heap*3)] # прописываем ходы возможные в партии
    petya_win = [i for i in moves if i <= 0]
    if petya_win: # проверяем есть ли выигрыш Пети в данной позиции
        return -max(petya_win) + 1
    else: # если в данной позиции выигрыш Вани
        return -max(moves)

for i in range(1,50):
    if game(i) == 2: # если в данной позиции возможен выигрыш Пети вторым ходом
        print(i)

Решение АР

from functools import lru_cache

def moves(h):
    return h + 1, h + 2, h * 3

@lru_cache(None)
def f(h):
    if (h >= 50):
        return ’END’
    if any(f(x) == ’END’ for x in moves(h)):
        return ’P1’
    if all(f(x) == ’P1’ for x in moves(h)):
        return ’V1’
    if any(f(x) == ’V1’ for x in moves(h)):
        return ’P2’

for s in range(1, 50):
    if f(s) == ’P2’:
        print(s)

Решение руками

Петя может выиграть своим первым ходом при или Таким образом, если мы возьмем то Петя никак не сможет выиграть первым ходом, но при этом любым своим ходом он создаст выигрышную позицию для Вани, и тогда Ваня уже гарантированно победит своим первым ходом.

Но нам то нужно, чтобы Петя победил вторым ходом. Тогда мы возьмем чтобы Петя первым ходом удвоил вторую кучу и получил позицию (4, 10). А из этой позиции Ваня уже любым своим ходом создают выигрышную позицию для Пети, после чего Петя выигрывает своим вторым ходом.

Решение БУ

from functools import lru_cache


@lru_cache(None)
def game(first_heap, second_heap):  # Функция игры
    if first_heap + second_heap >= 25:  # Если камней в куче стало больше 25
        return 0  # Прекращаем игру
    moves = [game(first_heap + 1, second_heap), game(first_heap, second_heap + 1), game(first_heap * 2, second_heap),
             game(first_heap, second_heap * 2)]  # Генерация всех возможных ходов
    petya_win = [i for i in moves if i <= 0]
    if petya_win:
        return -max(petya_win) + 1  # Выигрышный ход Пети
    else:
        return -max(moves)  # Выигрышный ход Вани


# Поиск минимального значения S для выигрыша Пети
for s in range(1, 21):
    if game(4, s) == 2:
        print(s)  # Вывод минимального значения S
        break

Решение АР

from functools import lru_cache
def moves(h):
    a, b = h
    return (a + 1, b), (a, b + 1), (a * 2, b), (a, b * 2)
@lru_cache(None)
def f(h):
    if (sum(h) >= 25):
        return ’END’
    if any(f(x) == ’END’ for x in moves(h)):
        return ’P1’
    if all(f(x) == ’P1’ for x in moves(h)):
        return ’V1’
    if any(f(x) == ’V1’ for x in moves(h)):
        return ’P2’
for s in range(1, 21):
    h = 4, s
    if f(h) == ’P2’:
        print(s)
        break

Решение руками

Петя может выиграть своим первым ходом при или Таким образом, если мы возьмем то Петя никак не сможет выиграть первым ходом, но при этом любым своим ходом он создаст выигрышную позицию для Вани, и тогда Ваня уже гарантированно победит своим первым ходом.

Но нам то нужно, чтобы Петя победил вторым ходом. Тогда мы возьмем чтобы Петя первым ходом утроил вторую кучу и получил позицию . А из этой позиции Ваня уже любым своим ходом создают выигрышную позицию для Пети, после чего Петя выигрывает своим вторым ходом.

Решение БУ

from functools import lru_cache


@lru_cache(None)
def game(first_heap, second_heap):  # Функция игры
    if first_heap + second_heap >= 43:  # Если камней в куче стало больше 43
        return 0  # Прекращаем игру
    moves = [game(first_heap + 2, second_heap), game(first_heap, second_heap + 2), game(first_heap * 3, second_heap),
             game(first_heap, second_heap * 3)]  # Генерация всех возможных ходов
    petya_win = [i for i in moves if i <= 0]
    if petya_win:
        return -max(petya_win) + 1  # Выигрышный ход Пети
    else:
        return -max(moves)  # Выигрышный ход Вани


# Поиск минимального значения S для выигрыша Пети
for s in range(1, 37):
    if game(6, s) == 2:
        print(s)  # Вывод минимального значения S
        break

Решение руками

Петя может выиграть своим первым ходом при или Таким образом, если мы возьмем то Петя никак не сможет выиграть первым ходом, но при этом любым своим ходом он создаст выигрышную позицию для Вани, и тогда Ваня уже гарантированно победит своим первым ходом.

Но нам то нужно, чтобы Петя победил вторым ходом. Тогда мы возьмем чтобы Петя первым ходом удвоил вторую кучу и получил позицию (4, 12). А из этой позиции Ваня уже любым своим ходом создают выигрышную позицию для Пети, после чего Петя выигрывает своим вторым ходом.

Решение БУ

from functools import lru_cache


@lru_cache(None)
def game(first_heap, second_heap):  # Функция игры
    if first_heap + second_heap >= 31:  # Если в двух кучах камней больше или равно 31
        return 0  # Прекращаем игру
    moves = [game(first_heap + 3, second_heap), game(first_heap, second_heap + 3), game(first_heap * 2, second_heap),
             game(first_heap, second_heap * 2)]  # Генерация всех возможных ходов
    petya_win = [i for i in moves if i <= 0]
    if petya_win:
        return -max(petya_win) + 1  # Выигрышный ход Пети
    else:
        return -max(moves)  # Выигрышный ход Вани


# Поиск значения S для выигрыша Пети
for s in range(1, 27):
    if game(4, s) == 2:
        print(s)  # Вывод минимального значения S
        break

Решение руками

Петя может выиграть своим первым ходом при Теперь найдем значение максимальное значение S, при котором Петя побеждает вторым ходом. Мы возьмем чтобы Петя первым ходом добавил в первую кучу 1 камень и получил позицию . А из этой позиции Ваня уже любым своим ходом создает выигрышную позицию для Пети, после чего Петя выигрывает своим вторым ходом.

Решение БУ

from functools import lru_cache
@lru_cache(None)
def game(first_heap, second_heap):  # Функция игры
    if first_heap + second_heap >= 99:  # Если камней в куче стало больше 98
        return 0  # Прекращаем игру
    moves = [game(first_heap + 1, second_heap), game(first_heap, second_heap + 1), game(first_heap * 2, second_heap),
             game(first_heap, second_heap * 2)]  # Генерация всех возможных ходов
    petya_win = [i for i in moves if i <= 0]
    if petya_win: # если в данной позиции есть выигрыш Пети
        return -max(petya_win) + 1
    else: # если в данной позиции выигрыш Вани
        return -max(moves)

for i in range(1,76):
    if game(23,i) == 2: # если в данной позиции возможен выигрыш Пети вторым ходом
        print(i)

Решение руками

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

Но нам то нужно, чтобы Петя победил вторым ходом. Тогда мы возьмем чтобы Петя первым ходом увеличил вторую кучу на и получил позицию (5, 26). А из этой позиции Ваня уже любым своим ходом создают выигрышную позицию для Пети, после чего Петя выигрывает своим вторым ходом.

Решение БУ

from functools import lru_cache
@lru_cache(None)
def game(first_heap, second_heap):  # Функция игры
    if first_heap + second_heap >= 84:  # Если камней в куче стало больше 83
        return 0  # Прекращаем игру
    moves = [game(first_heap + 2, second_heap), game(first_heap, second_heap + 2), game(first_heap * 3, second_heap),
             game(first_heap, second_heap * 3)]  # Генерация всех возможных ходов
    petya_win = [i for i in moves if i <= 0]
    if petya_win: # если в данной позиции есть выигрыш Пети
        return -max(petya_win) + 1
    else: # если в данной позиции выигрыш Вани
        return -max(moves)

for i in range(1,79):
    if game(5,i) == 2: # если в данной позиции возможен выигрыш Пети вторым ходом
        print(i)
        break

Решение руками

Оливье может выиграть своим первым ходом при Таким образом, если мы возьмем , то Оливье никак не сможет выиграть первым ходом, но при этом любым своим ходом он создаст выигрышную позицию для Крабового, и тогда Крабовый уже гарантированно победит своим первым ходом.

Но нам нужно, чтобы Оливье победил вторым ходом. Тогда мы возьмем , чтобы Оливье первым ходом добавил в кучу камень и получил камней. А из этой позиции Крабовый уже любым своим ходом создаст выигрышную позицию для Оливье, после чего Оливье выиграет своим вторым ходом.

По такой же логике, в можно попасть из , что тоже является ответом.

Решение БУ

#Петя - Оливье
#Ваня - Крабовый
def game(first_heap): # функция игры
    if first_heap >= 33: # если камней в куче стало больше 32
        return 0 # прекращаем игру
    moves = [game(first_heap+1),game(first_heap*2)] # прописываем ходы возможные в партии
    petya_win = [i for i in moves if i <= 0]
    if petya_win: # проверяем есть ли выигрыш Пети в данной позиции
        return -max(petya_win) + 1
    else: # если в данной позиции выигрыш Вани
        return -max(moves)

for i in range(1,33):
    if game(i) == 2: # если в данной позиции Петя побеждает вторым ходом
        print(i)

Решение АР

from functools import lru_cache


def moves(h):
    return h + 1, h * 2


@lru_cache(None)
def f(h):
    if h >= 33:
        return ’END’
    if any(f(x) == ’END’ for x in moves(h)):
        return ’WIN1’
    if all(f(x) == ’WIN1’ for x in moves(h)):
        return ’LOSE1’
    if any(f(x) == ’LOSE1’ for x in moves(h)):
        return ’WIN2’


for i in range(1, 33):
    if f(i) == ’WIN2’:
        print(i, end=’’)

Решение руками

Оливье может выиграть своим первым ходом при Таким образом, если мы возьмем , то Оливье никак не сможет выиграть первым ходом, но при этом любым своим ходом он создаст выигрышную позицию для Крабового, и тогда Крабовый уже гарантированно победит своим первым ходом.

Но нам нужно, чтобы Оливье победил вторым ходом. Тогда мы возьмем , чтобы Оливье первым ходом добавил в кучу камень и получил камней. А из этой позиции Крабовый уже любым своим ходом создаст выигрышную позицию для Оливье, после чего Оливье выиграет своим вторым ходом.

По такой же логике, в можно попасть из и , что тоже является ответом.

Решение БУ

#Петя - Оливье
#Ваня - Крабовый

from functools import lru_cache
@lru_cache(None)
def game(first_heap): # функция игры
    if first_heap >= 42: # если камней в куче стало больше 41
        return 0 # прекращаем игру
    moves = [game(first_heap+1),game(first_heap*2),game(first_heap + 3)] # прописываем ходы возможные в партии
    petya_win = [i for i in moves if i <= 0]
    if petya_win: # проверяем есть ли выигрыш Пети в данной позиции
        return -max(petya_win) + 1
    else: # если в данной позиции выигрыш Вани
        return -max(moves)

for i in range(1,42):
    if game(i) == 2: # если в данной позиции Петя побеждает вторым ходом
        print(i)

Решение АР

from functools import lru_cache


def moves(h):
    return h + 1, h + 3, h * 2


@lru_cache(None)
def f(h):
    if h >= 42:
        return ’END’
    if any(f(x) == ’END’ for x in moves(h)):
        return ’WIN1’
    if all(f(x) == ’WIN1’ for x in moves(h)):
        return ’LOSE1’
    if any(f(x) == ’LOSE1’ for x in moves(h)):
        return ’WIN2’
    if all(f(x) == ’WIN1’ or f(x) == ’WIN2’ for x in moves(h)):
        return ’LOSE2’


for i in range(1, 42):
    if f(i) == ’WIN2’:
        print(i, end=’’)

Решение руками

Оливье может выиграть своим первым ходом при Таким образом, если мы возьмем , то Оливье никак не сможет выиграть первым ходом, но при этом любым своим ходом он создаст выигрышную позицию для Крабового, и тогда Крабовый уже гарантированно победит своим первым ходом.

Но нам нужно, чтобы Оливье победил вторым ходом. Тогда мы возьмем , чтобы Оливье первым ходом убрал из кучи камень и получил камней. А из этой позиции Крабовый уже любым своим ходом создаст выигрышную позицию для Оливье, после чего Оливье выиграет своим вторым ходом.

По такой же логике, в можно попасть из , что тоже является ответом.

Решение БУ

#Петя - Оливье
#Ваня - Крабовый

from functools import lru_cache
@lru_cache(None)
def game(first_heap): # функция игры
    if first_heap <= 34: # если камней в куче стало меньше 34
        return 0 # прекращаем игру
    moves = [game(first_heap-1),game(first_heap-2)] # прописываем ходы возможные в партии
    petya_win = [i for i in moves if i <= 0]
    if petya_win: # проверяем есть ли выигрыш Пети в данной позиции
        return -max(petya_win) + 1
    else: # если в данной позиции выигрыш Вани
        return -max(moves)

for i in range(36,100):
    if game(i) == 2: # если в данной позиции Петя побеждает вторым ходом
        print(i)

Решение АР

from functools import lru_cache


def moves(h):
    return h - 1, h - 2


@lru_cache(None)
def f(h):
    if h <= 34:
        return ’END’
    if any(f(x) == ’END’ for x in moves(h)):
        return ’WIN1’
    if all(f(x) == ’WIN1’ for x in moves(h)):
        return ’LOSE1’
    if any(f(x) == ’LOSE1’ for x in moves(h)):
        return ’WIN2’


for i in range(36, 100):
    if f(i) == ’WIN2’:
        print(i, end=’’)

Решение руками

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

Но нам нужно, чтобы Петя победил вторым ходом. Тогда мы возьмем , чтобы Петя первым ходом добавил в первую кучу камень и получил позицию . А из этой позиции Ваня уже любым своим ходом создаст выигрышную позицию для Пети, после чего Петя выиграет своим вторым ходом.

Решение БУ

from functools import lru_cache
@lru_cache(None)
def game(first_heap, second_heap):  # Функция игры
    if first_heap + second_heap >= 50:  # Если камней в куче стало больше 49
        return 0  # Прекращаем игру
    moves = [game(first_heap + 1, second_heap), game(first_heap, second_heap + 1), game(first_heap * 3, second_heap),
             game(first_heap, second_heap * 3)]  # Генерация всех возможных ходов
    petya_win = [i for i in moves if i <= 0]
    if petya_win: # если в данной позиции есть выигрыш Пети
        return -max(petya_win) + 1
    else: # если в данной позиции выигрыш Вани
        return -max(moves)

for i in range(1,47):
    if game(3,i) == 2: # если в данной позиции возможен выигрыш Пети вторым ходом
        print(i)

Решение АР

from functools import lru_cache


def moves(h):
    a, b = h
    return (a + 1, b), (a, b + 1), (a * 3, b), (a, b * 3)


@lru_cache(None)
def f(h):
    if sum(h) >= 50:
        return ’END’
    if any(f(x) == ’END’ for x in moves(h)):
        return ’WIN1’
    if all(f(x) == ’WIN1’ for x in moves(h)):
        return ’LOSE1’
    if any(f(x) == ’LOSE1’ for x in moves(h)):
        return ’WIN2’


for i in range(1, 47):
    h = i, 3
    if f(h) == ’WIN2’:
        print(i)

Решение руками

Петя может выиграть своим первым ходом при . Таким образом, если мы возьмем , то Петя никак не сможет выиграть первым ходом, но при этом любым своим ходом он создаст выигрышную позицию для Вани, и тогда Ваня уже гарантированно победит своим первым ходом.

Но нам нужно, чтобы Петя победил вторым ходом. Тогда мы возьмем , чтобы Петя первым ходом добавил во вторую кучу камня и получил позицию . А из этой позиции Ваня уже любым своим ходом создаст выигрышную позицию для Пети, после чего Петя выиграет своим вторым ходом.

Так же мы можем взять , чтобы Петя первым ходом добавил в первую кучу камня и получил позицию . А из этой позиции Ваня уже любым своим ходом создаст выигрышную позицию для Пети, после чего Петя выиграет своим вторым ходом.

Решение БУ

from functools import lru_cache
@lru_cache(None)
def game(first_heap, second_heap):  # Функция игры
    if first_heap + second_heap >= 48:  # Если камней в куче стало больше 47
        return 0  # Прекращаем игру
    moves = [game(first_heap + 2, second_heap), game(first_heap, second_heap + 2), game(first_heap * 2, second_heap),
             game(first_heap, second_heap * 2)]  # Генерация всех возможных ходов
    petya_win = [i for i in moves if i <= 0]
    if petya_win: # если в данной позиции есть выигрыш Пети
        return -max(petya_win) + 1
    else: # если в данной позиции выигрыш Вани
        return -max(moves)

for i in range(1,35):
    if game(12,i) == 2: # если в данной позиции возможен выигрыш Пети вторым ходом
        print(i)

Решение АР

from functools import lru_cache


def moves(h):
    a, b = h
    return (a + 2, b), (a, b + 2), (a * 2, b), (a, b * 2)


@lru_cache(None)
def f(h):
    if sum(h) >= 48:
        return ’END’
    if any(f(x) == ’END’ for x in moves(h)):
        return ’WIN1’
    if all(f(x) == ’WIN1’ for x in moves(h)):
        return ’LOSE1’
    if any(f(x) == ’LOSE1’ for x in moves(h)):
        return ’WIN2’


for i in range(1, 35):
    h = i, 12
    if f(h) == ’WIN2’:
        print(i, end=’’)

Решение руками

Из предыдущего задания мы знаем, что в отрезке [21;62] Петя побеждает своим первым ходом. Для начала нам нужно определить в каких значениях побеждает Ваня своим первым ходом. Если ВСЕ первые ходы Пети ведут в выше описанную область, то данное значение – это значение, при котором Ваня гарантированно побеждает своим первым ходом. Распишем значения и стратегии, при которых Ваня побеждает своим первым ходом:

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

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

После того как мы узнали значения, где Ваня побеждает своим первым ходом, мы можем определить значения, при которых Петя побеждает своим вторым ходом. Значение, из которого ХОТЯ БЫ ОДИН ход ведёт в значения или является значением, где Петя побеждает своим вторым ходом. Минимальное значение S, когда Петя побеждает вторым ходом равно .

Решение БУ

from functools import lru_cache
@lru_cache(None)
def game(first_heap): # функция игры
    if first_heap >= 63: # если камней в куче стало больше 62
        return 0 # прекращаем игру
    moves = [game(first_heap+2),game(first_heap*3)] # прописываем ходы возможные в партии
    petya_win = [i for i in moves if i <= 0]
    if petya_win: # проверяем есть ли выигрыш Пети в данной позиции
        return -max(petya_win) + 1
    else: # если в данной позиции выигрыш Вани
        return -max(moves)

for i in range(1,63):
    if game(i) == 2: # если в данной позиции Петя побеждает вторым ходом
        print(i)
        break

Решение руками

Из предыдущего задания мы знаем, что в значении Ваня гарантированно побеждает своим первым ходом. Значение, из которого ХОТЯ БЫ ОДИН ход ведёт в – это значение, из которого Петя гарантированно побеждает своим вторым ходом. Распишем значения и стратегии, при которых Петя победит своим вторым ходом:

. Петя увеличит количество камней до ходом .

. Петя увеличит количество камней до ходом .

. Петя увеличит количество камней до ходом .

Ответ:

Решение БУ

from functools import lru_cache
@lru_cache(None)
def game(first_heap): # функция игры
    if first_heap >= 62: # если камней в куче стало больше 61
        return 0 # прекращаем игру
    moves = [game(first_heap+1),game(first_heap+3),game(first_heap*2)] # прописываем ходы возможные в партии
    petya_win = [i for i in moves if i <= 0]
    if petya_win: # проверяем есть ли выигрыш Пети в данной позиции
        return -max(petya_win) + 1
    else: # если в данной позиции выигрыш Вани
        return -max(moves)

for i in range(1,62):
    if game(i) == 2: # если в данной позиции Петя побеждает вторым ходом
        print(i)

Решение БУ

from functools import lru_cache
@lru_cache(None)
def game(first_heap, second_heap):  # Функция игры
    if first_heap + second_heap >= 38:  # Если камней в куче стало больше 37
        return 0  # Прекращаем игру
    moves = [game(first_heap + 2, second_heap), game(first_heap, second_heap + 2), game(first_heap * 2, second_heap),
             game(first_heap, second_heap * 2)]  # Генерация всех возможных ходов
    petya_win = [i for i in moves if i <= 0]
    if petya_win: # если в данной позиции есть выигрыш Пети
        return -max(petya_win) + 1
    else: # если в данной позиции выигрыш Вани
        return -max(moves)

for i in range(1,33):
    if game(5,i) == 2: # если в данной позиции возможен выигрыш Пети вторым ходом
        print(i)
        break

Решение БУ

from functools import lru_cache
@lru_cache(None)
def game(first_heap, second_heap):  # Функция игры
    if first_heap + second_heap >= 136:  # Если камней в куче стало больше 135
        return 0  # Прекращаем игру
    moves = [game(first_heap + 1, second_heap), game(first_heap, second_heap + 1), game(first_heap * 3, second_heap),
             game(first_heap, second_heap * 3)]  # Генерация всех возможных ходов
    petya_win = [i for i in moves if i <= 0]
    if petya_win: # если в данной позиции есть выигрыш Пети
        return -max(petya_win) + 1
    else: # если в данной позиции выигрыш Вани
        return -max(moves)

for i in range(1,102):
    if game(34,i) == 2: # если в данной позиции возможен выигрыш Пети вторым ходом
        print(i)

Решение БУ

from functools import lru_cache
@lru_cache(None)
def game(first_heap, second_heap):  # Функция игры
    if first_heap + second_heap >= 51:  # Если камней в куче стало больше 50
        return 0  # Прекращаем игру
    moves = [game(first_heap + 3, second_heap), game(first_heap, second_heap + 3), game(first_heap * 2, second_heap),
             game(first_heap, second_heap * 2), game(first_heap + 2, second_heap), game(first_heap, second_heap + 2)]  # Генерация всех возможных ходов
    petya_win = [i for i in moves if i <= 0]
    if petya_win: # если в данной позиции есть выигрыш Пети
        return -max(petya_win) + 1
    else: # если в данной позиции выигрыш Вани
        return -max(moves)

for i in range(1,46):
    if game(5,i) == 2: # если в данной позиции возможен выигрыш Пети вторым ходом
        print(i)
        break

Решение руками

Из предыдущего задания мы знаем, что в значениях [21;41] Петя гарантированно побеждает своим первым ходом. Для начала нам нужно определить значение, в котором Ваня побеждает своим первым ходом. Значение, из которого ВСЕ первые ходы ведут в вышеописанный отрезок – это значение, в котором Ваня гарантированно побеждает своим первым ходом. Распишем значение и стратегии, при которых Ваня побеждает своим первым ходом:

. Петя может увеличить камней до или камней. В обоих случаях, Ване не составит труда закончить игру следующим ходом.

После того как мы определили значение, в котором Ваня побеждает первым ходом мы можем определить значения, в которых Петя гарантированно побеждает своим вторым ходом. Значение, из которого ХОТЯ БЫ ОДИН ход ведёт в – это значение, где Петя гарантированно побеждает своим вторым ходом. Распишем значения и стратегии, при которых Петя побеждает своим вторым ходом:

Петя может увеличить количество камней до ходом

Петя может увеличить количество камней до ходом

В ответ нужно указать максимальное значение S. Ответ:

Решение БУ

from functools import lru_cache
@lru_cache(None)
def game(first_heap): # функция игры
    if first_heap >= 42: # если камней в куче стало больше 41
        return 0 # прекращаем игру
    moves = [game(first_heap+1),game(first_heap*2)] # прописываем ходы возможные в партии
    petya_win = [i for i in moves if i <= 0]
    if petya_win: # проверяем есть ли выигрыш Пети в данной позиции
        return -max(petya_win) + 1
    else: # если в данной позиции выигрыш Вани
        return -max(moves)

for i in range(1,42):
    if game(i) == 2: # если в данной позиции Петя побеждает вторым ходом
        print(i)

Решение АР

from functools import lru_cache

def moves(heap):
    return heap + 1, heap * 2

@lru_cache(None)
def game(heap):
    if heap >= 42:
        return ’END’
    elif any(game(x) == ’END’ for x in moves(heap)):
        return ’P1’
    elif all(game(x) == ’P1’ for x in moves(heap)):
        return ’V1’
    elif any(game(x) == ’V1’ for x in moves(heap)):
        return ’P2’
    elif all(game(x) == ’P1’ or game(x) == ’P2’ for x in moves(heap)):
        return ’V2’

for s in range(1, 42):
    print(s, game(s))

Решение руками

Из предыдущего задания мы знаем, что в значении Ваня побеждает своим первым ходом. Значение, из которого ХОТЯ БЫ ОДИН ведёт в – это значение, в котором Петя гарантированно побеждает своим вторым ходом. Распишем значения и стратегии, при которых Петя побеждает своим вторым ходом:

. Петя может увеличить количество камней до ходом .

. Петя может увеличить количество камней до ходом .

Ответ:

Решение БУ

from functools import lru_cache
@lru_cache(None)
def game(first_heap): # функция игры
    if first_heap >= 50: # если камней в куче стало больше 49
        return 0 # прекращаем игру
    moves = [game(first_heap+1),game(first_heap+2),game(first_heap*3)] # прописываем ходы возможные в партии
    petya_win = [i for i in moves if i <= 0]
    if petya_win: # проверяем есть ли выигрыш Пети в данной позиции
        return -max(petya_win) + 1
    else: # если в данной позиции выигрыш Вани
        return -max(moves)

for i in range(1,50):
    if game(i) == 2: # если в данной позиции Петя побеждает вторым ходом
        print(i)

Решение АР

from functools import lru_cache

def moves(heap):
    return heap + 1, heap + 2, heap * 3

@lru_cache(None)
def game(heap):
    if heap >= 50:
        return ’END’
    elif any(game(x) == ’END’ for x in moves(heap)):
        return ’P1’
    elif all(game(x) == ’P1’ for x in moves(heap)):
        return ’V1’
    elif any(game(x) == ’V1’ for x in moves(heap)):
        return ’P2’
    elif all(game(x) == ’P1’ or game(x) == ’P2’ for x in moves(heap)):
        return ’V2’

for s in range(1, 50):
    print(s, game(s))

Решение БУ

from functools import lru_cache
@lru_cache(None)
def game(first_heap, second_heap):  # Функция игры
    if first_heap + second_heap >= 33:  # Если камней в куче стало больше 32
        return 0  # Прекращаем игру
    moves = [game(first_heap + 1, second_heap), game(first_heap, second_heap + 1), game(first_heap * 2, second_heap),
             game(first_heap, second_heap * 2)]  # Генерация всех возможных ходов
    petya_win = [i for i in moves if i <= 0]
    if petya_win: # если в данной позиции есть выигрыш Пети
        return -max(petya_win) + 1
    else: # если в данной позиции выигрыш Вани
        return -max(moves)

for i in range(1,29):
    if game(4,i) == 2: # если в данной позиции возможен выигрыш Пети вторым ходом
        print(i)
        break

Решение АР

from functools import lru_cache

def moves(heap):
    a, b = heap
    return (a + 1, b), (a, b + 1), (a * 2, b), (a, b * 2)

@lru_cache(None)
def game(heap):
    if sum(heap) >= 33:
        return ’END’
    elif any(game(x) == ’END’ for x in moves(heap)):
        return ’P1’
    elif all(game(x) == ’P1’ for x in moves(heap)):
        return ’V1’
    elif any(game(x) == ’V1’ for x in moves(heap)):
        return ’P2’
    elif all(game(x) == ’P1’ or game(x) == ’P2’ for x in moves(heap)):
        return ’V2’

for s in range(1, 29):
    print(s, game((4, s)))

Решение БУ

from functools import lru_cache
@lru_cache(None)
def game(first_heap, second_heap):  # Функция игры
    if first_heap + second_heap >= 99:  # Если камней в куче стало больше 98
        return 0  # Прекращаем игру
    moves = [game(first_heap + 2, second_heap), game(first_heap, second_heap + 2), game(first_heap * 3, second_heap),
             game(first_heap, second_heap * 3)]  # Генерация всех возможных ходов
    petya_win = [i for i in moves if i <= 0]
    if petya_win: # если в данной позиции есть выигрыш Пети
        return -max(petya_win) + 1
    else: # если в данной позиции выигрыш Вани
        return -max(moves)

for i in range(1,94):
    if game(5,i) == 2: # если в данной позиции возможен выигрыш Пети вторым ходом
        print(i)

Решение АР

from functools import lru_cache

def moves(heap):
    a, b = heap
    return (a + 2, b), (a, b + 2), (a * 3, b), (a, b * 3)

@lru_cache(None)
def game(heap):
    if sum(heap) >= 99:
        return ’END’
    elif any(game(x) == ’END’ for x in moves(heap)):
        return ’P1’
    elif all(game(x) == ’P1’ for x in moves(heap)):
        return ’V1’
    elif any(game(x) == ’V1’ for x in moves(heap)):
        return ’P2’
    elif all(game(x) == ’P1’ or game(x) == ’P2’ for x in moves(heap)):
        return ’V2’

for s in range(1, 94):
    print(s, game((5, s)))