Между любыми двумя городами имеется прямое сообщение самолётом или пароходом. Докажите, что, пользуясь лишь каким-то одним видом транспорта, из любого города можно попасть в любой другой (быть может, с пересадками).
Между любыми двумя городами имеется прямое сообщение самолётом, поездом или пароходом. Докажите, что можно выбрать не менее $\dfrac{N}{2}$ городов и один из трёх видов транспорта так, что, пользуясь им одним, из любого выбранного города можно попасть в любой другой выбранный город.
Приведите пример, доказывающий, что в утверждении б) заменить число $\dfrac{N}{2}$ бо́льшим, вообще говоря, нельзя.
а) Утверждение легко доказывается индукцией по $N$. Для двух городов оно очевидно. Докажем его для $N+1$ города, предполагая, что оно справедливо для $N$ городов.
Пусть $\mathit\Gamma$ — один из $N+1$ городов, тогда оставшиеся $N$ городов по предположению индукции соединены одним видом транспорта, например водным. Если хотя бы один из этих $N$ городов имеет пароходное сообщение с городом $\mathit\Gamma$, то всё ясно. В противном случае любой из этих городов связан самолётом с городом $\mathit\Gamma$, а значит, и с любым другим из них (с пересадкой в $\mathit\Gamma$).
б) Переформулируем задачу так:
Даны $N$ точек, каждые две из которых соединены красным, синим или чёрным отрезками. Будем говорить, что какие-то из этих точек образуют красную (синюю или чёрную) связку, если их можно обойти, двигаясь только по красным (синим или чёрным) отрезкам. Надо доказать, что можно выбрать связку, содержащую не менее $\dfrac N2$ точек.
Пусть $A$ — связка с наибольшим числом точек; для определённости будем считать, что она красная. Пусть $B$ — наибольшая по числу точек не красная связка (например, синяя). Разобьём данные $N$ точек на 4 непересекающихся множества: $A_0$ — точки, входящие в $A$, но не входящие в $B$; $B_0$ — точки, входящие в $B$, но не в $A$; $C=A\cap B$ — точки, входящие и в $A$, и в $B$; $D$ — точки, не входящие ни в $A$, ни в $B$ (см. рис. 1).
Рис. 1
Предположим, что число точек в $A$ меньше $\dfrac N2$, тогда и в связке $B$ меньше $\dfrac N2$ точек; следовательно, множество $D$ не пусто. Заметим теперь, что любой отрезок, соединяющий точку из $A_0$ с точкой из $B_0$ или точку из $C$ с точкой из $D$, является чёрным (в противном случае одна из связок $A$ или $B$ не была бы максимальной). Отсюда вытекает, что множество $C$ не пусто (иначе $A_0\cup B_0=A\cup B$ — чёрная связка, содержащая больше точек, чем $A$), а также, что $C\cup D$ — чёрная связка. Поскольку число точек в связках $A=A_0\cup C$ и $B=B_0\cup C$ не меньше, чем в связке $C\cup D$, множества $A_0$ и $B_0$ не пусты. Таким образом, все данные $N$ точек разбиваются на две связки — $A_0\cup B_0$ и $C\cup D$. Одна из них должна содержать не менее $\dfrac N2$ точек, а это противоречит тому, что число точек в максимальной связке $A$ меньше $\dfrac N2$.
в) Построим пример множества из $N=4k$ точек с соединяющими их отрезками трёх цветов, в котором число точек в максимальной связке равно в точности $\dfrac N2$. (Для $N=4k+r$ при $r=1$, 2, 3 построение аналогично, но максимальный размер связки будет равен $\left[\dfrac N2\right]+1$, причём можно доказать, что в этих случаях связка такого размера найдётся всегда.)
Разделим все точки на 4 группы $A_0$, $B_0$, $C$ и $D$ по $k$ точек в каждой. Соединим чёрными отрезками все точки множества $A_0$ со всеми точками $B_0$ и все точки $C$ со всеми точками $D$. Аналогично соединим точки множеств $A_0$ и $C$, $B_0$ и $D$, $A_0$ и $D$, $B_0$ и $C$ красными отрезками, а точки множеств $A_0$ и $B_0$, $C$ и $D$ — синими (на рисунке 2 изображён случай $k=2$). Внутри каждой из четырёх групп отрезки можно провести произвольно — любые две точки любого из множеств $A_0$, $B_0$, $C$ и $D$ уже соединены ломаными каждого из трёх цветов.
Рис. 2
Легко видеть, что при такой раскраске отрезков любые две из четырёх групп образуют связку с максимальным числом точек, равным $2k=\dfrac N2$.
