На лестнице стоят 4 человека. Самый верхний стоит на ступеньке, спрятанной за непроницаемой стеной и не видит никого. Все остальные видят только вышестоящих: A видит B и С, B видит C, С видит стену.
На каждом из человечков одета шляпа. На двоих красные шляпы, на других двоих черные. Кто из них первый поймет какого цвета у него шляпа, если никто не может ее снять и посмотреть?
Дополнительные условия: человечки не могут поворачиваться, не могут переговариваться и перемещаться по лестнице, так же они не могут блефовать и ломать стену.
ЗЫ: Выглядит это примерно так:
среда, 29 октября 2008 г.
Задача о шляпах от Microsoft
Подписаться на:
Комментарии к сообщению (Atom)
28 комментариев:
ну попробуем.
если задача от микрософта, то подсознательно жду подставы :)
если на B и C шляпы одинакового цвета, то A
иначе он может угадывать с вероятностью 1/2.
какова ценность чувака за стеной ?
Тю. Если на Б и С одинаковые, то А сразу говорит. Если нет, то А молчит и Б понимает что у них с С разные и сразу говорит
Плохой перевод. В задаче не сказано что ктото должен чтото вслух сказать. В задаче сказано "поймёт". А это слово означает обычно нечто происходящее молча
2Анонимный: это не перевод. но замечание правильное, ничего не сказано, как один из чувачков сообщит о своем озарении
2caezar: в точку! если у B и C разные цвета, A молчит, и B видит какой цвет у C, то ему должно стать все понятно. главное, как заметил, Анонимный, что бы чувачки издавали звуки
Ещё раз замечу что издавать звуки им запрещено по условиям задачи - так как это попадает под термин "переговариваться"
+1 анонимусу.
плюс они не могут договариваться заранее о плане угадывания.
Вариант - если помещение освещено то по отсвету на стене или светлой шляпе впереди стоящего довольно легко определить тёмная шляпа или светлая - тока что проверил с листом бумаги ; )
Также не запрещено закатывать вверх глаза и пытатся рассмотреть поля шляпы : )
Короче задачка бы была красивей будь она сформулирована так, чтоб не допускала хаков. Ну например в терминах програмных объектов с чётким интерфейсом через который попадает информация о окружении и через который объект однозначно ограничен в методах комуникации. Как результат испытуемого можно просить - напишите AI алгоритм определения цвета собственной шляпы для каждого объекта.
анонимус, при чем тут AI?
вам построить алгоритм клональной селекции или нейронную сеть ? не пишите бред...
зачем вам хаки? условие предельно простое.
условие простое, но его можно трактовать как библию :) например, "не могут переговариваться" с одной стороны может означать вообще не издавать звуки, с другой стороны может означать "не переговариваться только о цвете шляп".
такая неоднозначность, наличие множества хаков и возможная неполнота условия как раз и делают эту задачу интересной. насколько я понял, чувакам из микрософт важен в первую очередь не результат, а методы его достижения и им интересно слушать расуждения, уточняющие вопросы и т.д.
если бы все было предельно ясно, и основная сложность - закодить алгоритм, то это мало что скажет о человеке, исключительно его кодерские какчества.
я не знаю точного ответа, но думаю, что решение, предложенное caezar, правильное - все просто и без хаков :)
> зачем вам хаки? условие предельно простое.
Как уже было замечено, да простое, но не допускающее приведённого варианта решения при строгой трактовке. Помойму это очевидно.
Лично мне бы было на интервью довольно интересен сам факт того что человек будет пробовать искать хаки вне плоскости "математики" но и тем не менее стараясь выполнить условия задачи.
Ключевые слова "будет пробовать".
А не тушеваться из-за того, что его вариант посчитают недостаточно "взрослым" (на самом деле это ж очевидно, что закатив глаза можно элементарно увидеть цвет своей шляпы не снимая её ;)
2сашко
"Кто из них первый поймет" - "поймет" - не значит "скажет".
эта задача похожа с гномами и шляпами, что была на девелоперсах пару месяцев назад.
там тоже пипл на сотню камментов рассуждал, как должны были договариваться гномы.
ну нафига придумывать несуществующую легенду. есть данные, есть условия.
2очередной анонимус - а я бы не очень позитивно отнесся к соискателю, который начал бы выдумывать решение в стиле "а если первый гном перднет, а у жены второго критические дни..."
2анонимус - если у тебя на голове в роли шляпы - кипа, то закатывай что угодно, а увидеть ты вряд ли что сможешь.
почему в условии задачи нет ширины полей и угла обзора глаз человечка ?
"Кто из них первый поймет" - "поймет" - не значит "скажет"
но и не значит, что не скажет ;)
имхо такие задачи хотя бы примерно позволяют оценить, как человек может справиться с реальной задачей. в реальности не всегда встречаются задачи, в которых есть все данные и условия, поэтому решения в стиле решение в стиле "а если первый гном перднет, а у жены второго критические дни..." тоже имеют право на существование.
кстати, задачу про гномов на девелоперсах - нифиговые там баталии развернулись :)
Я когда в первый раз нанимался мне загадали 3 загадки из разряда почему канализационные люки круглые (в том числе и про люки). На все я практически мгновенно ответил, после чего последовал комент типа: "ну да, задачки известные", хотя я реально их слышал впервый раз - было чертовски обидно (хотя и взяли меня). Собеседуясь через 3 года второй раз, и услышав знакомую мне задачку на указатели (как узнать что в списке нет петель) я (весьма обрадовавшись) на всякий случай минут 10 повыпендривался чёта там рисуя на бумажке и придумывая всякие неправильные решения перед тем как сказать верное.
Вообще на самом деле о людях которые таки могут таки задачки решать довольно просто это понять просто пообщавшись с ними о их жизни и о том, что они уже в ней попробовали и сделали. Это свойство не появляется вдруг и обычно человек им много раз успевал воспользоваться перед тем как он пришол на собеседование. Это куда надёжнее чем загадки загадывать
>>>Ещё раз замечу что издавать звуки им запрещено по условиям задачи - так как это попадает под термин "переговариваться"
Им запрещено "переговариваться",но не запрещено 1 раз сказать их виденье правильного ответа. А фраза
"так же они не могут блефовать" означает что все-таки какой-то версии от них ждут
Ба, Саня, какие люди :)
О, Тимоха, ты? :)
А то :)
Я так понимаю, что никто из человечков самостоятельно угадать не может: либо A либо B.
Ну на фига нужен мистер D, который за стеной??
2Анонимный: самостоятельно может угадать только А, когда у В и С шляпы одинакового цвета.
2Andrey: с тремя чувачками задача бы сильно упрощалась: было бы 2 шляпы одного цвета и одна другого, в таком случае А всегда бы знал цвет своей шляпы, а В мог знать если у них с А шляпы одинакового цвета. ставить D не за стену не имеет смысла, тогда тоже все было бы ясно сразу. короче, наличие D делает задачу задачей :)
Отправить комментарий