еще одна задачка

[avva]

migmit:

Я не помню, где видел эту задачу, если здесь - звиняйте.
В тюрьме содержатся 100 узников. Однажды их собирают во дворе и объявляют, что проведут с ними испытание. Состоит оно в следующем. В одной из камер расставлены (можно считать, что в ряд) 100 ящиков. В каждый из них положена бумажка с именем одного из узников, причём в разные ящики - разные имена. Узников по одному будут заводить в эту камеру. В камере узник может открыть любые - какие захочет - 50 ящиков из 100. После этого его уведут и сразу отправят в его камеру, так что никакого обмена информацией со следующими не будет. Уходя, он должен оставить камеру точно в том же состоянии, в котором её нашёл - в частности, запрещено перекладывать бумажки, оставлять ящики открытыми и т.п. Узников выпустят, если КАЖДЫЙ из них найдёт бумажку со своим именем, в противном случае всех казнят. У них есть полчаса перед началом испытания, чтобы договориться. Как им следует действовать, чтобы вероятность выжить составила хотя бы 30%?

Не могу решить :(

Comments

[slonarch.livejournal.com]

И бумажку со своим именем он тоже оставляет в камере?

[avva.livejournal.com]

"Уходя, он должен оставить камеру точно в том же состоянии, в котором её нашёл", т.е. да.

[normal-homyak.livejournal.com]

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

[signamax.livejournal.com]

условие противоречивое
там нет вероятности выжить 30% поскольку по условию КАЖДЫЙ должен найти своё имя

как им решить чтобы каждый нашел - я не знаю
может пока
так что вероятность выше 0 не поднимается

[monomyth.livejournal.com]

Узников выпустят, если КАЖДЫЙ из них найдёт бумажку со своим именем, в противном случае всех казнят.

о каких 30% речь? Умрут все.

[signamax.livejournal.com]

условие может быть сведено к менее громоздкому
в комнате всего 2 ящика
один всегда пустой
а в другой кладут бумажку входящего
найдет ли он ее?

[monomyth.livejournal.com]

что он должен сделать перед входом, что бы найти бумажку с вероятностью в 30% :)

[signamax.livejournal.com]

он и так ее будет находить с вероятностью 40-60% или около того
или я не понял пафоса?

[signamax.livejournal.com]

а-а-а
теперь понял
вы просто повторили мой комент выше

[monomyth.livejournal.com]

я его увидел, но не прочитал...

[signamax.livejournal.com]

это мудро

[akor168.livejournal.com]

так что вероятность выше 0 не поднимается

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

[pivchanskiy.livejournal.com]

Каждый узник заходит в камеру и с некоторой долей вероятности находит своё имя. Перемножение этих вероятностей - общая вероятность того, что все узники найдут своё имя. Нужно, чтобы она была больше 30%.

Очевидно, что если все узники будут выбирать первые 50 ящиков, или будут выбирать ящики от балды - вероятности будут разные

[akor168.livejournal.com]

Но здесь то как раз все просто: первый открывает первый ящик, а второй - второй. С вероятностью 50% они выжили.

[akor168.livejournal.com]

Если все участники будут выбирать первые 50, то вероятность выжить - ноль. Необходимое условие - все сто яшиков должны быть открыты хотя бы по одному разу.

[pivchanskiy.livejournal.com]

Кстати, да :)
Самым простым кажется смещатсья на один ящик вправо, допустим, но математически никак это подтвердить не могу, и интутивно кажется, что это неправильно

[mura-vey.livejournal.com]

Ну почему 0, всего навсего (1/2)^100.

[akor168.livejournal.com]

Трудно сказать. Скорее всего, вероятность будет менше, иначе нет смысла задавать задачку. Я бы предложил скакать: первый выирает 50 слева, второй 50 справа. Третий 25 с каждого, четвертый делит свои 50 на три части, стараясь равномерно пересечься с предыдущими долями. Однако, какой бы метод не предложишь, надо считать вероятности.

[akor168.livejournal.com]

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

[anhinga-anhinga.livejournal.com]

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

Пусть тянут бумажки только два узника (100 имен, каждый смотрит на 50 ящиков). Если они не договариваются между собой, вероятность успеха 1/4. Оптимальный договор для них -- непересекающиеся множества ящиков, и веороятность успеха (1/2)*(50/99), то есть лишь чуть выше 1/4 и уже меньше 30%.

Если это предположение неверно, то кажется, что задача не вполне определена..

[yurilax.livejournal.com]

ну да, наверное, чтобы максимизировать общую вероятность, каждый ящик должен быть открыт 50 раз (т.е. 50-ю узниками). но даже в этом случае, я пока выше 0.5^100 вероятности не вижу.

[yurilax.livejournal.com]

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

из оригинальной формулировки, это условие не вытекает: могут всегда казнить в конце, по итогам.

[akor168.livejournal.com]

Вы зря перемножаете. Финальная вероятность считается гораздо сложнее. Надо использовать условную вероятность, но это очень муторно, значит должно быть красивое решение.

[slonarch.livejournal.com]

Думаю, решение задачи сводится к тому, где в условии наиболее вероятная ошибка :)

[yurilax.livejournal.com]

ага, мне кажется, у задачи что-то с формулировкой не то.