Правитель собрал 1000 мудрецов своего тауна и говорит:
-Через три дня выстрою я всех друг за другом. Надену на каждого колпаки либо черный, либо белый, соотношение которых вы не знает. И поинтересуюсь у каждого цвет колпака его. Остается в живых тот кто правильно отгадает свой цвет. Начну с последнего, тот кто все колпаки видит перед собой, за исключением своего. Потом предпоследний, кто не видит своего колпака и последнего мудреца, но слышит его... и т.д. Закончу первым, кто никого не видит, но слышит всех.

Итак. Существует алгоритм, позволяющий погибнуть только одному мудрецу с вероятностью 50 %, и оставить в живых 999.

---

/ Сборник задач,  #162093  /

Первые решившие: пока никто (из 10 // осталось: 10)

Область: другое

Характер и уровень: Логические

было
Wolf решил тогда

Да уж больно давно это было. Много воды с тех пор утекло. Так что пусть снова будет.

а если взять 1001 мудреца?

да хоть миллион

a po4emu by poslednemu ne govorit' cvet predposlednego? s4itat' ne nuna

Гы... а сколько времени потребуется последнему, чтобы сосчитать все колпаки перед собой (кстати, сколько затылков он увидит? думаю, десяток), причём белые и чёрные отдельно, и не сбиться? и это в состоянии стресса? Не реально.

читайте внимательно условия задачи;
предидущий автор ответил правильно

Представленное решение задачи неверно. Поскольку неоговорено какое соотношение белых черных колпаков может быть, то первое же соотношение 1 к 999 и попытка применить "алгоритм" убъет практически всех мудрецов.

а подумать не пробовали?

Eсли под предыдущим автором имелся в виду guest Dima, то вы ошибаетесь.

Ключевое слово - четность. Так ведь?

ага, ну да, сорри...

Вот ведь черт! В тот самый момент, когда мое изложеное на ста страницах многоходовое решение, отнимающее у злосчастных мудрецов годы жизни на реализацию этого алгоритма было запощщено, ко мне и пришла мысль, что можно же ж решить все это намного проще! ;-)
Отсюда мораль - оформление предварительных результатов это благо, а вовсе не наоборот ;-)

Нужно говорить "черный-черный" если впереди тебя стоит черный колпак, и говорить просто "черный" если впереди тебя стоит белый. Им же можно говорить только свой цвет, вот они его и произнесут. А считать общее количество четных нечетных в такой ситуации может быть очень нервным занятием.

Алгоритм: Последний (первый которому зададут вопрос) должен сказать цвет колпака предпоследнего (умрет он или нет - мне лично безразлично. Мавр сделал свое дело - мавр может умереть). Каждый последующий мудрец, должен говорить свой_цвет если следующий в колпаке такого же как у него цвета, или не_не_свой_цвет если перед ним стоит мудрец в колпаке противоположного цвета. Например у предпоследнего (999й) черный колпак. Тогда последний сказав "черный" сообщает 999му цвет его колпака и либо умирает, либо нет. У 998 черный колпак. Тогда 999 говорит "черный" сообщая цвет колпака 998 и правильно называет свой цвет. У 997 белый колпак. В этом случае 998 говорит "не белый" ("не_не_черный") то есть "черный" и передавая меседж 997 верно называет цвет своего колпака. Если 996 в белом колпаке 997му нужно только отбросить частицу не в сообщении 998 т.е. сказать "белый" - называя цвет своего колпака и передавая информацию о цвете колпака 996. Если 996 в черном, 997 говорит "не черный" ("не_не_белый") и остается жив, верно назвав цвет своего колпака и передав необходимые сведения своему собрату по профессии. Вот и все. Позже попробую нарисовать, а то с этим языком - вся формализация к черту.

...ну да, формально, нужно добавить, что первому (последнему из списка приговоренных))) нужно сказать либо "черный" либо "белый" в зависимости от того, что сказал 2й

Низачет всем. Правильное решение и формулировка:
1. "соотношение которых вы не знает" -> процент белых/черных равномерно распр. 0-100%
2. распр. между мудрецами случайно.
Правильный вопрос:
Существует алгоритм, позволяющий погибнуть только одному мудрецу с вероятностью *не более* 50 %, и оставить в живых 999.
Первый подсчитывает соотношение б/ч и пытается угадать свой цвет как более частый, а далее все по упомянутому плану. Его средний шанс помереть - 25%. ~50% только в случае б/ч=0.5

C таким же успехом, можно угадывать свой цвет как менее частый - чем больше черных колпаков среди стоящих впереди тебя 999 мудрецов, тем больше вероятность того, что у тебя белый колпак. Очевидно, что если у 999 колпаки черные, то 1000, если он не дурак конечно, может быть с вероятностью равной 1 (!!!) говорить что на нем белый колпак.

Т.е. правильнее истолковывать 50% вероятность гибели 1000го как следствие того, что ему неизвестно распределение, и для него цвет его колпака - событие случайное.

И, честно говоря, я не понял почему "низачет". Насколько я могу видеть, мой алгоритм работает. Единственное слабое место которое я в нем нахожу - это необходимость говорить "не черный" или "не белый", вместе с тем, в условии не обговорено как они должны отвечать. Преимущества такого алгоритма - простота в использовании: вместо того, чтоб подсчитывать количество колпаков черного и белого цветов участники акции всего то должны говорить "цвет" если цвет колпака впередистоящего совпадает с их цветом и "не цвет" если не совпадает. Остальное получается автоматически. Требую лавровый венок с гравировкой и титановый стилос!

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

Хм...да я то, как раз, грешным делом подумал, что именно в нахождении неожиданного и главное простого решения, как раз и состоит красота таких задач. Ну да бог с ним - не работает значит не работает. Однако, в условии, в таком случае нужно было бы написать "Могут отвечать только черный или белый".

Что то задачка не простая подалась.

всетаки условие пожеще прописать надо. строго ли ответ чорный белый или допускаются модификации "не белый" "не черный", кроме того вопрос, когда казнят , сразу или после опроса всех?

Запостил решение. Единственное допущение четко не прописанное в условии - неправильно ответившего мудреца казнят незамедлительно, до того как спросят следующего.

На самом деле неважно когда его казнят. Более того, вероятнось выжить у него 50%. Но всех остальных он гарантированно спасает.

Решения размещаем с помощью кнопочки "ввести решение".

не очень понял в чем сложность, последний называет цвет впереди стоящего вот и все. Все кроме него свой цвет знают, а последний молится чтобы его цвет совпал с впередистоящим (фифти фифти)