Загадка Эйнштейна

Страница журнала с приведённой в статье загадкой

Загадка Эйнштейна — известная логическая задача, по легенде созданная Альбертом Эйнштейном в годы его детства^[1]. Также бытует мнение, что она использовалась Эйнштейном для проверки кандидатов в ассистенты на способность к логическому мышлению. Иногда автором головоломки называют Льюиса Кэрролла^[2]. Тем не менее, нет никаких доказательств того, что задачу придумал Эйнштейн или Кэрролл. Более того, в приведённом ниже условии задачи упоминаются марки сигарет, например Kools, которые не существовали при жизни Кэрролла и во времена детства Эйнштейна.

Некоторые приписывают Эйнштейну рассуждение, в котором тот утверждает, что лишь два процента населения земного шара способны оперировать в уме закономерностями, связанными сразу с пятью признаками^[3]. Как частное следствие этого, приведённая головоломка может быть решена без использования бумаги лишь теми, кто принадлежит к этим двум процентам. Однако не существует никаких документальных свидетельств того, что Эйнштейн когда-либо утверждал подобное.

В своём самом сложном варианте задача предполагает решение в уме, без использования каких-либо записей или средств сохранения информации. Без этих ограничений головоломка заметно теряет в сложности, поскольку может быть решена простым составлением таблицы с исключением заведомо противоречивых вариантов, и, следовательно, мало что говорит о способностях испытуемого.

Оригинальный текст задачи

Здесь приведён первый известный опубликованный вариант головоломки, который появился в журнале англ.) в номере от 17 декабря 1962 года^[4]. Выпуск от 25 марта 1963 года содержал нижеприведённый ответ и список из нескольких сотен фамилий читателей, правильно решивших задачу.

1. На улице стоят пять домов.
2. Англичанин живёт в красном доме.
3. У испанца есть собака.
4. В зелёном доме пьют кофе.
5. Украинец пьёт чай.
6. Зелёный дом стоит сразу справа от белого дома.
7. Тот, кто курит Old Gold, разводит улиток.
8. В жёлтом доме курят Kools.
9. В центральном доме пьют молоко.
10. Норвежец живёт в первом доме.
11. Сосед того, кто курит Chesterfield, держит лису.
12. В доме по соседству с тем, в котором держат лошадь, курят Kools.
13. Тот, кто курит Lucky Strike, пьёт апельсиновый сок.
14. Японец курит Parliament.
15. Норвежец живёт рядом с синим домом.

Кто пьёт воду? Кто держит зебру?

В целях ясности следует добавить, что каждый из пяти домов окрашен в свой цвет, а их жители — разных национальностей, владеют разными животными, пьют разные напитки и курят разные марки американских сигарет. Ещё одно замечание: в утверждении 6, справа означает справа относительно Вас.

Оригинальный текст  (англ.)  

1. There are five houses.
2. The Englishman lives in the red house.
3. The Spaniard owns the dog.
4. Coffee is drunk in the green house.
5. The Ukrainian drinks tea.
6. The green house is immediately to the right of the ivory house.
7. The Old Gold smoker owns snails.
8. Kools are smoked in the yellow house.
9. Milk is drunk in the middle house.
10. The Norwegian lives in the first house.
11. The man who smokes Chesterfields lives in the house next to the man with the fox.
12. Kools are smoked in the house next to the house where the horse is kept.
13. The Lucky Strike smoker drinks orange juice.
14. The Japanese smokes Parliaments.
15. The Norwegian lives next to the blue house.

Now, who drinks water? Who owns the zebra?

In the interest of clarity, it must be added that each of the five houses is painted a different color, and their inhabitants are of different national extractions, own different pets, drink different beverages and smoke different brands of American cigarets. One other thing: in statement 6, right means your right.

— Life International, 17 декабря 1962 года

Исходное условие опускает некоторые существенные детали, в частности то, что дома расположены подряд.

Так как в условии не сказано о том, что кто-либо вообще пьёт воду или держит зебру, то эти утверждения полагаются неявными посылками, как это принято в подобных логических задачах. В противном случае ответом будет «Не хватает данных».

Посылка 12 в оригинале сформулирована не совсем корректно. Она должна гласить «Kools are smoked in a house next to the house where the horse is kept», а не «the house», так как в таком случае «the» подразумевает, что рядом с домом, в котором держат лошадь, находится только один дом, из чего, в свою очередь, следует, что дом с лошадью — либо крайний левый, либо крайний правый. А это в результате приводит к противоречию.

Решение

Здесь приведены дедуктивные шаги, следуя которым можно получить решение. Суть метода заключается в том, чтобы попытаться вписать известные соотношения в таблицу, последовательно исключая невозможные варианты. Ключевые умозаключения выделены курсивом.

Шаг 1

По условию норвежец живёт в первом доме (10). Не имеет значения откуда — слева или справа — ведётся нумерация. Нас интересует только порядок домов, а не направление, в котором они нумеруются.

Из (10) и (15) следует, что второй дом синий. Какого цвета первый дом? Не зелёный и не белый, потому что они должны стоять рядом (это следует из 6-й посылки и того, что 2-й дом синий). Не красный, потому что там живёт англичанин.

Какого цвета первый дом? Он не может быть ни зелёным, ни белым, ведь дома этих двух цветов должны располагаться рядом (3). Красным он тоже не может быть, потому что в красном доме живёт англичанин (2). Поэтому первый дом жёлтый.

Из этого следует, что в первом доме курят Kools (8), а во втором доме держат лошадь (12).

Что пьёт норвежец, который живёт в первом, жёлтом доме и курит Kools? Это не чай, поскольку чай пьёт украинец (5). И не кофе, потому что кофе пьют в зелёном доме (4). И не молоко, которое пьют в третьем доме (9). И не апельсиновый сок, потому что человек, который пьёт сок, курит Lucky Strike (13). Следовательно, норвежец пьёт воду, и это ответ на первый вопрос загадки.

дом	1	2	3	4	5
цвет	жёлтый	синий	?	?	?
национальность	норвежец	?	?	?	?
напиток	вода	?	молоко	?	?
сигареты	Kools	?	?	?	?
животное	?	лошадь	?	?	?

Шаг 2

Тогда что же курят во втором, синем доме, где, как мы знаем, держат лошадь?

Это не Kools, который курят в первом доме (8). И не Old Gold, поскольку тот, кто их курит, разводит улиток (7).

Предположим, что в нём курят Lucky Strikes, что означает, что здесь же пьют апельсиновый сок (13). В таком случае, кто может здесь жить? Это не норвежец — он живёт в первом доме (10). Не англичанин — его дом красный (2). Не испанец, поскольку испанец держит собаку (3). Не украинец, потому что украинец пьёт чай (5). И не японец, который курит Parliament (14). Так как данная ситуация невозможна, то во втором доме курят не Lucky Strike.

Предположим, что во втором доме курят Parliament, из чего следует, что здесь живёт японец (14). В таком случае, что он пьёт? Не чай, поскольку чай пьёт украинец (5). Не кофе — кофе пьют в зелёном доме (4). Не молоко — молоко пьют в третьем доме (9). И не сок, потому что сок пьёт человек, который курит Lucky Strike (13). Итак, данная ситуация также невозможна, и во втором доме курят не Parliament.

Следовательно, во втором доме курят Chesterfield.

Какой национальности человек, живущий во втором, синем доме, предпочитающий Chesterfield и держащий лошадь? Это не норвежец — он в первом доме (10). Не англичанин — он в красном доме (2). Не испанец — у испанца собака (3). Не японец — японец курит Parliament (14). Значит, во втором доме живёт украинец и, как следует из (5), пьёт чай!

дом	1	2	3	4	5
цвет	жёлтый	синий	?	?	?
национальность	норвежец	украинец	?	?	?
напиток	вода	чай	молоко	?	?
сигареты	Kools	Chesterfield	?	?	?
животное	?	лошадь	?	?	?

Шаг 3

Так как Chesterfield курят во втором доме, то из (11) нам становится известно, что лису держат либо в первом, либо в третьем доме.

Давайте сначала предположим, что лиса в третьем доме. В таком случае, что пьёт человек, который курит Old Gold и разводит улиток (7)? Мы уже исключили воду и чай на предыдущих шагах. Он также не может пить сок, поскольку сок пьёт человек, который курит Lucky Strike (13). Молоко тоже не подходит — его пьют в третьем доме (9), где, как мы предположили, держат лису. Остаётся кофе, который, по условию, пьют в зелёном доме (4).

Итак, если в третьем доме держат лису, то в зелёном доме живёт человек, который курит Old Gold, разводит улиток и пьёт кофе,. Кто этот человек? Он не норвежец — норвежец в первом доме (10). Не украинец — тот пьёт чай (5). Не англичанин — тот живёт в красном доме (2). Не японец — он курит Parliament (14). И не испанец — у испанца собака (3).

Такая ситуация невозможна. Из чего следует, что лису держат в первом доме, а не в третьем.

дом	1	2	3	4	5
цвет	жёлтый	синий	?	?	?
национальность	норвежец	украинец	?	?	?
напиток	вода	чай	молоко	?	?
сигареты	Kools	Chesterfield	?	?	?
животное	лиса	лошадь	?	?	?

Шаг 4

Из всего вышеизложенного следует, что кофе и апельсиновый сок пьют в четвёртом и пятом доме. Не имеет значения, какой из напитков — в каком доме; будем просто называть их «дом, где пьют сок» и «дом, где пьют кофе».

Итак, где живёт человек, который курит Old Gold и разводит улиток? Не в доме, где пьют сок, потому что там курят Lucky Strike (13).

Предположим, что он живёт в доме, где пьют кофе. Тогда человек, который курит Old Gold, разводит улиток и пьёт кофе, живёт в зелёном (4) доме. Опять же, по тем же соображениям, что и в шаге 3, это невозможно.

Значит, человек, который курит Old Gold и разводит улиток, живёт в третьем доме.

дом	1	2	3	4	5
цвет	жёлтый	синий	?	?	?
национальность	норвежец	украинец	?	?	?
напиток	вода	чай	молоко	?	?
сигареты	Kools	Chesterfield	Old Gold	?	?
животное	лиса	лошадь	улитки	?	?

Отсюда следует, что Parliament курят в зелёном доме, где пьют кофе, а живёт там японец (14). Это означает, что испанец — тот, кто пьёт апельсиновый сок, курит Lucky Strikes и держит собаку. Продолжая эти рассуждения, приходим к выводу, что англичанин должен жить в третьем доме, и дом этот — красный. Методом исключения получаем, что дом испанца белый.

дом	1	2	3	4	5
цвет	жёлтый	синий	красный	белый	зелёный
национальность	норвежец	украинец	англичанин	испанец	японец
напиток	вода	чай	молоко	сок	кофе
сигареты	Kools	Chesterfield	Old Gold	Lucky Strikes	Parliament
животное	лиса	лошадь	улитки	собака	?

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

Ответ

дом	1	2	3	4	5
цвет	жёлтый	синий	красный	белый	зелёный
национальность	норвежец	украинец	англичанин	испанец	японец
напиток	вода	чай	молоко	сок	кофе
сигареты	Kools	Chesterfield	Old Gold	Lucky Strikes	Parliament
животное	лиса	лошадь	улитки	собака	зебра

Замечание

В вышезложенном решении неявно предполагалось, что первый дом — крайний слева. Если предположить, что первый дом — крайний справа, получим немного другую ситуацию, но тот же ответ. Норвежец всё так же пьёт воду, а японец держит зебру.

дом	5	4	3	2	1
цвет	белый	зелёный	красный	синий	жёлтый
национальность	испанец	японец	англичанин	украинец	норвежец
напиток	сок	кофе	молоко	чай	вода
сигареты	Lucky Strikes	Parliament	Old Gold	Chesterfield	Kools
животное	собака	зебра	улитки	лошадь	лиса

Другие формулировки условия задачи

Существует множество различных вариантов условий задачи. В некоторых из них первая посылка оригинального условия оговаривается отдельно или подразумевается неявно, а вместо неё вводится другая, зачастую облегчающая решение задачи. Вместо двух вопросов нередко оставляют один, например, «Кто разводит рыбок?». Иногда вместо марок сигарет указывают средства передвижения или названия растений. Меняются и национальности пяти упоминающихся людей^[1]. Например, весьма распространённым в Интернете вариантом является следующий:

На одной улице подряд стоят пять домов, каждый — своего цвета. В каждом живёт человек, все пять — разных национальностей. Каждый человек предпочитает уникальную марку сигарет, напиток и домашнее животное. Кроме того:

1. Норвежец живёт в первом доме.
2. Англичанин живёт в красном доме.
3. Зелёный дом находится слева от белого, рядом с ним.
4. Датчанин пьёт чай.
5. Тот, кто курит Marlboro, живёт рядом с тем, кто выращивает кошек.
6. Тот, кто живёт в жёлтом доме, курит Dunhill.
7. Немец курит Rothmans.
8. Тот, кто живёт в центре, пьёт молоко.
9. Сосед того, кто курит Marlboro, пьёт воду.
10. Тот, кто курит Pall Mall, выращивает птиц.
11. Швед выращивает собак.
12. Норвежец живёт рядом с синим домом.
13. Тот, кто выращивает лошадей, живёт в синем доме.
14. Тот, кто курит Winfield, пьет пиво.
15. В зелёном доме пьют кофе.

Вопрос:

Кто разводит рыбок?

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

Примечания

1. ↑ ^{1 2} История загадки в Сети.
2. ↑ James Little, Cormac Gebruers, Derek Bridge, & Eugene Freuder Capturing Constraint Programming Experience: A Case-Based Approach (PDF). Cork Constraint Computation Centre, University College, Cork, Ireland. Архивировано из первоисточника 4 февраля 2012. Проверено 21 октября 2011.
3. ↑ Jeremy Stangroom Einstein's Riddle: Riddles, Paradoxes, and Conundrums to Stretch Your Mind. — Bloomsbury USA, 2009. — P. 10–11. — ISBN 978-1-59691-665-4
4. ↑ Life International, December 17, 1962, P. 95.

Ссылки

• История публикации загадки в Интернете и её распространения
• От Эйнштейна к Шерлоку Холмсу (дедуктивный метод поиска в базе данных)