Реши задачу: Оля и Максим оплатили путешествие по архипелагу из 2009 островов, где некоторые острова связаны двусторонними маршрутами катера. Они путешествуют, играя. Сначала Оля выбирает остров, на который они прилетают. Затем они путешествуют вместе на катерах, по очереди выбирая остров, на котором еще не были (первый раз выбирает Максим). Кто не сможет выбрать остров, проиграл. Докажите, что Оля может выиграть.



user
Решение
Назовём спариванием разбиение архипелага на пары островов, соединённых катером, и отдельные острова. Рассмотрим максимальное спаривание (с наибольшим числом пар). Прилетим на какой-нибудь отдельный остров (такой очевидно есть). Если Максим ходит на остров из какой-то пары, Оля отвечает ходом на второй остров этой пары. Предположим, что Максиму удастся сделать ход на отдельный остров. Путь с начала до этого острова состоит из чётного числа 2k островов: из  k – 1  пары и двух отдельных островов. Но этот путь можно было разбить на k пар, что увеличило бы спаривание Противоречие.
Значит, ход Максима на отдельный остров невозможен, и Оля выиграет.
assistant