|
В некоторой стране имеется n городов и некоторая сеть дорог с двусторонним движением. Каждая дорога соединяет ровно два города и при этом дороги попарно не пересекаются. Из каждого города выходят ровно три дороги. Все дороги в стране пронумерованы цифрами 1, 2 и 3 так, что из каждого города выходят ровно три дороги с различными номерами. Найдите сумму всех n не превосходящих 1000, при которых такая конфигурация возможна. задан 15 Янв '14 11:53 
serg55 |
Здравствуйте
Математика - это совместно редактируемый форум вопросов и ответов для начинающих и опытных математиков, с особенным акцентом на компьютерные науки.
Присоединяйтесь!
отмечен:
задан
15 Янв '14 11:53
показан
1477 раз
обновлен
15 Янв '14 14:38
Связанные исследования
Связанные вопросы
Дизайн сайта/логотип © «Сеть Знаний». Контент распространяется под лицензией cc by-sa 3.0 с обязательным указанием авторства.
Пусть k – число различных дорог в стране. Посчитаем суммарное количество дорог в стране с учетом повторений. Будем идти по всем городам и считать количество дорог их соединяющих. Так как из каждого города выходит ровно три дороги, то суммарное количество дорог с учетом повторений равно 3n. В то же время, каждая дорога соединяет два города, а значит, при таком подсчете будет учитываться дважды, а стало быть, 3n=2k. Следовательно, n четное и n >=4, т.к. из города выходит 3 дороги и куда-то идут. Значит надо посчитать сумму четных чисел >= 4 и не превосходящих 1000. S=((4+1000)/2)*499=250498
@serg55: здесь помимо численного ответа ещё важна такая вещь как наличие доказательства, что для любого чётного числа, начиная с 4, возможна требуемая конфигурация на плоскости, причём с попарно не пересекающимися дорогами. Могут ведь быть какие-то ещё препятствия к осуществлению этого помимо чётности. Поэтому к решению надо добавить ещё несколько соображений по этому поводу.
@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. Можно еще сделать рисунок, иллюстрирующий вышесказанное, но я не умею. Такое доказательство подойдет? А сам ответ верен? Заранее благодарен.
@serg55: я понял Вашу конструкцию. Рисунок не нужен -- словесного описания вполне достаточно. Сам я рассуждал так: если есть система дорог, то число городов можно увеличить на 2 таким образом: если из A выходят дороги в города B, C, D, то удалим город A вместе с короткими отрезками этих дорог, и построим там города B', C', D' на местах обрыва, соединив их далее по треугольнику.
Численный ответ у Вас, насколько я могу судить, верен, но я был бы очень признателен Вам, а также другим участникам форума, чтобы они сами проверяли свои вычисления. Можно, например, сверить, посчитав другим способом.