В доску вбито 1234 гвоздя. Петя и Вася играют в игру, делая ходы по очереди (начинает Петя). За один ход можно соединить два ещё не соединённых между собой гвоздя ниткой. Тот игрок, после хода которого образуется замкнутая цепь, проигрывает. Кто из игроков может всегда выигрывать, как бы ни играл его соперник?
В данной игре мы можем представить каждый гвоздь как вершину графа, а каждую нитку как ребро между вершинами. То есть, у нас будет граф с 1234 вершинами.
Правило игры состоит в том, чтобы соединять ниткой две вершины, которые еще не соединены. Цель игры - создать замкнутую цепь.
Для того чтобы определить, какой из игроков может всегда выигрывать, нам нужно разобраться в свойствах этого графа.
В нашем случае, количество вершин (гвоздей) равно 1234.
Теперь рассмотрим пары четных и нечетных чисел в данном диапазоне:
1 и 2, 3 и 4, 5 и 6, и т.д.
Заметим, что у каждой незавершенной пары есть другая пара, у которой каждый элемент на 1 больше или на 1 меньше.
Поскольку пар должно быть ровно 617, это значит, что игрок, делающий первый ход (Петя), всегда может выбрать пару изначально незавершенных гвоздей и соединить их.
Тем самым, после каждого хода Пети остаются только незавершенные пары гвоздей, и пока все пары не будут завершены, Вася не сможет создать замкнутую цепь.
Таким образом, Петя всегда может выигрывать, независимо от того, как играет Вася.