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

Омг, ДВ пишет про слова в 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

Источник

Добавить в слово одну букву, У или А

Удвоить количество букв У

Удвоить количество букв А

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

Задание 1. Для каждой из начальных позиций (4, 10), (6, 9), (7, 8) укажите, кто из игроков имеет выигрышную стратегию.

Задание 2. Для каждой из начальных позиций (4, 9), (6, 8), (7, 7) укажите, кто из игроков имеет выигрышную стратегию.

Задание 3. Для начальной позиции (6, 7) укажите, кто из игроков имеет выигрышную стратегию. Постройте дерево всех партий, возможных при указанной выигрышной стратегии.

4) Два игрока, Петя и Ваня по очереди стирают буквы из слова или фразы. Первым ходит Петя. За один ход разрешается стереть или ровно одну букву, или все одинаковые буквы. Выигрывает тот, кто сотрёт последнюю букву.

Задание 1. Укажите все слова из списка ниже, начиная с которых выигрывает Петя.

КУ РАК АРА КУКУ ЛОООМ ОКОРОК КАРАТ МЕМО КЕТЕКЕ НАНАЦА ПРОРОК

МОЛОКО РАПИРА АНКАРА АРАРАТ

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

Задание 3. Дана фраза: ТЕХНИЧЕСКАЯ КИБЕРНЕТИКА. Кто выиграет в этой игре, и какой будет выигрышная стратегия этого игрока?

5) Два игрока, Петя и Ваня по очереди стирают буквы из слова или фразы. Первым ходит Петя. За один ход разрешается стереть или ровно одну букву, или все одинаковые буквы. Выигрывает тот, кто сотрёт последнюю букву.

Задание 1. Укажите все слова из списка ниже, начиная с которых выигрывает Петя.

АЗ МАК ЛОЛА ЛАЛА КРЯКРЯ КОМОН ТРРР ТОРОС ЛОЛОЛО ФЫЫЫФ СЕЛЕН ЛЕТЕЛ

ТРААРА ГАГАРА ШАШШАШ

Задание 3. Дана фраза: МАТЕМАТИКА И АВТОМАТИКА. Кто выиграет в этой игре, и какой будет выигрышная стратегия этого игрока?

ПОЯСНЕНИЕ К 2 ПОСЛЕДНИМ ЗАДАНИЯМ.

P-06.Два игрока,Петя и Ваня по очереди стирают буквы из слова или фразы. Первым ходит Петя. За один ход разрешается стереть или ровно одну букву, или все одинаковые буквы. Выигрывает тот, кто сотрёт последнюю букву.

Задание 1. Укажите все слова из списка ниже, начиная с которых выигрывает Петя.

ДА, АГА, СТО, МАМА, СССР, ОГОГО, ТАРТАР, ТОРТ, РОКОКО, РЕННЕР, АВАТАР, КАРАКУРТ, КАСКАД, АНАТАНА, НЯННЯН, НАГАН.

Задание 3. Дана фраза: ИНФОРМАТИКА ЭТО НАУКА. Кто выиграет в этой игре, и какой будет выигрышная стратегия этого игрока?

1) Разберём задачу в общем виде. Когда в слове (фразе) не осталось ни одной буквы, по условию эта позиция – проигрышная. Тогда позиция, в которой осталась одна буква или только одинаковые буквы – выигрышная.

2) Сначала для простоты предположим, что все буквы в заданной фразе разные. Если их чётное число, то их можно разбить на две группы равного размера. Например, для слова КУРА можно использовать такую разбивку: КУ-РА. Теперь, когда Петя вычеркивает какую-то букву (например, У), Ване нужно вычеркнуть одну букву в другой половине (например, А) для того, чтобы восстановить симметрию. Таким образом, на каком-то шаге Ваня получит пустую строку и выиграет. Поэтому

Любая симметричная позиция – проигрышная (выигрышная для соперника).

3) Если начальная позиция несимметричная, Петя может своим первым ходом сделать её симметричной и Ваня оказывается в проигрышной позиции. Выигрышная стратегия Пети состоит в том, чтобы на каждом шаге восстанавливать симметрию.

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

В общем случае при правильной игре выиграет тот, кто первым построит симметричную позицию.

4) Если в слове есть парные буквы, ситуация несколько осложняется. Одинаковые буквы нужно при разбиении располагать в одной и той же половине. Например, слово КАА представляет собой несимметричную (выигрышную) позицию, так как, убрав одну букву А, получаем симметричную позицию К-А. Слово МАМА – это симметричная (проигрышная) позиция ММ-АА, поэтому при правильной игре выиграет Ваня.

5)Рассмотрим ещё один вариант, когда одна буква встречается 3 раза, а вторая – один, например, АААБ. Если Петя стёр все буквы А или одну букву Б, Ваня стирает все оставшиеся буквы и сразу выигрывает. Если Петя стёр одну букву А, Ваня должен стереть ещё одну букву А и получает симметричную (проигрышную для Пети) позицию А-Б. Поэтому позиция АААБ – проигрышная. Будем также называть её симметричной.

6) Рассмотрим ещё один вариант, когда одна буква встречается 4 раза, а вторая – два, например, ААААББ. Если Петя стёр все буквы одной группы (все А или все Б), Ваня стирает все буквы второй группы и сразу выигрывает. Если Петя стёр одну букву А, Ваня должен стереть ещё одну букву А и получает симметричную (проигрышную для Пети) позицию АА-ББ.
Если Петя стер одну букву Б, Ваня стирает одну букву А, получая позицию АААБ, в которой он выиграет в любом случае (см. предыдущий пункт). Поэтому позиция ААААББ – проигрышная. Будем также называть её симметричной.

7) Рассмотрим слова, приведённые в задании.

ДА ® Д-А – симметричная (проигрышная для Пети) позиция, выиграет Ваня своим первым ходом.

АГА – убрав одну букву А, Петя получает (проигрышную для Вани) симметричную позицию А-Г; выиграет Петя своим вторым ходом;

СТО – убрав любую букву, Петя получает симметричную (проигрышную для Вани) позицию и выиграет своим вторым ходом;

МАМА ® ММ-АА – симметричная проигрышная позиция, выиграет Ваня своим первым или ходом;

СССР ® симметричная (проигрышная для Пети) позиция (см. п. 5), поэтому Петя проиграет, а Ваня выиграет своим первым или вторым ходом;

ОГОГО – убрав одну букву О, Петя получает симметричную позицию ОО-ГГ и выиграет своим вторым ходом или третьим ходом;

ТАРТАР – убрав любую пару одинаковых букв, Петя получает симметричную позицию (например, ТТ-АА) и выигрывает своим вторым или третьим ходом;

ТОРТ – убрав две буквы Т, Петя получает симметричную позицию О-Р и выигрывает своим вторым ходом;

РОКОКО – убрав две буквы К, Петя получаем проигрышную (для Вани) позицию ООО-Р (см. п. 5) и выигрывает;

РЕННЕР – убрав любую пару одинаковых букв, Петя получает симметричную позицию (например, ЕЕ-НН) и выигрывает своим вторым или третьим ходом;

АВАТАР – все возможные ходы ведут в выигрышные позиции ААВТР, ВТР, ААВР, ААТР или АААВТ (каждую из них можно свести одним ходом к симметричной позиции); это проигрышная позиция, выиграет Ваня;

КАРАКУРТ – убрав любую пару букв, Петя получает симметричную (проигрышную для Вани) позицию (например, УКК-РРТ) и выигрывает своим третьим или четвертым ходом;

КАСКАД – симметричная (проигрышная) позиция СКК-ААД, выиграет Ваня своим вторым или третьим ходом;

АНАТАНА – убрав одну букву Т, Петя получает симметричную (проигрышную для Вани) позицию ААААНН (см. п. 6) и выигрывает;

НЯННЯН – симметричная (проигрышная для Пети) позиция ННННЯЯ (см. п. 6), выиграет Ваня;

НАГАН – убрав букву Г, Петя получает симметричную (проигрышную для Вани) позицию НН-АА и выигрывает своим вторым или третьим ходом.

8) Таким образом, ответы на первые два вопроса следующие:

1. Петя выигрывает, если игра начинается со слов

АГА, СТО, ОГОГО, ТАРТАР, ТОРТ, РОКОКО, РЕННЕР, КАРАКУРТ, АНАТАНА, НАГАН.

2. Если игра начинается со слов МАМА или СССР, выигрывает Ваня своим первым или вторым ходом в зависимости от ходов Пети; во всех случаях Ваня должен восстанавливать симметрию позиции.

9) Теперь рассмотрим фразу ИНФОРМАТИКА ЭТО НАУКА. Расставим буквы с учётом повторений: (АААА ИИ) (КК НН ОО ТТ) (МРУФЭ). В первой скобке позиция симметричная (см. п. 6), во второй – тоже симметричная, а в третьей – несимметричная. Поэтому вся позиция несимметричная, то есть выигрышная. Убрав любую одиночную букву из последней скобки Петя может свести игру к симметричной (проигрышной для Вани) позиции.

10) Таким образом,

3. Если игра начинается с фразы ИНФОРМАТИКА ЭТО НАУКА, выигрывает Петя. Сначала ему нужно стереть одну из букв, которая встречается только один раз, а затем своими ходами поддерживать симметрию позиции.