Решения заданий ФИПИ ЕГЭ по информатике: «Игры и стратегии» — с ответами

После первого хода Пети возможны позиции $(16,S)$, $(14,S+2)$, $(28,S)$ и $(14,2S)$.

Для минимального значения $S$ выгоднее всего Петя должен удвоить вторую кучу. Тогда после его хода получится позиция $(14,2S)$.

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

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

Петя не должен иметь возможности выиграть одним ходом. Для этого после начального количества камней должно быть меньше 33 камней, поскольку при $S\geq 33$ Петя сможет удвоить кучу и получить не менее 66 камней.$$S<33$$

После любого хода Пети Ваня должен иметь возможность выиграть одним ходом. Если после хода Пети в куче не менее 33 камней, Ваня удваивает их количество и получает не менее 66 камней.$$S+1\geq 33,\quad 2S\geq 33$$

Чтобы Петя не выиграл первым ходом, после каждого возможного хода количество камней должно быть меньше 35:$$S+1<35,\quad S+4<35,\quad 2S<35$$

Из условия $2S<35$ следует $S\leq 17$. Именно это ограничение является наиболее сильным.

Петя выигрывает за один ход, если после одного из его ходов количество камней становится не более 17.$$S-2 \le 17 \quad\text{или}\quad S-4 \le 17 \quad\text{или}\quad \left\lfloor\frac{S}{3}\right\rfloor \le 17$$

Для третьего варианта условие выполняется при $S \le 53$. Поэтому при $S=54$ Петя уже не может выиграть за один ход: после его ходов остаётся $52$, $50$ или $18$ камней.

Петя не должен иметь возможности выиграть первым ходом. Поэтому после любого его хода количество камней должно быть меньше 103: $S+1<103$, $S+4<103$ и $3S<103$.

Из последнего неравенства получаем $S \le 34$.

Чтобы Петя не выиграл первым ходом, оба его возможных результата должны быть меньше 129:$$S+1<129,\quad 2S<129$$

Из второго неравенства следует $S\leq 64$. Значение $S=64$ является наибольшим возможным кандидатом.

Игрок может выиграть одним ходом из позиции с $n$ камнями, если после добавления одного камня или удвоения количество камней станет не менее 49.$$n+1 \geq 49 \quad \text{или} \quad 2n \geq 49$$

Минимальное целое значение $n$, из которого можно выиграть одним ходом, равно 25.

Чтобы Петя не выиграл первым ходом, после каждого из его возможных ходов количество камней должно быть меньше 91:$$S+1<91,\quad S+4<91,\quad 3S<91$$

Наиболее ограничивающим является условие $3S<91$, поэтому $S\leq 30$.

Петя не должен иметь возможности выиграть за один ход. Для этого ни один из результатов его ходов не должен быть не менее 58. В частности, $2S < 58$, поэтому $S \leq 28$.

После любого хода Пети Ваня должен иметь возможность выиграть одним ходом. Если после хода Пети в куче $x$ камней, то Ваня выигрывает при $x \geq 29$ удвоением, при $x \geq 54$ добавлением 4 или при $x \geq 57$ добавлением 1.

Петя не должен иметь возможности выиграть одним ходом. Поэтому после любого его первого хода количество камней должно быть меньше 38: $S+1<38$ и $2S<38$.

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

Петя не должен иметь возможности выиграть первым ходом. Поэтому для начального значения $S$ должно выполняться $2S < 27$, а также $S+4 < 27$. Наиболее существенное ограничение даёт удвоение: $S \leq 13$.$$2S < 27$$

Ваня может выиграть одним ходом из позиции $x$, если удвоением получить не менее 27 камней. Это возможно при $x \geq 14$.$$2x \geq 27 \Rightarrow x \geq 14$$

Петя не должен иметь возможности выиграть первым ходом. Поэтому должны выполняться неравенства $S+1<133$ и $2S<133$, откуда $S\leq 66$.

Чтобы Ваня мог выиграть после любого хода Пети, обе возможные позиции после хода Пети должны позволять Ване завершить игру. При ходе «добавить один камень» необходимо $S+1\geq 67$, поэтому $S\geq 66$.

Чтобы Петя не выиграл первым ходом, все возможные результаты его ходов должны быть меньше 85:$$S+1<85,\quad S+4<85,\quad 3S<85$$

Наиболее ограничивающим является условие $3S<85$, поэтому $S\leq 28$.

После первого хода Пети возможны четыре позиции: $(17,S)$, $(14,S+3)$, $(42,S)$ и $(14,3S)$.

Проверим вариант, при котором Петя утроил вторую кучу. После этого позиция имеет вид $(14,3S)$, а сумма камней равна $14+3S$, поэтому ход Пети не является завершающим при найденном значении $S$.

Петя не должен иметь возможности выиграть первым ходом. Поэтому должны выполняться неравенства $S+4<67$ и $3S<67$, откуда $S\leq 22$.

Проверим значение $S=22$. После хода Пети количество камней может стать равным $23$, $26$ или $66$.

Чтобы Петя не выиграл первым ходом, все возможные результаты его хода должны быть меньше 36: $S+1<36$, $S+4<36$ и $2S<36$.

После любого хода Пети Ваня должен иметь возможность выиграть одним ходом. При $S=17$ возможные позиции равны $18$, $21$ и $34$.

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

При малых значениях $S$ выгоднее всего Петя удваивает вторую кучу: $(13,S) \rightarrow (13,2S)$. После этого Ваня также удваивает вторую кучу.

Чтобы найти минимальное значение $S$, рассмотрим ход Пети: он удваивает количество камней во второй куче. После этого в кучах находится 5 и $2S$ камней.$$5 + 2S < 59$$

Ваня может своим первым ходом снова удвоить вторую кучу. После этого суммарное количество камней станет равным $5 + 4S$.$$5 + 4S \geq 59$$

Петя не должен иметь возможности закончить игру своим первым ходом. Поэтому результат каждого возможного хода Пети должен быть больше 16.$$S-3>16,\quad S-8>16,\quad \left\lfloor\frac{S}{3}\right\rfloor>16$$

Наиболее строгое ограничение даёт ход с делением на 3:$$\left\lfloor\frac{S}{3}\right\rfloor>16\Rightarrow S\ge 51$$