Принцип крайнего, индукция и другие методы в комбигео

Рассмотрим минимальное множество дорожек покрывающее весь коридор. Требование минимальности означает, что при удалении любой дорожки из оно перестаёт покрывать коридор.

Покажем, что каждая точка коридора покрывается не более, чем двумя отрезками из (нетрудно понять, что этого достаточно для решения задачи). Предположим противное, пусть некоторая точка покрыта тремя отрезками множества Пусть — точка, наиболее удалённая от среди трёх правых концов отрезков, а — среди трёх левых. Тогда отрезок является объединением данных трёх отрезков, но он является объединением не более чем двух из данных трёх отрезков (а именно, отрезков и ). Таким образом, один из трёх отрезков множества лежит в объединении двух других, что противоречит выбору множества