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

Из начальной позиции $(7,S)$ Петя может выиграть одним ходом, если после одного из возможных ходов сумма станет не менее 65.$$7+S+1\geq65 \Rightarrow S\geq57;\quad 14+S\geq65 \Rightarrow S\geq51;\quad 7+2S\geq65 \Rightarrow S\geq29$$

Объединяя условия, получаем все значения $S$ от 29 до 57 включительно.$$S\in\{29,30,\ldots,57\}$$

Если в куче не менее $13$ камней, игрок может умножить количество камней на 5 и получить не менее $65$. Поэтому Петя выигрывает за один ход при всех $13 \leq S \leq 62$.$$5S \geq 63 \Longleftrightarrow S \geq 13$$

Для меньших значений последовательно определяем проигрышные позиции. Позиция проигрышная, если все возможные ходы переводят её в выигрышную позицию.$$L=\{1,4,7,9,10,12\}$$

Из начальной позиции $(6,S)$ Петя может выиграть за один ход утроением второй кучи, если $6+3S\geq74$. Отсюда $S\geq23$. При меньших значениях утроение первой кучи и добавление одного камня также не дают выигрыша.$$6+3S\geq74\Longleftrightarrow S\geq\frac{68}{3}\Longleftrightarrow S\geq23$$

Следовательно, в задании 1а подходят все значения $S$ от 23 до 67.

Петя может выиграть за один ход, если после одного из разрешённых действий в куче будет не менее 68 камней. Условия $S+1 \geq 68$ и $S+4 \geq 68$ дают только значения, уже входящие в диапазон $14 \leq S \leq 67$, а условие $5S \geq 68$…$$S \in \{14,15,\ldots,67\}$$

Для задания 1б подходит $S=2$. Петя не может выиграть одним ходом: после его ходов получится 3, 6 или 10 камней. Из каждой из этих позиций Ваня выигрывает своим первым ходом: соответственно, умножением на 5 получает 15, 30 или 50? Нет…

Рассмотрим позиции $(6, 27)$ и $(8, 26)$. Из позиции $(6, 27)$ возможны переходы в $(7, 27)$, $(12, 27)$, $(6, 28)$ и $(6, 54)$. В первых трёх позициях удвоение второй кучи приводит к сумме не менее 61, а из $(6, 54)$ соперник может сразу…$$6+27=33$$

Аналогично позиция $(8, 26)$ является проигрышной для игрока, делающего ход: любой его ход переводит игру в позицию, из которой следующий игрок может завершить игру или перейти к проигрышной для соперника позиции.

Петя может выиграть первым ходом, если после одного из разрешённых действий сумма камней станет не менее 63. Из позиции $(5,S)$ удвоение второй кучи даёт сумму $5+2S$, поэтому требуется $5+2S \geq 63$, то есть $S \geq 29$. При $S \geq 29$…$$5+2S\geq 63\Longleftrightarrow S\geq 29$$

Следовательно, в задании 1а подходят все значения $S$ от 29 до 57 включительно.

Из исходной позиции $(3,2)$ первый игрок может получить только четыре различные позиции: $(9,2)$, $(6,2)$, $(3,6)$ или $(3,5)$.

Если первый игрок получил позицию $(9,2)$, второй игрок умножает число камней в первой куче на 3 и получает $27$ камней. Если получена позиция $(3,6)$, второй игрок умножает вторую кучку на 3 и получает $18$ камней, а затем анализ…

Игрок выигрывает одним ходом, если после прибавления одного камня или удвоения количество камней становится не менее 65. При $S \geq 33$ достаточно удвоения. При $S=64$ можно также прибавить один камень.$$2S \geq 65 \Rightarrow S \geq 33; \qquad S+1 \geq 65 \Rightarrow S=64$$

Для задания 1б подходит $S=32$: Петя не может выиграть сразу, но после его хода получаются позиции $33$ или $64$, из которых Ваня выигрывает одним ходом.

Для каждой позиции рассматриваются четыре возможных хода: (a+1,b), (3a,b), (a,b+1), (a,3b). Если после хода сумма не менее 74, ход является немедленно выигрышным.

В позициях (4,23) и (7,22) выигрышная стратегия есть у Вани. После любого хода Пети Ваня получает возможность закончить игру или перевести её в позицию, из которой Петя вынужден открыть Ване немедленную победу.$$W(4,23)=W(7,22)=\text{Ваня}$$

Задание 1. Из позиции $(14,S)$ можно получить либо $(14+S,S)$ с суммой $14+2S$, либо $(14,14+S)$ с суммой $28+S$.$$14+2S\ge 65 \quad\text{или}\quad 28+S\ge 65$$

Первое неравенство даёт $S\ge 25{,}5$, поэтому при целом $S$ получаем $S\ge 26$. Второе даёт $S\ge 37$. Минимальное подходящее значение — $S=26$; Петя получает позицию $(40,26)$ с суммой 66.$$14+2\cdot 26=66$$

В первом наборе слова начинаются с разных букв: А и Д. Если Петя начинает с А, все последующие буквы однозначно определены, и слово АБВГДАБВГДХ получается на 11-м ходу. Нечётный номер хода означает победу Пети.$$11 \equiv 1 \pmod 2$$

Если Петя начинает с Д, слово ДГВБАДГВБА получается на 10-м ходу, поэтому победил бы Ваня. Следовательно, выигрышная стратегия Пети — первым написать А, затем каждый раз приписывать единственную возможную букву.$$10 \equiv 0 \pmod 2$$

В задании 1 при замене числа 15 на сумму чисел получится позиция $(15+S,S)$ с суммой $15+2S$. При замене числа $S$ получится позиция $(15,15+S)$ с суммой $30+S$.$$15+2S\geq 62\quad\text{или}\quad 30+S\geq 62$$

Минимальное значение определяется первым неравенством: $S\geq 23$. При $S=23$ Петя заменяет число 15 на сумму чисел и получает позицию $(38,23)$ с суммой 61 — это недостаточно. Поэтому нужно внимательно выбрать ход: заменить число $S$ на…$$15+2S\geq62\Rightarrow S\geq\frac{47}{2}\Rightarrow S\geq24$$

Игрок может выиграть одним ходом, если из текущей позиции можно получить не менее 36 камней. При $S<18$ это невозможно, поскольку даже удвоение даёт менее 36 камней. При $18\leq S\leq35$ удвоение приводит к позиции не менее 36.$$2S\geq36\Longleftrightarrow S\geq18$$

Следовательно, в задании 1а все значения $S$ имеют вид $18\leq S\leq35$.

В задании 1а первое слово начинается с А, а второе — с Д. Поэтому после первого хода Пети выбор ветви полностью определяется его первой буквой.

Слово АБВГДАБВГДХ имеет длину 11. Если Петя начинает с буквы А, все последующие буквы определяются однозначно, и на одиннадцатом ходу слово получает Петя.$$11 \equiv 1 \pmod 2$$

Из начальной позиции $(1, 2)$ возможны четыре различных результата первого хода: $(3, 2)$, $(1, 6)$, $(4, 2)$ и $(1, 5)$.

Рассмотрим ход в позицию $(1, 6)$: первый игрок увеличивает в 3 раза число камней во второй куче.

В задании 1а длина слова АБВГДАБВГДХ равна 11, а длина слова ДГВБАДГВБА равна 10. Петя первым ходом может выбрать начальную букву А или Д.

Если Петя пишет А, далее буквы определяются однозначно, и получается слово длины 11. Последнюю букву записывает Петя, поэтому он выигрывает.

В первом задании Петя может заменить число $9$ на сумму чисел и получить позицию $(9+S,S)$. Её сумма равна $9+2S$. Для победы одним ходом необходимо:$$9+2S\geq36$$

Получаем $2S\geq27$, то есть $S\geq13{,}5$. Так как $S$ — целое число, минимальное значение равно $14$. При замене числа $S$ условие было бы $18+S\geq36$, то есть $S\geq18$, поэтому найденное значение действительно минимально.$$S_{\min}=14$$

В задании 1а длина слова АБВГДАБВГДХ равна 11. Если Петя первым пишет букву А, дальнейшие ходы определены однозначно, и Петя получает последнюю, одиннадцатую букву. Значит, он выигрывает.$$11 \text{ — нечётное число}$$

Слово ДГВБАДГВБА имеет длину 10. Если Петя начинает с буквы Д, последнюю, десятую букву, пишет Ваня. Поэтому Петя выбирает А и использует выигрышную стратегию.

В задании 1а первое слово начинается с А, второе — с Д. Петя может выбрать любую из этих букв.

Если Петя выбирает А, дальнейшее продолжение однозначно и заканчивается словом АБВГДАБВГДХ длины 11. Последнюю, одиннадцатую, букву дописывает Петя, поэтому Петя выигрывает.

Из начальной позиции $(6,S)$ Петя может выиграть одним ходом, если после добавления камня или утраивания одной из куч сумма станет не менее 68.

Добавление одного камня в любую кучу даёт условие $7+S\geq68$, то есть $S\geq61$. Утраивание первой кучи даёт $18+S\geq68$, то есть $S\geq50$. Утраивание второй кучи даёт $6+3S\geq68$, то есть $S\geq21$.