Дошкольникам
1 класс
2 класс
3 класс
4 класс
5 класс
6 класс
7 класс
8 класс
9 класс
10 класс
11 класс
ОГЭ
ЕГЭ
ВУЗ
Для всех
Назад

21. Выигрышная стратегия: часть 3: Тогда за один ход можно получить любую из четырёх позиций: (24…

Задание #295169
Решено верно
Решено неверно
Сообщить о проблеме

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

За один ход игрок может:
— добавить в одну из куч (по своему выбору) $4$ камня;
— увеличить количество камней в одной из куч (по своему выбору) в 3 раза.

Например, пусть в одной куче $20$ камней, а в другой $30$ камней; такую позицию в игре обозначим ($20, 30$). Тогда за один ход можно получить любую из четырёх позиций: $(24, 30), (20, 34), (60, 30), (20, 90).$

Для того чтобы делать ходы, у каждого игрока есть неограниченное количество камней. Игра завершается в тот момент, когда суммарное количество камней в двух кучах становится не менее $154$. Победителем считается игрок, сделавший последний ход, то есть первым получивший такую игровую позицию, при которой в двух кучах суммарно $154$ камня или больше. В начальный момент в первой куче $11$ камней, во второй куче – $S$ камней; $1 \leq S \leq 142$.

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

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

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

Первый способ – математическое решение

Проверка игрового дерева даёт подходящие значения $S=41,\ 42,\ 44$. Минимальное из них: $S=41$.

Рассмотрим $S=41$. После первого хода Пети возможны позиции: $(15;41),\ (11;45),\ (33;41),\ (11;123)$.

Если получено $(33;41)$ или $(11;123)$, Ваня выигрывает сразу.

Из позиций $(15;41)$ и $(11;45)$ Ваня переводит игру в позицию $(15;45)$.

После любого хода Пети получим: $(19;45),\ (15;49),\ (45;45),\ (15;135)$.

  • Из каждой позиции Ваня выигрывает одним ходом. Например:
  • $19+45\cdot3=154$,
  • $15+49\cdot3=162$,
  • $45\cdot3+45=180$,
  • $15+135+4=154$.

При этом после хода Пети $(11;41)\rightarrow(15;41)$ Ваня не может выиграть сразу. Значит, гарантированной победы первым ходом у него нет.

Второй способ – решение с помощью Python

def moves(a, b):
    return [(a + 4, b), (a, b + 4),
            (a * 3, b), (a, b * 3)]

def win1(a, b):
    return a + b < 154 and any(
        x + y >= 154 for x, y in moves(a, b)
    )

def win2(a, b):
    if win1(a, b):
        return True

    return any(
        all(
            x + y < 154 and win1(x, y)
            for x, y in moves(c, d)
        )
        for c, d in moves(a, b)
        if c + d < 154
    )

for S in range(1, 143):
    petya = moves(11, S)

    if (all(a + b < 154 and win2(a, b)
            for a, b in petya)
        and not all(win1(a, b) for a, b in petya)):
        print(S)
        break

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

Программа выведет: $41$.

Показать
Очки опыта 20
Спросить Зави
0 заданий сегодня

Предложить улучшение