Войти в систему

Home
    - Создать дневник
    - Написать в дневник
       - Подробный режим

LJ.Rossia.org
    - Новости сайта
    - Общие настройки
    - Sitemap
    - Оплата
    - ljr-fif

Редактировать...
    - Настройки
    - Список друзей
    - Дневник
    - Картинки
    - Пароль
    - Вид дневника

Сообщества

Настроить S2

Помощь
    - Забыли пароль?
    - FAQ
    - Тех. поддержка



Пишет flaass ([info]flaass)
@ 2008-08-20 10:33:00


Previous Entry  Add to memories!  Tell a Friend!  Next Entry
Восток - дело тонкое
Султан вызвал своих сто мудрецов и велел каждому принести шкатулку, внутри которой - листочек с его именем. Шкатулки расставили в ряд, и султан объявил:
- Сейчас вы уйдете, а я переложу листки наугад (но в каждой шкатулке будет по одному листку). Завтра каждый из вас по по одному войдет в этот зал и найдет листок со своим именем. Разрешаю каждому для этого заглянуть не более, чем в 50 шкатулок. Запрещаю переставлять шкатулки, оставлять какие-то пометки и перекладывать листки. Прошедших испытание будут уводить в темницу, чтоб ничего не подсказали остальным. Если хоть один из вас не сможет найти свой листок - казню всех. А теперь идите думать.

Группа самых умных мудрецов сразу отошла в уголок решать задачу (протоколы их работы вот тут).
Другая группа стала обсуждать, рутинная ли это проверка, или козни врагов (и кого именно).
Третья группа занялась султаном: насколько он умен, есть ли у него сторонние советчики, что от него можно ожидать. Четвертая группа искала пути перехитрить правила.
Остальные пили чай и беседовали: нечасто удается собраться в неформальной обстановке такой хорошей компанией. Впрочем, некоторые из них тоже работали: не привлекая ничьего внимания, урывками и шепотом разрабатывали версию предателя среди мудрецов.

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

Когда испытание закончилось, мудрецы пали перед султаном ниц, восхваляя его мудрость и милосердие: каждый листок оказался на своем первоначальном месте.

Одного, впрочем, потом все-таки казнили: второпях он забыл написать на листке свое имя.


(Добавить комментарий)


[info]rezoner@lj
2008-08-20 02:33 (ссылка)
Хм.
Очевидно, что если бы султан хотел их казнить, у него бы это получилось: достаточно рандомизировать листки, и первый же с вероятностью 1/2 не найдет листок.

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

Думаем дальше.

(Ответить) (Ветвь дискуссии)


[info]rezoner@lj
2008-08-20 02:37 (ссылка)
Исходя из этого, мудрецы должны заходить в зал в том же порядке, в котором они изначально поставили шкатулки - иначе султан не мог бы гарантировать успеха, даже если бы они угадали алгоритм. Точнее, они должны были заходить в КАКОМ-ТО порядке, известном султану; любое изменение исходного порядка неоднозначно, и султан может ошибиться.

(Ответить) (Уровень выше) (Ветвь дискуссии)


[info]rezoner@lj
2008-08-20 02:46 (ссылка)
Далее, нельзя, чтобы все мудрецы открывали одни и те же шкатулки, тогда 50 из них ошибутся. Лучше всего, чтобы они начинали со сдвигом на 1 шкатулку.

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

В таком случае, султан должен, не меняя порядка, сдвинуть все 100 имен не более чем на 49 шкатулок в направлении счета.

Но направление счета он заранее не знает! Он не знает, с какого конца начнут мудрецы!

Если он и мудрецы выберут разное направление, всем абзац.

Поэтому правильно сдвинуть на 0. На 49 нельзя, потому что с другой стороны это будет 51-я шкатукла.

Итак, единственный вариант - всë оставить на месте.

(Ответить) (Уровень выше) (Ветвь дискуссии)


[info]flaass@lj
2008-08-20 02:49 (ссылка)
Вот и он так же подумал :)
Действительно, нельзя же просто так рисковать жизнью ста человек, даже если они полные идиоты.

(Ответить) (Уровень выше)


[info]some@lj
2008-08-20 11:47 (ссылка)
В начальном предложении задачи - двусмыслица: «листочек с его именем» читается как с «именем сулатана».
Надо было бы хоть «с именем владельца», что ли. Но, - поздно, да.
Хорошо, что (почти) все выжили
:)

(Ответить)


[info]9000@lj
2008-08-20 16:40 (ссылка)
Теперь ещё обработать известную задачу с пилотками двух цветов, осветив армейские нравы.

(Ответить) (Ветвь дискуссии)


[info]flaass@lj
2008-08-21 07:14 (ссылка)
Это, уже после, два мудреца обсуждают:
- Да, хорошо посидели, весело...
- Прям как в прошлый раз, когда он всех выстроил в черно-белых колпаках.
- Я тогда чуть не обсчитался. А первый и вовсе выжил чудом.
- Да какое там "чудом"! Все же знают, что у султана колпаков только 100, 50 белых и 50 черных.
- А султан наш - молодец. И где он только такую траву такие задачи берет?

(Ответить) (Уровень выше)