Question

В городе 19 маршрутов автобусов, при этом, каждый, имеет общую остановку не менее чем с 9 маршрутами. докажите, что можно сесть на автобус любого маршрута и попасть на рейс любого другого автобуса

Answer 1

Используем принцип Дирихле:
{Если кролики рассажены в клетки, причём число кроликов больше числа клеток, то хотя бы в одной из клеток находится более одного кролика.}
Пусть количество маршрутов равно n. Тогда количество маршрутов автобусов равно 2n + 1. Т.к. для того, чтобы совершить рейс, нужно 2 автобуса, то количество тогда количество автобусов, от которых можно будет пересесть, равно n + 1. 
Тогда всегда будет автобус, на который можно сесть и попасть на рейс другого автобуса.