Сто заключенных и одна лампочка

[Alexan]

Я тут был в отпуске 2 недели и от нечего делать решил задачу. В соответствии с первым решением понадобится лет 25-30, второе, усовершенствованное решение требует в два раза меньше времени, возможно, я думаю и дальнейшее усовершенствование. Если интересно, могу написать решение.

[Alexander Ch.]

Новая песня Тату как раз в тему этой задачки

"Не зажигай и не гаси, не верь, не бойся, не проси!"

[Циник]

Я тут был в отпуске 2 недели и от нечего делать решил задачу. В соответствии с первым решением понадобится лет 25-30, второе, усовершенствованное решение требует в два раза меньше времени, возможно, я думаю и дальнейшее усовершенствование. Если интересно, могу написать решение.

Конечно, интересно - давай, товарищ, пиши!
Наверно, уже можно

[Циник]

Задача пустяковая

Конечно, пустяковая. Решение в студию, товарищ.

раз есть вероятность, что хотя бы один заключённый ни разу в комнате не окажется, зачем спекуляции?

Спекуляции, товарищ Илид, бывают на фондовом рынке, а у нас тут математика, понимаешь

есть вероятность, что хотя бы один заключённый ни разу в комнате не окажется

Есть такая вероятность, товарищ. И равна она нулю, для выбранной тобой формулировки утверждения. Есть также не равная нулю вероятность, что 99 заключенных не окажутся в комнате в течение 100 лет - это да. Но решению задачи это никак не мешает.

Или я чего-то не понимаю? И не может быть никакого математического решения.

Скорее всего да, товарищ, ты чего-то не понимаешь.

Задачка дурацкая, на вшивость.

Сам ты дурацкий

[ilid]

Ничего себе математика... Циник, ну честное слово. Вот тебе задачка. Пришёл бандит в дом и говорит: " Вот буду сейчас подбрасывать монету, а ты с завязанными глазами будешь считать сколько раз выпал Орёл, когда ты подумаешь что орёл выпал 100 раз - скажешь мне, если орёл и вправду выпал 100 или больше раз - отпущю, а если нет - всё имущество заберу, а для облегчения можешь лампочку включать" непохоже? Кстати совсем я наезда не понял. Ответь товарищ на вопрос, если есть вероятность что хотя бы один заключённый ВООБЩЕ не окажется в комнате, откуда же появится ТОЧНОЕ решение? Если оно есть, то это не математика тогда...

[ilid]

Значит Попробую доказать свою точку зрения. Для начала попробуем решить задачу для 2-их заключённых. Тут - всё просто, даже лампочка не нужна, один день тебя не позвали - значит и другой побывал. Для 3 заключённых: если человек оказывается в комнате в первый раз - он либо включает лампочку либо оставляет её горящей. Если он заходит во второй раз или больше - то тушит её или оставляет её потухшей. Если заключённый заходит когда он не был в комнате в общей сложности хотя бы 2 дня и видит что лампочка горит - это возможно лишь в том случае, если последний, кто заходил - был в комнате в первый раз, если так - то всё хорошо - он говорит что все 3 побывали - и их отпускают. Если же лампочка погасшая? Как может заключённый знать что именно произошло?Предположим,что заключённый номер 3 попадает попадает в комнату в первый раз через 10 дней. Если лампочка горит - всё отлично, а если нет? Он не знает, был ли это только один заключённый или оба, если же например в случае, если человек заходит подряд несколько раз в комнату, то он оставит свет зажёным (зайдя первый раз после этого заключённый заходил несколько раз подряд), то получаем неизвестность с другой стороны, потому как если через те же 10 дней 3-ий заключёный зайдёт и увидит свет включёным - ему это так же ничего не скажет. Задача таки имеет решение, всё что требуется, это чтоб заключённый который зайдёт после, обнаружит свет зажёным и всё будет отлично. Но есть одно НО. Существует вероятность, которая может и стремится к нулю в пределе (бесконечно большое количество дней) для любого натурального числа дней не равна нулю, что этот 3-ий заключённый так никогда и не появится в комнате, тем самым у 2-их его товарищей останется неопределённость и тем самым они возможно будут ждать пока 3-ий зайдёт в комнату чтоб включить свет бесконечное количество дней. Как видно, хоть решение и очевидно для 3 заключённых - оно не идеально. Для 4-х заключённых при тех же правилах даже если свет зажжён после хотя бы 3-х дней осутствия, нельзя сказать наверняка или 2 или 3 человека побывали в комнате.Для 100 человек степень неопределённости только больше. Так что, товарищ Циник, давайте решение, если конечно оно у Вас есть.

Дурацкий Илид.

[Alexan]

Есть решение, сейчас некогда, вечером напишу.

[Alexan]

Значит так: выбирается один человек, который будет считать остальных. Когда в комнату заходит заключенный, который там раньше не был, и видит выключенную лампочку, он ее включает. Если же лампочка горит или заключенный уже раньше был в комнате, то он ничего не делает. Выключать лампочку имеет право только человек, который считает. Значит когда он выключит лампочку 99 раз, то все заключенные побывали в комнате. Для этого он должен побывть в комнате 99 раз. В среднем он бывает в комнате раз в 100 дней, значит должно пройти примерно 100*99=9900 дней или 27 лет, прежде чем заключенные смогут выйти на свободу.
Завтра напишу как можно этот срок сократить по крайней мере вдвое.

[Циник]

Ничего себе математика... Циник, ну честное слово.

Здесь тебе не Французская Академия, товарищ Илид, на честное слово не ведемся
А математика здесь - да, ничего себе так, я бы даже сказал - красивая

Вот тебе задачка. Пришёл бандит в дом и говорит: " Вот буду сейчас подбрасывать монету, а ты с завязанными глазами будешь считать сколько раз выпал Орёл, когда ты подумаешь что орёл выпал 100 раз - скажешь мне, если орёл и вправду выпал 100 или больше раз - отпущю, а если нет - всё имущество заберу, а для облегчения можешь лампочку включать" непохоже?

Нет, совсем непохоже. Жалко даже тебя, товарищ - так много слов написал и все равно непохоже

Кстати совсем я наезда не понял.

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

Ответь товарищ на вопрос, если есть вероятность что хотя бы один заключённый ВООБЩЕ не окажется в комнате, откуда же появится ТОЧНОЕ решение?

Товарищ, у меня в принципе нет слов, но я все равно попробую что-нибудь объяснить, чисто из уважения к товарищу Карло, давшему нам такую замечательную конфу
Если не поймешь, так, может, хоть заинтересуешься

Для любого конечного промежутка времени t (например, 2 гугля лет) и любого количества заключенных n (0 < n < 100) существует вероятность P (n, t) > 0 того, что n заключенных никогда не окажутся в комнате в течение времени t.
Это утверждение верно, а вышеприведенное твое, между если и откуда - ложно.

Теперь по поводу "ТОЧНОГО решения".
Точное решение многих вероятностных задач, и в частности, нашей задачи, заключается не в том, чтобы сказать что-то типа того: через один миллион триста восемьдесят девять тысяч четыреста двадцать один день все заключеннные точно выйдут на свободу, а в том, чтобы придумать алгоритм, при котором, во-первых, гарантируется результат (то есть вероятность неудачи равна нулю), а во-вторых, матожидание (см. БСЭ, статья Математическое ожидание) времени выхода на свободу минимально.

Если оно есть, то это не математика тогда...

Кролики, товарищ Илид, это не только ценный мех. Так же и математика - это не только дважды два четыре

[Циник]

Значит так: ...

Архиверно, товарищ Алексан!

Завтра напишу как можно этот срок сократить по крайней мере вдвое.

Ждем-с! Тут-то как раз самое интересное

[ilid]

Циник, творческих успехов, математический Вы наш. При написаном решени - какова функция лампочки? Или всё-таки НЕ МЕНЕЕ 99 РАЗ имелось ввиду? Предупреждать надо. Но я конечно жду решения когда все 100 заключённых кроликов будут считать дни. Говорил, же, товарищ, задачка-то дурацкая.

[select]

Молодец, Alexan!

Я не догадался про счетчик!
Но, мне кажется, что версия все равно не очень убедительна.
Ведь заключенных вызывают не по очереди, а случайным образом. Тут 27 годами можно и не обойтись. Я уж не говорю о "времени жизни" счетчика. Я так думаю.

А решение узнать бы хотелось.
Товарищ Циник, нельзя же так цинично заставлять народ думать

[Циник]

Циник, творческих успехов

Спасибо, товарищ Илид.

математический Вы наш.

Не ваш, товарищ Илид. Да, по правде говоря, не такой уж и математический, как бывало

При написаном решени - какова функция лампочки?

Функция лампочки - загораться при включении выключателя и гаснуть при выключении. Хоть при написанном решении, хоть при ненаписанном.

Или всё-таки НЕ МЕНЕЕ 99 РАЗ имелось ввиду?

Поясни вопрос, товарищ. Что именно тебе неясно?

Предупреждать надо.

Куда уж больше предупреждать - 55 постингов уже предупреждаем тебя, товарищ

Но я конечно жду решения когда все 100 заключённых кроликов будут считать дни.

Жди, конечно, товарищ, раз есть желание. А вот есть ли смысл?

Говорил, же, товарищ, задачка-то дурацкая.

Ты, товарищ, все непонятные тебе задачки дурацкими считаешь или только выборочно? Каковы тогда критерии?

[Alexan]

Молодец, Alexan!

Я не догадался про счетчик!
Но, мне кажется, что версия все равно не очень убедительна.
Ведь заключенных вызывают не по очереди, а случайным образом. Тут 27 годами можно и не обойтись. Я уж не говорю о "времени жизни" счетчика. Я так думаю.

А решение узнать бы хотелось.
Товарищ Циник, нельзя же так цинично заставлять народ думать

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

[ilid]

Ладно, товарищ Циник, надоело мне ругаться изза пустяка, складывается ощущение, что Вы, товарищ, только себя самого и слышите. Я оценил Ваш саркастический стиль. Задачка-то понятная, только от этого менее дурацкой она не стала. Она не плохая, прикольная, весёлая, какая угодно слваная и забавная, но она дурацкая, я конечно понимаю, что Вас возможно тяготит опыт интервьюирования, но это когда-нибудь тоже пройдёт. Всяческих благ!