четверг, 3 марта 2011 г.

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

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

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

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

Вопрос:

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

Текст задачи скопирован со страницы по ссылке: http://ru.wikipedia.org/wiki/Загадка_Эйнштейна Там же можно почитать интересную историю её возникновения и посмотреть решение.

5 комментариев:

  1. Встретил эту задачку несколько лет назад и минут за 10 её решил (естественно, составлением таблички на бумаге). А ты хочешь сказать, что построил решение в уме? Сколько это заняло времени?

    Мне кажется, что при решении в уме, ты мысленно рисуешь себе ту же самую табличку. Конечно, это существенно сложнее, но думаю, что за неограниченное время, это сможет сделать каждый. Другой вопрос, что эффективность такого решения почти во всех случаях будет неоправданно низка.

    ОтветитьУдалить
  2. Виталий, да, я не использовал бумагу - только постоянно держал текст задачи перед глазами. Но я бы не стал говорить о существовании какого-то решения, для которого ещё можно оценивать эффективность, потому что, на мой взгляд, это чисто логическая задачка (т.е. требуется определить непротиворечивое распределение 15-ти утверждений по пяти позициям, а не разработать универсальный алгоритм решения этой задачи за минимальное число шагов на компьютере), и основная трудность при её решении в уме заключается в запоминании промежуточных результатов без использования бумаги с учётом того, что в ней целых пять параметров. Разумеется, тот факт, что время на её решение не ограничивается, сильно обнадёживало. Я думал над ней в несколько заходов с перерывами и суммарное время, конечно же, не засекал по часам, но, полагаю, что процесс занял у меня около трёх с половиной часов. По поводу идеи мысленно рисовать себе ту же самую табличку хочу сказать, что да - это, пожалуй, первое, что приходит в голову, но для случая таблицы 6х5, вероятно, нужна феноменальная зрительная память... по крайней мере, у меня так не получилось.

    Возвращаясь к решению, думаю, можно утверждать, что у всех, решивших эту задачку в уме, решение будет совпадать, потому что оно у всех будет логическое. Отличаться будет только подход, выбранный для запоминания промежуточных результатов. Разумеется, по окончании я сравнил ход своих размышлений с эталонным, и могу сказать, что на первом (начальном, в котором я отобрал и обработал 8 условий из 15-ти) этапе решения задачи он очень сильно его напоминает, а на втором (заключительном, в котором происходит перебор оставшихся условий и рассматриваются варианты логически непротиворечивого наложения их на частично заполненную в первом этапе таблицу) - отличается только порядком следования, но сами по себе рассуждения по отдельности точь в точь такие же, поскольку основаны на элементарной логике.

    ОтветитьУдалить
  3. Могу также сказать, что когда я читал официальное решение, моими первыми эмоциями было, что оно сложнее, и я не смог бы решить эту задачу так. Вероятно, это связано с тем, что в нём четыре шага - следовательно, их тяжелее удержать в памяти. Использованный же мной подход, по сути, состоит всего из двух этапов. Не стану утверждать, что на этом основании его следует признать более эффективным, но, очевидно, что он легче - раз уж с его помощью удалось решить эту задачу в уме. Думаю, в данном случае уместно даже привести аналогию с вычислительными машинами: полагаясь на избыточную мощь компьютера можно заложить в него даже самый неэффективный алгоритм решения несложной задачи, и он выдаст правильный результат за десятую долю секунды. Когда ты решаешь ту же задачу не на компьютере, а на бумаге, то твои возможности, очевидно, более ограничены и поэтому ты становишься более разборчив в средствах и тщательнее подбираешь алгоритм для решения той же задачи. Естественно, что при решении задачи в уме приходится быть ещё более изобретательным, поскольку ресурсов, находящихся в твоём распоряжении, остаётся ещё меньше :) Это я к тому, что твоё предположение: "эффективность такого решения почти во всех случаях будет неоправданно низка" (про эффективность решения, выбранного для решения задачи в уме, если я правильно тебя понял) может вполне оказаться верным, что называется, только с точностью до наоборот, хотя опять же смотря что конкретно подразумевать под словом "эффективность"... Ещё раз, но другими словами: используя менее эффективный алгоритм, чем тот, который использовался для решения этой задачи на бумаге, ты просто не решишь её в уме - вот что я имею в виду. В качестве поясняющего примера: (если речь, конечно, не идёт о человеке с выдающимися способностями в области памяти) для решения этой задачи в уме приходится дополнительно отбирать и группировать условия по определённым признакам, с целью облегчения запоминания, в то время как при решении на бумаге можно не заморачиваться и брать условия и заносить их в таблице в относительно более свободном порядке. Таким образом, при решении задачи в уме возникает необходимость в выявлении дополнительных закономерностей, скрытых в исходных условиях, а само решение при этом получается если не более эффективным (вначале надо определиться со значением этого термина), то уж точно более интеллектуальным по сравнению с решением той же задачи на бумаге. Сразу уточню, что под интеллектуальностью я подразумеваю способность решать задачи, алгоритм решения которых неизвестен (по крайней мере тому, кто решает). Ну и под неизвестностью алгоритма решения этой задачи имеется в виду невозможность ТОЧНОГО воспроизведения при решении в уме алгоритма её решения на бумаге. Разумеется, умственные возможности разных людей могут сильно отличаться, но мне кажется, что любому человеку при решении этой задачи в уме обязательно придётся внести определённые коррективы в бумажный алгоритм (с учётом своих индивидуальных особенностей), чтобы осилить её решение.

    В общем, Виталий, как говорится, лучше один раз попробовать, вместо того, чтобы участвовать в теоретических дискуссиях на ту же тему. Тем более, что, как ты говоришь, у тебя прошло уже несколько лет. Думаю, самое правильное в твоём случае - это взять и самому попробовать решить эту задачу в лоб и посмотреть, что из этой затеи получится. Сразу сам почувствуешь - в чём ты был прав, в чём быть может заблуждался. К чему напрасно философствовать? :) Думаю, тебе самому будет очень интересно посмотреть на результаты. Уверен, что адаптированное тобой решение обязательно будет в чём-то отличаться от моего.

    P.S. Чуть не забыл написать: фраза "за неограниченное время, это сможет сделать каждый" меня особенно порадовала :))) Спасибо за то, что высказал своё мнение!

    ОтветитьУдалить
  4. Я немного неправильно выразился. Понятно, что представлять себе в голове реальную разлинованную табличку довольно глупо, тем не менее, примерно так ты и хранишь текущий результат, просто информация разбита не на строки и столбцы, а на объекты со свойствами. Решение этой конкретной задачи в уме неэффективно с практической точки зрения, но, бесспорно, сам алгоритм решения при этом может быть вполне не хуже бумажного.

    * * *
    О.к., не освежая в памяти решение, я заново нашёл его в уме. Честно говоря, думал это займёт больше времени, но хватило 34 минут. Как потом оказалось, я упустил из вида пару взаимосвязей и шёл не по оптимальному пути. Возможно, кто-то может решить эту задачу минуты за две - видимо, такие люди реально гении, видящие чёткую связь между взмахом крыла бабочки и ураганом в Тихом океане.

    ОтветитьУдалить
  5. Вчера совершенно случайно узнал по Радио России, что у Альберта Эйнштейна День рождения:
    http://ru.wikipedia.org/wiki/Альберт_Эйнштейн

    ОтветитьУдалить