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