Уменьшение количества камней —Каталог задач по ЕГЭ - Информатика БУ

Ошибка.
Попробуйте повторить позже

Задача 1#19950

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

В начальный момент в первой куче было $25$ камней, во второй куче — $S$ камней, $1 ≤ S ≤ 99$ . Будем говорить, что игрок имеет выигрышную стратегию, если он может выиграть при любых ходах противника.

Известно, что Ваня выиграл своим первым ходом после неудачного первого хода Пети. Назовите минимальное значение $S$ , при котором это возможно.

Показать ответ и решение

from functools import lru_cache

def moves(h):
    a, b = h
    res = []

    if a - 2 >= 0:
        res.append((a - 2, b))
    if b - 2 >= 0:
        res.append((a, b - 2))
    if a > 0:
        res.append((a // 2, b))
    if b > 0:
        res.append((a, b // 2))

    return tuple(res)

@lru_cache(None)
def f(h):
    if sum(h) <= 12:
        return "END"
    if any((f(x) == "END") for x in moves(h)):
        return "P1"
    if any((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) == "P2") for x in moves(h)):
        return "V2"

for s in range(1, 100):
    h = 25, s
    if f(h) == "V1":
        print(s, "V1")

Ответ: 1

Ошибка.
Попробуйте повторить позже

Задача 2#19953

Два игрока, Петя и Ваня, играют в следующую игру. Перед игроками лежат две кучи камней. Игроки ходят по очереди, первый ход делает Петя. За один ход игрок может убрать в одной из куч три камня или уменьшить количество камней в куче в 5 раз (целочисленное деление). Чтобы делать ходы, у каждого игрока есть неограниченное количество камней. Количество камней не может быть отрицательно и игрок не может производить действие с кучей если она пуста. Игра завершается в тот момент, когда суммарное количество камней в кучах становится не более $75$ . Победителем считается игрок, сделавший последний ход, т. е. первым получивший позицию, в которой в кучах будет $75$ или меньше камней.

В начальный момент в первой куче было $100$ камней, во второй куче — $S$ камней, $50 ≤ S ≤ 100$ . Будем говорить, что игрок имеет выигрышную стратегию, если он может выиграть при любых ходах противника.

Известно, что Петя выиграл своим первым ходом. Назовите минимальное значение $S$ , при котором это возможно.

Показать ответ и решение

from functools import lru_cache

def moves(h):
    a, b = h
    res = []

    if a - 3 >= 0:
        res.append((a - 3, b))
    if b - 3 >= 0:
        res.append((a, b - 3))
    if a > 0:
        res.append((a // 5, b))
    if b > 0:
        res.append((a, b // 5))

    return tuple(res)

@lru_cache(None)
def f(h):
    if sum(h) <= 75:
        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) == "P2" or f(x) == "P1") for x in moves(h)):
        return "V2"

for s in range(50, 101):
    h = 100, s
    if f(h) == "P1":
        print(s, "P1")

Ответ: 50

Ошибка.
Попробуйте повторить позже

Задача 3#23624

Два игрока, Петя и Ваня, играют в следующую игру. Перед игроками лежат две кучи камней. Игроки ходят по очереди, первый ход делает Петя. За один ход игрок может убрать из одной из куч один камень или уменьшить количество камней в куче в два раза (если количество камней в куче нечётно, остаётся на $1$ камень больше, чем убирается). Например, пусть в одной куче $6$ , а в другой $9$ камней; такую позицию мы будем обозначать $(6,9)$ . За один ход из позиции $(6,9)$ можно получить любую из четырёх позиций: $(5,9)$ , $(3,9)$ , $(6,8)$ , $(6,5)$ .

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

В начальный момент в первой куче было $20$ камней, во второй куче — $S$ камней, $S > 20.$

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

Известно, что Петя выигрывает в первый ход. Укажите максимальное значение $S,$ когда такая ситуация возможна.

Показать ответ и решение

Решение 1

Петя может выиграть первым ходом, если $S = 21,...,40$ . Для выигрыша достаточно вдвое уменьшить количество камней во второй куче. При больших значениях $S$ за один ход нельзя получить $40$ или менее камней в двух кучах.

Решение 2

from functools import lru_cache
def moves(h):
    a, b = h
    m = []
    if a > 1:
        m += [((a + 1)//2, b), (a - 1, b)]
    if b > 1:
        m += [(a, (b + 1)//2), (a, b - 1)]
    return m

@lru_cache(None)
def f(h):
    if sum(h) <= 40:
        return ’END’
    if any(f(x) == ’END’ for x in moves(h)):
        return ’P1’

for i in range(19, 100):
    h = i, 20
    if f(h) == ’P1’:
        print(i)

Ответ: 40

Ошибка.
Попробуйте повторить позже

Задача 4#23693

Два игрока, Пинки и Вжик, играют в следующую игру. Перед игроками лежат две кучи камней. Игроки ходят по очереди, первый ход делает Пинки. За один ход игрок может убрать из одной из куч один камень или уменьшить количество камней в куче в два раза (если количество камней в куче нечётно, остаётся на $1$ камень меньше, чем убирается). При любом из ходов кол-во камней в одной из куч должно измениться. Например, пусть в одной куче будет $6$ камней, а в другой $9$ камней; такую позицию мы будем обозначать $(6,9)$ . За один ход из позиции $(6,9)$ можно получить любую из четырёх позиций: $(5,9),(6,8),(3,9),(6,4)$ . Игра завершается в тот момент, когда суммарное количество камней в кучах становится не более $34$ .

Победителем считается игрок, сделавший последний ход, то есть первым получивший позицию, в которой в кучах будет $34$ или менее камней. В начальный момент в первой куче было $22$ камня, во второй куче $S$ камней, $S > 12$

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

Найдите максимальное значение $S$ , при котором Вжик выигрывает своим первым ходом при любой игре Пинки.

Показать ответ и решение

Решение 1

Подпишем ячейки: $A1$ — $Start$ , $D1$ — $P 1$ . Поместим в ячейке $A2$ число $22$ , а $B2$ наше значение $S$ . В ячейке $C1$ запишем формулу $= A2 + B2$ — там будет сумма камней во время старта

В ячейках $E2 : F5$ запишем все возможные пары куч, которые можно получить: в $E2$ поместим $= A2 − 1$ , в $F2$ — $= B2$ , в $E3$ поместим $= (A2∕2)$ (ЦЕЛОЕ возвращает как раз нужный нам результат деления), в $F 3$ — $= B2$ , в $E4$ поместим $= A2$ , в $F 2$ — $= B2 − 1$ , в $E4$ поместим $= A2$ , в $F2$ — $= (B2∕2)$ . В ячейках столбца $G$ будем вести сумму куч (в $G2$ поместим $= E2 + F 2$ и растянем эту формулу на все пары куч).

В ячейке $I2$ запишем формулу $= ((E2 : F 2)∕2)+ (E2 : F 2)$ . Так мы получим сумму куч после самого аргессивного хода Вжика.

Условно окрасим в зеленый цвет ячейку $I2$ , если значение в ней меньше 35.

Постепенно перебирая значения ячейки $B2$ от 50 (например) вниз, заметим, что первый раз все ячейки результата выделяются зеленым при $S = 26$ . Значит, это максимальное значение, при котором выполняется условие.

Решение 2

from functools import cache
def moves(h):
    a, b = h
    mesi = []
    if a >= 1:
        mesi.append((a // 2, b))
        mesi.append((a - 1, b))
    if b >= 1:
        mesi.append((a, b // 2))
        mesi.append((a, b - 1))
    return mesi

@cache
def game(h):
    if sum(h) <= 34:
        return ’end’
    if any(game(x) == ’end’ for x in moves(h)):
        return ’win1’
    if all(game(x) == ’win1’ for x in moves(h)):
        return ’lose1’

for i in range(100, 11, -1):
    h = i, 22
    print(i, game(h))

Ответ: 26

Ошибка.
Попробуйте повторить позже

Задача 5#23711

Два игрока, Пупсень и Вупсень, играют в следующую игру. Перед игроками лежит куча камней. Игроки ходят по очереди, первый ход делает Пупсень. За один ход игрок может убрать из кучи один камень или убрать из кучи три камня. Например, имея кучу из 30 камней, за один ход можно получить кучу из 29 или 27 камней. Игра завершается в тот момент, когда количество камней в куче становится не более 11.

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

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

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

Показать ответ и решение

from functools import lru_cache
def moves(heap):
    m = []
    if heap > 0:
        m += [heap - 1]
    if heap > 2:
        m += [heap - 3]
    return m
@lru_cache(None)
def game(heap):
    if heap <= 11:
        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(12, 100):
    print(s, game(s))
# или
from functools import lru_cache
def moves(heap):
    m = []
    if heap > 0:
        m += [heap - 1]
    if heap > 2:
        m += [heap - 3]
    return m
@lru_cache(None)
def game(heap):
    if heap <= 11:
        return 0
    steps = [game(x) for x in moves(heap)]
    if any(x % 2 == 0 for x in steps):
        return min(x for x in steps if x % 2 == 0) + 1
    return max(steps) + 1
                                                                                                     
                                                                                                     
for s in range(1, 100):
    print(s, game(s), [game(x) for x in moves(s)])

Ответ: 17

Ошибка.
Попробуйте повторить позже

Задача 6#23802

Два игрока, Наруто и Саске, играют в следующую игру. Перед игроками лежат три кучи кунаев. Игроки ходят по очереди, первый ход делает Наруто. За один ход игрок может убрать из одной из куч один кунай или уменьшить количество кунаев в куче в два раза (если количество кунаев в куче нечётно, остаётся на 1 кунай больше, чем убирается). При любом из ходов кол-во кунаев в одной из куч должно измениться. Например, пусть в первой куче будет 6 кунаев, во второй куче 7 кунаев, а в третьей 8 кунаев; такую позицию мы будем обозначать (6, 7, 8). За один ход из позиции (6, 7, 8) можно получить любую из шести позиций: (5, 7, 8), (6, 6, 8), (6, 7, 7), (3, 7, 8), (6, 4, 8), (6, 7, 4). Игра завершается в тот момент, когда суммарное количество кунаев в кучах становится не более 32.

Победителем считается игрок, сделавший последний ход, то есть первым получивший позицию, в которой в кучах будет 32 или менее кунаев. В начальный момент в первой и второй куче было 11 кунаев, в третьей куче S кунаев, $S > 11$ .

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

Известно, что Саске выиграл своим первым ходом после неудачного первого хода Наруто. Укажите максимальное значение S, когда такая ситуация возможна.

Показать ответ и решение

from functools import lru_cache

def moves(heap):
    a, b, c = heap
    m = []
    if a > 1:
        m += [(a - 1, b, c), ((a + 1) // 2, b, c)]
    if b > 1:
        m += [(a, b - 1, c), (a, (b + 1) // 2, c)]
    if c > 1:
        m += [(a, b, c - 1), (a, b, (c + 1) // 2)]
    return m

@lru_cache(None)
def game(heap):
    if sum(heap) <= 32:
        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’

for s in range(100, 11, -1):
    if game((11, 11, s)) == ’LOSE1’:
        print(s)
        break

Ответ: 40

Ошибка.
Попробуйте повторить позже

Задача 7#26098

Два игрока, Петя и Ваня, играют в следующую игру. Перед игроками лежат две кучи камней. Игроки ходят по очереди, первый ход делает Петя. За один ход игрок может убрать из одной из куч один камень или уменьшить количество камней в куче в два раза (если количество камней в куче нечётно, остаётся на 1 камень больше, чем убирается). Например, пусть в одной куче 6, а в другой 9 камней; такую позицию мы будем обозначать (6, 9). За один ход из позиции (6, 9) можно получить любую из четырёх позиций: (5, 9), (3, 9), (6, 8), (6, 5). Игра завершается в тот момент, когда суммарное количество камней в кучах становится не более 32. Победителем считается игрок, сделавший последний ход, то есть первым получивший позицию, в которой в кучах будет 32 или меньше камней. В начальный момент в первой куче было 10 камней, во второй куче – $S$ камней, $S$ > 22.

Найдите значение $S$ , при котором Ваня выигрывает своим первым ходом при любой игре Пети.

Показать ответ и решение

from functools import lru_cache

def moves(h):
    a, b = h
    if a > 1 and b > 1:
        return (a - 1, b), (a, b - 1), (a // 2 + (a % 2), b), (a, b // 2 + (b % 2))
    if a > 1:
        return (a - 1, b), (a, b - 1), (a // 2 + (a % 2), b)
    if b > 1:
        return (a - 1, b), (a, b - 1), (a, b // 2 + (b % 2))
    return (a - 1, b), (a, b - 1)

@lru_cache(None)
def f(h):
    if sum(h) <= 32:
        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(23, 100):
    h = i, 10
    if f(h) == ’LOSE1’:
        print(i)

Ответ: 45

Ошибка.
Попробуйте повторить позже

Задача 8#30379

Два игрока, Петя и Ваня, играют в следующую игру. Перед игроками лежит куча камней. Игроки ходят по очереди, первый ход делает Петя. За один ход игрок может убрать из кучи один камень или убрать из кучи три камня. Например, имея кучу из $30$ камней, за один ход можно получить кучу из $29$ или $27$ камней. Игра завершается в тот момент, когда количество камней в куче становится не более $7.$

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

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

Известно, что Ваня выиграл своим первым ходом после неудачного первого хода Пети. Укажите максимальное значение $S,$ когда такая ситуация возможна.

Показать ответ и решение

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

Очевидно, что Петя должен «сглупить», чтобы изначальная позиция была максимальной.

Значит $S − 3− 3 ≤ 7 ⇒ S ≤ 13 ⇒ S = 13.$

Решение Excel

$PIC$

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

В первую ячейку в столбце Петя записываем формулу =B4-1. Далее из полученного значения рассматриваем ходы Вани и, соответственно, записываем формулу в ячейки столбца Ваня =J4-3 (рассматриваем только один ход, так как Ване выгоднее всего вычесть как можно больше камней, чтобы точно победить, если это возможно в данном случае).

Теперь добавим условное форматирование. Все ячейки, относящиеся к столбику Петя мы окрасим красным (в разделе Главная выберем условное форматирование $⇒$ Правила выделения ячеек $⇒$ Меньше…, в открывшемся окошке записываем $8$ и выбираем красный цвет), а те, что относятся к столбцам Старт и Ваня мы сделаем зелёными (делаем аналогично с ходами Пети, только вместо красного цвета выбираем зелёный).

Скопируем табличку с первого хода Пети по второй ход Пети без заголовков и вставим её копию чуть ниже первой, теперь заменим формулу в первом ходе Пети на =B4-3.

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

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

from functools import lru_cache


def moves(heap):
    m = []
    if heap >= 1:
        m += [heap - 1]
    if heap >= 3:
        m += [heap - 3]
    return m


@lru_cache(None)
def game(heap):
    if heap <= 7:
        return ’END’
    elif any(game(x) == ’END’ for x in moves(heap)):
        return ’P1’
    elif any(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(100, 7, -1):
    if game(s) == ’V1’:
        print(s)
        break

Ответ: 13

Ошибка.
Попробуйте повторить позже

Задача 9#30382

Два игрока, Петя и Ваня, играют в следующую игру. Перед игроками лежат две кучи камней. Игроки ходят по очереди, первый ход делает Петя. За один ход игрок может убрать из одной из куч один камень или уменьшить количество камней в куче в два раза (если количество камней в куче нечётно, остаётся на $1$ камень меньше, чем убирается). При любом из ходов кол-во камней в одной из куч должно измениться. Например, пусть в одной куче будет $6$ камней, а в другой $9$ камней; такую позицию мы будем обозначать $(6,9).$ За один ход из позиции $(6,9)$ можно получить любую из четырёх позиций: $(5,9),(6,8),(3,9),(6,4).$ Игра завершается в тот момент, когда суммарное количество камней в кучах становится не более $12.$

Победителем считается игрок, сделавший последний ход, то есть первым получивший позицию, в которой в кучах будет $12$ или менее камней. В начальный момент в первой куче было $9$ камня, во второй куче $S$ камней, $S > 3$

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

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

Показать ответ и решение

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

Очевидно, что при $S ≤ 8$ Петя выигрывает своим первым ходом (уменьшением кучи, в которой лежит $9$ камней, в два раза). Значит при $S = 9$ Петя не сможет победить своим первым ходом, зато это сможет сделать Ваня. Ответ $9$ .

Решение Excel

$PIC$

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

В ячейку $B4$ запишем $9$ , а в D4 запишем формулу =СУММ(B4:C4).

Так как Ване нужно победить первым ходом, то выгоднее всего ходить самым агрессивным ходом — делением на два. В ячейку $H4$ запишем формулу =ЦЕЛОЕ(МАКС(E4:F4)/2), в $I4$ — =МИН(E4:F4).

В ячейку J4 запишем формулу =СУММ(H4:I4), скопируем и вставим её в следующую клеточку.

В $E4$ запишем =B4-1, в $F4−$ =C4, а в $G4$ — =СУММ(E4:F4).

Добавим условное форматирование. Выделим суммы, которые относятся к Пете и затем в разделе Главная выберем условное форматирование $⇒$ Правила выделения ячеек $⇒$ Меньше…, в открывшемся окошке записываем $13$ и выбираем красный цвет. Выделим сумму, которая относится к старту, сделаем её зелёной по аналогии с суммой после хода Пети. То же самое сделаем с суммой, которая относится к Ване.

Скопируем полученную таблицу и вставим её три раза, каждый раз чуть ниже предыдущей. Заменим первые ходы Пети, чтобы не было повторов.

В начальную позицию запишем $9$ и начнём подставлять значения в ячейку $C4$ , пока все суммы камней после хода Вани не станут зелёными.

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

from functools import lru_cache


def moves(heap):
    a, b = heap
    m = []
    if a >= 1:
        m += [(a - 1, b), (a // 2, b)]
    if b >= 1:
        m += [(a, b - 1), (a, b // 2)]
    return m


@lru_cache(None)
def game(heap):
    if sum(heap) <= 12:
        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(100, 3, -1):
    if game((9, s)) == ’V1’:
        print(s)

Ответ: 9

Ошибка.
Попробуйте повторить позже

Задача 10#30397

Два игрока, Петя и Ваня, играют в следующую игру. Перед игроками лежит куча камней. Игроки ходят по очереди, первый ход делает Петя. За один ход игрок может убрать из кучи половину камней, если количество камней в куче делится на два, иначе убрать из кучи два камня или убрать из кучи две трети камней, если количество камней в куче делится на три, иначе убрать из кучи три камня. Например, пусть в куче будет $6$ камней. Тогда за один ход можно получить кучу из $3$ или $2$ камней. Игра завершается в тот момент, когда количество камней в куче становится меньше или равно $2.$

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

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

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

Показать ответ и решение

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

Рассмотрим $S = 6.$ Первым ходом Петя делает неудачный ход в $S = 3,$ после чего Ваня убирает из кучи две трети камней, создавая этим позицию $S = 1$ и побеждая.

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

from functools import lru_cache


def moves(heap):
    m = []
    if heap % 2 == 0:
        m += [heap // 2]
    else:
        if heap > 1:
            m += [heap - 2]
    if heap % 3 == 0:
        m += [heap // 3]
    else:
        if heap > 2:
            m += [heap - 3]
    return m


@lru_cache(None)
def game(heap):
    if heap <= 2:
        return 0
    steps = [game(x) for x in moves(heap)]
    if any(x % 2 == 0 for x in steps):
        return min(x for x in steps if x % 2 == 0) + 1
    return max(steps) + 1


for s in range(3, 100):
    print(s, game(s), [game(x) for x in moves(s)])

Ответ: 6

19.04 Уменьшение количества камней