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

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

Условие

В стране 1001 город, каждые два города соединены дорогой с односторонним движением. Из каждого города выходит ровно 500 дорог, в каждый город входит ровно 500 дорог. От страны отделилась независимая республика, в которую вошли 668 городов. Докажите, что из каждого города этой республики можно доехать до любого другого ее города, не выезжая за пределы республики.


Решение

  Предположим, что утверждение неверно; скажем, из города X нельзя добраться до Y по городам республики.
  Обозначим через A множество всех городов республики, до которых можно добраться из X по городам республики (включая сам город X), а через B – множество всех остальных её городов (оно непусто, так как содержит Y). Тогда города республики разбились на две группы так, что все дороги между группами направлены от B к A.
  Обозначим количество городов в группах A и B через a и b соответственно,  a + b = 668.  Пусть в A городов не меньше, чем в B, то есть  a ≥ 334 ≥ b.  В B есть город Z, из которого выходит не менее  b–1/2  дорог в города из B.
  Кроме того, из Z выходит a дорог к городам группы A. Значит, из Z выходит не менее     дорог. Противоречие.
  Случай, когда в B больше городов, чем в A, рассматривается аналогично.

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

олимпиада
Название Всероссийская олимпиада по математике
год
Год 2004
Этап
Вариант 5
Класс
Класс 10
задача
Номер 04.5.10.6

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

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