ЗАДАЧИ
problems.ru
О проекте | Об авторах | Справочник
Каталог по темам | по источникам |
К задаче N

Проект МЦНМО
при участии
школы 57
Задача 66147
Темы:    [ Ориентированные графы ]
[ Доказательство от противного ]
[ Принцип крайнего (прочее) ]
Сложность: 3+
Классы: 8,9,10
В корзину
Прислать комментарий

Условие

В стране некоторые пары городов соединены односторонними прямыми авиарейсами (между любыми двумя городами есть не более одного рейса). Скажем, что город A доступен для города B, если из B можно долететь в A, возможно, с пересадками. Известно, что для любых двух городов P и Q существует город R, для которого и P, и Q доступны. Докажите, что существует город, для которого доступны все города страны. (Считается, что город доступен для себя.)


Решение

Рассмотрим город A, для которого доступно наибольшее количество городов (если таких несколько – любой из них). Предположим, что некоторый город B недоступен для A. По условию существует город C, для которого A и B доступны. Но тогда для С доступны B, а также все города, доступные для A. Противоречие.

Источники и прецеденты использования

олимпиада
Название Всероссийская олимпиада по математике
год
Вариант 2016/2017
этап
Вариант 5
класс
Класс 9
задача
Номер 9.1

© 2004-... МЦНМО (о копирайте)
Пишите нам

Проект осуществляется при поддержке Департамента образования г.Москвы и ФЦП "Кадры" .