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

[avva]

migmit:

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

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

Comments

[akor168.livejournal.com]

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

[migmit.livejournal.com]

Кстати - вполне себе начало правильного решения.

[akor168.livejournal.com]

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

[akor168.livejournal.com]

Смотри-ка. Я таки догадался сам, правда с твоего намека. Однако, я с самого начала мыслил в терминах S_n - специальное образование все-таки помогает. Тем не менее, пойду возьму с полки пирожок - для себя я нажожусь в очень неплохой форме.

[migmit.livejournal.com]

Крут. Однозначно.
Я, кстати, не догадался. Правда, я и не решал особо сильно: ко мне задача попала в комплекте с решением.