Разделы 
Дополнительно
Задача по математике - 1992
2019-01-22 
В стране $N$ городов. Между любыми двумя из них проложена либо автомобильная, либо железная дорога. Турист хочет объехать страну, побывав в каждом городе ровно один раз, и вернуться в город, с которого он начинал путешествие. Докажите, что турист может выбрать город, с которого он начнет путешествие, и маршрут так, что ему придется поменять вид транспорта не более одного раза.
Решение:
Переформулируем задачу на языке графов. Нам дан полный граф с $N$ вершинами, ребра которого покрашены в два цвета. Требуется доказать, что мы можем выделить в этом графе цикл, проходящий через все вершины, состоящий не более чем из двух одноцветных частей. Доказательство проведем по индукции. Для полного графа с тремя вершинами утверждение очевидно. Пусть доказываемое утверждение верно для $N = к$. Рассмотрим полный граф с $к + 1$ вершиной. Удалим из рассмотрения одну вершину $M$ с выходящими из нее ребрами. Для оставшегося графа с $к$ вершинами по предположению индукции существует цикл, проходящий через все вершины, состоящий не более чем из двух одноцветных частей. Возможны два случая.
1) Все ребра цикла окрашены в один цвет. Занумеруем вершины цикла по порядку $A_1, A_2, \cdots, A_k$. Тогда, удалив ребро $A_1A_2$ и соединив вершину $M$ с вершинами $A_1$ и $A_2$, мы получим цикл, состоящий не более чем из двух одноцветных частей.
2) Не все ребра цикла окрашены в один цвет. Пусть изменение цвета происходит в вершинах $A_1$ и $A_m$, т. е. в цикле есть две одноцветные части: $A_1A_2 \cdots A_m$ (первого цвета) и $A_mA_{m+1} \cdots A_1$ (второго цвета). Тогда посмотрим на цвет ребра $A_mA$. Если это ребро первого цвета, то цикл $A_1A_2 \cdots A_mMA_m + 1 \cdots A_1$ - искомый, если же оно второго цвета, то искомым будет цикл $A_1A_2 \cdots A_{m-1}MA_m \cdots A_1$.
То есть в любом случае мы получили требуемый цикл с $к + 1$ вершиной.
В стране $N$ городов. Между любыми двумя из них проложена либо автомобильная, либо железная дорога. Турист хочет объехать страну, побывав в каждом городе ровно один раз, и вернуться в город, с которого он начинал путешествие. Докажите, что турист может выбрать город, с которого он начнет путешествие, и маршрут так, что ему придется поменять вид транспорта не более одного раза.
Решение:
Переформулируем задачу на языке графов. Нам дан полный граф с $N$ вершинами, ребра которого покрашены в два цвета. Требуется доказать, что мы можем выделить в этом графе цикл, проходящий через все вершины, состоящий не более чем из двух одноцветных частей. Доказательство проведем по индукции. Для полного графа с тремя вершинами утверждение очевидно. Пусть доказываемое утверждение верно для $N = к$. Рассмотрим полный граф с $к + 1$ вершиной. Удалим из рассмотрения одну вершину $M$ с выходящими из нее ребрами. Для оставшегося графа с $к$ вершинами по предположению индукции существует цикл, проходящий через все вершины, состоящий не более чем из двух одноцветных частей. Возможны два случая.
1) Все ребра цикла окрашены в один цвет. Занумеруем вершины цикла по порядку $A_1, A_2, \cdots, A_k$. Тогда, удалив ребро $A_1A_2$ и соединив вершину $M$ с вершинами $A_1$ и $A_2$, мы получим цикл, состоящий не более чем из двух одноцветных частей.
2) Не все ребра цикла окрашены в один цвет. Пусть изменение цвета происходит в вершинах $A_1$ и $A_m$, т. е. в цикле есть две одноцветные части: $A_1A_2 \cdots A_m$ (первого цвета) и $A_mA_{m+1} \cdots A_1$ (второго цвета). Тогда посмотрим на цвет ребра $A_mA$. Если это ребро первого цвета, то цикл $A_1A_2 \cdots A_mMA_m + 1 \cdots A_1$ - искомый, если же оно второго цвета, то искомым будет цикл $A_1A_2 \cdots A_{m-1}MA_m \cdots A_1$.
То есть в любом случае мы получили требуемый цикл с $к + 1$ вершиной.
