Убей неделю, как про

[^p1x]

Задача

В тюрьме сидят 10 заключенных, каждый — в одиночной камере. Общаться между собой они не могут. В один прекрасный день начальник тюрьмы объявил им, что предоставляет всем шанс выйти на свободу на следующих условиях:

 

«В подвале тюрьмы есть комната с переключателем, имеющим два состояния: ON и OFF («вкл.» и «выкл.»). Каждую ночь я буду приводить в эту комнату ровно одного заключенного (выбирая его абсолютно случайно) и через некоторое время уводить. Находясь в комнате, каждый из вас может либо изменить положение переключателя, либо ничего с ним не делать. Персонал тюрьмы трогать этот переключатель не будет. В какой-то момент один из вас (любой) должен понять, что в комнате побывали все заключенные, и сообщить об этом. Если он окажется прав — всех отпустят, если ошибется — все вы навсегда останетесь в тюрьме. Я обещаю, что в комнате побывают все заключенные, причем каждого будут приводить туда неограниченное число раз».

 

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

 

Могут ли заключенные гарантированно выйти на свободу, и если да, то как им этого добиться?

 

ебался неделю с этой задачкой, пиздец.

 

офк раковым которые будут искать ответ в интернете - грац

[Гость arcania]

ненавижу математику

[banditwp]

ебать как я люблю математику

[Zarathustra]

Посмотрел решения, задачка - пиздец

[W(Deidara)W]

нет офк

[Гость PwnsoOme]

8.261069 и арагонит

пиздец ты тупой

 

[Gish]

КОРОЧЕ Я ПРИДУМАЛ ОТВЕТ НО МНЕ ЛЕНЬ ЕГО ПИСАТЬ

ВСЕ СЕЙЧАС ОЧЕНЬ ПИЗДАТО

Я ОЧЕНЬ АКТИВЕН И МНЕ ХОРОШОООООООООооооу

 

[tesla-faber]

у меня встал

[volosi_nazad]

Помню на социологии когда-то загадывали такое, подумал 2 минуты и хуй забил, не вспоминал даже.

Напишите кто-то ответ под спойлер, интересно почитать.

[EkspressO]

задача старая, когда то ее читал, решения непомню..

[pischeblok]

держи поц отключить Caps Lock через регистр навсегда - http://www.brainmixer.ru/files/soft/disable_caps/disable_caps_lock.reg

 

вернуть обратно - http://www.brainmixer.ru/files/soft/disable_caps/remove_scancode_mappings.reg

 

после установки файла необходима перезагрузка :mage:

[EkspressO]

держи поц отключить Caps Lock через регистр навсегда - http://www.brainmixer.ru/files/soft/disable_caps/disable_caps_lock.reg

 

вернуть обратно - http://www.brainmixer.ru/files/soft/disable_caps/remove_scancode_mappings.reg

 

после установки файла необходима перезагрузка :mage:

вам в другую тему

[pischeblok]

держи поц отключить Caps Lock через регистр навсегда - http://www.brainmixer.ru/files/soft/disable_caps/disable_caps_lock.reg

 

вернуть обратно - http://www.brainmixer.ru/files/soft/disable_caps/remove_scancode_mappings.reg

 

после установки файла необходима перезагрузка :mage:

ето мне сука выдало 1й строко1 на 1й странице сука написал вв поисковике "как отключить capslock" рак ты ебаный

[YSM370]

ответ в том что

[volosi_nazad]

держи поц отключить Caps Lock через регистр навсегда - http://www.brainmixer.ru/files/soft/disable_caps/disable_caps_lock.reg

 

вернуть обратно - http://www.brainmixer.ru/files/soft/disable_caps/remove_scancode_mappings.reg

 

после установки файла необходима перезагрузка :mage:

ето мне сука выдало 1й строко1 на 1й странице сука написал вв поисковике "как отключить capslock" рак ты ебаный

кому ты это писал то, идиот, гиш, очевидно, на шифте, а не на капсе.

[Bounty]

Помню на социологии когда-то загадывали такое, подумал 2 минуты и хуй забил, не вспоминал даже.

Напишите кто-то ответ под спойлер, интересно почитать.

 

 

1. Самый простой, но и самый долгий вариант  — действовать так, как было сказано в подсказке. Чтобы просигнализировать последнему, каждый из заключенных, которого завели в комнату НЕ В СВОЙ день, должен поставить переключатель в положение ON. Если же 10-й заключенный действительно оказался в комнате на 10-й день декады и видит переключатель в положении OFF, он немедленно говорит начальнику тюрьмы, что в комнате побывали все заключенные. Если в 10-й день в комнате оказался кто-то другой или же 10-й видит переключатель в положении ON, то всё начинается заново...

 

Это решение, несмотря на всю свою простоту, плохо в главном — бедным узникам придется слишком долго ждать. Действительно, из всех возможных 1010 вариантов посещения ими комнаты в течение декады их устраивает только один — таким образом, вероятность p их выхода на волю в течение одной декады равна 1/1010. Сравнительно несложными вычислениями можно доказать, что среднее время, которое потребуется им на освобождение, равно 1/p = 1010 декад, или 1011 дней, или более 270 миллионов лет. В общем, столько люди не живут.

 

2. Однако это же решение подсказывает, как они могут ускорить свой выход на свободу. Для этого они должны дожидаться следующего события: в течение декады каждый из 10 человек побывал в комнате ровно один раз. Как такое событие «сигнализируется»? Да почти так же: если кого-нибудь заводят второй раз в одной декаде, он ставит переключатель на ON. Таким образом, если на 10-й день декады узник, которого туда отвели, оказался там впервые (за декаду) и видит переключатель в положении OFF, он сообщает начальнику тюрьмы, что всех можно освобождать.

 

Этот способ работает уже существенно быстрее, потому что количество благоприятных исходов теперь не 1, а 10! = 3628800. Это означает, что вероятность p' выхода на свободу за первую же декаду не так уж и мала — она равна 0,00036288. Следовательно, ожидаемое число декад до выхода равно 1/p' ≈ 2755, то есть освободятся они примерно через 75 лет. Так что кто-нибудь, может быть, и доживет до освобождения, хотя особо надеяться на это не стоит.

 

Неужели всё так печально?

 

3. К счастью, у заключенных существует принципиально другой способ действий.

 

Например,они могут договориться о том, что тот, кого заведут в комнату в первую ночь, выставляет переключатель на OFF и становится СЧЕТЧИКОМ. Остальные заключенные остаются ОБЫЧНЫМИ. Каждый обычный заключенный должен передать счетчику ровно один сигнал о своем попадании в комнату с переключателем. Это делается так: попав туда, обычный заключенный смотрит на положение переключателя. Если оно OFF, то заключенный ставит его на ON и считает сигнал переданным. Если же выключатель уже находится в положении ON, то заключенный ничего не делает — иначе говоря, ждет следующего подходящего случая.

 

Счетчик, попадая в камеру и видя переключатель в положении ON, понимает, что ему передали сигнал (запоминает это), а чтобы сделать возможной передачу следующего сигнала — ставит переключатель в OFF. Если же он видит переключатель в OFF, то ничего не делает и тоже ждет следующего раза.

 

Как только счетчик примет 9-й сигнал, он сразу же сообщает об этом начальнику тюрьмы.

 

Как долго продлится их отсидка при такой стратегии? Сосчитать это уже не столь просто, как раньше, потому что вероятность того, что заключенному в очередной день удастся передать сигнал, постепенно уменьшается от 9/10 для первого сигнала до 1/10 для последнего сигнала. В то же время вероятность попадания в комнату Счетчика в любой момент равна 1/10. Тем не менее механизм подсчета в целом аналогичен: до момента передачи первого сигнала в среднем пройдет 10/9 дня, а до момента его приема Счетчиком — еще 10 дней. Затем на второй сигнал уйдет 10/8 + 10 дней, на третий — 10/7 + 10, и так далее. Итого  дней — совсем не так много, как в предыдущих решениях.

 

 

 

 

[Bounty]

а мне больше Энштейновская нравится. про домики и прочую лабуду

[volosi_nazad]

Помню на социологии когда-то загадывали такое, подумал 2 минуты и хуй забил, не вспоминал даже.

Напишите кто-то ответ под спойлер, интересно почитать.

 

 

1. Самый простой, но и самый долгий вариант  — действовать так, как было сказано в подсказке. Чтобы просигнализировать последнему, каждый из заключенных, которого завели в комнату НЕ В СВОЙ день, должен поставить переключатель в положение ON. Если же 10-й заключенный действительно оказался в комнате на 10-й день декады и видит переключатель в положении OFF, он немедленно говорит начальнику тюрьмы, что в комнате побывали все заключенные. Если в 10-й день в комнате оказался кто-то другой или же 10-й видит переключатель в положении ON, то всё начинается заново...

 

Это решение, несмотря на всю свою простоту, плохо в главном — бедным узникам придется слишком долго ждать. Действительно, из всех возможных 1010 вариантов посещения ими комнаты в течение декады их устраивает только один — таким образом, вероятность p их выхода на волю в течение одной декады равна 1/1010. Сравнительно несложными вычислениями можно доказать, что среднее время, которое потребуется им на освобождение, равно 1/p = 1010 декад, или 1011 дней, или более 270 миллионов лет. В общем, столько люди не живут.

 

2. Однако это же решение подсказывает, как они могут ускорить свой выход на свободу. Для этого они должны дожидаться следующего события: в течение декады каждый из 10 человек побывал в комнате ровно один раз. Как такое событие «сигнализируется»? Да почти так же: если кого-нибудь заводят второй раз в одной декаде, он ставит переключатель на ON. Таким образом, если на 10-й день декады узник, которого туда отвели, оказался там впервые (за декаду) и видит переключатель в положении OFF, он сообщает начальнику тюрьмы, что всех можно освобождать.

 

Этот способ работает уже существенно быстрее, потому что количество благоприятных исходов теперь не 1, а 10! = 3628800. Это означает, что вероятность p' выхода на свободу за первую же декаду не так уж и мала — она равна 0,00036288. Следовательно, ожидаемое число декад до выхода равно 1/p' ≈ 2755, то есть освободятся они примерно через 75 лет. Так что кто-нибудь, может быть, и доживет до освобождения, хотя особо надеяться на это не стоит.

 

Неужели всё так печально?

 

3. К счастью, у заключенных существует принципиально другой способ действий.

 

Например,они могут договориться о том, что тот, кого заведут в комнату в первую ночь, выставляет переключатель на OFF и становится СЧЕТЧИКОМ. Остальные заключенные остаются ОБЫЧНЫМИ. Каждый обычный заключенный должен передать счетчику ровно один сигнал о своем попадании в комнату с переключателем. Это делается так: попав туда, обычный заключенный смотрит на положение переключателя. Если оно OFF, то заключенный ставит его на ON и считает сигнал переданным. Если же выключатель уже находится в положении ON, то заключенный ничего не делает — иначе говоря, ждет следующего подходящего случая.

 

Счетчик, попадая в камеру и видя переключатель в положении ON, понимает, что ему передали сигнал (запоминает это), а чтобы сделать возможной передачу следующего сигнала — ставит переключатель в OFF. Если же он видит переключатель в OFF, то ничего не делает и тоже ждет следующего раза.

 

Как только счетчик примет 9-й сигнал, он сразу же сообщает об этом начальнику тюрьмы.

 

Как долго продлится их отсидка при такой стратегии? Сосчитать это уже не столь просто, как раньше, потому что вероятность того, что заключенному в очередной день удастся передать сигнал, постепенно уменьшается от 9/10 для первого сигнала до 1/10 для последнего сигнала. В то же время вероятность попадания в комнату Счетчика в любой момент равна 1/10. Тем не менее механизм подсчета в целом аналогичен: до момента передачи первого сигнала в среднем пройдет 10/9 дня, а до момента его приема Счетчиком — еще 10 дней. Затем на второй сигнал уйдет 10/8 + 10 дней, на третий — 10/7 + 10, и так далее. Итого  дней — совсем не так много, как в предыдущих решениях.

 

 

 

 

нихуя там букв 

ну щас почитаю, пасиба 

[volosi_nazad]

а мне больше Энштейновская нравится. про домики и прочую лабуду

за пару минут вроде решил еще давно 

[IceTitan]

я дибил даже не понял что нужно зделать