21. Теория игр

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

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

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

Ответ:

Решение БУ

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’
    if all(f(x) == ’P1’ or f(x) == ’P2’ for x in moves(h)):
        return ’V2’


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

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

Рассмотрим и стартовую позицию .

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

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

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

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

Решение БУ

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’
    if all(f(x) == ’P1’ or f(x) == ’P2’ for x in moves(h)):
        return ’V2’
for s in range(1, 21):
    h = 4, s
    if f(h) == ’V2’:
        print(s)
        break

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

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

Если Петя домножит первую кучу на 3 и получит позицию , то Ваня выиграет своим первым ходом, умножив первую кучу на 3 и получив позицию .

Если Петя домножит вторую кучу на 3 и получит позицию , то Ваня выиграет своим первым ходом, умножив вторую кучу на 3 и получив позицию .

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

Если Петя добавит 2 камня во вторую кучу и получит позицию , то Ваня своим первым ходом поставит Петю в позицию и так же, как в предыдущем случае, гарантированно выиграет своим вторым ходом.

Решение БУ

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

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

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

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

Если Петя домножит вторую кучу на 2 и получит позицию , то Ваня выиграет своим первым ходом умножив вторую кучу на 2, и получив позицию .

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

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

Решение БУ

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

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

Рассмотрим и стартовую позицию .

Если Петя домножит первую кучу на 2 и получит позицию , то Ваня выиграет своим первым ходом, умножив первую кучу на 2 и получив позицию .

Если Петя домножит вторую кучу на 2 и получит позицию , то Ваня выиграет своим первым ходом, умножив вторую кучу на 2 и получив позицию .

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

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

Решение БУ

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)

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

Рассмотрим и стартовую позицию .

Если Петя домножит первую кучу на 3 и получит позицию , то Ваня выиграет своим первым ходом, умножив вторую кучу на 3 и получив позицию .

Если Петя домножит вторую кучу на 3 и получит позицию , то Ваня выиграет своим первым ходом, умножив вторую кучу на 3 и получив позицию .

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

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

Решение БУ

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)

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

Рассмотрим .

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

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

Решение БУ

#Петя - Оливье
#Ваня - Крабовый
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’
    if all(f(x) == ’WIN1’ or f(x) == ’WIN2’ for x in moves(h)):
        return ’LOSE2’


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

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

Рассмотрим .

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

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

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

Решение БУ

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

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(42, 1, -1):
    if f(i) == ’LOSE2’:
        print(i)
        break

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

Рассмотрим .

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

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

Решение БУ

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

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’
    if all(f(x) == ’WIN1’ or f(x) == ’WIN2’ for x in moves(h)):
        return ’LOSE2’


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

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

Рассмотрим и стартовую позицию .

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

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

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

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

Решение БУ

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’
    if all(f(x) == ’WIN1’ or f(x) == ’WIN2’ for x in moves(h)):
        return ’LOSE2’


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

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

Рассмотрим и стартовую позицию .

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

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

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

Если Петя добавит 2 камня во вторую кучу и получит позицию , то Ваня своим первым ходом поставит Петю в позицию и так же, как в предыдущем случае, гарантированно выиграет своим вторым ходом.

Решение БУ

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’
    if all(f(x) == ’WIN1’ or f(x) == ’WIN2’ for x in moves(h)):
        return ’LOSE2’


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

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

Из предыдущих заданий мы знаем, что в значениях , Петя гарантированно побеждает своим вторым ходом и в отрезке [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

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

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

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

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

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

Решение БУ

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)
        break

Решение БУ

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)
# Таких значений нет, значит, в ответ указываем 0

Решение БУ

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
def moves(h):
    a, b = h
    return (a*3, b), (a+1, b), (a, b*3), (a, b+1)
@lru_cache(None)
def game(h):
    if sum(h) >= 136:
        return ’END’
    elif any(game(x) == ’END’ for x in moves(h)):
        return ’WIN1’
    elif all(game(x) == ’WIN1’ for x in moves(h)):
        return ’LOSE1’
    elif any(game(x) == ’LOSE1’ for x in moves(h)):
        return ’WIN2’
    elif all(game(x) == ’WIN2’ or game(x) == ’WIN1’ for x in moves(h)):
        return ’LOSE2’
for s in range(1, 102):
    if game((34, s)) == ’LOSE2’:
        print(s)

Решение БУ

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)

Решение АР

from functools import lru_cache
def moves(h):
    a, b = h
    return (a*2, b), (a+2, b), (a+3, b), (a, b*2), (a, b+2), (a, b+3)
@lru_cache(None)
def game(h):
    if sum(h) >= 51:
        return ’END’
    elif any(game(x) == ’END’ for x in moves(h)):
        return ’WIN1’
    elif all(game(x) == ’WIN1’ for x in moves(h)):
        return ’LOSE1’
    elif any(game(x) == ’LOSE1’ for x in moves(h)):
        return ’WIN2’
    elif all(game(x) == ’WIN2’ or game(x) == ’WIN1’ for x in moves(h)):
        return ’LOSE2’
for s in range(1, 46):
    if game((5, s)) == ’LOSE2’:
        print(s)

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

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

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

Ответ:

Решение БУ

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))

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

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

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

Ответ:

Решение БУ

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)

Решение АР

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)))