В стране 2017 городов, некоторые из них соединены дорогами (при этом у каждой дороги концы в разных городах и никакие два города не соединяются друг с другом более чем одной дорогой). Назовем город <<провинциальным>>, если из него выходит не больше 7 дорог. Оказалось, что у любой дороги хоть одним из концов является провинциальный город. Какое наибольшее количество дорог может быть в этой стране?

задан 6 Янв '17 14:50

изменен 6 Янв '17 15:09

knop's gravatar image


18.9k224

В упор не вижу алгебры в этой задачке

(6 Янв '17 15:09) knop

Ну не знаю алгебра, не алгебра, так написано...

(6 Янв '17 15:21) Fghjj Ggyhu
10|600 символов нужно символов осталось
0

Задача из этой серии уже была здесь. Отличие тут есть, но оно не очень принципиальное. Всё решается из тех же соображений.

Пусть n=2017. Легко привести пример, когда дорог 7(n-7)=14070. Покажем, что больше их быть не может.

Если провинциальных городов не более n-7, то данная оценка очевидна. Допустим, что провинциальных городов n-k, где 0<=k<=6. Тогда остальных городов (пусть они называются "большими") не больше 6. Можно считать, что каждый провинциальный город соединён с каждым из больших. Действительно, если какое-то из этих соединений отсутствует, то его можно добавить, увеличивая количество дорог -- за исключением случая, когда провинциальный город A уже имеет 7 соединений. Но тогда он соединён дорогой с каким-то провинциальным городом B ввиду k<7. Тогда эту дорогу из A в B перенаправляем в большой город, не меняя число дорог.

Теперь получается, что у нас есть k(n-k) соединений больших городов с провинциальными. Каждый провинциальный город при этом может быть соединён не более чем с 7-k провинциальными, что даёт ещё (7-k)(n-k)/2 соединений в качестве максимального значения. Общее же число дорог при этом не превосходит (7+k)(n-k)/2. Эту величину можно грубо оценить сверху значением 13n/2, то что заведомо меньше 7(n-7) при n=2017.

Можно оценить чуть точнее: (7+k)(n-k)/2 = (7+k)(n-7)/2 + (7+k)(7-k)/2 < 7(n-7) равносильно (7+k)(7-k)/2 < (n-7)(7-k)/2, то есть верно при n > 14+k.

ссылка

отвечен 6 Янв '17 18:15

10|600 символов нужно символов осталось
Ваш ответ

Если вы не нашли ответ, задайте вопрос.

Здравствуйте

Математика - это совместно редактируемый форум вопросов и ответов для начинающих и опытных математиков, с особенным акцентом на компьютерные науки.

Присоединяйтесь!

отмечен:

×480
×23

задан
6 Янв '17 14:50

показан
1782 раза

обновлен
6 Янв '17 18:15

Отслеживать вопрос

по почте:

Зарегистрировавшись, вы сможете подписаться на любые обновления

по RSS:

Ответы

Ответы и Комментарии

Дизайн сайта/логотип © «Сеть Знаний». Контент распространяется под лицензией cc by-sa 3.0 с обязательным указанием авторства.
Рейтинг@Mail.ru