47 мудрецов замышляли государственный переворот. Царь их построил в колонну, одев каждому на голову колпак: белый или черный. Спрашивает последнего (который видит 46 предыдущих): "Какого цвета на тебе колпак?" Отвечает правильно - остается в живых, нет - его убивают. Потом спрашивают второго (он видит уже 45 предыдущих) и так далее. Мудрецы имеют право договориться о тактике ответов, причем царь (расположенный к ним явно недружелюбно) их подслушивает, и все это знают. Понятно, что жизнь первого мудреца зависит от везения. Понятно, что если первый мудрец видит перед собой много черных колпаков и мало белых, то он скажет "черный" и тем спасет хотя бы половину своих друзей - они все будут говорить "черный". Можно ли еще как-то минимизировать человеческие потери?
-
-
16.04.2008 в 17:44-
-
16.04.2008 в 17:51Изменять слова - нет...
-
-
16.04.2008 в 17:55Скажем, он может сказать сразу «черный», а может помолчать пару секунд, будто раздумывая, и потом произнести «черный». Для царя это будет один и тот же ответ, а мудрецы уловят паузу.
Если так можно, то спасутся все, кроме, возможно, первого.
-
-
16.04.2008 в 17:59-
-
16.04.2008 в 18:04Первый говорит цвет колпака того, который стоит перед ним.
Теперь цикл.
Очередной мудрец знает цвет своего колпака (если это второй мудрец — то он получил информацию от первого, если не второй — то дальше будет понятно, откуда).
Если у того, кто стоит перед ним, цвет такой же, то мудрец называет свой цвет без паузы. Стоящий впереди слышит быстрый ответ и понимает, что у него такой же цвет.
Если же у того, кто стоит перед ним, другой цвет, то мудрец называет свой цвет с паузой. При этом он остается в живых, а стоящий впереди понимает, что названный цвет не соответствует цвету его колпака.
Без пауз пока придумал только, как спасти примерно 47/2*(логарифм трех по основанию два) — то есть примерно в полтора раза больше половины.
А мудрецы знают, что произошло с тем, кто только что говорил: убили его или оставили в живых?
-
-
16.04.2008 в 18:19Нет, не знают. .
В оригинале задаче оставшиеся K мудрецов не знают, что произошло с (47-k) мудрецами. Если я не ошибаюсь, то опрошенные мудрецы не могут передавать информацию в колонну. По крайней мере оригинальное решение задание не используется связь от выбранных мудрецов колонне.
Так что вариант с паузами - это одна из трактовок... Попробуй решить задачу без пауз с учетом сказанного выше.
-
-
16.04.2008 в 18:291) произнести "черный";
2) произнести "белый";
3) промолчать.
Ткнуть впереди стоящего пяткой или произнести слово с другой интонацией он не может. Его товарищи воспринимают только эти три варианта.
Тогда можно так: если мудрец видит, что перед ним два мудреца с колпаками одного цвета, он называет этот цвет. Если колпаки разных цветов, то он молчит. Тогда двое следующих смогут выжить. То есть в худшем случае погибнет каждый третий мудрец.
-
-
16.04.2008 в 18:40Прошу прощения - считать мой предыдущий коммент недействительным.
Пишу уточнения.
-
-
16.04.2008 в 18:452) В колонне мудрецы видят впередистоящих, но не видят позади стоящиз
3) Впереди стоящие мудрецы слышат ответ очередного мудреца (и могут его запомнить)
4) Впередистоящие не могут узнать, что произошло в конечном итоге с позадистоящими мудрецами
Теперь точно.
-
-
16.04.2008 в 18:56Тогда так. Первые четыре мудреца своими ответами сигнализируют остальным о количестве черных колпаков у оставшихся 43 мудрецов. Сигнализируют так: ответ каждого мудреца рассматриваем как троичную цифру, троичное число из 4 цифр вполне может представить все числа от 0 до 43 (а если молчать нельзя, тогда шесть мудрецов передают остальным 41 количество черных колпаков с помощью двоичной системы).
Дальше проще: каждый мудрец знает, сколько всего черных колпаков; также он знает, сколько их было до него; и еще видит, сколько их осталось перед ним. То есть все остальные будут спасены.
-
-
16.04.2008 в 19:06-
-
16.04.2008 в 19:08-
-
16.04.2008 в 19:11И без применения молчания (хотя молчать ему не возбраняется по условию)
Все гораздо проще
-
-
16.04.2008 в 19:17Решение писать не буду — пусть другие подумают.)
Эх, рано мне перевороты замышлять)
-
-
16.04.2008 в 23:02>Первые четыре мудреца своими ответами сигнализируют остальным о количестве черных колпаков у оставшихся 43 мудрецов.
>Оригинальное решение спасло больше народу?
>Увы, да
То есть в решении гибнет меньше четырех человек?
-
-
16.04.2008 в 23:09-
-
16.04.2008 в 23:13гм... буду думать...
Disprein
до меня еще (?) не дошло, но твой ход решения просто высокий класс!!! )))
-
-
17.04.2008 в 05:54-
-
17.04.2008 в 09:39мне вчера казалось, что я додумалась, а сегодня не кажется уже (((
-
-
17.04.2008 в 10:04А вот если мудрецы отгадают цвета своих колпаков, то со стороны царя будет весьма неосмотрительно оставлять в живых таких хитрых мудрецов.)
-
-
17.04.2008 в 10:18хорошо глумиться, зная ответ)))
а у меня уже мозги набекрень )))
-
-
17.04.2008 в 11:10Решила!
Один бедолага пострадает!
Но что-то мозги со скрипом вертятся (((((((((
-
-
17.04.2008 в 13:52-
-
17.04.2008 в 14:14-
-
17.04.2008 в 16:26Amicus Plato
а может и не пострадает. как повезет...
-
-
17.04.2008 в 20:07-
-
17.04.2008 в 21:40решение-то простое... а вот допереть было непросто (((
Тем более я как зациклилась на решении Disprein'а, что кроме двоичных-троичных чисел мне вообще ничего в голову не лезло... ))))
***
А вообще у меня сразу тут этические вопросы ))) Ничего ведь не стоит переврать цвет! Тогда пропадет не один последний (т.е. первый), а все вместе (предыдущие-то не знают, что делается там сзади)... Хреново ведь одному за всех отдуваться...
-
-
17.04.2008 в 22:14в моем решении вероятность пострадать 50%....
-
-
17.04.2008 в 22:22это если не считать
добройзлой воли царя.Он же всех подслушивает, и наденет на первого специально не тот колпак.
(или у тебя не такой ответ)))
-
-
17.04.2008 в 22:33И цвет своего колпака он не знает.
А значит, на него можно надеть такой колпак, который не соответствует его ответу.
А вообще царь мог бы надеть на всех зеленые колпаки и потом истерически хохотать над каждым ответом)