Вдоску вбито 111 гвоздей. петя и вася играют в игру, делая ходы по очереди (начинает петя). за один ход можно соединить два ещё не соединённых между собой гвоздя ниткой. тот игрок, после хода которого образуется замкнутая цепь из нечётного количества ниток, проигрывает. кто из игроков может всегда выигрывать, как бы ни играл его соперник?

! 35 . с полным решением и обоснованием.

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

1. Если на доске есть четное количество гвоздей (2, 4, 6, ...), то первым ходом Петя может соединить любые два гвоздя, таким образом образуется одна нить. После этого Пете нужно просто копировать ходы Васи. Таким образом, каждый раз на доске будет четное число гвоздей и цепь будет состоять из четного числа ниток, поэтому победителем будет Петя.

2. Если на доске есть нечетное количество гвоздей (3, 5, 7, ...), то первым ходом Петя может соединить любые два гвоздя так, чтобы образовалась одна нить. После этого вне зависимости от хода Васи, на доске всегда будет два гвоздя и одна нить. Поэтому Петя всегда будет победителем независимо от хода Васи.

Теперь рассмотрим случай, когда на доске ровно три гвоздя.

Пусть гвозди нумеруются: 1, 2, 3.

1. Первым ходом Петя может, например, соединить гвозди 1 и 2, таким образом образуется одна нить.
Теперь Вася может соединить гвозди 2 и 3, получится две нити.
После этого каждый следующий ход Пети будет необходимо копировать ходы Васи. Таким образом, Петя всегда будет проигрывать.

2. Первым ходом Петя может соединить гвозди 2 и 3, таким образом образуется одна нить.
Теперь Вася может соединить гвозди 1 и 2, получится две нити.
После этого каждый следующий ход Пети будет необходимо копировать ходы Васи. Таким образом, Петя всегда будет проигрывать.

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