Сколько дней потребуется, чтобы все голубоглазые уехали с острова?

На острове существует правило — голубоглазые люди не могут там находиться. Самолет улетает с острова каждый вечер в 20:00. Все жители собираются за круглым столом ежедневно, каждый человек может видеть цвет глаз других людей, но не знает цвет собственных. Никто не имеет права сказать человеку, какой у его цвет глаз. На острове находится не менее одного голубоглазого человека. Сколько дней потребуется, чтобы все голубоглазые уехали?

Решение

Давайте используем подходы «базовый случай» и «сборка». Предположим, что на острове находится N голубоглазых людей. Мы знаем, что N > 0.

N = 1: у одного человека голубые глаза

Предположим, что все люди на острове достаточно умны. Если известно, что на острове есть только один голубоглазый человек, то, обнаружив, что у всех глаза не голубые, он придет к выводу, что он и является тем единственным голубоглазым человеком, которому следует улететь вечерним рейсом.

N = 2: у двух человек голубые глаза

Два человека с голубыми глазами видят друг друга, но не знают, чему равно c: c = 1 или c = 2. Из предыдущего случая известно, что если c = 1, то голубоглазый человек может себя идентифицировать и покинуть остров в первый же вечер. Если голубоглазый человек находится на острове (c = 2), это означает, что человек, видящий только одного голубоглазого, сам голубоглаз. Оба человека должны будут вечером покинуть остров.

N > 2: общий случай

Давайте использовать ту же логику. Если N = 3, то эти три человека сразу увидят, что на острове есть еще 2 (или 3) человека с голубыми глазами. Если бы таких людей было двое, они покинули бы остров накануне. Поскольку на острове все еще остаются голубоглазые люди, то любой человек может прийти к заключению, что c = 3 и что у него голубые глаза. Все они уедут той же ночью.

Такой шаблон можно использовать для произвольного значения N — если на острове находится N человек с голубыми глазами, понадобится N ночей, чтобы все они покинули остров.

Разбор головоломки по книге «Карьера программиста. Как устроиться на работу в Google, Microsoft или другую ведущую IT – Компанию»