Question

Два игрока, Паша и Валя, играют в следующую игру. Перед игроками лежит куча камней. Игроки ходят по очереди, первый ход делает Паша. За один ход игрок может добавить в кучу один камень или увеличить количество камней в куче в два раза. Например, имея кучу из 15 камней, за один ход можно получить кучу из 16 или 30 камней. У каждого игрока, чтобы делать ходы, есть неограниченное количество камней.Игра заканчивается, когда в куче не меньше 42 камней. При этом, если число камней в куче не превышает 74, то побеждает игрок, сделавший последний ход, иначе выигрывает его оппонент. В начальный момент в куче было *S* камней; 1 ≤ *S* ≤ 41.

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

Задание 1а) Укажите все такие значения числа *S*, при которых Паша может выиграть в один ход. Опишите его стратегию.б) У кого есть выигрышная стратегия при *S* = 38, 39, 40?

Задание 2Кто из игроков имеет выигрышную стратегию при *S* = 19, 20?

Задание 3Кто из игроков имеет выигрышную стратегию при *S* = 18?

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

Accepted Answer

Answer

### СТАТЕМЕНТ

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

Игра заканчивается, когда в куче не меньше 42 камней. При этом, если число камней в куче не превышает 74, то побеждает игрок, сделавший последний ход, иначе выигрывает его оппонент. В начальный момент в куче было $S$ камней; $1 \leq S \leq 41$.

Выигрышная стратегия — это описание ходов, при которых игрок побеждает при любых действиях противника.

**Задание 1**

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

б) У кого есть выигрышная стратегия при $S = 38, 39, 40$?

**Задание 2**

Кто из игроков имеет выигрышную стратегию при $S = 19, 20$?

**Задание 3**

Кто из игроков имеет выигрышную стратегию при $S = 18$? Постройте дерево игры, где узлы — позиции (количество камней), а рёбра — сделанные ходы.

### РЕШЕНИЕ

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

**Задание 1а)**

Паша выигрывает в один ход, если после его хода куча содержит от 42 до 74 камней (тогда Паша сделал последний ход и побеждает).

Возможные ходы Паши из позиции $S$:
- Добавить 1: получить $S + 1$
- Удвоить: получить $2S$

Условие победы в один ход: $42 \leq S + 1 \leq 74$ или $42 \leq 2S \leq 74$.

Из первого: $41 \leq S \leq 73$, но $S \leq 41$, поэтому $S = 41$.

Из второго: $21 \leq S \leq 37$.

**Ответ на 1а):** При $S \in \{21, 22, \ldots, 37, 41\}$ Паша выигрывает в один ход.
- При $21 \leq S \leq 37$ Паша удваивает количество камней.
- При $S = 41$ Паша добавляет 1 камень.

**Задание 1б)**

Анализируем позиции 38, 39, 40 через дерево игры.

При $S = 40$:
- Паша может сделать 41 (добавить 1) или 80 (удвоить).
- Если 41: Валя добавляет 1 → 42, Валя побеждает.
- Если 80: Валя побеждает (≥ 75).
- Обе ветви ведут к победе Вали.

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

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

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

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