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

В задании 1 из позиции $(9,S)$ Петя может получить $(9,9+S)$ с суммой $18+S$ или $(9+S,S)$ с суммой $9+2S$. Чтобы Петя не мог выиграть одним ходом, обе суммы должны быть меньше 26.$$18+S<26,\quad 9+2S<26$$

Получаем $S<8$ и $S<8{,}5$. Максимальное неотрицательное целое значение — $S=7$.

За один ход из позиции $S$ можно получить $S+1$ или $2S$. Петя выигрывает первым ходом, если один из результатов не меньше 26.

Условие $S+1 \geq 26$ даёт $S=25$, а условие $2S \geq 26$ даёт $S \geq 13$. Поэтому все значения: $13,14,\ldots,25$.

1а. Из начальной позиции $(5,S)$ Петя может выиграть одним ходом, если удвоение второй кучи даёт сумму не менее 75: $5+2S\geq75$. Отсюда $S\geq35$. Удвоение первой кучи требует $10+S\geq75$, то есть $S\geq65$, что уже входит в найденный…$$35\leq S\leq69$$

1б. Петя может сделать невыигрышный ход, удвоив первую кучу: $(5,S)\to(10,S)$. Ваня затем удваивает вторую кучу. Для победы Вани нужно $10+2S\geq75$, поэтому $S\geq32{,}5$. Минимальное целое значение — $S=33$.

Из начальной позиции $(7,S)$ Петя может выиграть первым ходом, если удвоение второй кучи даёт сумму не менее 77: $7+2S\geq77$, то есть $S\geq35$. Удвоение первой кучи даёт условие $14+S\geq77$, то есть $S\geq63$, которое уже входит в…

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

Для анализа каждой позиции перечисляют все возможные ходы: увеличение одной из куч на 1 и удвоение одной из куч. Если после хода сумма становится не менее 59, игра заканчивается победой сделавшего ход.

Для позиции (4, 27) выигрышная стратегия принадлежит Ване. После любого первого хода Пети Ваня выбирает ход, переводящий игру в позицию, из которой Петя не может гарантированно выиграть, а затем отвечает симметричным или компенсирующим…

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

В задании 1б Петя выбирает букву Т. Далее продолжение однозначно: ТРИ повторяется 33 раза, длина слова равна 99. Последнюю букву пишет Петя, поэтому выигрышная стратегия есть у Пети.

Позиция (4, 20) выигрышна для Пети: первым ходом он утраивает вторую кучу и получает сумму 4 + 60 = 64? Нет, при правильном подсчёте после утроения второй кучи получается позиция (4, 60), сумма 64; поэтому этот ход не является немедленной…

При обратном анализе проигрышными для игрока, которому предстоит ход, являются позиции (4, 21), (7, 20), (5, 20). Поэтому в позициях (4, 21) и (7, 20) выигрышная стратегия принадлежит Ване.