Кружковская задача #17

Продолжаем серию публикаций о кружковском мышлении. Первые тридцать две части:
1. Об осмысленности и автоматизме;
2. Кружковская задача;
3. Кружковская задача 2;
4. Шахматематика;
5. Кружковская задача 3;
6. Уровни очевидности;
7. Комплексный тест;
8. Кружковская задача 4;
9. Кружковская задача 5;
10. Разрезания и замощения;
11. Кружковская задача 6;
12. Кружковская задача 7;
13. Авторская задача;
14. Кружковская задача 8;
15. Задача про жизнь;
16. Кружковская задача 9;
17. Кружковская задача 10;
18. Хитрые доминошки;
19. Школьная задача;
20. Кружковская задача 11;
21. Деление с остатком;
22. Оценка плюс пример;
23. Опять двадцать пять...;
24. Кружковская задача 12;
25. Про календарь;
26. Кружковская задача 13;
27. Великая комбинаторика;
28. Дискретная непрерывность;
29. Кружковская задача 14;
30. Кружковская задача 15;
31. Ханойская башня;
32. Кружковская задача 16.

Александр Сергеевич плохому не научит...

Задача

Сеть автобусных маршрутов устроена так, что:

• на каждом маршруте есть ровно три остановки;
• каждые два маршрута либо вовсе не имеют общих остановок, либо имеют только одну общую остановку.

Какое наибольшее количество маршрутов может быть в сети, если в ней всего 9 остановок?

Решение

Оценка

Рассмотрим любую остановку. Через неё проходит не более восьми маршрутов, так как никакая из восьми оставшихся остановок не может входить больше, чем в один подобный маршрут. Если теперь сложить все маршруты, проходящие через первую остановку, проходящие через вторую и так далее, то получится утроенное количество маршрутов (так как каждый маршрут посчитан три раза). С другой стороны, так как каждое слагаемое не превосходит четырёх, то эта сумма не превосходит 36.

Таким образом, утроенное количество маршрутов не превосходит 36, поэтому само количество маршрутов не превосходит 12.

Пример

Обозначим остановки А1, А2, А3, В1, В2, В3, С1, С2, С3 и выпишем все маршруты:

1. А1, А2, А3;
2. В1, В2, В3;
3. С1, С2, С3;
4. А1, В1, С1;
5. А2, В2, С2;
6. А3, В3, С3;
7. А1, В2, С3;
8. А1, В3, С2;
9. А2, В1, С3;
10. А2, В3, С1;
11. А3, В2, С1;
12. А3, В1, С2.

Наглядно это можно представить на картинке:

#математика #математическийкружок #образованиевроссии #школа

P.S. Не забывайте прочитать об истории математических кружков в Ленинграде/Санкт-Петербурге и обо мне.