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

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

Задача 1#56322

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

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

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

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

from functools import lru_cache
def moves(h):
    a = [h * 2]
    if (h + 1) % 2 == 0:
        a += [h + 1]
        a += [h + 3]
    return a
@lru_cache(None)
def f(h):
    if h >= 88:
        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, 88)):
    if f(s) == ’V2’:
        print(s)
        break

Ответ: 10

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

Задача 2#56321

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

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

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

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

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

from functools import lru_cache
def moves(h):
    a = [h * 2]
    if (h + 1) % 2 == 0:
        a += [h + 1]
        a += [h + 3]
    return a
@lru_cache(None)
def f(h):
    if h >= 88:
        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’
ans = []
for s in reversed(range(1, 88)):
    if f(s) == ’P2’:
        ans += [str(s)]
        if len(ans) == 2:
            break
print(ans[-1] + ans[-2])

Ответ: 3941

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

Задача 3#56320

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

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

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

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

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

from functools import lru_cache
def moves(h):
    a = [h * 2]
    if (h + 1) % 2 == 0:
        a += [h + 1]
        a += [h + 3]
    return a
@lru_cache(None)
def f(h):
    if h >= 88:
        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, 88):
    if f(s) == ’V1’:
        print(s)
        break

Ответ: 22

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

Задача 4#38810

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

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

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

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

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

from functools import lru_cache


def moves(h):
    a, b = h
    return (a + 2, b), (a, b + 2), (a * 3, b), (a, b * 3)


@lru_cache(None)
def f(h):
    if (sum(h) >= 99):
        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, 94):
    h = 5, s
    if f(h) == ’V2’:
        print(s)

Ответ: 28

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

Задача 5#38809

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

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

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

from functools import lru_cache


def moves(h):
    a, b = h
    return (a + 2, b), (a, b + 2), (a * 3, b), (a, b * 3)


@lru_cache(None)
def f(h):
    if (sum(h) >= 99):
        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, 94):
    h = 5, s
    if f(h) == ’P2’:
        print(s)

Ответ: 2930

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

Задача 6#38808

Два игрока, Финес и Ферб, играют в следующую игру. Перед игроками лежат две кучи деталей. Игроки ходят по очереди, первый ход делает Финес. За один ход игрок может добавить в одну из куч две детали или увеличить количество деталей в куче в три раза. Например, пусть в одной куче будет $11$ деталей, а в другой $9$ деталей; такую позицию мы будем обозначать $(11,9)$ . За один ход из позиции $(11,9)$ можно получить любую из четырёх позиций: $(13,9),(11,11),(33,9),(11,27)$ . Игра завершается в тот момент, когда суммарное количество деталей в кучах становится не менее $99$ .

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

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

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

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

from functools import lru_cache


def moves(h):
    a, b = h
    return (a + 2, b), (a, b + 2), (a * 3, b), (a, b * 3)


@lru_cache(None)
def f(h):
    if (sum(h) >= 99):
        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, 94):
    h = 5, s
    if f(h) == ’V1’:
        print(s)
        break

Ответ: 31

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

Задача 7#30396

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

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

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

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

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

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

Рассмотрим $2$ позиции, когда $S = 84$ и $S = 91 :$

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

from sys import setrecursionlimit
from functools import lru_cache

setrecursionlimit(50000)


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


@lru_cache(None)
def game(heap):
    a, b = heap
    if a * b >= 2048:
        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, 187):
    if game((11, s)) == ’V2’:
        print(s, end=’’)

Ответ: 8491

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

Задача 8#30395

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

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

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

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

После небольшого перебора выясняем, что нам подходят значения $S = 46,85,92.$ В каждой из этих позиций есть ход, ведущий Ваню в позицию $LOSE1$ : при первом значении Петя умножит первую кучу на $2$ , при втором увеличит первую кучу на $1$ , а при третьем значении увеличит вторую кучу на $1$ . Значит они нам подходят.

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

from sys import setrecursionlimit
from functools import lru_cache

setrecursionlimit(50000)


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


@lru_cache(None)
def game(heap):
    a, b = heap
    if a * b >= 2048:
        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, 187):
    if game((11, s)) == ’P2’:
        print(s, end=’’)

Ответ: 468592

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

Задача 9#30394

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

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

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

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

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

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

Очевидно, что при $S ≥ 94$ Петя выигрывает первым ходом, домножая кучу $S$ на $2$ . Однако при $S = 93$ Петя не выигрывает своим первым ходом, а Ваня же выигрывает при любой игре Пети. Меньшие значения S не подходят, так как ни одна из них не ведёт только в позиции $WIN1$ .

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

from sys import setrecursionlimit
from functools import lru_cache

setrecursionlimit(50000)


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


@lru_cache(None)
def game(heap):
    a, b = heap
    if a * b >= 2048:
        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, 187):
    if game((11, s)) == ’V1’:
        print(s)
        break

Ответ: 93

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

Задача 10#30387

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

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

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

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

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

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

Рассмотрим позицию $(27,5)$ :

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

from functools import lru_cache


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


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

Ответ: 27

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

Задача 11#30386

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

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

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

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

Рассмотрим позицию $(28,5)$ . Петя добавит в первую кучу $1$ камень, после чего любой ход Вани не приведёт его к победе. Таким образом Петя выигрывает за $2$ хода.

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

from functools import lru_cache


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


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

Ответ: 28

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

Задача 12#30385

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

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

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

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

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

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

Очевидно, что самый сильный ход (добавление в одну из куч количество из другой) произошёл $2$ раза. Рассмотрим позицию $(5,S)$ . Петя добавляет к первой куче $S$ камней, создавая позицию $(5+ S,18)$ . После этого Ваня добавляет ко второй куче $5 + S$ камней, создавая позицию $(5 + S,5+ 2S)$ и выигрывает. При каком $S$ это возможно? При $5 + S + 5 +2S = 10 +3S ≥ 63$ , а минимальное такое целое $S$ равно 18.

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

from functools import lru_cache


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


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

Ответ: 18

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

Задача 13#30384

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

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

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

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

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

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

Рассмотрим позицию $(9,20)$ :

Если Петя сходит в $(9,10)$ , то Ваня ответит ходом, ведущим в $(9,9)$ , а мы знаем, что Петя проигрывает в этой позиции за один ход;
Если Петя сходит в $(4,20)$ , то Ваня сходит в $(3,20)$ . Из этой позиции Петя никак не выиграет за один ход, а Ваня победит делением второй кучи;
Если Петя сходит в $(8,20)$ , то Ваня сходит в $(8,10)$ . Петя никак не выиграет за $1$ ход, а Ваня выиграет делением второй кучи;
Если Петя сходит в $(9,19)$ , то Ваня сходит в $(9,9)$ . Петя не выигрывает за $1$ ход, а Ваня побеждает делением второй кучи.

Решение Excel

$PIC$ $PIC$

Для решения используем табличку, которую сделали для решения 20 задачи.

Добавляем новый столбец Ваня (второй ход Вани).

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

Перепишем формулы в ячейках, отвечающих за первый ход Пети, так, чтобы не было повторов.

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

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

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

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

Ответ: 20

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

Задача 14#30383

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

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

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

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

Мы знаем, что позиция $(9,9)$ – это позиция $LOSE1$ . Значит все позиции, которые ведут в эту, являются $WIN2$ . Нам подойдут значения $S = 18$ и $S = 19$ $(18∕2 = 9 и 19∕2 = 9$ ). Значит нам подойдёт значение $19$ .

Решение Excel

$PIC$

Для решения используем табличку, которую сделали для решения 19 задачи.

Добавляем новый столбик — Петя (второй ход Пети).

Вырезаем имеющиеся числовые значения из таблички и вставляем их в ячейку $E4$ , в неё же записываем =B4-1, а в F4 — =С4

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

Копируем полученную таблицу в вставляем её три раза. Меняем первые ходы Пети, чтобы не было повторов.

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

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

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

Ответ: 19

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

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

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

Задача 16#30378

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

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

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

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

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

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

Мы знаем, что при $S = 21$ Петя выигрывает своим вторым ходом. Рассмотрим позицию $(20,4)$ . Ваня сходит из нее в позицию $(21,4)$ и игра отразится. Теперь уже Ваня выиграет своим вторым ходом.

Решение Excel

$PIC$ $PIC$

Для решения используем табличку, которую сделали для решения 20 задачи.

Добавляем новый столбец Ваня (второй ход Вани).

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

Перепишем формулы в ячейках, отвечающих за первый ход Пети, так, чтобы не было повторов.

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

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

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

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) >= 48:
        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, 44):
    if game((4, s)) == ’V2’:
        print(s)

Ответ: 20

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

Задача 17#30377

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

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

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

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

Очевидно, что при $S ≥ 22$ Петя выигрывает свои первым ходом. Рассмотрим позицию $(21,4)$ . Из неё Петя пойдёт в $(21,5)$ , и тогда любой ход Вани не приведёт к победе, а Петя выиграет своим вторым ходом. Значит $S = 21$ нам подходит.

Решение Excel

$PIC$

Для решения используем табличку, которую сделали для решения 19 задачи.

Добавляем новый столбик — Петя (второй ход Пети).

Вырезаем имеющиеся числовые значения из таблички и вставляем их в ячейку $E4$ , в неё же записываем =B4+1, а в F4 — =С4

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

Копируем полученную таблицу в вставляем её три раза. Меняем первые ходы Пети, чтобы не было повторов.

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

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

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) >= 48:
        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, 44):
    if game((4, s)) == ’P2’:
        print(s)

Ответ: 21

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

Задача 18#30376

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

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

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

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

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

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

Предположим, что Петя увеличил наибольшую кучку в $2$ раза. Тогда Ваня мог увеличить её еще в $2$ раза и выиграть. Рассмотрим неравенство:

$4S + 4 ≥ 48 ⇒ S ≥ 11$

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

Решение Excel

$PIC$

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

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

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

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

В $E4$ запишем =B4+1, а в $F 4−$ =C4.

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

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

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

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

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) >= 48:
        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(1, 44):
    if game((4, s)) == ’V1’:
        print(s)
        break

Ответ: 11

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

Задача 19#30375

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

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

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

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

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

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

Рассмотрим позицию $(17,7)$ :

$(17,7) ⇒ (51,7) ⇒ (153,21) ⇒$ Ваня выиграл за $1$ ход
$(17,7) ⇒ (17,21) ⇒ (56,21) ⇒$ Ваня выиграл за $1$ ход
$(17,7) ⇒ (19,7) ⇒ (57,9) ⇒$ Ваня выиграл за $1$ ход
$(17,7) ⇒ (17,9) ⇒ (51,9) ⇒ (153,9)$ Ваня выиграл за $2$ хода

Значит это позиция $LOSE2$ . Ответ $17$ .

Решение Excel

$PIC$ $PIC$

Для решения используем табличку, которую сделали для решения 20 задачи.

Добавляем новый столбец Ваня (второй ход Вани).

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

Перепишем формулы в ячейках, отвечающих за первый ход Пети, так, чтобы не было повторов.

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

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

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

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) >= 63:
        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, 56):
    if game((7, s)) == ’V2’:
        print(s)

Ответ: 17

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

Задача 20#30374

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

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

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

Мы знаем, что позиция $(18,7)$ это $LOSE1$ . В неё мы можем прийти из позиций $(6,7)$ и $(16,7)$ , поэтому ответ $2$ .

Решение Excel

$PIC$ $PIC$

Для решения используем табличку, которую сделали для решения 19 задачи.

Добавляем новый столбик — Петя (второй ход Пети).

Вырезаем имеющиеся числовые значения из таблички и вставляем их в ячейку $E4$ , в неё же записываем =B4+2, а в F4 — =С4

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

Копируем полученную таблицу в вставляем её три раза. Меняем первые ходы Пети, чтобы не было повторов.

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

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

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) >= 63:
        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’


count = 0
for s in range(1, 56):
    if game((7, s)) == ’P2’:
        count += 1
print(count)

Ответ: 2