Еще три интересные логические задачи

Продолжаю публикацию интересных задач на логику с красивым решением.

Формулировка:

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. Но это противоречит тому, что мы изначально выбрали вариант с самой минимальной суммой длин. Значит, в конфигурации с минимальной суммой никаких пересечений быть не может.