Ещё одна загадка - отдельно.

[Мифическая личность]

А вот эту загадку я считаю жемчужиной коллекции. Те кто уже решал её - не подсказывайте и не смотрите ответ в инете. Загадка очень интересная. ))

100 колдунов

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

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

Услышав такую новость, колдуны собрались, и задумались, как им действовать, чтобы спасти наибольшее число своих коллег.

Сколько колдунов можно (со 100% вероятностью) спасти в таких условиях?

@темы: Загадки

Comments

[Nidhegg Anth]

Так то что на голове видеть они не могут, а то что рядом? Если так то 99. Ибо одному голову срубят по любом, значит у стоящего рядом есть возможность узнать цвет своего. То есть если голову первому таки оттяпали то у второго цвет колпака противоположен сказанному. и тыпы. Как то так.

[Nari Mortem]

Как спасти 50 со 100% гарантией - знаю.
Наверное, можно больше.

половину точно)

[Мифическая личность]

Ceallach O Callaghan
Колпаки надеты в произвольном порядке. Она видят только впередистоящих колдунов.
Как работает твой метод, если подробнее?

[Nidhegg Anth]

Мифическая личность Так все я понял, того кто неверно скажет цвет казнят, а остальных отпустят это в задаче. Ошибется первый, или второй но погибнет только один человек. остальных отпустят, уфф...

[Мифическая личность]

Ceallach O Callaghan
Там написано "тем", а нет "тот" или "одному". То есть - отрубят всем тем, кто ошибётся.

[Nidhegg Anth]

Мифическая личность Так. Дай подумать.

Мифическая личность Точно спасти можно от 50 (наугад) до 99 (если они умеют быстро считать, ситуация-то стрессовая)
Спасибо. Прикольная задача

.

Первый считает количество всех черных колпаков и договаривается с остальными, что, к примеру, если число нечетное-то он говорит чёрный, а если чётное-белый, таким образом следующий за ним сможет сам подсчитать количество черных колпаков и если у него результат совпадет с предыдущим, то на нём белый колпак, а если нет, то черный, последующие также считают черные колпаки и заодно отнимают уже названные предыдущими. Таким образом только первый будет угадывать, поэтому непонятно выживет ли?

[Радистка-Кэт]

полтину точно можно спасти)

[halfhant]

половину можно спасти со 100% вероятностью, но по факту получится больше. Мой алгоритм тут, кому хочется подумать - не смотрите) Условия: колпаки надеты в абсолютно случайном порядке, колдуны в процессе не могут как-либо обменяться инфой, кроме одного слова.
Первый колдун называет цвет колпака впередистоящего. Если у них одинаковые колпаки - то ему повезло) Второй гарантированно выживает. Третьему-снова лотерея, но четвертый спасается, и.т.д. Т.е. на больших числах средняя выживаемость равна 75%, абсолютный минимум - 50%

[Nari Mortem]

halfhant У меня тоже самое получалось.
Но у Nagual вариант круче.

[Мифическая личность]

Есть способ спасти 99 со 100% вероятностью. По моему, очень элегантное решение.

Nagual
Возьмём за утверждение, что они умеют быстро считать и весьма "хладнокровны".

Мифическая личность

По моему, очень элегантное решение

Да-да, здорово )))

[Bercut_bird]

В конец ряда ставим самых невероятно холоднокровных гениев счета, остальным будет легче

Bercut_bird Простите за флуд, но я рыдаю

В конец ряда ставим самых невероятно холоднокровных гениев счета, остальным будет легче

. Это действительно оччень элегантное решение. У меня так решение описать не получилось

[Bercut_bird]

Nagual Рациональное использование человеческого ресурса, хех.

[Мифическая личность]

Ответ

Выживают со 100% вероятностью 99 мудрецов.
1-ый колдун считает сумму по модулю 2 всех колпаков которые он видит(0-Чёрный 1-белый) в результате получается 0 или 1, что соответствует одному из цветов. Именно цвет и говорит колдун(условие не нарушается, он говорит только одно слово, "чёрный" или "белый").
2-ой колдун считает сумму по модулю 2 всех колпаков которые он видит перед собой(0-Чёрный 1-белый) в результате получается 0 или 1, что опять же соответствует одному из цветов. Он сравнивает получившийся результат с результатом который сказал 1 колдун.Если результат не изменился значит на нём чёрный колпак, если изменился,значит белый.
3-ий колдун прекрасно слышал что говорили первые два, из их слов он определяет сумму по модулю 2 всех оставшихся колпаков включая и его собственный. Дальше аналогично второму определяет цвет своего колпака.
Все остальные колдуны внимательно слушают ВСЁ что происходит сзади и действуют аналогично третьему.

Пусть черная шапка - 0, белая - 1. Последний называет четность "суммы шапок" всех кроме себя. Он умрет с вероятностью 1/2. Предпоследний считает "суммы шапок" всех впереди стоящих и знает "сумму шапок" впереди стоящих + свою. Он легко называет цвет своей шапки. При таком алгоритме действий гарантированно выживают 99 мудрецов. Стоящий в очереди последним, выживает с вероятность 0,5 (если считать, что вероятность выдачи черной и белой шапки одинакова).