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