Логическая задачка

// Ноябрь 18th, 2010 // Логические задачки

Тут товарищ задачку загадал. Было у великого султана 100 колдунов. Все они, конечно, были шарлатанами, и султан это заподозрил. Собрал он их и сказал:
— Завтра поутру устроим вам проверку, кто настоящий колдун, а кто нет. Проверка будет такой.

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

Стоя в ряду, каждый колдун видит всех, кто стоит перед ним, и слышит все, что происходит сзади. Цвет своего колпака никакими уловками никто узнать не может. Каждый колдун может сказать только одно слово — «черный» или «белый». И только в свою очередь. Иначе — всем хана.
Услышав такую новость, колдуны собрались, и задумались, как им действовать, чтобы спасти наибольшее число своих коллег.
Сколько колдунов можно со 100%-вероятностью спасти в таких условиях?

Пишите варианты в комментах.

Share

Спасибо!


Если вам помогла статья, или вы хотите поддержать мои исследования и блог - вот лучший способ сделать это:


16 Responses to “Логическая задачка”

    • google.com Андрей Токарчук:

      Да. Вчера как раз спорили за кружечкой чая. Можно спасти 99 колдунов со 100% верятностью и одного с 50%-ой. Пока знаю как можно спасти 75 колдунов со 100% вероятностью.

      • KickBack:

        Солюшен ф студию!

        • google.com Андрей Токарчук:

          А я пока не знаю :-)

          • KickBack:

            я готов выслушать и вариант на 75 колдунов

          • google.com Андрей Токарчук:

            Колдуны называют не свой цвет колпака, а цвет колпапка с начала очереди. В результате 50 колдунов с начала очереди выживут, т.к. будут знать свой цвет, а остальные имеют 50%-ную вероятность, т.е. по идее выживут еще 25 колдунов, у которых цвет собственного колпака совпадет с цветом колпака другого колдуна.

          • KickBack:

            Ответ не правильный. В задаче спрашивают сколько колдунов можно спасти со 100% вероятностью.

          • google.com Андрей Токарчук:

            Тогда 50.

  1. KickBack:

    Хорошая задачка.
    По моим прикидкам 50.

  2. Да, 99 + полмудреца.
    Есть задачка интереснее, решали её за обедами на работе.

    Было у султана счётное количество мудрецов, у каждого мудреца бесконечная память и безлимитный канал общения с другими мудрецами.
    Чем-то они провинились, не суть важно. Построил их султан с утра в цепочку лицом к бесконечному хвосту из мудрецов: первый видит всех, начиная со второго, второй — всех, начиная с третьего, и т.д. На каждом мудреце утром будет надет белый или чёрный колпак. Мудрец в колпаке ничего не слышит. Палач подходит к мудрецу, тот говорит цвет своего колпака, если не угадывает — голову с плеч.
    Мудрецы заранее про утро узнали, собрались и разработали стратегию.
    Вопрос: какой стратегии надо придерживаться мудрецам, чтобы погибло конечное (!) количество мудрецов?

    • jpchshc:

      Vitaly, не совсем понятно, у мудрецов безлимитный канал общения, или же они ничего не слышат? Или колпаки надевают не сразу всем, а по очереди?

  3. jpchshc:

    Те кто говорит про 99 со 100% и 1 с 50% — разъясните решение! Точно ли оно есть?

    У меня получается только как у всех 50 со 100%, остальные 50%.
    Есть еще вариант запоминать серии, как у рулетке. Но это уже не 100% вероятности, хотя в целом эффективность будет выше 50 спасеных человек. Можно накодить, проверить, но пока некогда.

  4. Они решают так:

    Путь Белый=0, черный=1.
    Последний назвает их сумму по модулю 2.
    Предпоследний, видя то что перед собой — если сумма соответствует тому что сказал последний — говорит «белый», иначе черный и т.д.

    Только они бредят.

    В условии четко сказано: Каждый колдун может сказать только одно слово — «черный» или «белый». И только в свою очередь.

    Не может последний колдун сказать модуль.

    Так что правильный ответ — 50

  5. Хотя нет.
    Вот так, и действительно 99.
    99 колдунов
    первый с конца считает четность белых колпаков и говорит белый, если четное, черный — если нечетное
    у него шансов выжить 50%
    зато у остальных 100%

  6. makcs:

    прямо динамическая маршрутизация какая-то…

  7. Markevich:

    Может я конечно не все правильно понял. Но у меня есть вероятность когда башка кердык более одного.
    предположим что шапочки надели так 00110000 то второго черного тоже обезглавят. Или я что то не так понял?

Комментировать