19.01 Перекладывание камней одна куча

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

Для начала определим значения, при которых Петя побеждает первым ходом. Максимальный ход доступный нам в партии это . Минимальное значение отрезка значений, в которых Петя побеждает первым ходом равняется: (округляем в большую сторону) =

Получается, что в отрезке [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) == -1: # если в данной позиции возможен выигрыш Вани первым ходом
        print(i)
        break

Решение АР

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’

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

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

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

Получается, что в отрезке [21;82] Петя выигрывает своим первым ходом.

Ответ:

Решение БУ

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

Решение АР

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’


for i in range(1, 33):
    if f(i) == ’LOSE1’:
        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+1) == 1 or game(i+3) == 1 or game(i*2) == 1: # если после неудачного хода Пети возможен выигрыш Вани в один ход
        print(i)
        break

Решение АР

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 any(f(x) == ’WIN1’ for x in moves(h)):
        return ’LOSE1’


for i in range(1, 42):
    if f(i) == ’LOSE1’:
        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) == -1: # если в данной позиции Ваня побеждает первым ходом
        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’


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

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

Максимальный ход, доступный нам в партии это . Определим минимальное значение 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) == 1: # если в данной позиции Петя побеждает первым ходом
        print(i)
        break

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

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

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

Ответ:

Решение БУ

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) == -1: # если в данной позиции Ваня побеждает первым ходом
        print(i)
        break

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

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

Получается, в отрезке значений [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) == 1: # если в данной позиции Петя побеждает первым ходом
        print(i)
        break

Решение АР

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) == -1: # если в данной позиции Ваня побеждает первым ходом
        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))

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

Максимальный ход, доступный нам в партии это +10. Значит, в отрезке [61;70] Петя гарантированно побеждает своим первым ходом.

Если , то Пете достаточно прибавить к куче камней.

Если , то Пете достаточно прибавить к куче камень.

Решение БУ

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

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

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

Округляем в бОльшую сторону и получаем . В отрезке [20;38] Петя побеждает в один ход. Минимальное значение S: .

Решение БУ

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

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

Для начала найдем значения S, при которых Петя гарантированно побеждает своим первым ходом. Максимальный ход, доступные в партии это . Определим минимальное значение, из которого Петя может победить в один ход: (округляем в большую сторону) = . Значения, после которых мы гарантированно можем попасть в область [19;54] – это значения, в которых Ваня побеждает своим первым ходом. Распишем подробно значение и стратегии, в которых Ваня побеждает своим первым ходом:

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

При Петя может прийти в три позиции: , и . Так как то Ване уже неважно, какой конкретно ход сделает Петя.

В ответ нужно указать максимальное значение S, по этой причине ответ .

Решение БУ

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

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

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

Решение БУ

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

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

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

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

Решение БУ

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

Решение АР

from functools import lru_cache
def moves(h):
    return (h+2), (h*3)
@lru_cache(None)
def game(h):
    if h >= 27:
        return ’END’
    elif any(game(x) == ’END’ for x in moves(h)):
        return ’WIN1’
for s in range(1, 27):
    if game(s) == ’WIN1’:
        print(s)

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

Максимальный ход доступный нам в партии это . Минимальное значение S, при котором Петя гарантированно побеждает своим первым ходом равняется: (округляем в большую сторону) =

Получается, что в отрезке значений [11;30] Петя побеждает своим первым ходом.

Ответ:

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

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

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

Для начала определим отрезок, в котором игра заканчивается за один ход, при условии, что игрок не делает неудачных ходов. Максимальный ход доступный нам в партии это . Минимальное значение отрезка равняется: (округляем в большую сторону) =

Получается, что в отрезке [17;32] игра завершается в один ход. Неудачный ход – это ход, который ухудшает вашу позицию в партии. Минимальное значение, из которого за один ход можно попасть в отрезок [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+1) == 1 or game(i+3) == 1 or game(i*2) == 1: # если в данной позиции после неудачного хода Пети возможен выигрыш Вани
        print(i)
        break

Решение АР

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 any(game(x) == "WIN1" for x in moves(h)):
        return "LOSE1"

for s in range(1, 33):
    if game(s) == "LOSE1":
        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+1) == 1 or game(i*2) == 1: # если в данной позиции после неудачного хода Пети возможен выигрыш Вани
        print(i)
        break

Решение АР

from functools import lru_cache

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

@lru_cache(None)
def game(heap):
    if heap >= 46:
        return "END"
    elif any(game(x) == "END" for x in moves(heap)):
        return "WIN1"
    elif any(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(s))

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

Максимальный ход доступный нам в партии это . Определим отрезок, в котором игра заканчивается за один ход. Минимальное значение отрезка равняется:

Получается, что в отрезке [19;37] игра заканчивается в один ход. Минимальное значение, из которого ходом можно попасть в данный отрезок и есть минимальное значение S, из которого Ваня может победить после неудачного хода Пети. Определим данное значение: (округляем в большую сторону) =

Ответ:

Решение БУ

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+1) == 1 or game(i+2) == 1 or game(i*2) == 1: # если в данной позиции после неудачного хода Пети возможен выигрыш Вани
        print(i)
        break

Решение АР

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

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

Для начала нужно определить в каких ситуациях какие ходы мы можем совершать. Мы знаем, что после хода должно быть обязательно нечётное количество камней в куче. Если значение камней в куче это чётное число, то тогда мы можем совершить только , ходы, так как чётное + нечётное = нечётное число. В обратном случае, если значение камней в куче это нечётное число, то тогда мы можем совершить только ход, так как нечётное * нечётное = нечётное число. Теперь определим при каких значениях Петя побеждает своим первым ходом. Максимальный ход, который мы имеем в партии это ход. Значит, минимальное значение, при котором Петя побеждает своим первым ходом равняется: .

Поскольку это значение нечётное, то оно подходит. Получается, нам подходят все нечётные значения от до и также и , так как из этих значений можно дойти до камней ходом . Теперь определелим значение, при котором Ваня побеждает своим первым ходом. Значение, из которого ВСЕ ходы ведут в вышеописанные значения – это значение, в котором Ваня выигрывает своим первым ходом. Распишем минимальное значение 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) == -1:
        print(i)
        break

Решение АР

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) == ’LOSE1’:
        print(s)
        break

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

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

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

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

Ответ:

Решение БУ

from functools import lru_cache
@lru_cache(None)
def game(first_heap): # функция игры
    if first_heap >= 75: # если камней в куче стало больше 74
        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,75):
    if game(i) == -1: # если в данной позиции возможен выигрыш Вани первым ходом
        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 >= 75:
        return ’END’
    if any(f(i) == ’END’ for i in moves(h)):
        return ’WIN1’
    if all(f(i) == ’WIN1’ for i in moves(h)):
        return ’LOSE1’


for i in range(1, 75):
    print(i, f(i))