Вход Регистрация Забыли пароль?
Виктор Кузнецов

Сто гномов и великан

от delta

Вчера на был на собеседовании, и мне задали вот такую логическую задачку.

Дано: 100 гномов, великан и лестница из 100 ступенек.

Великан хочет полакомиться гномами, начиная с верхнего или нижнего, перед этим надев на каждого белый или черный колпаки и расставив по ступенькам лестницы (по одному на ступеньку). Если гном угадает какого цвета на нем колпак — будет жить. Гном не знает колпак какого цвета у него на голове, но видит колпаки других гномов. Когда гном называет цвет, то это могут слышать другие гномы. Перед тем как стать на ступеньки и одеть колпаки они договорились о плане, который позволит выжить как минимум 99 гномам.

Каков план?

P.S. Готов предоставить необходимые уточнения по запросу =)

План по выживанию гномов:

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

Пример:

Например, из 100 гномов — 35 белых и 65 черных. Первый гном, например, в черном колпаке, говорит белый. Он будет съеден. Второй гном знает, что всего гномов 100, первый был черный и белых без учета первого нечетное количество, считает оставшихся гномов. Например, если белых оказывается нечетное количество (35) и черных — нечетное (63), следовательно он черный. Оставшие делают тоже самое и выживают.

 
Последнее обновление — 30 Март 2009 г. в 23:11
Рубрики — Без рубрики
Back to the future.. Плановое обновление

Комментарии (33)

Виктор Кузнецов

Неужели никто не может решить? =)

26 Март 2009 г. в 21:00 | Ответить | Постоянная ссылка
Брат

Какой цвет может назвать гном? Соседский? Видит всех или соседей?

26 Март 2009 г. в 23:26 | Ответить | Постоянная ссылка
Виктор Кузнецов

Каждый гном видит колпаки остальных, но не видит свой. Назвать может только черный или белый, соседский тоже может.

26 Март 2009 г. в 23:56 | Ответить | Постоянная ссылка
Snowbird

А они не могут друг-другу перешептывать или каким-то знаком показывтьа черный или белый?

28 Март 2009 г. в 00:26 | Ответить | Постоянная ссылка
Алексей Иванов

Ну в принципе, самое логичное — встать так, чтобы колпаки чередовались =)

28 Март 2009 г. в 00:36 | Ответить | Постоянная ссылка
Алексей Иванов

«Перед тем как стать на ступеньки и одеть колпаки»

Кстати как это они не видят колпак на самом себе, если колпак еще не одет? ;) ))

28 Март 2009 г. в 00:38 | Ответить | Постоянная ссылка
Snowbird

2 Werewolf:

в таком случае выживут все, а не только 99. Первый же видит, какой колпак стоит за ним.

28 Март 2009 г. в 00:38 | Ответить | Постоянная ссылка
Алексей Иванов

to Snowbird: Значит, первый не имеет права оборачиваться и смотрит только в пасть Великану :)

28 Март 2009 г. в 00:39 | Ответить | Постоянная ссылка
Snowbird

2 Werewolf:

а такого не было в условиях! :р

28 Март 2009 г. в 00:43 | Ответить | Постоянная ссылка
Алексей Иванов

to Snowbird: а вот этим кстати многие подобные задачи грешат — вспомни все ту же задачку про Ивашку, Кощея и йад :)

28 Март 2009 г. в 00:44 | Ответить | Постоянная ссылка
Виктор Кузнецов

Гномы не знают в каком порядке чередуются цвета колпаков и сколько их вообще. Гномы видят все колпаки, кроме своего. Могут сказать только одно слово — черный или белый и их услышат все остальные гномы.

28 Март 2009 г. в 09:17 | Ответить | Постоянная ссылка
Виктор Кузнецов

Сообщать информацию другими видами общения, например, перемигиваться, запрещено. Великан тогда всех съест! =)

28 Март 2009 г. в 09:21 | Ответить | Постоянная ссылка
goose

Мама дорогая, во вас накрыло-то...

28 Март 2009 г. в 23:59 | Ответить | Постоянная ссылка
Виктор Кузнецов

to goose: Есть решение? =)

29 Март 2009 г. в 00:01 | Ответить | Постоянная ссылка
Брат

А если гном называет цвет, он как-то идентифицируется? Или услышавшие его не могут сказать точно, кто именно говорил?

29 Март 2009 г. в 00:23 | Ответить | Постоянная ссылка
Виктор Кузнецов

to Брат: Все видят какой гном назвал цвет. Можете для простоты считать, что гномов не 100, а, например, 10.

29 Март 2009 г. в 09:49 | Ответить | Постоянная ссылка
goose

TO delta: Да откуда у меня может взяться решение то??? Я и условия задачи до конца дочитать не могу, не то, что решить... Полнейшая деградация и разложение.

29 Март 2009 г. в 13:21 | Ответить | Постоянная ссылка
Брат

Т.е. гномы тупо встают лицом к великану и по-очереди, начиная со второго, называют цвет колпака впередистоящего. Т.о. все они узнают, что у них на голове. Правда в таком раскладе уцелеют все гномы.

30 Март 2009 г. в 12:59 | Ответить | Постоянная ссылка
Snowbird

to delta: А разгадка-то будет? :)

30 Март 2009 г. в 15:00 | Ответить | Постоянная ссылка
Виктор Кузнецов

to Брат: Гном не может называть цвет за кого-то. Великан знает, кто ему отвечает и будет есть или не есть именно того, кто ему ответил.

30 Март 2009 г. в 16:00 | Ответить | Постоянная ссылка
Виктор Кузнецов

Подумаете еще или пора ответ говорить?

30 Март 2009 г. в 16:01 | Ответить | Постоянная ссылка
Snowbird

to delta: Я уже вполне созрела, чтоб услышать ответ :)

30 Март 2009 г. в 17:02 | Ответить | Постоянная ссылка
Snowbird

Я придумала!!!

Гномы должны говорить только черное или белое. Но не сказано ничего про то, каким голосом (тембром) они должны это говорить.

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

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

30 Март 2009 г. в 23:04 | Ответить | Постоянная ссылка
Виктор Кузнецов

Увы все основано на холодном расчете... Опубликовал ответ! =)

30 Март 2009 г. в 23:12 | Ответить | Постоянная ссылка
Виктор Кузнецов

Хотел спросить, хотите ли вы будущем решать подобные интересные задачки?

30 Март 2009 г. в 23:29 | Ответить | Постоянная ссылка
Snowbird

to delta:

А мне кажется мое решение намного проще :) )) Я бы не успела на месте гномов так быстро посчитать...

Да, я бы не прочь порешать еще, я люблю задачки на логику.

31 Март 2009 г. в 00:26 | Ответить | Постоянная ссылка
Алексей Иванов

to delta: суть понятна, но от стеба в то же время удержатся не могу :)

Первый гном считает количество черных и белых колпаков и называет цвет, количество колпаков которого, например, нечетное.

Из 100 колпаков нечетное количество будет и у черных колпаков, и у белых. Как и четное, если оно будет четное :) ))

Так что по четности-нечетности определять первый цвет бесполезно :)

31 Март 2009 г. в 00:38 | Ответить | Постоянная ссылка
Алексей Иванов

блин, тут какие тэги работают-то?.. :)

31 Март 2009 г. в 00:39 | Ответить | Постоянная ссылка
Snowbird

to delta:

А ведь точно!

Если оин договорились, что первый называет, например, четное. А колпаков 40 черных и 60 белых. То какой колпак должен назвать гном?

А если договорились называть нечетное, а колпаков 45 черных и 55 белых?

31 Март 2009 г. в 00:49 | Ответить | Постоянная ссылка
Виктор Кузнецов

Он может посчитать только 99 колпаков, про свой он ничего сказать не может.

31 Март 2009 г. в 00:55 | Ответить | Постоянная ссылка
Брат

Что-то после вчерашнего отжига я даже готовый ответ с трудом понял...

1 Апрель 2009 г. в 12:30 | Ответить | Постоянная ссылка
Виктор Кузнецов

to Брат: Рассказал бы, где отжигал... Или это не для наших ушей?! =)

4 Апрель 2009 г. в 22:58 | Ответить | Постоянная ссылка
Брат

Это был официально разрешенный отжиг, но с секретной программой :)

6 Апрель 2009 г. в 14:24 | Ответить | Постоянная ссылка

Добавить комментарий