Помогите решить задачу.
Oct. 22nd, 2007 10:26 am![[identity profile]](https://www.dreamwidth.org/img/silk/identity/openid.png)
![[community profile]](https://www.dreamwidth.org/img/silk/identity/community.png)
Тюремщик встречает 23 новых заключенных и говорит им:
"Вы можете собраться сегодня для того чтобы выработать стратегию по решению задачи которую я вам приготовил. Но после этой встречи вы все будете изолированы, и не будете иметь возможность общаться.
В тюрьме есть техническая комната, в ней есть два выключателя А и Б, каждый из этих выключателей имеет две позиции: On и Off. Эти выключатели ни к чему не подлкючены. Я не говорю вам, в каких позициях они сейчас находятся.
После сегодняшнего дня, время от времени, когда я захочу, я буду выбирать одного из вас, по случайному принципу и провожу его в эту комнату. Этот заключенный выберет один из выключателей и изменит его позицию. Он будет должен изменить только один из выключателей. Он не может изменить оба, и не может вообще не изменить ничего. Затем я проведу этого заключенного обратно в его камеру. Никто не войдет в техническую комнату пока я лично никого не проведу. Сами никто туда не заходят. Затем я проведу другого заключенного, когда захочу, и скажу ему делать тоже самое, поменять позицию одного из выключателей.
Я буду выбирать кого вести случайно. Могу одного и того же вызвать несколько раз подряд, могу вразброс выбирать, но, после определенного времени все заключенные будут вызваны в эту комнату столько же раз сколько и другие. В любое время, если вы уверены на 100 процентов, любой из вас может мне заявить: "Мы все побывали в технической комнате по крайней мере по одному разу". Если этот человек прав, вы все свободны. Если нет, и если кто-то еще не побывал в технической комнате, то я вас скормлю аллигаторам."
Какую стратегию они выбрали?
"Вы можете собраться сегодня для того чтобы выработать стратегию по решению задачи которую я вам приготовил. Но после этой встречи вы все будете изолированы, и не будете иметь возможность общаться.
В тюрьме есть техническая комната, в ней есть два выключателя А и Б, каждый из этих выключателей имеет две позиции: On и Off. Эти выключатели ни к чему не подлкючены. Я не говорю вам, в каких позициях они сейчас находятся.
После сегодняшнего дня, время от времени, когда я захочу, я буду выбирать одного из вас, по случайному принципу и провожу его в эту комнату. Этот заключенный выберет один из выключателей и изменит его позицию. Он будет должен изменить только один из выключателей. Он не может изменить оба, и не может вообще не изменить ничего. Затем я проведу этого заключенного обратно в его камеру. Никто не войдет в техническую комнату пока я лично никого не проведу. Сами никто туда не заходят. Затем я проведу другого заключенного, когда захочу, и скажу ему делать тоже самое, поменять позицию одного из выключателей.
Я буду выбирать кого вести случайно. Могу одного и того же вызвать несколько раз подряд, могу вразброс выбирать, но, после определенного времени все заключенные будут вызваны в эту комнату столько же раз сколько и другие. В любое время, если вы уверены на 100 процентов, любой из вас может мне заявить: "Мы все побывали в технической комнате по крайней мере по одному разу". Если этот человек прав, вы все свободны. Если нет, и если кто-то еще не побывал в технической комнате, то я вас скормлю аллигаторам."
Какую стратегию они выбрали?
no subject
Date: 2007-10-22 02:48 pm (UTC)no subject
Date: 2007-10-22 02:50 pm (UTC)no subject
Date: 2007-10-22 03:12 pm (UTC)no subject
Date: 2007-10-22 03:25 pm (UTC)Это надо в ру_драгз запостить, пусть подумают по укурке :lol:
У меня лично от этой задачи ощущение полной шизы :)
no subject
Date: 2007-10-22 03:31 pm (UTC)Определяем риск ошибки (например, 0.5%)
По формуле определяем что такая уверенность наступит при 120 итерациях (22/23^120) = 0.0048
Т.к. есть предположение что выбор случайный, и все сходят к выключателю по одинаковому количеству раз, то тот, кого поведут в шестой раз (не подряд), может кричать что все там уже были (120/23 = 5.2)
ловкость рук:
Договариваемся о коде, например
0-1 = 1
1-1 = 2
1-0 = 3
0-0 = 4
Все щелкают в сторону увеличения, вне зависимости от того с чего начали. Первый кто увидит 6 разных комбинаций, отличных от того, чего поставил он, говорит чтобы всех выпустили :)
длинный путь
каждый должен посетить комнату 22 раза :)
no subject
Date: 2007-10-22 04:10 pm (UTC)5-ый не может знать, первый он или 8-ой.
И они не знают, сколько раз остальные были.
no subject
Date: 2007-10-22 04:07 pm (UTC)Если выключатель А в положении off, счётчик меняет положение выключателя Б.
Каждый ЗК, кроме счетчика, может поставить выключатель А в положение on дважды. Если выключатель А в положении on, ЗК меняет положение выключателя Б. Если он уже дважды приводил выключатель А в положение on, он работает только с выключателем Б.
Счетчик досчитывает до 44 "выключений" А и сообщает, что все уже были.
no subject
Date: 2007-10-22 04:20 pm (UTC)no subject
Date: 2007-10-22 04:27 pm (UTC)no subject
Date: 2007-10-22 04:32 pm (UTC)no subject
Date: 2007-10-22 07:12 pm (UTC)no subject
Date: 2007-10-22 07:28 pm (UTC)no subject
Date: 2007-10-22 08:07 pm (UTC)no subject
Date: 2007-10-22 08:13 pm (UTC)no subject
Date: 2007-10-22 04:25 pm (UTC)Интересно, что если изменить правила с "после сегодняшнего дня, время от времени, когда я захочу" на "начиная с завтрашнего дня, раз в день", то "рядовым" будет достаточно включать "основной" выключатель лишь однажды. Но при этих условиях такая стратегия неоптимальна, а задача поиска оптимальной стратегии очень сложна и пока не решена.
no subject
Date: 2007-10-22 07:07 pm (UTC)no subject
Date: 2007-10-22 07:36 pm (UTC)no subject
Date: 2007-10-22 08:45 pm (UTC)