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

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

Условие

В стране 1988 городов и 4000 дорог.
Докажите, что можно указать кольцевой маршрут, проходящий не более, чем через 20 городов (каждая дорога соединяет два города).


Решение

  Назовём город "захолустным", если из него идёт не более двух дорог. Сотрём с карты страны любой захолустный город, если таковой имеется, вместе с выходящими из него дорогами. Подчистим таким же образом новую карту и будем продолжать стирание захолустных городов, пока они не исчезнут. Число дорог, которые мы при этом можем стереть, не превосходит  2·1988 < 4000;  поэтому хотя бы один город останется.
  Выберем любой из оставшихся городов. Из него, как и из других оставшихся городов, выходят по меньшей мере три дороги. Пойдём по одной из них и каждый раз, приходя в новый город, будем двигаться дальше по одной из дорог, отличных от дороги, по которой мы пришли. Если какие-нибудь два маршрута, состоящие не более чем из 10 дорог, закончатся в одном городе, то мы получим искомый кольцевой маршрут не более чем из 20 дорог. В противном случае число всех таких маршрутов не меньше чем  3(1 + 2 + 2² + ... + 29) = 3(210 – 1) = 3069,  а число городов, то есть возможных концов этих маршрутов – не больше 1988. Противоречие.

Замечания

6 баллов

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

журнал
Название "Квант"
год
Год 1989
выпуск
Номер 6
Задача
Номер М1168
олимпиада
Название Турнир городов
Турнир
Дата 1988/1989
Номер 10
вариант
Вариант осенний тур, основной вариант, 9-10 класс
Задача
Номер 4

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

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