*** ВНИМАНИЕ: Блог переехал на другой адрес - demin.ws ***

среда, 7 апреля 2010 г.

Задача про гномов

Товарищ рассказал интересную задачку и был очень удивлен, что я ее не слышал.

Поймал людоед несколько гномов (количество в задаче не задается), и сказал, что завтра он всех выстроит в колонну один за другим и оденет всем на головы либо черную, либо белую шапку. Гномы будут стоять так, что каждый будет видеть шапки только тех, кто впереди (последний видит всех, кроме себя, а первый – никого). Свою собственную шапку гномы не видят. Количество черных и белых шапок произвольное (хоть все белые, хоть все черные). Далее людоед, начиная с последнего, будет каждого спрашивать, какая шапка у него на голове. Гном может ответить только одним из двух слов «черная» или «белая». Если ответ неверный, но гном съедается, иначе переходят к следующему. В процессе поедания все пока еще живые гномы слышат, что проиходит сзади, то есть хоть они и не видят товарищей сзади, но слышат – когда кого съели, а кого нет, и также их ответы.

В общем, за ночь гномы покумекали, и придумали стратегию, как они все останутся живыми кроме одного. Но и тот один будет иметь шанс выжить.

Вопрос: что за стратегию придумали гномы?

Задача имеет очень красивое решение, имеющее прямое отношение к компьютерной науке.

Ответ будет позже, если кто вдруг не догадается.

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

  1. Знаю эту задачку. Весьма хорошая.
    Года полтора назад услышал её.
    Только шапочки были синие и красные у мя.
    Подсказка: решается творчески))

    ОтветитьУдалить
  2. Тоже слышал порядка 2 лет назад, но в моей интерпретации фигурировали мудрец в колпаках. К своему стыду, самостоятельно не смог ничего придумать (хотя логические и программистские задачки обожаю). Решили вдвоем со знакомой, причем способом, отличным от варианта загадавшего (у него гарантированно выживало не N-1, а меньше, так что его собственный вариант будем считать неправильным :))

    ОтветитьУдалить
  3. OpenID - дурак (предыдущий комментарий мой)

    ОтветитьУдалить
  4. Так как я эту задачку раньше не знал и решал сам (не подглядывая в гугл), рискну предложить свой ответ: последний гном сообщает остальным чётность числа переходов от одного цвета к другому в колонне впереди стоящих. Говорит «белая» если число переходов нечётное и «чёрная» если чётное.

    Почему-то первой ассоциацией из компьютерного мира были RAID-массивы дисков.

    ОтветитьУдалить
  5. Задачу не видел, но решение само собой напрашивается.

    Последний говорит: «чёрная», если черных шапок перед ним нечётное количество, и «белая», если чётное.

    А остальные, раз уж видят, кто впереди, делают расчёт.

    P.S. Последнего жалко…

    ОтветитьУдалить
  6. Хороша задачка. Есть, кстати, её интересное усложнение — гномов бесконечное количество и нужно придумать решение, при котором умирает конечное число гномов. Ответ не скажу ;)

    ОтветитьУдалить
  7. Мой вариант такой, гном у которого спрашивают называет цвет стоящего перед ним гнома. Таким образом все кроме того что будут жрать первым - выживут. Первый - как повезет.

    ОтветитьУдалить
  8. xander-prowler: А что будет, чем шапки будет через одну: черная, белая, черная, белая и т.д. Погибнет как минимум половина.

    ОтветитьУдалить
  9. черт, написал не подумав, неправ

    ОтветитьУдалить
  10. Извините, я не нашел как приложить файл со схемой к комментарию, поэтому решение опубликовал у себя в дневнике.
    Вот оно: http://blog.zfilin.org.ua/2010/04/blog-post_08.html

    ОтветитьУдалить
  11. Гномы сами решают как встать или их расставляет людоед в случайном порядке?

    ОтветитьУдалить
  12. Евгений Коростелев: В данном случае - это не имеет значения, так как они все одинаковые, у них есть возможность договориться о стратегии и они слышат и частично видят процесс экзекуции.

    ОтветитьУдалить
  13. надумалось следующее:
    первый считает четность суммы единиц и называет ее: нечет - черный, чет - белый, остальные считают сколько было за ними и сколько они видят перед собой

    ОтветитьУдалить
  14. Гном слушает, как говорит свой цвет его собрат сзади. Если тот говорит высоким голосом, подражая Леголасу, то белая, а если низким и сиплым, как у Дарта Вейдера, то чёрная. )

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

    ОтветитьУдалить
  16. Еще вот задачка. Возможно, что баян, особонно для тех кто читал про гору фуджи.

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

    Вопрос: Как так ходить, чтобы выйграть?

    ОтветитьУдалить
  17. Положить свой первый камень в геометрический центр стола.

    ОтветитьУдалить
  18. Ну только этого не достаточно...

    ОтветитьУдалить
  19. Почему? Сходи в центр сначала, а затем ставь свои фишки симметрично фишкам противника односителько твоей центрально фишки.

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