2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки


Правила форума


Посмотреть правила форума



Начать новую тему Ответить на тему
 
 Городок DIV-GRAD
Сообщение19.02.2024, 15:29 


20/04/15
20
Правильное ли решение следующей задачи?
Городок DIV-GRAD обладает отличной автобусной сетью! С каждой остановки можно проехать на любую другую без пересадок. Каждый маршрут имеет 5 остановок, а каждые два маршрута имеют единственную общую остановку. Сколько же автобусных маршрутов в этом дивном граде? Нарисуйте карту.
Решение:
Пусть a – один из маршрутов, B – остановка, через которую маршрут a не проходит. Каждый маршрут, проходящий через B, пересекает маршрут a. При этом два разных маршрута, проходящих через B, пересекают a по разным остановкам (иначе они имели бы две общие остановки, что противоречит условию). Поэтому через B проходит ровно пять маршрутов.
На каждом из них есть по 4 остановки, отличных от B. Значит, всего в городе 21 остановка. Через каждую пару остановок (а их 210) проходит единственный маршрут, при этом на каждом маршруте – пять пар остановок. Следовательно, всего маршрутов 210 : 5 = 42.

Карту не получилось нарисовать.

 Профиль  
                  
 
 Posted automatically
Сообщение19.02.2024, 17:10 
Админ форума


02/02/19
2649
 i  Тема перемещена из форума «Олимпиадные задачи (М)» в форум «Помогите решить / разобраться (М)»
Причина переноса: темы, в которых нужно что-то объяснить или подсказать в пределах учебных курсов, создаются в этом разделе.
В олимпиадном разделе размещаются задачи, решение которых известно топикстартеру, но он предлагает другим участникам попробовать свои силы в поисках этого решения.

 Профиль  
                  
 
 Re: Городок DIV-GRAD
Сообщение19.02.2024, 17:32 
Заслуженный участник
Аватара пользователя


16/07/14
9216
Цюрих
Zeddikus в сообщении #1630236 писал(а):
Через каждую пару остановок (а их 210) проходит единственный маршрут, при этом на каждом маршруте – пять пар остановок
А сколько пар остановок на маршруте?

 Профиль  
                  
 
 Re: Городок DIV-GRAD
Сообщение19.02.2024, 17:47 
Аватара пользователя


07/01/16
1612
Аязьма
Формально автобусная "сеть" из одного маршрута тоже подходит

 Профиль  
                  
 
 Re: Городок DIV-GRAD
Сообщение19.02.2024, 19:08 
Аватара пользователя


07/01/16
1612
Аязьма
Задача обладает некоторым коварством: если на каждом маршруте по две остановки (а не по пять), - подходит вообще любое количество маршрутов (от трёх и больше)

 Профиль  
                  
 
 Re: Городок DIV-GRAD
Сообщение19.02.2024, 22:50 
Заслуженный участник
Аватара пользователя


30/01/09
7136
В качестве юмора :D
Zeddikus в сообщении #1630236 писал(а):
С каждой остановки можно проехать на любую другую без пересадок. Каждый маршрут имеет 5 остановок, а каждые два маршрута имеют единственную общую остановку.

Можно взять правильный пятиугольник. Его стороны единственный маршрут в городе. Условие "каждые два маршрута ..." выполняется автоматически, поскольку маршрут всего один :lol:

 Профиль  
                  
 
 Re: Городок DIV-GRAD
Сообщение21.02.2024, 21:45 


02/04/18
240
Zeddikus в сообщении #1630236 писал(а):
при этом на каждом маршруте – пять пар остановок. Следовательно, всего маршрутов 210 : 5 = 42.

А разве не 10 пар? Тогда маршрутов тоже 21.

 Профиль  
                  
 
 Re: Городок DIV-GRAD
Сообщение22.02.2024, 20:12 


02/04/18
240
Zeddikus в сообщении #1630236 писал(а):
Карту не получилось нарисовать.

Собственно, задача распространяется на общий случай $N$ станций на каждом маршруте, тогда в городе $N^2-N+1$ станция и столько же маршрутов.

Случай $N=2$ - это треугольник, каждая из сторон которого - один маршрут. Банально...

Для $N=3$ рисовать нетрудно почти наугад, но картинка ясности не вносит, там просто семиконечный граф из разноцветных треугольников. Мне кажется, лучше подобрать логику и объяснить на словах.
Есть Центральный автовокзал (обозначим его буквой $O$), через который проходит 3 треугольных маршрута (для удобства все маршруты - круговые), на каждом из них остановки пронумерованы: $A_0, A_1, B_0, B_1, C_0, C_1$. Еще 4 маршрута формируются так: $\{A_iB_jC_k\; |\; i+j+k \equiv 0\mod{2}\}$, можно и единице - неважно. Тогда все условия выполнены.

Соответственно, для $N=5$ можно поступить аналогично: центр $O$, через который строятся маршруты $A, B, C, D, E$ с остановками с индексами $0..3$. Тогда еще 16 маршрутов проходят по точкам $A_iB_jC_kD_lE_m$. Здесь можно исхитриться суммой по модулю, но мне лениво, а можно составить таблицу, где обозначить маршруты буквами от $F$ до $U$ по этим точкам. Например:
Изображение
На карте, очевидно, выйдет месиво из линий, поэтому можно рисовать, но лучше воображать.

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 8 ] 

Модераторы: Модераторы Математики, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group