Question

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

**Вопросы:**

1. Найдите максимальное значение $S$, при котором Петя не может выиграть первым ходом из позиции $(7, S)$.
2. Кто имеет выигрышную стратегию из позиции $(6, 7)$? Опишите эту стратегию.
3. Кто имеет выигрышную стратегию из позиции $(2, 3)$? Опишите эту стратегию.

Accepted Answer

Answer

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

**Вопрос 1.**

После первого хода Петя из позиции $(7, S)$ может получить либо $(7+S, S)$, либо $(7, S+7)$. Чтобы Петя не выиграл первым ходом, обе получившиеся позиции должны иметь сумму меньше 28:
- $(7+S) + S < 28 \Rightarrow 2S < 21 \Rightarrow S < 10{,}5$
- $7 + (S+7) < 28 \Rightarrow S < 14$

Более строгое условие: $S < 10{,}5$, откуда $S_{\max} = 10$.

**Вопрос 2.**

Из позиции $(6, 7)$ Петя может сделать ход в $(13, 7)$ или $(6, 13)$. Обе позиции имеют сумму 20, что меньше 28, поэтому Петя не выигрывает первым ходом.

Из позиции $(13, 7)$ Ваня может перейти в $(20, 7)$ (сумма 27) или $(13, 14)$ (сумма 27). Из позиции $(6, 13)$ Ваня может перейти в $(19, 13)$ (сумма 32 ≥ 28) или $(6, 19)$ (сумма 25).

Ваня выбирает ход в $(19, 13)$ и выигрывает. Таким образом, **выигрышная стратегия у Вани**: независимо от хода Петя, Ваня может ответить ходом, приводящим к сумме ≥ 28.

**Вопрос 3.**

Дерево ходов из позиции $(2, 3)$:

```
                    (2,3)
                   /     \
              П   /       \   П
                 /         \
            (5,3)           (2,5)
            /   \           /   \
        В  /     \  В   В  /     \  В
          /       \       /       \
      (5,8)      (5,3)  (7,5)    (2,7)
      /   \      (сумма 8)  /   \
  П  /     \  П          P /     \ P
    /       \            /       \
(13,8)    (5,13)    (12,5)    (7,12)
(сумма 21) (сумма 18) /   \      /   \
                   В /     \ В  В /     \ В
                    /       \    /       \
                (12,17)   (12,5) (19,12) (7,19)
                (сумма 29) (сумма 17) (сумма 31) (сумма 26)
```

Анализируя дерево: из $(2, 3)$ оба хода Петя приводят к позициям, из которых Ваня может гарантировать выигрыш. Из $(5, 3)$ Ваня ходит в $(5, 8)$, откуда любой ход Петя приводит к выигрышу Вани. Из $(2, 5)$ Ваня ходит в $(7, 5)$, откуда также любой ход Петя ведёт к победе Вани.

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

![Рисунок](https://inf-ege.sdamgia.ru/get_file?id=65503)

Задание №26ПрограммированиеЕГЭ по информатике