Два игрока петя и ваня по очереди стирают буквы

Омг, ДВ пишет про слова в 26
Ок.
Раз пошла такая пьянка — решение 26 с сайта К. Полякова (для тех, кому лень искать).

Два игрока, Петя и Ваня по очереди стирают буквы из слова или фразы. Первым ходит Петя. За один ход разрешается стереть или ровно одну букву, или все одинаковые буквы. Выигрывает тот, кто сотрёт последнюю букву.
Задание 1. Укажите все слова из списка ниже, начиная с которых выигрывает Петя.
ДА, АГА, СТО, МАМА, СССР, ОГОГО, ТАРТАР, ТОРТ, РОКОКО, РЕННЕР, АВАТАР, КАРАКУРТ, КАСКАД, АНАТАНА, НЯННЯН, НАГАН.
Задание 2. Укажите все слова из представленных, начиная с которых Ваня не может гарантиро-ванно выиграть своим первым ходом, но может выиграть либо своим первым или вторым ходом, в зависимости от хода Пети. Для всех выбранных слов укажите его выигрышную стратегию.
Задание 3. Дана фраза: ИНФОРМАТИКА ЭТО НАУКА. Кто выиграет в этой игре, и какой будет выигрышная стратегия этого игрока?

Решение:
1) Разберём задачу в общем виде. Когда в слове (фразе) не осталось ни одной буквы, по усло-вию эта позиция – проигрышная. Тогда позиция, в которой осталась одна буква или только одинаковые буквы – выигрышная.
2) Сначала для простоты предположим, что все буквы в заданной фразе разные. Если их чёт-ное число, то их можно разбить на две группы равного размера. Например, для слова КУРА можно использовать такую разбивку: КУ-РА. Теперь, когда Петя вычеркивает какую-то букву (например, У), Ване нужно вычеркнуть одну букву в другой половине (например, А) для того, чтобы восстановить симметрию. Таким образом, на каком-то шаге Ваня получит пустую строку и выиграет. Поэтому
Любая симметричная позиция – проигрышная (выигрышная для соперника).
3) Если начальная позиция несимметричная, Петя может своим первым ходом сделать её симметричной и Ваня оказывается в проигрышной позиции. Выигрышная стратегия Пети состоит в том, чтобы на каждом шаге восстанавливать симметрию.
Любая позиция, из которой можно одним ходом получить симметричную позицию – выигрышная.
В общем случае при правильной игре выиграет тот, кто первым построит симметричную позицию.
4) Если в слове есть парные буквы, ситуация несколько осложняется. Одинаковые буквы нужно при разбиении располагать в одной и той же половине. Например, слово КАА представляет собой несимметричную (выигрышную) позицию, так как, убрав одну букву А, получаем симметричную позицию К-А. Слово МАМА – это симметричная (проигрышная) позиция ММ-АА, поэтому при правильной игре выиграет Ваня.
5) Рассмотрим ещё один вариант, когда одна буква встречается 3 раза, а вторая – один, напри-мер, АААБ. Если Петя стёр все буквы А или одну букву Б, Ваня стирает все оставшиеся буквы и сразу выигрывает. Если Петя стёр одну букву А, Ваня должен стереть ещё одну букву А и получает симметричную (проигрышную для Пети) позицию А-Б. Поэтому позиция АААБ – проигрышная. Будем также называть её симметричной.
6) Рассмотрим ещё один вариант, когда одна буква встречается 4 раза, а вторая – два, напри-мер, ААААББ. Если Петя стёр все буквы одной группы (все А или все Б), Ваня стирает все бук-вы второй группы и сразу выигрывает. Если Петя стёр одну букву А, Ваня должен стереть ещё одну букву А и получает симметричную (проигрышную для Пети) позицию АА-ББ.
Если Петя стер одну букву Б, Ваня стирает одну букву А, получая позицию АААБ, в которой он выиграет в любом случае (см. предыдущий пункт). Поэтому позиция ААААББ – проигрышная. Будем также называть её симметричной.
7) Рассмотрим слова, приведённые в задании.
ДА  Д-А – симметричная (проигрышная для Пети) позиция, выиграет Ваня своим первым ходом.
АГА – убрав одну букву А, Петя получает (проигрышную для Вани) симметричную позицию А-Г; выиграет Петя своим вторым ходом;
СТО – убрав любую букву, Петя получает симметричную (проигрышную для Вани) позицию и выиграет своим вторым ходом;
МАМА  ММ-АА – симметричная проигрышная позиция, выиграет Ваня своим первым или ходом;
СССР  симметричная (проигрышная для Пети) позиция (см. п. 5), поэтому Петя проиграет, а Ваня выиграет своим первым или вторым ходом;
ОГОГО – убрав одну букву О, Петя получает симметричную позицию ОО-ГГ и выиграет своим вторым ходом или третьим ходом;
ТАРТАР – убрав любую пару одинаковых букв, Петя получает симметричную позицию (на-пример, ТТ-АА) и выигрывает своим вторым или третьим ходом;
ТОРТ – убрав две буквы Т, Петя получает симметричную позицию О-Р и выигрывает своим вторым ходом;
РОКОКО – убрав две буквы К, Петя получаем проигрышную (для Вани) позицию ООО-Р (см. п. 5) и выигрывает;
РЕННЕР – убрав любую пару одинаковых букв, Петя получает симметричную позицию (на-пример, ЕЕ-НН) и выигрывает своим вторым или третьим ходом;
АВАТАР – все возможные ходы ведут в выигрышные позиции ААВТР, ВТР, ААВР, ААТР или АААВТ (каждую из них можно свести одним ходом к симметричной позиции); это проиг-рышная позиция, выиграет Ваня;
КАРАКУРТ – убрав любую пару букв, Петя получает симметричную (проигрышную для Вани) позицию (например, УКК-РРТ) и выигрывает своим третьим или четвертым ходом;
КАСКАД – симметричная (проигрышная) позиция СКК-ААД, выиграет Ваня своим вторым или третьим ходом;
АНАТАНА – убрав одну букву Т, Петя получает симметричную (проигрышную для Вани) позицию ААААНН (см. п. 6) и выигрывает;
НЯННЯН – симметричная (проигрышная для Пети) позиция ННННЯЯ (см. п. 6), выиграет Ваня;
НАГАН – убрав букву Г, Петя получает симметричную (проигрышную для Вани) позицию НН-АА и выигрывает своим вторым или третьим ходом.
8) Таким образом, ответы на первые два вопроса следующие:
1. Петя выигрывает, если игра начинается со слов
АГА, СТО, ОГОГО, ТАРТАР, ТОРТ, РОКОКО, РЕННЕР, КАРАКУРТ, АНАТАНА, НАГАН.
2. Если игра начинается со слов МАМА или СССР, выигрывает Ваня своим первым или вто-рым ходом в зависимости от ходов Пети; во всех случаях Ваня должен восстанавливать симметрию позиции.
9) Теперь рассмотрим фразу ИНФОРМАТИКА ЭТО НАУКА. Расставим буквы с учётом повторе-ний: (АААА ИИ) (КК НН ОО ТТ) (МРУФЭ). В первой скобке позиция симметричная (см. п. 6), во второй – тоже симметричная, а в третьей – несимметричная. Поэтому вся позиция несимметричная, то есть выигрышная. Убрав любую одиночную букву из последней скобки Петя может свести игру к симметричной (проигрышной для Вани) позиции.
10) Таким образом,
3. Если игра начинается с фразы ИНФОРМАТИКА ЭТО НАУКА, выигрывает Петя. Сначала ему нужно стереть одну из букв, которая встречается только один раз, а затем своими ходами поддерживать симметрию позиции.

https://kpolyakov.spb.ru/school/ege.htm

Содержание верного ответа и указания по оцениванию

(допускаются иные формулировки ответа, не искажающие его смысла)

Общая идея решения

Если в наборе только одно слово, то все ходы игроков единственно возможные. Если длина слова нечётная, то выигрывает Петя; если длина чётная – Вова.

Аналогично, пусть для некоторого слова существует единственная возможность продолжить его до слова из набора. Если длина продолжения нечётная, то выигрывает тот игрок, который ходит; если длина чётная, выигрывает его противник.

Задание 1

1. Выигрышная стратегия есть у Пети. Первым ходом он пишет К. В конце игры у игроков должно получиться слово КЛМНБВГ. Длина слова равна (нечетная), поэтому последнюю букву напишет Петя.
2. Выигрышная стратегия есть у Пети. Первым ходом он пишет Д. После этого у игроков должно получиться слово ДВАДВА…ДВА. В этом слове букв. Петя напишет -ю, -ю, -ю и т.д. буквы. Поэтому -ю букву напишет Петя, и, следовательно, выиграет Петя.

Задание 2

Нужно в слове КЛМНБВГ поставить на первое место букву Г. Например, можно поменять местами первую и последнюю буквы; получится слово ГЛМНБВК.

Полученный набор слов: {ГДЕЖЗИКЛ, ГЛМНБВК}. Теперь оба слова начинаются с буквы Г, и Петя должен написать Г. Вова пишет Д, получается ГД. Теперь в конце игры получится слово ГДЕЖЗИКЛ. Длина слова – букв. Поэтому выиграет Вова.

Задание 3

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

Указания по оцениванию

Предварительные замечания

В задаче от ученика требуется выполнить три задания. Их трудность возрастает. Количество баллов в целом соответствует количеству выполненных заданий (подробнее см. ниже).

Пункты 1А и 1Б считаются выполненным, если (I) правильно указано, кто из игроков имеет выигрышную стратегию в на данном наборе, и (II) описаны выигрышные стратегии – так, как это сделано в образце решения, или любым другим способом (таблица, словесно и т.д.).

Первое задание считается выполненным полностью, если выполнены полностью оба пункта: 1А и 1Б.

Замечание для проверяющего. Описать стратегию игрока – значит описать, какой ход он должен сделать в любой ситуации, которая ему может встретиться при различной игре противника (см. условие задачи). Экзаменуемый может описывать стратегию любым удобным ему способом. Существенно, чтобы было понятно, какой ход должен сделать игрок, реализующий стратегию, и было показано, что все возможные заключительные позиции выигрышные для этого игрока.

Задание 2 считается выполненным, если описана выигрышная
стратегия Вовы.

Задание 3 считается выполненным, если правильно построено дерево всех возможных партий для выигрышной стратегии Вовы.

Если в дереве указаны пути, которые не могут встретиться при использовании выигрышной стратегии, то задание считается не выполненным. Во всех случаях стратегии могут быть описаны так, как это сделано в примере решения, или другим способом.