Вчера на был на собеседовании, и мне задали вот такую логическую задачку.
Дано: 100 гномов, великан и лестница из 100 ступенек.
Великан хочет полакомиться гномами, начиная с верхнего или нижнего, перед этим надев на каждого белый или черный колпаки и расставив по ступенькам лестницы (по одному на ступеньку). Если гном угадает какого цвета на нем колпак — будет жить. Гном не знает колпак какого цвета у него на голове, но видит колпаки других гномов. Когда гном называет цвет, то это могут слышать другие гномы. Перед тем как стать на ступеньки и одеть колпаки они договорились о плане, который позволит выжить как минимум 99 гномам.
Каков план?
P.S. Готов предоставить необходимые уточнения по запросу =)
План по выживанию гномов:
Т.к. гномы могут сказать только одно слово — черный или белый, то они договариваются о следующей схеме. Первый гном считает количество черных и белых колпаков и называет цвет, количество колпаков которого, например, нечетное. Второй и последующие гномы теперь могут посчитать количество оставшихся белых и черных колпаков и узнать какой колпак на нем, посчитав оставшиеся количество черных и белых колпаков и отталкиваясь от ответа первого гнома.
Пример:
Например, из 100 гномов — 35 белых и 65 черных. Первый гном, например, в черном колпаке, говорит белый. Он будет съеден. Второй гном знает, что всего гномов 100, первый был черный и белых без учета первого нечетное количество, считает оставшихся гномов. Например, если белых оказывается нечетное количество (35) и черных — нечетное (63), следовательно он черный. Оставшие делают тоже самое и выживают.
Комментарии (33)
Неужели никто не может решить? =)
Какой цвет может назвать гном? Соседский? Видит всех или соседей?
Каждый гном видит колпаки остальных, но не видит свой. Назвать может только черный или белый, соседский тоже может.
А они не могут друг-другу перешептывать или каким-то знаком показывтьа черный или белый?
Ну в принципе, самое логичное — встать так, чтобы колпаки чередовались =)
«Перед тем как стать на ступеньки и одеть колпаки»
Кстати как это они не видят колпак на самом себе, если колпак еще не одет?
))
2 Werewolf:
в таком случае выживут все, а не только 99. Первый же видит, какой колпак стоит за ним.
to Snowbird: Значит, первый не имеет права оборачиваться и смотрит только в пасть Великану
2 Werewolf:
а такого не было в условиях! :р
to Snowbird: а вот этим кстати многие подобные задачи грешат — вспомни все ту же задачку про Ивашку, Кощея и йад
Гномы не знают в каком порядке чередуются цвета колпаков и сколько их вообще. Гномы видят все колпаки, кроме своего. Могут сказать только одно слово — черный или белый и их услышат все остальные гномы.
Сообщать информацию другими видами общения, например, перемигиваться, запрещено. Великан тогда всех съест! =)
Мама дорогая, во вас накрыло-то...
to goose: Есть решение? =)
А если гном называет цвет, он как-то идентифицируется? Или услышавшие его не могут сказать точно, кто именно говорил?
to Брат: Все видят какой гном назвал цвет. Можете для простоты считать, что гномов не 100, а, например, 10.
TO delta: Да откуда у меня может взяться решение то??? Я и условия задачи до конца дочитать не могу, не то, что решить... Полнейшая деградация и разложение.
Т.е. гномы тупо встают лицом к великану и по-очереди, начиная со второго, называют цвет колпака впередистоящего. Т.о. все они узнают, что у них на голове. Правда в таком раскладе уцелеют все гномы.
to delta: А разгадка-то будет?
to Брат: Гном не может называть цвет за кого-то. Великан знает, кто ему отвечает и будет есть или не есть именно того, кто ему ответил.
Подумаете еще или пора ответ говорить?
to delta: Я уже вполне созрела, чтоб услышать ответ
Я придумала!!!
Гномы должны говорить только черное или белое. Но не сказано ничего про то, каким голосом (тембром) они должны это говорить.
Они договариваются, что если у соседа, например, черный колпак, то гном произносит низким тембром, а если белый — высоким. Таким образом соседний гном узнает, какого цвета у него колпак.
Получается, что все остальные, кроме первого, будут знать, что им говорить. А первый угадывает наобум.
Увы все основано на холодном расчете... Опубликовал ответ! =)
Хотел спросить, хотите ли вы будущем решать подобные интересные задачки?
to delta:
А мне кажется мое решение намного проще
)) Я бы не успела на месте гномов так быстро посчитать...
Да, я бы не прочь порешать еще, я люблю задачки на логику.
to delta: суть понятна, но от стеба в то же время удержатся не могу
Первый гном считает количество черных и белых колпаков и называет цвет, количество колпаков которого, например, нечетное.
Из 100 колпаков нечетное количество будет и у черных колпаков, и у белых. Как и четное, если оно будет четное
))
Так что по четности-нечетности определять первый цвет бесполезно
блин, тут какие тэги работают-то?..
to delta:
А ведь точно!
Если оин договорились, что первый называет, например, четное. А колпаков 40 черных и 60 белых. То какой колпак должен назвать гном?
А если договорились называть нечетное, а колпаков 45 черных и 55 белых?
Он может посчитать только 99 колпаков, про свой он ничего сказать не может.
Что-то после вчерашнего отжига я даже готовый ответ с трудом понял...
to Брат: Рассказал бы, где отжигал... Или это не для наших ушей?! =)
Это был официально разрешенный отжиг, но с секретной программой