Продолжаю публикацию интересных задач на логику с красивым решением.
Формулировка:
3 честных рациональных инопланетянина (А, Б, В) стоят в колонне. В видит А и Б; Б видит только А; А не видит никого. На каждого надет колпак либо синего, либо зеленого, либо красного цвета, количество колпаков того или иного цвета не ограничено. Договорившись об общей стратегии, они по очереди (начиная с В) называют возможный цвет своего колпака. Цель - гарантировать, чтобы верно ответили все, кроме одного.
Решение:
Воспользуемся арифметикой по модулю 3 (будем считать остатки от деления на 3, соответствующего количеству цветов). Участники заранее присваивают каждому цвету число - красный = 0, синий = 1, зеленый = 2. Инопланетянин В видит двоих перед собой (Б и А). Он складывает их числа и называет цвет, который соответствует остатку от деления суммы на 3. Например, В видит у Б - синий (1), у А — зеленый (2). 1 + 2 = 3. Остаток от деления 3 на 3 равен 0. В говорит: «Красный» (код числа 0). Б слышит «Красный» (0) и понимает: «Мой цвет + цвет А делится на 3 без остатка». Затем он смотрит на А. Допустим, Б видит, что на А — зеленый колпак (2). Единственное число, которое при сложении с 2 дает число, делящееся на 3 — это 1. Б понимает, что он — Синий (1), и уверенно это произносит. А слышал код от В (0) и ответ от Б (1) и понимает, что на нем колпак зеленого цвета (2).
Данный метод работает для любого количества цветов и любого количества инопланетян.
Формулировка:
На изолированном острове живут 65 демонов. Все они — идеальные логики, которые видят любые действия друг друга, точно знают общую численность и постоянно хотят кушать. Каждый демон при первой же возможности готов съесть яблоко или любого спящего сородича, мгновенно засыпая после этого навсегда, но сделает это только при полной уверенности в своей безопасности. Нападение же на бодрствующего приносит агрессору мгновенную смерть. Главная цель каждого — выжить и безопасно уснуть, но если есть хоть малейший риск быть съеденным во сне, демон предпочтет вообще не рисковать и остаться живым и бодрствующим. Вдруг на острове появляется одно яблоко. Что сделает самый первый демон, получивший по жребию право хода, и съест ли он его?
Решение:
Представим, что на острове всего 1 демон — он съест яблоко и спокойно уснет, ведь съедать его некому. Если демонов 2, то первый яблоко не тронет: он понимает, что как только он уснет, ситуация сведется к задаче для одного демона, и второй его гарантированно съест. Если демонов 3, то первый смело съедает яблоко: он знает, что после этого останутся 2 бодрствующих демона, а в ситуации для двоих (как мы только что выяснили) никто не станет есть спящего из страха перед соседом. Продолжая эту цепочку, мы видим, что при любом нечётном числе демонов первый в очереди абсолютно застрахован от гибели, поэтому он спокойно съедает яблоко, а остальные демоны остаются бодрствовать дальше. Таким образом, на острове останется один спящий демон (съевший яблоко) и 64 бодрствующих.
Формулировка:
На плоскости отмечены n синих и n красных точек, причем никакие три из них не лежат на одной прямой. Можно ли соединить все точки попарно отрезками (каждую синюю точку строго с одной красной) так, чтобы эти отрезки не пересекались друг с другом?
Решение:
Рассмотрим все способы соединить наши точки в сине-красные пары (их количество конечно). Для каждого варианта посчитаем общую сумму длин всех получившихся отрезков и выберем ту конфигурацию, где эта сумма минимальна. В таком положении отрезки гарантированно не пересекаются. Действительно, если бы какие-то два отрезка AB и CD пересеклись в точке X, мы могли бы «распутать» этот крест и пересоединить те же четыре точки в пары AD и CB. Сумма длин новых отрезков окажется меньше суммы старых AD + CB < AB + CD. Но это противоречит тому, что мы изначально выбрали вариант с самой минимальной суммой длин. Значит, в конфигурации с минимальной суммой никаких пересечений быть не может.
Комментарии (13)
t1geAr
17.08.2026 07:48Решение первой задачи работает благодаря тому, что система вычетов - это кольцо. Прикольно)
Akina
Вполне возможна ситуация, когда конфигураций с одинаковой минимальной суммой несколько. Это касается и дальнейшего рассуждения - 4 точки могут образовывать квадрат/ромб. Придётся доказывать, что среди таких конфигураций существует та, в которой отсутствуют пересечения.
Правильно для текущей задачи, но некорректно для дополнения про произвольное число цветов и инопланетян. Корректная формулировка - "гарантировать не более одной ошибки".
marsel84 Автор
Ага, спасибо. Не совсем понял про “придётся доказывать, что среди таких конфигураций существует та, в которой отсутствуют пересечения”. Разве не очевидно что такая конфигурация существует? Что касается нескольких вариантов с минимальной длиной, это не меняет ничего.
Akina
Увы, но я не вижу вообще никаких предпосылок к ОЧЕВИДНОСТИ такого утверждения. С вашим утверждением получается вообще ерунда, а не задача - существует ли конфигурация, которая (по вашим словам) очевидно существует.
Задача-то как раз и состоит в том, чтобы установить, всегда ли существует такая конфигурация.
marsel84 Автор
Мы похоже не поняли друг друга. Я комментировал Ваше замечание:
Мои слова об очевидности относились к тому, что сумма длин отрезков без пересечения всегда меньше чем сумма длин пересекающихся отрезков для группы из четырех точек.
Alexandroppolus
С отрезками я бы так переформулировал ответ, при сохранении идеи: сначала соединяем попарно синие точки с красными как попало, а потом смотрим и "распутываем" пересечения. Каждое "распутывание" уменьшает суммарную длину (и эта дельта всегда больше некоторого положительного значения), поэтому за конечное число "распутываний" мы достигнем результата. То есть на старте не надо искать какие-то минимальные конфигурации и т.д.
marsel84 Автор
Их совсем не обязательно искать, достаточно понять что оно (они) есть, и в нем не будет пересечений.
misha_erementchouk
Конструктивное решение тем любопытно, что оно решает задачу о построении семейства непересекающихся отрезков без решения задачи о таком семействе минимальной полной длины. Вторая задача выглядит сложной (кроме полного перебора, т.е.
, в голову навскидку ничего не приходит), а по поводу первой можно порассуждать.
Akina
А вот это может и не сработать, если под термином "распутывать" вы разумеете замену отрезков строго в четвёрке точек. Потому как переход между имеющейся и оптимальной конфигурацией может включать в путь конфигурацию с бОльшим количеством пересечений или бОльшей суммарной длиной отрезков.
Alexandroppolus
точно нет. У нас за одну операцию два отрезка заменяются на другие два, суммарно более коротких, а все прочие отрезки не меняются. Пересечений при такой замене может возникнуть больше, но нас интересует именно сумма длин отрезков - она каждый раз уменьшается.
wataru
А как доказать, что оно уменьшается на какую-то ограниченную снизу длину? Ясно, что на положительную, но надо доказать, что процесс остановится. Абстрактно рассуждая, может быть ситуация бесконечного уменьшения длины на все меньшие числа. Гораздо проще просто сказать, что множество возможных суммарных длинн конечно, ведь конечно количество всевозможных паросочетаний (n!). А значит процесс уменьшения всегда сойдется куда-то. И там не будет пересечений, потому что пересечение позволило бы уменьшить длину еще дальше.
Исходное решение с поиском минимальной длины сразу мне кажется короче и концептуально проще. Возьмем вот эту конфигурацию. Там нет пересечений. Ведь если бы они были, то можно было бы расрезать крест и получить меньшую суммарную длину. Противоречие.
Alexandroppolus
Среди всех возможных пар пересекающихся отрезков есть такая, у которой "распутывание" дает наименьшую разницу суммарных длин (равную d), причем d > 0. Вот это как раз ограничение снизу.
wataru
Все-равно прямой метод оказывается проще. Если в вашем тоже надо докывать минимум по множеству пар, то почему-бы не взять минимум не по уменьшению длины, а по самой длине. А потом вместо процесса и рассуждений о его сходимости гораздо проще сразу взять минимум и от противного сказать, что там нет пересечений.