Условие писал не я и переводить/править впадло, так что цитирую:

Є купа зеків. Їм адміністрація пенітенціарного закладу пропонує цікаву гру, і оголошує умови. У зеків є час на обговорення, а потім гра починається. У випадку виграшу зеків - всі виходять по амністії.

Ось умова:

Всіх розводять по окремих камерах, і час від часу, по рандому (тру рандом, без приколов /mist/) , по одному, щоб інші не бачили і не чули, відводять до кімнати у якій є рубильник. Рубильник можна перевести або у стан "уверх" або у стан "униз", або ж не чіпати. Будьхто із зеків може сказати адміністрації таку фразу "у цій кімнаті вже побували всі в"язні" (только эта фраза может прекратить игру, иначе до упора /mist/). Якщо це істинно (може і не по одному разу побувати)- всіх випускають, якщо ні - гра програна.

Как себя должны вести зеки чтобы выиграть в этой игре?

Питання:
1. Чи може так бути, щоб хтось побував у кімнаті N-ний раз, у той час як хтось інший не був там взагалі?
2. У якому стані знаходиться рубильник з самого початку?

1. Да, но рано или поздно там побывают все.
2. Этого никто не знает.

1. Вполне. Иначе задача тривиальна. Как только попадаешь 2 раз, говоришь "стоп".
2. Пох.
Пока идей нет. А жаль.
Хотя... кое-что есть. Есть некоторые общие идеи,но они слишком общие. В принципе, хорошо было бы знать изначальное положение рубильника. Но, похоже, не надо. Плохо с алгоритмами, гнать меня в шею с фака.
Предполагаю, что известно общее число зеков. Иначе кина не будет, ИМХО.

В условии написано что им дают посоветоваться, значит и пересчитаться они могут =)

Ні, все одно адміни одного чувака триматимуть, поки всі не заъбуться

А якщо тру рендом - доведеться імовірності рахувати.

Чёрт, откуда у людей такое желание придираться?


Да, они несколько противоречат друг другу, так как на любом ограниченном промежутке времени (даже 10^1000 лет) есть веротяность что одного таки не заведут. Но ты рассматривай это по другому - это дополнение к правилу с которым надо смириться.

ще раз для чіткості - всі зміни зроблені зеками в кімнаті окрім рубильника ретельно прибираються і не беруться до уваги?

той хто приходить в кімнату вперше смикає рубильник вниз
той хто приходить вдруге смикає вверх
втретє, четверте, пяте - не рухає
коли він прийде N-й раз і побачить що рубильник вверху він з ймовірністю близькою до 1 може бути впевненим що тут були всі

сказати точно за таких умов мабуть нереально... поки шо не придумав

Ымовирнисть — фикня. Задача стопроцентно имеет точное решение.

Да.

Не разглядел логики. А если его одного просто Н раз подряд завели?

И собственно, как я уже говорил и как заметил ВАНО должно быть точное, а не веротяностное решение.

а адміністрація може підгавняти з рубильником і на n-му кроці змінити його положення?

Ніхто не чіпає рубильник допоки не приходить туди в сотий раз. Час є поспішати нема куди. Якщо ймовірність не влаштовує - тисячний раз. Адміністрація здула.

Администрация это заметит и будет выводить только, допустим, трёх чуваков из тысячи)

Им тоже спешить некуда))

Але ж вони мають рандомно виводити! Інакше порушать таєнство задачі~

Ну в таком случае таинство задачи ещё и в том, чтобы решение было точным

Грррр что за демагогия? =) Решение должно быть точным =)

Был бы я модером, я бы Crusader дал бан где-то на недельку. По крайней мере на этот раздел.

//добавлено через пару минут
Спасибо за столь быстро реагирование. Премного благодарен.

//добавлено через пару часов
Всё, вопрос решён. Мир, дружба, красота.

Перший опускає рубильник (якщо він вже опущений, то залишає так) - щоб не було плутанини. Всі інші носять з собою транспортир і піднімають рубильник на певний кут, і коли всі побувають в кімнаті, рубильник буде піднятим до кінця

1. ніхто не знає перший він чи ні
2. рубильник має тільки 2 положення

Пропоную альтернативну відповідь.

Перший зек, що заходить вирубає рубильник - у в'язниці зникає світло - інші зеки вирубають охорону - всі щасливі, всі здорові. А задача... та йух з нею.

Остроумно. А главное с достоинством и скромностью (болд и красный цвет не считаются).

Звиняйте, що зачепив таку древню тему, але так вже повелося - я переглядаю форум раз на кілька місяців.
Тепер безпосередньо до роз'язку задачі:
{Доречі, для простоти доведення рахуємо, що зеків скінченна к-сть = N}
Розглянемо дещо простіший варіант задачі(так простіше вловити суть узагальненого рішення) - це коли відомо початкове положення рубильника(напр.догори).
Тоді серед зеків обирається вожак(ним може бути пахан) і такі правила:
кожен із зеків окрім вожака
1) якщо рубильник вверху, то нічого не чіпає.
2) переводить рубильник догори, якщо він унизу, АЛЕ ЛИШЕ РАЗ після чого з'являється нове правило
3) після події 2 жодного наступного разу не змінює положення рубильника.

Вожак=В, Простий зек=ПЗ

Якщо першим в кімнату зайде ПЗ, то за умовами він нічого не чіпає.
На якомусь кроці заходить В (вперше) і переводить рубильник донизу. Після нього заходить ПЗ і переводить рубильник догори, символізуючи, що він порахований. Після нього жоден ПЗ за умовами нічого не чіпає. Накінець, вдруге заходить В і бачить, що хтось змінив його положення. Тому починає рахувати скільки разів змінювали положення знизу угору. Таким чином ПЗ нічого не чіпає, якщо він уже порахований вожаком. Вожаку лише залишається постійно ставити ручку донизу і рахувати лише ті появи в кімнаті, коли ручка після цього знову перемістилась угору. Тоді змінюють положення ручки знизу вверх лише ті ПЗ, які до цього часу це не робили. Якщо В заходить в кімнату і ручка далі унизу, то він нічого не робить, оскільки є ще ПЗ. Вожак ставить ручку донизу допоки її не піднімлять N-1 раз. Таким чином в кімнаті побували всі N-1 простих зеків і чималу к-сть разів вожак.

Так з цим варіантом розібралися. Дивлячись на попередні міркування аж ніяк не скажеш, що їх можна узагальнити на варіант, коли не відоме початкове положення. А саме трудність полягає в тому, що 1) Вожак повинен бути обраний до початку гри(як би не хотілось, а першим хто піде не відомо нікому),
2) початкове положення рубильника - НЕВІДОМЕ НІКОМУ ІЗ ЗЕКІВ.
Щоб легше роз'яснити це рішення перейде до числа зеків у к-сті 101 чоловік (100 ПЗ + 1 В).
Правила залишаються такими ж (тому, хто не догнав попереднє викладення раджу перечитати його допоки не стане все ясно). Насправді дещо змінені, але це дещо пізніше. Зрозуміло, що якщо рубильник одразу знаходиться угорі, то це зводиться до попереднього рішення. Якщо ж він унизу, то виникає проблема в тому, що можливий варіант, коли першим заходить ПЗ і, розуміючи для себе, що це зробив саме вожак, змінює положення рубильника і таким чином одного зека недораховано.
Тому, коли В нарахує 99 змін положення ручки знизу угору, то аж ніяк не означає, що пройшли 99 зеків. Зрозуміло, що це не влаштовує. Тому правила дещо змінені. Тепер кожен зек повинен змінити положення ручки 10 разів, а вже на 11 раз нічого не чіпати(звичайно, я тут використовую число 10 як дуже показове). Тоді за умовами В повинен нарахувати 10*100=1000 змін положень ручки знизу угору якщо початкове положення було угорі або 1000-1=999 змін положень, якщо унизу. Якщо ж він нарахував лише 990, то це ще може означати, що якийсь із зеків ще не побував жодного разу(мало ймовірно, але можливо). А вже на 991 раз можна із впевненістю сказати, що всі 100 ПЗ тут побували, ну і сам В також(цілих 991 раз і більше).
Той хто любить точні дані, то кожен ПЗ має смикнути ручку 2 рази, а вожак має нарахувати 2N-1 раз або 2N рівно.
Все.

Ух ти

Геніально.

Це ж треба, як все по-геніяльному просто. А я ніяк міг справитися з другою частиною задачі, тобто додуматися, як можна обійти проблему того, що не відомо початкового положення рубильника і хто з зеків зайде першим...

нема слів

Ура блин =) Наконец-то решили и подробно расписали решение. Рад.