| ||||
| ||||
|
![]() |
|
![]() ![]() |
#1 (permalink) |
Аксакал
Регистрация: 15.01.2006
Адрес: Питер
Сообщений: 2,211
|
Сегодня мне рассказали задачку, которая полностью изменила мое представление о комбинаторике и теории вероятности.
В тюрьме сидят 100 заключенных. У каждого заключенного есть свое уникальное имя. Имена всех 100 заключенных положили в 100 ящичков, по 1 в каждый ящик. Ящики расставили в линию в комнату, в которую по одному пускают заключенных. Каждый заключенный может посмотреть содержимое не более 50 ящиков. После этого он выходит из комнаты через другую дверь и никаким образом не может передать информацию еще не входившим в комнату заключенным. После того, как он выходит из комнаты, все содержимое комнаты приводится к ее изначальному состоянию. Если все 100 заключенных найдут свои имена, их выпустят. Если хотя бы один из 100 не найдет своего имени в своих 50 ящиках - всех казнят. Заключенные могут договорится между собой до похода первого из них в комнату о том, как они будут открывать ящики. Так вот, когда мой приятель сказал мне, что сущетсвует стратегия, при которой в >30% случаев их освободят, я, ес-но, не поверил. Когда я увидел решение, я прифигел - насколько оно простое. |
![]() |
![]() ![]() |
![]() |
#3 (permalink) |
Старожил
Регистрация: 27.10.2006
Сообщений: 752
|
У меня два варианта, один простой, второй немного математический (хоть бы они все умели считать
![]() 1. Четный смотрит первые 50, нечетный соответственно вторые 50. 2. Смотрится по два ящика с шагом в два ящика, а начинают смотреть ящик с того номера, которым по счету зашел заключенный (если дошел до конца, идет в начало). |
![]() |
![]() ![]() |
![]() ![]() |
#4 (permalink) | |
Аксакал
Регистрация: 15.01.2006
Адрес: Питер
Сообщений: 2,211
|
Цитата:
![]() Скажу честно, в формальном доказательстве присутствуют некоторые нетривиальные формулы, но в неформмальном виде, т.е. "на словах", оно (доказательство) очень простое. |
|
![]() |
![]() ![]() |
![]() |
#5 (permalink) |
Бессмертный
Регистрация: 13.02.2004
Адрес: Россия
Сообщений: 3,027
|
Давайте сначала для 2-х заключеных решим. Математическая вероятность 0.5*0.5=0.25. Как получить 0.3? Или открыть свое имя и найти его - не одно и тоже? После процедуры заключеные общаются? Если нет, то какая польза им от того что они договорятся как открывать ящики? Мне кажется что суть решения - найти подвох в условии.
|
![]() |
![]() ![]() |
![]() ![]() |
#6 (permalink) |
Аксакал
Регистрация: 15.01.2006
Адрес: Питер
Сообщений: 2,211
|
отредактировано
Тут было объяснение, почему для двоих вероятность не 0.25. Прочитав это объяснение понял, что оно является подсказкой и стер его. Подвоха в условии нет. Заключенные не могут общаться (в любых смыслах этого слова) с момента захода первого из них в комнату. |
![]() |
![]() ![]() |
![]() ![]() |
#8 (permalink) | |
Аксакал
Регистрация: 15.01.2006
Адрес: Питер
Сообщений: 2,211
|
Цитата:
|
|
![]() |
![]() ![]() |
![]() |
#9 (permalink) | |
Энтузиаст
Регистрация: 01.04.2004
Сообщений: 360
|
Цитата:
говорит об этом 2-му. С 50% он не угадает и их казнят. Если он попал, то второй смотрит ящик №2. P=0.5 Для более сложных моделей уже голова не варит, ибо 5 утра. |
|
![]() |
![]() ![]() |
![]() |
#11 (permalink) | |
Бессмертный
Регистрация: 13.02.2004
Адрес: Россия
Сообщений: 3,027
|
Цитата:
|
|
![]() |
![]() ![]() |
![]() ![]() |
#12 (permalink) | ||
Аксакал
Регистрация: 15.01.2006
Адрес: Питер
Сообщений: 2,211
|
Цитата:
Никакого подвоха нет. Собственно, Cardinal выше уже написал, почему в случае с двумя зэками P>0.3. |
||
![]() |
![]() ![]() |
![]() |
#13 (permalink) |
Бессмертный
|
заключенные заходят с часами и каждую минуту например смотрят по ящику. когда запускают следущего. то он знает в каком ящике нашел первый зек свое имя. в том ящике он смотреть не будет
![]() 1й зек найдет имя с вероятностью 50/100 2й уже 50/99 и т.д. думаю идея понятна верно? |
![]() |
![]() ![]() |
![]() ![]() |
#14 (permalink) | |
Аксакал
Регистрация: 15.01.2006
Адрес: Питер
Сообщений: 2,211
|
Цитата:
|
|
![]() |
![]() ![]() |
![]() |
#15 (permalink) | |||
Бессмертный
Регистрация: 13.02.2004
Адрес: Россия
Сообщений: 3,027
|
Цитата:
Цитата:
Цитата:
|
|||
![]() |
![]() ![]() |
![]() |
#16 (permalink) |
Увлечённый
|
Для простоты будем считать, что вместо имен у заключенных порядковые номера...
Договор такой: заключенный номер x идет смотреть ящик с номером x, затем ящик с порядковым номером, указанным в ящике x, и т.д. Для доказательства нужно рассмотреть множество всех подстановок на n (n=100) элементном множестве и выбрать из них только те подстановки, которые являются циклами длиной не более n/2 (т.е. 50) Edit: или разлагаются в произведение не более чем n/2 элементных независимых циклов |
![]() |
![]() ![]() |
![]() |
#17 (permalink) |
Увлечённый
|
Пример для n=4
1234=(1234) +++ 1243=(43) +++ 1324=(32) +++ 1342=(342) 1423=(432) 1432=(42) +++ 2134=(21) +++ 2143=(21)(43) +++ 2314=(231) 2341=(2341) 2413=(2431) 2431=(241) 3124=(321) 3142=(3421) 3214=(31) +++ 3241=(341) 3412=(31)(42) +++ 3421=(3241) 4123=(4321) 4132=(421) 4213=(431) 4231=(41) +++ 4312=(4231) 4321=(41)(32) +++ 10/24 ~ 0,42 Edit: остается вывести общую формулу для числа устраивающих нас подстановок. Число всех подстановок n! Как посчитать только устраивающие нас пока не соображу ![]() |
![]() |
![]() ![]() |
![]() |
#20 (permalink) | ||||
Увлечённый
|
Цитата:
Цитата:
Цитата:
Цитата:
|
||||
![]() |
![]() ![]() |
![]() |
||||
Тема | Автор | Раздел | Ответов | Последнее сообщение |
задача % 7кл. | Спортсмен | Поговорим за жизнь | 7 | 14.11.2009 14:58 |
задача | platon | Покер один на один | 3 | 02.09.2008 10:00 |
Задача | Gramazeka | Игра вообще | 17 | 09.10.2007 16:50 |
Задача от СС | Pon | Теории, стратегии, основы покера | 38 | 12.11.2005 18:51 |
Задача | NiHeraNeSsu | Limit Holdem, Omaha, 7-Card Stud и другие виды покера | 21 | 11.09.2005 04:49 |
|
|