Товарищ рассказал интересную задачку и был очень удивлен, что я ее не слышал.
Поймал людоед несколько гномов (количество в задаче не задается), и сказал, что завтра он всех выстроит в колонну один за другим и оденет всем на головы либо черную, либо белую шапку. Гномы будут стоять так, что каждый будет видеть шапки только тех, кто впереди (последний видит всех, кроме себя, а первый – никого). Свою собственную шапку гномы не видят. Количество черных и белых шапок произвольное (хоть все белые, хоть все черные). Далее людоед, начиная с последнего, будет каждого спрашивать, какая шапка у него на голове. Гном может ответить только одним из двух слов «черная» или «белая». Если ответ неверный, но гном съедается, иначе переходят к следующему. В процессе поедания все пока еще живые гномы слышат, что проиходит сзади, то есть хоть они и не видят товарищей сзади, но слышат – когда кого съели, а кого нет, и также их ответы.
В общем, за ночь гномы покумекали, и придумали стратегию, как они все останутся живыми кроме одного. Но и тот один будет иметь шанс выжить.
Вопрос: что за стратегию придумали гномы?
Задача имеет очень красивое решение, имеющее прямое отношение к компьютерной науке.
Ответ будет позже, если кто вдруг не догадается.
среда, 7 апреля 2010 г.
Подписаться на:
Комментарии к сообщению (Atom)
Сообщения
Знаю эту задачку. Весьма хорошая.
ОтветитьУдалитьГода полтора назад услышал её.
Только шапочки были синие и красные у мя.
Подсказка: решается творчески))
Тоже слышал порядка 2 лет назад, но в моей интерпретации фигурировали мудрец в колпаках. К своему стыду, самостоятельно не смог ничего придумать (хотя логические и программистские задачки обожаю). Решили вдвоем со знакомой, причем способом, отличным от варианта загадавшего (у него гарантированно выживало не N-1, а меньше, так что его собственный вариант будем считать неправильным :))
ОтветитьУдалитьOpenID - дурак (предыдущий комментарий мой)
ОтветитьУдалитьТак как я эту задачку раньше не знал и решал сам (не подглядывая в гугл), рискну предложить свой ответ: последний гном сообщает остальным чётность числа переходов от одного цвета к другому в колонне впереди стоящих. Говорит «белая» если число переходов нечётное и «чёрная» если чётное.
ОтветитьУдалитьПочему-то первой ассоциацией из компьютерного мира были RAID-массивы дисков.
Задачу не видел, но решение само собой напрашивается.
ОтветитьУдалитьПоследний говорит: «чёрная», если черных шапок перед ним нечётное количество, и «белая», если чётное.
А остальные, раз уж видят, кто впереди, делают расчёт.
P.S. Последнего жалко…
Хороша задачка. Есть, кстати, её интересное усложнение — гномов бесконечное количество и нужно придумать решение, при котором умирает конечное число гномов. Ответ не скажу ;)
ОтветитьУдалитьМой вариант такой, гном у которого спрашивают называет цвет стоящего перед ним гнома. Таким образом все кроме того что будут жрать первым - выживут. Первый - как повезет.
ОтветитьУдалитьxander-prowler: А что будет, чем шапки будет через одну: черная, белая, черная, белая и т.д. Погибнет как минимум половина.
ОтветитьУдалитьчерт, написал не подумав, неправ
ОтветитьУдалитьИзвините, я не нашел как приложить файл со схемой к комментарию, поэтому решение опубликовал у себя в дневнике.
ОтветитьУдалитьВот оно: http://blog.zfilin.org.ua/2010/04/blog-post_08.html
Гномы сами решают как встать или их расставляет людоед в случайном порядке?
ОтветитьУдалитьЕвгений Коростелев: В данном случае - это не имеет значения, так как они все одинаковые, у них есть возможность договориться о стратегии и они слышат и частично видят процесс экзекуции.
ОтветитьУдалитьнадумалось следующее:
ОтветитьУдалитьпервый считает четность суммы единиц и называет ее: нечет - черный, чет - белый, остальные считают сколько было за ними и сколько они видят перед собой
Гном слушает, как говорит свой цвет его собрат сзади. Если тот говорит высоким голосом, подражая Леголасу, то белая, а если низким и сиплым, как у Дарта Вейдера, то чёрная. )
ОтветитьУдалитьпоследний говорит цвет впереди стоящего, а дальше, если цвет у текущего и впереди стоящего совпадает, то текущий называет свой цвет громко (кричит), иначе тихо (шепотом). не нужно ничего считать при бесконечном числе гномов и даже не обязательно видеть никого, кроме того, кто стоит перед тобой, и слышать нужно только того, кто стоит сзади. решение проще, чем решение с просчетом четности и подходит даже для бесконечного числа гномов.
ОтветитьУдалитьЕще вот задачка. Возможно, что баян, особонно для тех кто читал про гору фуджи.
ОтветитьУдалитьЕсть такая игра для двух человек. Вам дан стол, обычный такой стол, прямогугольный или круглый, не важно. Еще вам дано нерграниченное количество камней в виде блинчиков. Камни одинакового размера и формы. Вы и оппонент по очереди кладете камни на стол. Класть их можно только плашмя и только на свободную на поверхность стола (хотя, если подумать, это не важно :) ). Выигрывает тот, кто положит последний камень.
Ваш ход первый.
Вопрос: Как так ходить, чтобы выйграть?
Положить свой первый камень в геометрический центр стола.
ОтветитьУдалитьНу только этого не достаточно...
ОтветитьУдалитьПочему? Сходи в центр сначала, а затем ставь свои фишки симметрично фишкам противника односителько твоей центрально фишки.
ОтветитьУдалить