20. Теория игр

Решение БУ

from functools import lru_cache
@lru_cache(None)
def game(first_heap, second_heap):  # Функция игры
    if first_heap + second_heap >= 49:  # Если камней в куче стало больше 48
        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,44):
    # если в данной позиции возможен выигрыш Пети вторым ходом
    if game(5,i) == 2:
        print(i)
        break

Аналитическое решение:

Скопируем область и вставим ее в , , , . Это будут все возможные ситуации при разных первых ходах Пинки. Подпишем стобец как , как , как .

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

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

 

Программное решение:

from functools import lru_cache


@lru_cache(None)
def f(a, b):
    if a + b <= 34:
        return 0
    moves = []
    if a > 0:
        moves.append(f(a - 1, b))
        moves.append(f(a // 2, b))
    if b > 0:
        moves.append(f(a, b - 1))
        moves.append(f(a, b // 2))
    pinki_win = [i for i in moves if i <= 0]
    if pinki_win:
        return -max(pinki_win) + 1
    else:
        return -max(moves)


for i in range(12, 100):
    if f(22, i) == 2:
        print(i)

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

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

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

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

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

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

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

Ответ:

Решение БУ

from functools import lru_cache
@lru_cache(None)
def game(first_heap): # функция игры
    if first_heap >= 33: # если камней в куче стало больше 32
        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,33):
    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 game(h):
    if h >= 33:
        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, 33):
    if game(s) == "WIN2":
        print(s)

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

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

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

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

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

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

Ответ:

Решение программой:

from functools import lru_cache
@lru_cache(None)
def game(first_heap): # функция игры
    if first_heap >= 46: # если камней в куче стало больше 45
        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,46):
    if game(i) == 2: # если в данной позиции возможен выигрыш Пети вторым ходом
        print(i)

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

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

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

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

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

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

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

Ответ:

Решение БУ

from functools import lru_cache
@lru_cache(None)
def game(first_heap): # функция игры
    if first_heap >= 38: # если камней в куче стало больше 37
        return 0 # прекращаем игру
    moves = [game(first_heap+1),game(first_heap+2),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,38):
    if game(i) == 2: # если в данной позиции возможен выигрыш Пети вторым ходом
        print(i)

Решение АР

from functools import lru_cache
def moves(heap):
    return heap + 1, heap + 2, heap * 2
@lru_cache(None)
def game(heap):
    if heap >= 38:
        return ’END’
    elif any(game(x) == ’END’ for x in moves(heap)):
        return ’WIN1’
    elif all(game(x) == ’WIN1’ for x in moves(heap)):
        return ’LOSE1’
    elif any(game(x) == ’LOSE1’ for x in moves(heap)):
        return ’WIN2’
    elif all(game(x) == ’WIN1’ or game(x) == ’WIN2’ for x in moves(heap)):
        return ’LOSE2’
for s in range(1, 38):
    print(s, game(s))

Решение БУ

from functools import lru_cache
@lru_cache(None)
def game(first_heap, second_heap):  # Функция игры
    if first_heap + second_heap >= 77:  # Если камней в куче стало больше 76
        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,70):
    # если в данной позиции возможен выигрыш Пети вторым ходом
    if game(7,i) == 2:
        print(i)

Решение АР

from functools import lru_cache

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

@lru_cache(None)
def game(heap):
    if sum(heap) >= 77:
        return "END"
    elif any(game(x) == "END" for x in moves(heap)):
        return "WIN1"
    elif all(game(x) == "WIN1" for x in moves(heap)):
        return "LOSE1"
    elif any(game(x) == "LOSE1" for x in moves(heap)):
        return "WIN2"
    elif all(game(x) == "WIN1" or game(x) == "WIN2" for x in moves(heap)):
        return "LOSE2"

for s in range(1, 70):
    print(s, game((7, s)))

Решение БУ

from functools import lru_cache
@lru_cache(None)
def game(first_heap, second_heap):  # Функция игры
    if first_heap + second_heap >= 82:  # Если камней в куче стало больше 81
        return 0  # Прекращаем игру
    moves = [game(first_heap + 1, second_heap), game(first_heap, second_heap + 1), game(first_heap * 4, second_heap),
             game(first_heap, second_heap * 4)]  # Генерация всех возможных ходов
    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,78):
    # если в данной позиции возможен выигрыш Пети вторым ходом
    if game(4,i) == 2:
        print(i)

Решение АР

from functools import lru_cache

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

@lru_cache(None)
def game(heap):
    if sum(heap) >= 82:
        return "END"
    elif any(game(x) == "END" for x in moves(heap)):
        return "WIN1"
    elif all(game(x) == "WIN1" for x in moves(heap)):
        return "LOSE1"
    elif any(game(x) == "LOSE1" for x in moves(heap)):
        return "WIN2"
    elif all(game(x) == "WIN1" or game(x) == "WIN2" for x in moves(heap)):
        return "LOSE2"

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

from functools import lru_cache


@lru_cache(None)
def f(a):
    if a <= 11:
        return 0
    moves = []
    if a > 0:
        moves.append(f(a - 1))
    if a > 2:
        moves.append(f(a - 3))
    pupsen_win = [i for i in moves if i <= 0]
    if pupsen_win:
        return -max(pupsen_win) + 1
    return -max(moves)


for i in range(12, 50):
    if f(i) == 2:
        print(i)

Решение БУ

from functools import lru_cache
@lru_cache(None)
def game(first_heap, second_heap):  # Функция игры
    if first_heap + second_heap >= 66:  # Если камней в куче стало больше 65
        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,55):
    # если в данной позиции возможен выигрыш Пети вторым ходом
    if game(11,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) >= 66:
        return ’END’
    elif any(game(x) == ’END’ for x in moves(heap)):
        return ’WIN1’
    elif all(game(x) == ’WIN1’ for x in moves(heap)):
        return ’LOSE1’
    elif any(game(x) == ’LOSE1’ for x in moves(heap)):
        return ’WIN2’
    elif all(game(x) == ’WIN1’ or game(x) == ’WIN2’ for x in moves(heap)):
        return ’LOSE2’
for s in range(1, 55):
    print(s, game((11, s)))

Решение БУ

from functools import lru_cache
@lru_cache(None)
def game(first_heap, second_heap):  # Функция игры
    if first_heap + second_heap >= 88:  # Если камней в куче стало больше 87
        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(9,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) >= 88:
        return ’END’
    elif any(game(x) == ’END’ for x in moves(heap)):
        return ’WIN1’
    elif all(game(x) == ’WIN1’ for x in moves(heap)):
        return ’LOSE1’
    elif any(game(x) == ’LOSE1’ for x in moves(heap)):
        return ’WIN2’
    elif all(game(x) == ’WIN1’ or game(x) == ’WIN2’ for x in moves(heap)):
        return ’LOSE2’
for s in range(1, 79):
    print(s, game((9, s)))

Решение БУ

from functools import lru_cache
@lru_cache(None)
def game(first_heap, second_heap):  # Функция игры
    if first_heap + second_heap >= 83:  # Если камней в куче стало больше 82
        return 0  # Прекращаем игру
    moves = [game(first_heap + 1, second_heap), game(first_heap, second_heap + 1), game(first_heap * 4, second_heap),
             game(first_heap, second_heap * 4)]  # Генерация всех возможных ходов
    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,78):
    # если в данной позиции возможен выигрыш Пети вторым ходом
    if game(5,i) == 2:
        print(i)

Решение АР

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

Решение программой

from functools import lru_cache
@lru_cache(None)
def game(first_heap, second_heap):  # Функция игры
    if first_heap + second_heap >= 55:  # Если камней в куче стало больше 54
        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,45):
    # если в данной позиции возможен выигрыш Пети вторым ходом
    if game(10,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) >= 55:
        return ’END’
    elif any(game(x) == ’END’ for x in moves(heap)):
        return ’WIN1’
    elif all(game(x) == ’WIN1’ for x in moves(heap)):
        return ’LOSE1’
    elif any(game(x) == ’LOSE1’ for x in moves(heap)):
        return ’WIN2’
    elif all(game(x) == ’WIN1’ or game(x) == ’WIN2’ for x in moves(heap)):
        return ’LOSE2’
for s in range(1, 45):
    print(s, game((10, s)))

from functools import lru_cache


@lru_cache(None)
def f(first_heap, second_heap, third_heap, c=0):
    if first_heap + second_heap + third_heap <= 32:
        return 0
    if c > 4:
        return 123123
    moves = []
    if first_heap > 1:
        moves.append(f(first_heap - 1, second_heap, third_heap, c + 1))
        moves.append(f((first_heap + 1) // 2, second_heap, third_heap, c + 1))
    if second_heap > 1:
        moves.append(f(first_heap, second_heap - 1, third_heap, c + 1))
        moves.append(f(first_heap, (second_heap + 1) // 2, third_heap, c + 1))
    if third_heap > 1:
        moves.append(f(first_heap, second_heap, third_heap - 1, c + 1))
        moves.append(f(first_heap, second_heap, (third_heap + 1) // 2, c + 1))

    petya_win = [i for i in moves if i <= 0]
    if petya_win:
        return -max(petya_win) + 1
    else:
        return -max(moves)


count = 0
for i in range(11, 100):
    if f(11, 11, i) == 2:
        count += 1
print(count)

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

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

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

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

Ответ:

Решение БУ

from functools import lru_cache
@lru_cache(None)
def game(first_heap): # функция игры
    if first_heap >= 51: # если камней в куче стало больше 50
        return 0 # прекращаем игру
    moves = [] # cписок всех возможных ходов в партии
    if first_heap % 2 == 0: # если количество камней в куче является чётным
        # то можем совершить только +1, +3 ходы, так как чётное+нечётное = нечётное
        moves = [game(first_heap+1),game(first_heap+3)]
    else: # если количество камней в куче является нечётным
        # то можем совершить только *3 ход, так как нечётное*нечётное = нечётное
        moves = [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,51):
    # если в данной позиции возможен выигрыш Пети вторым ходом
    if game(i) == 2:
        print(i)

Решение АР

from functools import lru_cache

def moves(heap):
    m = []
    if (heap * 3) % 2 != 0:
        m += [heap * 3]
    if (heap + 1) % 2 != 0:
        m += [heap + 1]
    if (heap + 3) % 2 != 0:
        m += [heap + 3]
    return m

@lru_cache(None)
def game(heap):
    if heap >= 51:
        return ’END’
    elif any(game(x) == ’END’ for x in moves(heap)):
        return ’WIN1’
    elif all(game(x) == ’WIN1’ for x in moves(heap)):
        return ’LOSE1’
    elif any(game(x) == ’LOSE1’ for x in moves(heap)):
        return ’WIN2’
    elif all(game(x) == ’WIN1’ or game(x) == ’WIN2’ for x in moves(heap)):
        return ’LOSE2’

for s in range(1, 51):
    if game(s) == ’WIN2’:
        print(s)

Решение БУ

from functools import lru_cache


@lru_cache(None)
def game(heap):  # Функция игры

    # Если кол-во таблеток в куче стало более 112
    if heap > 112:
        # Возвращаем 1,
        # которая преобразуется в победу Тринити первым ходом из-за "плохого" хода Нео
        return 1

    # Если кол-во таблеток в куче стало не менее 45
    if heap >= 45:
        return 0  # Прекращаем игру

    # Прописываем возможные ходы в партии
    moves = [game(heap + 2), game(heap * 3)]

    # Находим значения, через которые может победить Нео
    neo_win = [i for i in moves if i <= 0]

    if neo_win:  # Если такие значения нашлись и список не пуст
        return -max(neo_win) + 1
    else:  # Иначе побеждает Тринити максимальным ходом
        return -max(moves)


# Нео - первый игрок
# Тринити - второй игрок
for S in range(1, 44 + 1):
    # Если в данной позиции Нео гарантированно выигрывает своим вторым ходом
    if game(S) == 2:
        print(S, end=’’)  # Делаем вывод для получения готового ответа

Решение АР

from functools import lru_cache

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

@lru_cache(None)
def game(heap):
    if 45 <= heap <= 112:
        return ’END’
    elif heap > 112:
        return ’WIN1’
    elif any(game(x) == ’END’ for x in moves(heap)):
        return ’WIN1’
    elif all(game(x) == ’WIN1’ for x in moves(heap)):
        return ’LOSE1’
    elif any(game(x) == ’LOSE1’ for x in moves(heap)):
        return ’WIN2’
    elif all(game(x) == ’WIN1’ or game(x) == ’WIN2’ for x in moves(heap)):
        return ’LOSE2’

for s in range(1, 45):
    if game(s) == ’WIN2’:
        print(s)

Решение БУ

from functools import lru_cache


@lru_cache(None)
def game(heap):  # Функция игры

    # Если кол-во морковок в куче стало более 100
    if heap > 100:
        # Возвращаем 1,
        # которая преобразуется в победу Свена первым ходом из-за "плохого" хода Олафа
        return 1

    # Если кол-во морковок в куче стало не менее 50
    if heap >= 50:
        return 0  # Прекращаем игру

    # Прописываем возможные ходы в партии
    moves = [game(heap + 1), game(heap + 2), game(heap + 3), game(heap * 3)]

    # Находим значения, через которые может победить Олаф
    olaf_win = [i for i in moves if i <= 0]

    if olaf_win:  # Если такие значения нашлись и список не пуст
        return -max(olaf_win) + 1
    else:  # Иначе побеждает Свен максимальным ходом
        return -max(moves)


# Олаф - первый игрок
# Свен - второй игрок
if game(13) > 0:  # Если значение положительное - побеждает Олаф
    print("о")
elif game(13) < 0:  # Если отрицательное - Свен
    print("с")

Решение АР

from functools import lru_cache

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

@lru_cache(None)
def game(heap):
    if 50 <= heap <= 100:
        return ’END’
    elif heap > 100:
        return ’WIN1’
    elif any(game(x) == ’END’ for x in moves(heap)):
        return ’WIN1’
    elif all(game(x) == ’WIN1’ for x in moves(heap)):
        return ’LOSE1’
    elif any(game(x) == ’LOSE1’ for x in moves(heap)):
        return ’WIN2’
    elif all(game(x) == ’WIN1’ or game(x) == ’WIN2’ for x in moves(heap)):
        return ’LOSE2’

print(game(13))

Аналитическое решение:

Для начала найдём все позиции типа . Это все позиции Значит позиции и это позиции . В них можно прийти из позиций

 

Программное решение:

from functools import lru_cache


@lru_cache(None)
def f(a):
    if a >= 42:
        return 0
    moves = [f(a + 2), f(a * 3)]
    rick_win = [i for i in moves if i <= 0]
    if rick_win:
        return -max(rick_win) + 1
    return -max(moves)


for i in range(1, 42):
    if f(i) == 2:
        print(i)

from functools import lru_cache


@lru_cache(None)
def f(a, b):
    if a + b >= 100:
        return 0
    moves = [f(a + 1, b), f(a * 3, b), f(a, b + 1), f(a, b * 3)]
    anya_win = [i for i in moves if i <= 0]
    if anya_win:
        return -max(anya_win) + 1
    return -max(moves)


for i in range(1, 93):
    if f(7, i) == 2:
        print(i)

Решение БУ

from functools import lru_cache
@lru_cache(None)
def game(first_heap, second_heap):  # Функция игры
    if first_heap + second_heap >= 47:  # Если камней в куче стало больше 46
        return 0  # Прекращаем игру
    moves = [game(first_heap + 1, second_heap+2), game(first_heap+2, 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,37):
    # если в данной позиции возможен выигрыш Пети вторым ходом
    if game(10,i) == 2:
        print(i)

Решение АР

from functools import lru_cache
def moves(h):
    a, b = h
    return (a + 1, b + 2), (a + 2, b + 1), (a * 2, b), (a, b * 2)
@lru_cache(None)
def f(h):
    if sum(h) >= 47:
        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 i in range(1, 50):
    h = 10, i
    if f(h) == ’P2’:
        print(i)

from functools import lru_cache


@lru_cache(None)
def f(a, b, c=0):
    if a * b >= 1056:
        return 0
    if c > 4:
        return -10 ** 10
    moves = [f(a + 1, b, c + 1), f(a * 4, b, c + 1), f(a, b + 1, c + 1), f(a, b * 4, c + 1)]
    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, 132):
    if f(8, i) == 2:
        print(i)