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