Question

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

Вопросы:

При каких S:
- а) Петя выигрывает первым ходом;
- б) Валя выигрывает первым ходом?
Назовите два значения S, при которых Петя может выиграть своим вторым ходом.
Назовите одно значение S, при котором Валя выигрывает своим первым или вторым ходом.

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

1. При каких S:
   - а) Петя выигрывает первым ходом;
   - б) Валя выигрывает первым ходом?

2. Назовите два значения S, при которых Петя может выиграть своим вторым ходом.

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

Accepted Answer

Answer

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

**Вопрос 1а) Петя выигрывает первым ходом**

Петя выигрывает первым ходом, если он может за один ход достичь позиции с количеством камней $\ge 52$. Возможные ходы из позиции S:
- добавить 1: получить $S + 1$
- добавить 4: получить $S + 4$
- удвоить: получить $2S$

Для выигрыша нужно, чтобы хотя бы один из этих результатов был $\ge 52$:
- $S + 1 \ge 52 \Rightarrow S \ge 51$
- $S + 4 \ge 52 \Rightarrow S \ge 48$
- $2S \ge 52 \Rightarrow S \ge 26$

Таким образом, Петя выигрывает первым ходом при $26 \le S \le 51$.

**Вопрос 1б) Валя выигрывает первым ходом**

Валя выигрывает первым ходом, если при любом ходе Пети Валя может сразу выиграть. Это возможно только при $S = 25$:
- Если Петя добавит 1: $25 + 1 = 26$, Валя удваивает: $26 	imes 2 = 52$ — Валя выигрывает.
- Если Петя добавит 4: $25 + 4 = 29$, Валя удваивает: $29 	imes 2 = 58$ — Валя выигрывает.
- Если Петя удвоит: $25 	imes 2 = 50$, Валя добавляет 4: $50 + 4 = 54$ — Валя выигрывает.

При $S = 25$ Валя гарантированно выигрывает первым ходом.

**Вопрос 2) Петя выигрывает своим вторым ходом**

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

При $S = 24$:
- Петя добавляет 1: $24 + 1 = 25$
- Валя может добавить 1 ($	o 26$), добавить 4 ($	o 29$) или удвоить ($	o 50$)
- Из позиции 26 Петя удваивает: $26 	imes 2 = 52$ — выигрыш
- Из позиции 29 Петя удваивает: $29 	imes 2 = 58$ — выигрыш
- Из позиции 50 Петя добавляет 4: $50 + 4 = 54$ — выигрыш

При $S = 21$:
- Петя добавляет 4: $21 + 4 = 25$
- Валя может добавить 1 ($	o 26$), добавить 4 ($	o 29$) или удвоить ($	o 50$)
- Из каждой позиции Петя может выиграть вторым ходом (аналогично выше)

Два значения: $S = 24$ и $S = 21$.

**Вопрос 3) Валя выигрывает первым или вторым ходом**

При $S = 20$:
- Петя добавляет 1: $20 + 1 = 21$
  - Валя добавляет 4: $21 + 4 = 25$, затем Петя не может выиграть первым ходом, но Валя может выиграть вторым ходом.
- Петя добавляет 4: $20 + 4 = 24$
  - Валя добавляет 1: $24 + 1 = 25$, затем Валя выигрывает вторым ходом.
- Петя удваивает: $20 	imes 2 = 40$
  - Валя удваивает: $40 	imes 2 = 80$ — Валя выигрывает первым ходом.

Одно значение: $S = 20$ (также подходит $S = 23$).

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

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

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

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