Question

Два игрока, Петя и Ваня, играют в следующую игру. Перед игроками лежат две кучи камней. Игроки ходят по очереди, первый ход делает Петя. За один ход игрок может **добавить в одну из куч (по своему выбору) один камень** или **увеличить количество камней в куче в два раза**. Например, позицию (10, 5) можно преобразовать в (11, 5), (20, 5), (10, 6) или (10, 10).

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

В начальный момент в первой куче было 7 камней, во второй куче — $S$ камней; $1 \le S \le 69$.

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

Accepted Answer

18

Answer

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

Проанализируем условие. Игра должна завершиться за 2 хода: Петя делает первый ход (неудачный), Ваня делает второй ход и выигрывает. Это означает:
- После хода Пети сумма камней остаётся < 77.
- После хода Вани сумма камней становится ≥ 77.

Для того чтобы Ваня мог выиграть одним ходом, ему нужно иметь возможность достичь суммы ≥ 77. Если после хода Пети во второй куче будет $x$ камней, то Ваня может удвоить эту кучу, получив $2x$ камней. Вместе с 7 камнями в первой куче получится $7 + 2x \ge 77$, откуда $2x \ge 70$, то есть $x \ge 35$.

Поскольку удвоением нельзя получить ровно 35 (35 — нечётное число), минимальное значение, которое Ваня может получить удвоением, — это 36 (из 18). Следовательно, после хода Пети во второй куче должно быть ровно 36 камней.

Если Петя добавляет 1 камень ко второй куче, то $S + 1 = 36$, откуда $S = 35$. Но тогда сумма после хода Пети будет $7 + 36 = 43 < 77$, и Ваня удвоит вторую кучу: $7 + 72 = 79 \ge 77$ — выигрыш.

Если Петя удваивает вторую кучу, то $2S = 36$, откуда $S = 18$. После хода Пети сумма будет $7 + 36 = 43 < 77$, и Ваня удвоит вторую кучу: $7 + 72 = 79 \ge 77$ — выигрыш.

Минимальное из этих значений — $S = 18$.

Проверим несколько начальных значений:

| $S$ | После хода Пети | Может ли Ваня выиграть? |
|---|---|---|
| 17 | $(7, 34)$ или $(7, 18)$ или $(8, 17)$ или $(14, 17)$ | Нет (удвоение даёт макс. $7 + 68 = 75$) |
| 18 | $(7, 36)$ или $(7, 19)$ или $(8, 18)$ или $(14, 18)$ | Да (удвоение: $7 + 72 = 79$) |
| 19 | $(7, 38)$ или $(7, 20)$ или $(8, 19)$ или $(14, 19)$ | Да (удвоение: $7 + 76 = 83$) |

При $S = 18$ Петя может сделать неудачный ход (например, добавить 1 камень ко второй куче, получив $(7, 19)$), и тогда Ваня не сможет выиграть первым ходом. Однако если Петя удвоит вторую кучу, получив $(7, 36)$, то Ваня выигрывает удвоением.

Минимальное значение $S$, при котором существует неудачный ход Пети, после которого Ваня может выиграть первым ходом, — это $S = 18$.

Задание №19Алгоритмы и исполнителиЕГЭ по информатике