Привет, Хабр!
Недавно друзья задали мне задачу по дискретной математике. Задача так сильно понравилась, что я решил поделиться ей с широким кругом, а также рассказать свое решение и предложенное авторами задачи.
Текст задачи
Дана плоскость. На ней расположены n красных и n синих точек, причем никакие три точки не лежат на одной прямой. Докажите, что всегда можно соединить точки попарно непересекающимися отрезками так, что каждая красная точка соединена отрезком с синей и каждая синяя точка соединена отрезком с красной.
Предлагаю не переходить к разбору сразу, а остановиться и подумать. Ниже дана подсказка для самоконтроля, что условие правильно понято.
Подсказка для самоконтроля
Очевидно, что отрезков должно быть ровно n штук.
В самом деле, у нас n красных точек. На каждую красную точку требуется хотя бы один отрезок, поэтому отрезков должно быть хотя бы n.
При этом никакую точку не получится соединить больше чем с одной другой, т.к. в противном случае точка будет лежать на двух различных отрезках, а значит, технически будет являться точкой их пересечения, что запрещено. Следовательно, всего n отрезков.
Мое решение
Докажем по индукции. База - пустое множество точек. Идея перехода в том, чтобы свести задачу размера n к задачам размера меньше n.
Рассмотрим границу выпуклой оболочки множества всех точек (представьте, что мы натянули канцелярскую резинку на точки так, что они оказались внутри, часть точек попали на границу). Заметим, что получился многоугольник, в углах которого лежат точки. Причем точки могут лежать только в его углах, т.к. по условию никакие три точки не лежат на одной прямой.
Заметим, что если на границе получившегося многоугольника хотя бы две точки имеют разный цвет, то найдутся две соседние точки разных цветов. Найдем две такие точки, соединим отрезком. Теперь все остальные точки оказались в одной из полуплоскостей относительно прямой, на которой лежит наш отрезок, а значит никакие другие возможные отрезки с ним не пересекутся, т.е. можно "удалить" данную пару точек и перейти к задаче размера n - 1.
Так можно делать до тех пор, пока на границе выпуклой оболочки лежат хотя бы две точки разных цветов. Отдельно рассмотрим случай, когда все точки на границе имеют один цвет.
Не умаляя общности предположим, что все точки на границе оказались синими. Поскольку множество точек конечно, конечно и множество прямых, на которых лежат хотя бы две точки. Следовательно конечно и множество углов наклонов этих прямых. А значит, можно выбрать новый угол наклона, такой что никакие две точки не лежат на прямой с таким углом. Построим прямую с этим самым углом и начнем ее двигать (для определенности - слева на право). Тогда все точки сначала окажутся в правой полуплоскости относительно прямой, затем их количество будет изменяться по мере пересечения прямой с точками, и в конце - все точки окажутся слева.
Заметим, что самая левая и самая правя точки принадлежат границе выпуклой оболочки, а значит - они одного цвета!
Будем считать количество синих и красных точек слева от прямой: red_cnt(x) и blue_cnt(x). Изначально red_cnt(x) = blue_cnt(x) = 0. Затем прямая пересекает первую синюю точку и тогда red_cnt(x) = 0, blue_cnt(x) = 1. По мере продвижения прямой вправо эти числа растут (каждый раз одно из чисел увеличивается на 1). В конце будет добавлена последняя синяя точка и числа достигнут n (red_cnt(x) = blue_cnt(x) = n). Это значит, что прежде чем последняя синяя точка была добавлена значения были red_cnt(x) = n, blue_cnt(x) = n - 1. Т.е. мы имеем две функции, причем blue_cnt начала расти раньше, но достигла n позже чем red_cnt. А значит - эти функции принимают одинаковое значение где-то между началом левой и правой точкой: red_cnt(x) = blue_cnt(x). Иными словами, существует прямая, которая делит плоскость на две непустые полуплоскости, в каждой из которых равное количество синих и красных точек! А значит, мы свели задачу размера n к двум задачам меньшего размера. Ч.т.д.
Решение авторов задачи
Построим n отрезков, концы которых соединяют точки разных цветов (не обязательно без пересечений). Строить можно так: пока есть точки не соединенные отрезком, будем брать пару "свободных" точек и соединять их.
Теперь рассмотрим любую пару отрезков, которые имеют пересечение (см. рисунок). Удалим два отрезка с пересечением и построим два новых отрезка без пересечений. Заметим, что в силу неравенства треугольника, каждый раз выполняя такое действие, мы уменьшаем суммарную длину всех имеющихся отрезков. Поскольку количество способов соединить отрезки конечно и каждый раз мы переходим от одного способа к другому, уменьшая суммарную длину, то данный процесс должен будет однажды остановиться. В этот момент у нас не окажется больше пересечений, следовательно мы всегда получим искомое построение. Ч.т.д.
Заключение
Особенность второго решения в том, что мы ввели некоторый числовой параметр, которым охарактеризовали построение и научились делать действия, приводящие к его уменьшению. Лично мне оно напомнило задачу с двадцатью картами из моего любимого фильма X+Y (см. отрывок на англ.), таким образом нашло отклик в моей душе. Однако, если бы я сразу подсмотрел его, то ни за что не придумал бы своего.
Благодарности
Спасибо авторам Ace Your Next Coding Interview, благодаря которым я узнал о данной задаче.
Также отдельное спасибо Виктору Крыштаповичу, который слушал мой поток сознания.