Два игрока, Петя и Ваня, играют в следующую игру. Перед игроками находится неориентированный граф, изначально в котором каждая вершина соединена с двумя другими. Игроки ходят по очереди, первый ход делает Петя. За один ход игрок может добавить в граф одну вершину и соединить ее ребрами максимум с двумя другими вершинами (по своему выбору либо с одной вершиной, либо с двумя вершинами) или удалить из графа одно ребро. Повторять последний ход соперника нельзя (то есть нельзя ходить так, как только что сходил соперник, при этом повторять свои предыдущие ходы и предыдущие ходы соперника можно).
Игра завершается в тот момент, когда сумма степеней вершин графа (степень вершины - количество выходящих из данной вершины рёбер) становится не менее 70. Победителем считается игрок, сделавший последний ход, т. е. первым получивший сумму степеней графа >,= 70.
В начальный момент в графе было S ребер, 3 ≤ S ≤ 34.
Будем говорить, что игрок совершает неудачный ход, если у него есть ход, приводящий к победе, но при этом он ошибается, и в итоге на следующий ход побеждает его соперник.
Известно, что Ваня выиграл своим первым ходом после неудачного хода Пети. Укажите количество значений S, при которых такая ситуация возможна.
Задание 20
Для игры, описанной в предыдущем задании, укажите минимальное значение S, при котором Петя выигрывает своим вторым ходом после неудачного хода Вани.
Задание 21
Будем говорить, что игрок имеет выигрышную стратегию, если он может выиграть при любых ходах противника. Описать стратегию игрока – значит описать, какой ход он должен сделать в любой ситуации, которая ему может встретиться при различной игре противника.
Для игры, описанной ранее, найдите минимальное значение S, при которых одновременно выполняются четыре условия:
– у Вани есть выигрышная стратегия, позволяющая ему выиграть своим вторым ходом при любой первой игре Пети (любом его первом ходе),
– у Вани нет стратегии, которая позволит ему выиграть первым ходом.
– Второй ход Пети был неудачным.
– первым ходом нельзя удалить ребро.
