?

Log in

No account? Create an account

Previous Entry | Next Entry

Уважаемые френды, большая просьба -- не надо искать ответы в интернете и публиковать их в комментариях. Я понимаю, что в инете ответ на эту задачку есть. Но если Вы не сумели решить её сами и нашли ответ в инете, то оставьте его пожалуйста при себе. Здесь просьба публиковать только СОБСТВЕНОРУЧНО ПОЛУЧЕННЫЕ ответы. Большое спасибо...

Задача про заключенных и коробки

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

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

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

Оставлять какие бы то ни было знаки в комнате с коробками нельзя, тюремщик строго за этим следит. Предложите оптимальную стратегию перебора коробок.
promo torin_kr december 5, 2015 19:43 26
Buy for 200 tokens
Этот пост -- заказной. Меня его попросила написать одна моя хорошая знакомая, с которой мы знакомы такое количество лет. что аж страшно становится. Как говорит в таких случаях мой младший брат -- "Да ну нафиг. Столько и не живут". Живут... к сожалению. Ладно, это было лирическое…

Comments

( 17 comments — Leave a comment )
livejournal
Jul. 20th, 2014 05:33 pm (UTC)
ЗАДАЧКИ И ТЕСТЫ -- задача про заключенных и коробки
Пользователь artistbabochkin сослался на вашу запись в своей записи «ЗАДАЧКИ И ТЕСТЫ -- задача про заключенных и коробки» в контексте: [...] Оригинал взят у в ЗАДАЧКИ И ТЕСТЫ -- задача про заключенных и коробки [...]
shardon74
Jul. 20th, 2014 07:22 pm (UTC)
уточняющие вопросы:
отпустят только если все сто найдут свое имя?
Тюремщик знает имена заключенных?
коробки переставлять нельзя?
заключенные видят кого заводят?
заключенные знают результат перед ними, нашел или нет предедущий свое имя?
torin_kr
Jul. 20th, 2014 08:23 pm (UTC)
Ответы:

1 -- да
2 -- да
3 -- нет
4 -- нет
5 -- нет

alexthunder
Jul. 20th, 2014 07:55 pm (UTC)
Если высех отпустят только если каждый найдёт своё имя, то договариваться неочем. Если первый сумеет найти, то каждый следующий будет иметь ровно теже, а значит достаточные, шансы. Если первый не найдёт своё имя, то второму и следующим можно уже и не пытаться - незачем.

О чём и зачем в такой ситуации договариваться?
torin_kr
Jul. 20th, 2014 08:25 pm (UTC)
Вот это самоочевидный ответ... И тем не менее он не верный. Вы мыслите в категориях случайных СОБЫТИЙ, а надо -- случайных процессов...

С решения этой задачки началась новая отрасль математики, которая сейчас называется "теория массового обслуживания"

Edited at 2014-07-20 08:29 pm (UTC)
alexthunder
Jul. 20th, 2014 08:30 pm (UTC)
Любите вы собеседников обсуждать. Нет чтобы обрушиться с критикой на собственно комментарий и указать что именно не так с логикой.

Поясните, уж если не трудно, как предварительное обсуждение увеличивает шансы на успех для первого игрока?
torin_kr
Jul. 20th, 2014 08:35 pm (UTC)
Ну извините, честное слово не хотел Вас обидеть. А по сути -- для одного игрока никак. А шансы ВСЕХ игроков -- увеличивает.

Понимаете (только не обижайтесь) Вы интуитивно исходите из того, что КАЖДЫЙ выбор -- это НЕЗАВИСИМОЕ СОБЫТИЕ и общая вероятность есть произведение всех вероятностей. А это не так... Просто Вы в свое время видимо очень хорошо учили классическую теорию вероятности, которая вся построена но понятии СЛУЧАЙНОГО СОБЫТИЯ. Но со времен Эйлера прошло немного времени и нынешняя математика оперирует уже ДРУГИМИ понятиями...
alexthunder
Jul. 20th, 2014 08:52 pm (UTC)
Вы не обижайтесь тоже пожалуйста, но вы понятия не имеете ис чего я исхожу интуитивно - вы это лишь предполагаете.

Я вот совсем недавно перездавал экзамен по бизнес-статистике в университете, так вот там как-то всё учили рассматривать реальные выборы и считать то что поддаётся счёту. Я пока из этого исхожу в рассуждениях, а не из интуиции. Так что давайте всёже о задаче будем говорить, а не обо мне и о вас, хорошо?

Если шансы первого игрока никак не увеличиваются, а судьба всех игроков зависит от успеха первого (по условиям задачи), то договорённость достигнутая между игроками имеет смысл лишь в отношении действий второго и следующих игроков. Если первый не угадывает - остальным можно в игру не вступать, нет смысла. Так? Если так, то успехов всей игры можно считать только последовательный выигрыш каждого из игроков. Как только любой не выигрывает - следующему незачем даже вступать в игру. Так? Если так, то вопрос о договорённостях между игроками сводится к выбору стратегии для ВТОРОГО игрока таким образом чтобы увеличить его шансы выигрыша в случае УСПЕХА первого. В случае неуспеха первого им договариваться неочем. Верно?

Если да, то договориться стоит лишь о том чтобы первый игрок отыскав свою коробочку просто отложил её в сторону от общей кучи так чтобы следующему оставить меньше шансов на неправильный выбор. Может быть ещё по мере накопления неудачных попыток сортировать открытые коробочки по алфавиту дабы следующий игрок не начинал перебор с самого начала. И всё. Методика же поиска для каждого игрока (кроме последнего) останется одинаковой и она будет в точности поддаваться предсказанию классической теорией вероятности.

Тем не менее, при любой стратегии остаётся вероятность того что первый же игрок окажется неудачником и все разом проиграют. Или второй. Или третий...
torin_kr
Jul. 20th, 2014 08:59 pm (UTC)
Ладно, не будем больше друг друга обсуждать. Давайте вернемся к условию задачки -- "предложите оптимальную стратегию перебора коробок". ОПТИМАЛЬНУЮ -- это вовсе не значит ГАРАНТИРУЮЩУЮ победу. Это всего лишь самую лучшую из всех возможных.

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

Edited at 2014-07-20 08:59 pm (UTC)
alexthunder
Jul. 20th, 2014 09:10 pm (UTC)
И логика Ваша неверна... Ну вот по принципу неверна.

Покажите в чём именно неверна. Опровергните мои утверждения. Укажите на ошибку.
torin_kr
Jul. 20th, 2014 09:20 pm (UTC)
Я уже ДВА раза это сделал. Могу еще раз повторить -- потому что ВЫ ОПЕРИРУЕТЕ НЕ ТЕМИ ПОНЯТИЯМИ. В данном случае НЕЛЬЗЯ рассматривать выборы отдельных заключенных как НЕЗАВИСИМЫЕ события.

Да, Вы правы в том, что ошибка первого заключенного означает неуспех всех, но это правота не имеет никакого значения -- потому что требуется не 100% победа, а стратегия, гарантирующая МАКСИМАЛЬНЫЕ ШАНСЫ. Проще говоря, надо предложить такую стратегию перебора коробок, в результате которой при 100 попытках хотя бы 30 будут удачными. И такая стратегия есть, но в рамках НЕЗАВИСИМОГО ПЕРЕБОРА ее увидеть невозможно...
fon_rotbar
Jul. 21st, 2014 04:28 am (UTC)
Если "отысканные" коробки остаются на своём месте- то и говорить не о чем.
torin_kr
Jul. 21st, 2014 04:29 am (UTC)
Вот как ни странно есть о чем...
a_spyd
Jul. 21st, 2014 08:53 am (UTC)
Вопрос от прокурорского надзора: не пропагандирует ли уважаемый автор поста так называемые "заблуждения Даламбера"?!
torin_kr
Jul. 21st, 2014 08:59 am (UTC)
Нет, "заблуждения Даламбера" тут ни при чем. Речь идет о так называемых "длинных циклах" в "теории массового обслуживания"...
shardon74
Jul. 23rd, 2014 03:41 pm (UTC)
Троин, дорогой, ответ где? Так не честно!
torin_kr
Jul. 23rd, 2014 06:51 pm (UTC)
Ок, завтра напишу ответ...
( 17 comments — Leave a comment )