2019-04-29
В Швамбрании имеется 100 городов; при этом если два города $A$ и $B$ не соединены прямой телефонной связью, то имеются регулярные авиарейсы из $A$ в $B$ и наоборот, а если между $A$ и $B$ прямая телефонная связь есть, то таких рейсов нет. Известно, что в Швамбрании каждые два города могут быть (может быть - через- посредство нескольких промежуточных пунктов) соединены между собой телефоном и что из каждого города в каждый другой можно долететь самолетом, - возможно, с несколькими посадками в пути. Докажите, что в Швамбрании имеются такие 4 города, что из каждого из них можно и дозвониться и долететь в любой другой, используя, в случае необходимости, в качестве промежуточных пунктов лишь два других города этой четверки.
Решение:
Вот более «математическая» формулировка той же задачи. На плоскости (на карте Швамбрании) имеется 100 точек (городов); каждые две точки соединены либо сплошной линией (это означает, что между соответствующими городами имеется прямая телефонная связь), либо пунктирной линией (означающей наличие авиарейсов из одного города в другой); при этом известно, что из любой из заданных точек, (из любого города) в любую другую можно пройти как по цепочке сплошных линий, соединяющих наши точки, так и по цепочке пунктирных линий. Нам требуется доказать, что в таком случае среди имеющихся 100 точек можно выбрать такие 4, что здесь тоже из каждой точки можно пройти в любую из трех других как по цепочке сплошных, так и по цепочке пунктирных линий, используя при этом лишь линии, соединяющие наши 4 точки.
Доказывать это утверждение мы будем от противного: предположим, что такой четверки не существует, и, пользуясь этим, выделим из наших 100 точек-городов бесконечную их последовательность, что, разумеется, невозможно.
Мы начнем с некоторых (каких угодно!) точек $A_1$ и $A_2$, соединенных сплошной линией. По условию $A_1$ и $A_2$ можно также соединить цепочкой пунктирных линий; пусть $A_1A_3A_{3}^{ \prime}A_{3}^{ \prime \prime} \cdots A_2$ - кратчайшая из таких цепочек, т. е. цепочка, проходящая через наименьшее число промежуточных точек (городов). В таком случае любые две не соседние точки этой цепочки соединены сплошной линией - ведь иначе мы могли бы сократить нашу цепочку, просто отбросив все города, промежуточные между этими двумя. Но отсюда следует, что если бы наша цепочка содержала более одного промежуточного города - скажем, содержала, бы города $A_3$, $A_3^{ \prime}$ и $A_3^{ \prime \prime}$, (где $A_3^{ \prime \prime}$ может и совпадать с $A_2$),- то города $A_1$, $A_3$, $A_{3}^{ \prime}$ и $A_{3}^{ \prime \prime}$ (см. рис. а) уже образовывали бы требуемую четверку городов (по нашему предположению отсутствующую!), поэтому $A_1$ и $A_2$ соединены «пунктирным двусторонником» $A_1A_3A_2$.
Рассмотрим теперь (соединенные пунктирной линией!) города $A_2$ и $A_3$; в точности, как и ранее, устанавливается, что существует состоящий всего из двух звеньев сплошной путь $A_2A_4A_3$ из $A_2$ в $A_3$. Докажем, что точка $A_4$ соединена с $A_1$ сплошной линией. В самом деле, если бы $A_4$ и $A_1$ были соединены пунктирной линией, то $A$ и $A_2$, $A_3$ и $A_4$ образовывали бы запрещенную по нашему предположению четверку городов с требуемыми свойствами (см. рис. б).
Итак, мы нашли такие 4 точки $A_1, A_2, A_3$ и $A_4$, что $A_2$ соединена c $A_1$ сплошной линией; $A_3$ соединена с $A_1$ и с $A_2$ пунктирными линиями; $A_4$ соединена с $A_1$, $A_2$ и $A_3$ сплошными линиями. Далее воспользуемся методом математической индукции. Предположим, что мы уже нашли такие точки $A_1, A_2, A_3, \cdots, A_i$, что каждая из точек $A_3, A_5, \cdots$ (точек с нечетными номерами) соединена со всеми предшествующими точками пунктирными линиями, а каждая из точек $A_2, A_4, \cdots$ (точек с четными номерами) соединена с каждой из предшествующих ей точек сплошными линиями, и покажем, что этот ряд точек можно продолжить. Пусть, для определенности, линия $A_{i-1}A_i$ является сплошной, рассмотрим кратчайшую пунктирную ломаную $A_{i-1}A_{i+1}A_i$, соединяющую $А_{i-1}$ и $A_i$. Ясно, что точка $A_{i+1}$ не совпадает ни с одной из точек $A_1, A_2, \cdots A_{i-2}$ (и, конечно, $A_{i-1}, A_i$) - ведь все предшествующие $A_{i+1}$ точки соединены с одной из точек $A_{i-1}A_i$ сплошной линией, а со второй - пунктирной, в то время как $A_{i+1}$ соединена пунктирными линиями с ними обеими. С другой стороны, со всеми точками $ЛA_1, A_2, \cdots, A_{i-2}$ (а также и с $A_{i-1}, A_i$) точка $A_{i+1}$ соединена пунктирными линиями, ибо если линия $A_j, A_{i-1}, A_i, A_{i+1}$ (где $j < i-1)$ - сплошная, то точки $A_j$, $A_{i-1}$; $A_i$, $A_{i+1}$ образуют «запрещенную» по нашему предположению четверку точек (рис. б).
Тем самым мы «продолжили на один шаг» конструируемую цепочку $A_1, A_2, \cdots, A_{i-1}, A_i, A_{i+1}, \cdots$ точек-городов, которую, таким образом, можно сделать сколь угодно длинной.