Comments 13
Для каждого варианта посчитаем общую сумму длин всех получившихся отрезков и выберем ту конфигурацию, где эта сумма минимальна
Вполне возможна ситуация, когда конфигураций с одинаковой минимальной суммой несколько. Это касается и дальнейшего рассуждения - 4 точки могут образовывать квадрат/ромб. Придётся доказывать, что среди таких конфигураций существует та, в которой отсутствуют пересечения.
Цель - гарантировать, чтобы минимум двое ответили верно.
Правильно для текущей задачи, но некорректно для дополнения про произвольное число цветов и инопланетян. Корректная формулировка - "гарантировать не более одной ошибки".
Ага, спасибо. Не совсем понял про “придётся доказывать, что среди таких конфигураций существует та, в которой отсутствуют пересечения”. Разве не очевидно что такая конфигурация существует? Что касается нескольких вариантов с минимальной длиной, это не меняет ничего.
Разве не очевидно что такая конфигурация существует?
Увы, но я не вижу вообще никаких предпосылок к ОЧЕВИДНОСТИ такого утверждения. С вашим утверждением получается вообще ерунда, а не задача - существует ли конфигурация, которая (по вашим словам) очевидно существует.
Задача-то как раз и состоит в том, чтобы установить, всегда ли существует такая конфигурация.
Мы похоже не поняли друг друга. Я комментировал Ваше замечание:
Это касается и дальнейшего рассуждения - 4 точки могут образовывать квадрат/ромб. Придётся доказывать, что среди таких конфигураций существует та, в которой отсутствуют пересечения.
Мои слова об очевидности относились к тому, что сумма длин отрезков без пересечения всегда меньше чем сумма длин пересекающихся отрезков для группы из четырех точек.
С отрезками я бы так переформулировал ответ, при сохранении идеи: сначала соединяем попарно синие точки с красными как попало, а потом смотрим и "распутываем" пересечения. Каждое "распутывание" уменьшает суммарную длину (и эта дельта всегда больше некоторого положительного значения), поэтому за конечное число "распутываний" мы достигнем результата. То есть на старте не надо искать какие-то минимальные конфигурации и т.д.
Их совсем не обязательно искать, достаточно понять что оно (они) есть, и в нем не будет пересечений.
Конструктивное решение тем любопытно, что оно решает задачу о построении семейства непересекающихся отрезков без решения задачи о таком семействе минимальной полной длины. Вторая задача выглядит сложной (кроме полного перебора, т.е. 
, в голову навскидку ничего не приходит), а по поводу первой можно порассуждать.
А вот это может и не сработать, если под термином "распутывать" вы разумеете замену отрезков строго в четвёрке точек. Потому как переход между имеющейся и оптимальной конфигурацией может включать в путь конфигурацию с бОльшим количеством пересечений или бОльшей суммарной длиной отрезков.
А как доказать, что оно уменьшается на какую-то ограниченную снизу длину? Ясно, что на положительную, но надо доказать, что процесс остановится. Абстрактно рассуждая, может быть ситуация бесконечного уменьшения длины на все меньшие числа. Гораздо проще просто сказать, что множество возможных суммарных длинн конечно, ведь конечно количество всевозможных паросочетаний (n!). А значит процесс уменьшения всегда сойдется куда-то. И там не будет пересечений, потому что пересечение позволило бы уменьшить длину еще дальше.
Исходное решение с поиском минимальной длины сразу мне кажется короче и концептуально проще. Возьмем вот эту конфигурацию. Там нет пересечений. Ведь если бы они были, то можно было бы расрезать крест и получить меньшую суммарную длину. Противоречие.
А как доказать, что оно уменьшается на какую-то ограниченную снизу длину?
Среди всех возможных пар пересекающихся отрезков есть такая, у которой "распутывание" дает наименьшую разницу суммарных длин (равную d), причем d > 0. Вот это как раз ограничение снизу.
Все-равно прямой метод оказывается проще. Если в вашем тоже надо докывать минимум по множеству пар, то почему-бы не взять минимум не по уменьшению длины, а по самой длине. А потом вместо процесса и рассуждений о его сходимости гораздо проще сразу взять минимум и от противного сказать, что там нет пересечений.
Решение первой задачи работает благодаря тому, что система вычетов - это кольцо. Прикольно)
Еще три интересные логические задачи