В некоторой стране имеется n городов и некоторая сеть дорог с двусторонним движением. Каждая дорога соединяет ровно два города и при этом дороги попарно не пересекаются. Из каждого города выходят ровно три дороги. Все дороги в стране пронумерованы цифрами 1, 2 и 3 так, что из каждого города выходят ровно три дороги с различными номерами. Найдите сумму всех n не превосходящих 1000, при которых такая конфигурация возможна.

задан 15 Янв '14 11:53

изменен 15 Янв '14 12:18

Пусть k – число различных дорог в стране. Посчитаем суммарное количество дорог в стране с учетом повторений. Будем идти по всем городам и считать количество дорог их соединяющих. Так как из каждого города выходит ровно три дороги, то суммарное количество дорог с учетом повторений равно 3n. В то же время, каждая дорога соединяет два города, а значит, при таком подсчете будет учитываться дважды, а стало быть, 3n=2k. Следовательно, n четное и n >=4, т.к. из города выходит 3 дороги и куда-то идут. Значит надо посчитать сумму четных чисел >= 4 и не превосходящих 1000. S=((4+1000)/2)*499=250498

(15 Янв '14 12:17) serg55

@serg55: здесь помимо численного ответа ещё важна такая вещь как наличие доказательства, что для любого чётного числа, начиная с 4, возможна требуемая конфигурация на плоскости, причём с попарно не пересекающимися дорогами. Могут ведь быть какие-то ещё препятствия к осуществлению этого помимо чётности. Поэтому к решению надо добавить ещё несколько соображений по этому поводу.

(15 Янв '14 14:14) falcao

@falcao: Пусть на плоскости изображен выпуклый n угольник (при четном n ). Пронумеруем его вершины числами 1,2,3,4,… , а стороны последовательно цифрами 1,2,1,2,1…. Соединим отрезками вершины с номерами i+1 и n - i+1 при i = 1, 2, …, n/2-1. Эти отрезки пронумеруем цифрой 3. Остается соединить дорогой с номером 3 вершины 1 и n/2+1. Можно еще сделать рисунок, иллюстрирующий вышесказанное, но я не умею. Такое доказательство подойдет? А сам ответ верен? Заранее благодарен.

(15 Янв '14 14:30) serg55
2

@serg55: я понял Вашу конструкцию. Рисунок не нужен -- словесного описания вполне достаточно. Сам я рассуждал так: если есть система дорог, то число городов можно увеличить на 2 таким образом: если из A выходят дороги в города B, C, D, то удалим город A вместе с короткими отрезками этих дорог, и построим там города B', C', D' на местах обрыва, соединив их далее по треугольнику.

Численный ответ у Вас, насколько я могу судить, верен, но я был бы очень признателен Вам, а также другим участникам форума, чтобы они сами проверяли свои вычисления. Можно, например, сверить, посчитав другим способом.

(15 Янв '14 14:38) falcao
10|600 символов нужно символов осталось
Знаете, кто может ответить? Поделитесь вопросом в Twitter или ВКонтакте.

Ваш ответ

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

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

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

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

отмечен:

×3,938

задан
15 Янв '14 11:53

показан
1495 раз

обновлен
15 Янв '14 14:38

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

по почте:

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

по RSS:

Ответы

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

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