Перекладывание камней одна куча —Каталог задач по ЕГЭ - Информатика

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

Задача 1#38807

Для игры, описанной ранее, найдите такое значение $S$ , при котором одновременно выполняются два условия:

– у ТС есть выигрышная стратегия, позволяющая ему выиграть первым или вторым ходом при любой игре ДЮ;

– у ТС нет стратегии, которая позволит ему гарантированно выиграть первым ходом.

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

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)

Ответ: 13

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

Задача 2#38806

Для игры, описанной в предыдущем задании, найдите два таких значения $S$ , при которых у ДЮ есть выигрышная стратегия, причём ДЮ не может выиграть за один ход и ДЮ может выиграть своим вторым ходом независимо от того, как будет ходить ТС.

В ответе запишите числа в порядке возрастания без пробелов и знаков препинаний.

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

from functools import lru_cache

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

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

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

Ответ: 1415

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

Задача 3#38805

Два игрока, ДЮ и ТС, играют в следующую игру. Перед игроками лежит куча крабов. Игроки ходят по очереди, первый ход делает ДЮ. За один ход игрок может добавить в кучу одного краба или добавить в кучу два краба или увеличить количество крабов в куче в $3$ раза. Например, имея кучу из $10$ крабов, за один ход можно получить кучу из $11$ или $12$ или $30$ крабов. Чтобы делать ходы, у каждого игрока есть неограниченное количество крабов. Игра завершается в тот момент, когда количество крабов в куче становится не менее $50$ .

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

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

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

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

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)

Ответ: 16

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

Задача 4#38804

Для игры, описанной ранее, найдите такое значение $S$ , при котором одновременно выполняются два условия:

– у АВ есть выигрышная стратегия, позволяющая ему выиграть первым или вторым ходом при любой игре АР;

– у АВ нет стратегии, которая позволит ему гарантированно выиграть первым ходом.

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

from functools import lru_cache

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

@lru_cache(None)
def f(h):
    if (h >= 42):
        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 reversed(range(1, 42)):
    if f(s) == ’V2’:
        print(s)

Ответ: 18

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

Задача 5#38803

Для игры, описанной в предыдущем задании, найдите такое максимальное значение $S$ , при котором у АР есть выигрышная стратегия, причём АР не может выиграть за один ход и АР может выиграть своим вторым ходом независимо от того, как будет ходить АВ.

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

from functools import lru_cache

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

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

for s in reversed(range(1, 42)):
    if f(s) == ’P2’:
        print(s)
        break

Ответ: 19

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

Задача 6#38802

Два игрока, АР и АВ, играют в следующую игру. Перед игроками лежит куча маркеров. Игроки ходят по очереди, первый ход делает АР. За один ход игрок может добавить в кучу один маркер или увеличить количество маркеров в куче в $2$ раза. Например, имея кучу из $17$ маркеров, за один ход можно получить кучу из $18$ или $34$ маркеров. Чтобы делать ходы, у каждого игрока есть неограниченное количество маркеров. Игра завершается в тот момент, когда количество маркеров в куче становится не менее $42$ .

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

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

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

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

from functools import lru_cache

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

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

for s in range(1, 42):
    if f(s) == ’P1’:
        print(s)
        break

Ответ: 21

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

Задача 7#33612

Найдите значение $S$ , при котором одновременно выполняются два условия:

— у Вани есть выигрышная стратегия, позволяющая ему выиграть первым или вторым ходом при любой игре Пети;

— у Вани нет стратегии, которая позволит ему гарантированно выиграть первым ходом.

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

from functools import lru_cache

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

@lru_cache(None)
def f(h):
    if h >= 185:
        return "END"
    if any(f(x) == "END" for x in m(h)):
        return "P1"
    if all(f(x) == "P1" for x in m(h)):
        return "V1"
    if any(f(x) == "V1" for x in m(h)):
        return "P2"
    if all(f(x) == "P1" or f(x) == "P2" for x in m(h)):
        return "V2"
for i in range(1, 185):
    if f(i) == "V2":
        print(i)

Ответ: 90

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

Задача 8#33611

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

— Петя не может выиграть за один ход;

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

Найденные значения запишите в ответе в порядке возрастания без разделительных знаков.

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

def f(h):
    if h >= 185:
        return "END"
    if any(f(x) == "END" for x in m(h)):
        return "P1"
    if all(f(x) == "P1" for x in m(h)):
        return "V1"
    if any(f(x) == "V1" for x in m(h)):
        return "P2"
for i in range(1, 185):
    if f(i) == "P2":
        print(i)

Ответ: 4691

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

Задача 9#33610

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

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

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

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

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

from functools import lru_cache

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

@lru_cache(None)
def f(h):
    if h >= 185:
        return "END"
    if any(f(x) == "END" for x in m(h)):
        return "P1"
    if all(f(x) == "P1" for x in m(h)):
        return "V1"
for i in range(1, 185):
    if f(i) == "V1":
        print(i)

Ответ: 92

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

Задача 10#30408

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

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

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

Мы знаем, что $S = 6$ это позиция типа $WIN2$ . Тогда рассмотрим $S = 5 :$

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

from functools import lru_cache


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


@lru_cache(None)
def game(heap):
    if heap[0] >= 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):
    if game((s, -1)) == ’V2’:
        print(s)

Ответ: 5

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

Задача 11#30407

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

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

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

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

Рассмотрим позицию $S = 6.$ Из неё Петя сходит в позицию $S = 18$ утроением камней, после чего Ваня не сможет утроить кучу, и сходит либо в $S = 20,$ либо в $S = 19.$ Из этих позиций Петя выигрывает утроением камней. Также рассмотрим позицию $S = 15.$ Из неё Петя сходит в $S = 16,$ а это позиция типа $LOSE1$ .

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

from functools import lru_cache


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


@lru_cache(None)
def game(heap):
    if heap[0] >= 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):
    if game((s, -1)) == ’P2’:
        print(s)

Ответ: 615

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

Задача 12#30406

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

Например, если в начале игры в куче $3$ камня, Петя может первым ходом получить кучу из $4,5$ или $9$ камней. Если Петя получил кучу из $5$ камней (добавил $2$ камня), то следующим ходом Ваня может получить $6$ или $15$ камней. Получить $7$ камней Ваня не может, так как для этого нужно добавить $2$ камня, а такой ход только что сделал Петя.

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

В начальный момент в куче было $S$ камней, $1 ≤ S ≤ 49.$

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

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

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

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

Для начала найдём все позиции $WIN1$ . Это позиции $S ≥ 17.$ Рассмотрим позицию $S = 16.$ Из неё Петя утроением камней достигнет позиции $S = 48,$ из которой Ваня выиграет добавив в кучу $2$ камня.

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

from functools import lru_cache


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


@lru_cache(None)
def game(heap):
    if heap[0] >= 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):
    if game((s, -1)) == ’V1’:
        print(s)

Ответ: 16

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

Задача 13#30402

Для игры, описанной в задании $40,$ найдите два таких значения $S,$ при которых одновременно выполняются два условия:

– у Вани есть выигрышная стратегия, позволяющая ему выиграть первым или вторым ходом при любой игре Пети;

– у Вани нет стратегии, которая позволит ему гарантированно выиграть первым ходом.

В ответе запишите числа в порядке возрастания без пробелов и знаков препинаний.

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

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

Рассмотрим $S = 1$ . Из этой позиции Петя сможет сходить только в $S = 3,$ а мы знаем, что это позиция $WIN2$ . Теперь рассмотрим позицию $S = 2 :$

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

from functools import lru_cache


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


@lru_cache(None)
def game(heap):
    if heap >= 63:
        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, 63):
    if game(s) == ’LOSE2’:
        print(s)

Ответ: 12

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

Задача 14#30401

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

В ответе запишите числа в порядке возрастания без пробелов и знаков препинаний.

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

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

Рассмотрим $S = 3.$ Первым ходом Петя достигнет позиции $S = 9,$ из которой Ваня не сможет сделать никаких ходов, кроме утроения, что приведёт Петю в позицию $S = 27,$ из которой он победит утроением. Теперь рассмотрим $S = 18.$ Первым ходом Петя сходит в позицию $S = 19,$ из которой Ваня сможет сходить лишь в $S = 57,$ из которой Петя победит также утроением.

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

from functools import lru_cache


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


@lru_cache(None)
def game(heap):
    if heap >= 63:
        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, 63):
    if game(s) == ’WIN2’:
        print(s)

Ответ: 318

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

Задача 15#30400

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

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

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

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

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

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

Для начала найдём все позиции типа $WIN1$ . Это позиции $S = 60,$ $S = 62$ и все нечётные позиции $S ≥ 21.$ Тогда из позиции $S = 7$ Петя может сходить только в $S = 21$ и Ваня также умножит количество камней в куче на $3$ и победит.

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

from functools import lru_cache


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


@lru_cache(None)
def game(heap):
    if heap >= 63:
        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, 63):
    if game(s) == ’LOSE1’:
        print(s)
        break

Ответ: 7

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

Задача 16#30399

Для игры, описанной в задании $37,$ найдите минимальное значение $S,$ при котором одновременно выполняются два условия:

– у Вани есть выигрышная стратегия, позволяющая ему выиграть первым или вторым ходом при любой игре Пети;

– у Вани нет стратегии, которая позволит ему гарантированно выиграть первым ходом.

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

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

Рассмотрим $S = 13.$ Из этой позиции Петя может сходить в $S = 10$ или $S = 11,$ а из этих позиций Ваня сходит либо в $S = 7$ , либо в $S = 8,$ а мы знаем, что это позиции типа $LOSE1$ .

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

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):
    if game(s) == 4:
        print(s)
        break

Ответ: 13

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

Задача 17#30398

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

В ответе запишите числа в порядке возрастания без пробелов и знаков препинаний.

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

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

Для начала давайте найдём все позиции $WIN1$ . Это все $3 ≤ S ≤ 6.$ Теперь найдём все позиции $LOSE1$ . Это позиции $S = 7,8,12.$ Рассмотрим позицию $S = 9.$ Уменьшение на $2$ приведёт нас в $S = 7,$ а это $LOSE1$ . Теперь Рассмотрим позицию $S = 36.$ Уменьшение в $3$ раза приведёт нас в $S = 12,$ а это $LOSE1$ . Пишем их в ответ.

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

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):
    if game(s) == 3:
        print(s)

Ответ: 936

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

Задача 18#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#30393

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

– у Вани есть выигрышная стратегия, позволяющая ему выиграть первым или вторым ходом при любой игре Пети;

– у Вани нет стратегии, которая позволит ему гарантированно выиграть первым ходом.

Если такого значения нет, в ответ запишите $0.$

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

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

Рассмотрим $S = 57$ :

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

from functools import lru_cache


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


@lru_cache(None)
def game(heap):
    if 64 <= heap <= 84:
        return ’END’
    elif heap > 84:
        return ’P1’
    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(63, 0, -1):
    if game(s) == ’V2’:
        print(s)
        break

Ответ: 57

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

Задача 20#30392

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

В ответе запишите количество найденных чисел.

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

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

Из предыдущего задания мы знаем все позиции $LOSE1$ . Значит нам достаточно найти все позиции, которые ведут в $LOSE1$ . Это позиции $S = 7,19,20,58,59.$

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

from functools import lru_cache


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


@lru_cache(None)
def game(heap):
    if 64 <= heap <= 84:
        return ’END’
    elif heap > 84:
        return ’P1’
    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’


count = 0
for s in range(1, 64):
    if game(s) == ’P2’:
        print(s, end=’’)

Ответ: 5