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

Все, что вы хотели знать о программизме, но боялись спросить.
Аватара пользователя
Marmot
Графоман
Сообщения: 39343
Зарегистрирован: 17 фев 2003, 17:58
Откуда: Caulfeild
Контактная информация:

Re: Google знает ВСЁ!!!

Сообщение Marmot »

Циник писал(а): Сотри сейчас же, товарищ Мармот, свои еретические и провокационные речи (и эту и предыдущую) :twisted:
В 21-ом веке живём давно, господин Циник,
пора вырабатывать прогрессивные рефлексы :-)
Современное общество не нуждается в бездумных изобретениях велосипедов.
Думать надо о том, о чём до тебя ещё никто не думал! :-)
Мозги, конечно, нуждаются в тренировке, но выработка правильных мозговых рефлексов ещё важнее :-)
Аватара пользователя
Циник
Завсегдатай
Сообщения: 442
Зарегистрирован: 17 фев 2003, 17:17

Re: Google знает ВСЁ!!!

Сообщение Циник »

Marmot писал(а):В 21-ом веке живём давно, господин Циник,
пора вырабатывать прогрессивные рефлексы :-)
Современное общество не нуждается в бездумных изобретениях велосипедов.
Думать надо о том, о чём до тебя ещё никто не думал! :-)
Мозги, конечно, нуждаются в тренировке, но выработка правильных мозговых рефлексов ещё важнее :-)
Неплохо, неплохо сказано, товарищ Мармот :twisted:
Предлагаю обсудить эти вопросы отдельным тредом как-нибудь.
Woozy
Завсегдатай
Сообщения: 278
Зарегистрирован: 03 мар 2003, 08:55
Откуда: RU->BC->ON->FI -> Chicago, IL -> Seattle, WA

Сообщение Woozy »

11
Последний раз редактировалось Woozy 27 июн 2003, 10:39, всего редактировалось 2 раза.
Woozy
Завсегдатай
Сообщения: 278
Зарегистрирован: 03 мар 2003, 08:55
Откуда: RU->BC->ON->FI -> Chicago, IL -> Seattle, WA

Re: Google знает ВСЁ!!!

Сообщение Woozy »

Woozy писал(а):Странно, что тот постинг не положил конца обсуждению. :roll:
Циник писал(а):Да что там Гугль, он и читает-то плохо :twisted:
Циник писал(а):Нет, посещения, конечно, начинают считаться только после ночи, проведенной заключенными в обсуждении плана действий.
Если ты об этом, то должен был сказать с самого начала. Задача не тобой сочинена? Откуда взял тогда такой текст, с таким ляпом? Изначально пропущена важнейшая деталь. Так плохо перевёл текст, товарищ? :P Ведь не сам сочинил, как пишешь...

Да, недоглядел твою ремарку, поскольку после предложенного логически правильного решения даже читать всё blah-blah-blah не хотелось.
Аватара пользователя
Циник
Завсегдатай
Сообщения: 442
Зарегистрирован: 17 фев 2003, 17:17

Re: Google знает ВСЁ!!!

Сообщение Циник »

Woozy писал(а):Если ты об этом, то должен был сказать с самого начала.
Oб этом, товарищ Вузи, как не об этом. Должен был, ты совершенно прав. Что теперь поделаешь? Сделал поправку. Можно было, конечно, и историю подправить, благо мастерская товарища Карло позволяет. Но зачем?
Woozy писал(а): Задача не тобой сочинена?
Об этом мы уже говорили, товарищ. Не мной.
Woozy писал(а):Откуда взял тогда такой текст, с таким ляпом? Изначально пропущена важнейшая деталь. Так плохо перевёл текст, товарищ? :P Ведь не сам сочинил, как пишешь...
Во-первых, товарищ Вузи, у нас не наезжают.
Во-вторых, такой текст я никуда и ниоткуда не переводил, а просто дал его в своей интерпретации.
Woozy писал(а):Да, недоглядел твою ремарку, поскольку после предложенного логически правильного решения даже читать всё blah-blah-blah не хотелось.
Ничего, товарищ. Бывает :twisted:
Woozy
Завсегдатай
Сообщения: 278
Зарегистрирован: 03 мар 2003, 08:55
Откуда: RU->BC->ON->FI -> Chicago, IL -> Seattle, WA

Сообщение Woozy »

Циник, и что? Выдать в эфир заключение о решаемости задачи с учётом поправки условия? Уже можно?
Аватара пользователя
Циник
Завсегдатай
Сообщения: 442
Зарегистрирован: 17 фев 2003, 17:17

Сообщение Циник »

Woozy писал(а):Циник, и что? Выдать в эфир заключение о решаемости задачи с учётом поправки условия? Уже можно?
С учетом поправки - конечно. A что такое заключение о решаемости задачи, товарищ?

P.S. Toварищи, почему так мала активность?
Товарищ Александр Ч., есть ли новые идеи или как?
Может, вам подсказку дать небольшую, но важную?
Последний раз редактировалось Циник 28 июн 2003, 12:46, всего редактировалось 2 раза.
Аватара пользователя
Циник
Завсегдатай
Сообщения: 442
Зарегистрирован: 17 фев 2003, 17:17

Сообщение Циник »

Alexander Ch. писал(а):Пара идей:
Первый шаг первом прогоне (100 дней) - если заключенный заходит в комнату в первый раз, то он не включает лампочку. Ему присваивается номер дня. Соответственно, если входит второй раз, то включает. К примеру, на 37 день в комнату попал 25 заключенный, кт. и включает лампочку. Таким образом, два заключенных(№36 и №25) знают, что успешно прошли номера до 36.
Eсли честно, то не понял мысли. Можешь уточнить и растолковать?
Можно разбить сотню на 2 (64+36 или 50+50) части. С 50, если лампочка горит, счетчик обнуляется и новая последовательность для второй половины.
А для чего разбивать на половины и обнулять счетчик?
Но как передать информацию?
Во-во. Вопрос масштаба Что делать? :twisted:
Единственный способ, кт. приходит в голову - используя некоторое количество следущих прогонов (100 дней), чтобы передать инормацию (2 в 7 степени=128 + еще один прогон для того, чтобы все уяснили, итого 800 дней только для передачи информации)
У меня тогда вопрос - кому передается информация и кем?
Аватара пользователя
ajkj3em
Маньяк
Сообщения: 2063
Зарегистрирован: 12 ноя 2006, 06:53

Сообщение ajkj3em »

Циник писал(а):
Woozy писал(а):Циник, и что? Выдать в эфир заключение о решаемости задачи с учётом поправки условия? Уже можно?
С учетом поправки - конечно. A что такое заключение о решаемости задачи, товарищ?

P.S. Toварищи, почему так мала активность?
Товарищ Александр Ч., есть ли новые идеи или как?
Может, вам подсказку дать небольшую, но важную?
дык все кому было интересно уже давно прочитали обзорную
статью некоего китайца из berkeley по доступным алгоритмам
решения ..
Аватара пользователя
Циник
Завсегдатай
Сообщения: 442
Зарегистрирован: 17 фев 2003, 17:17

Сообщение Циник »

huh писал(а):дык все кому было интересно уже давно прочитали обзорную
статью некоего китайца из berkeley по доступным алгоритмам
решения ..
Э нет, товарищ. Так поступили те, кому было интересно узнать решение. Мы вот, например, с товарищами никаких китайцев знать не желали, пока сами не решили.
Alexander Ch.
Завсегдатай
Сообщения: 284
Зарегистрирован: 04 мар 2003, 08:49
Откуда: Hamilton, Ontario

Сообщение Alexander Ch. »

Я уезжаю на неделю. Прошу не говорить отгадку. Интересная задачка :)
Alexander Ch.
Завсегдатай
Сообщения: 284
Зарегистрирован: 04 мар 2003, 08:49
Откуда: Hamilton, Ontario

Вариант решения

Сообщение Alexander Ch. »

Вариант статистического решения. Не вполне строгий, но жизненно-практичный. :wink: Предлагаю назвать его "Проверка четности" :)

Каждый заключенный, входя первый раз в комнату, меняет бит лампочки. Иначе - игнорирует. Итого, когда все 100 заключенных прошли через комнату, лампочка должна вернуться к исходному состоянию (выключена).
(Далее все цифры - примерные)
Ждем 1000 дней, когда должна пройти примерно половина заключенных.
После этого начинается отсчет и любой заключенный, который заходит в комнату в 15-й раз и видит, что все эти 15 раз лампочка в положении выключено, объявляет, что все заключенные побывали в этой комнате.
Могу подсчитать вероятность благоприятного исхода, но не сразу :(
Аватара пользователя
Akrav
Графоман
Сообщения: 12530
Зарегистрирован: 17 июн 2003, 13:30

Сообщение Akrav »

По условию вероятность должна быть 1, поэтому надо искать другое решение.
Alexander Ch.
Завсегдатай
Сообщения: 284
Зарегистрирован: 04 мар 2003, 08:49
Откуда: Hamilton, Ontario

Настаиваю на своем варианте решения

Сообщение Alexander Ch. »

Akrav писал(а):По условию вероятность должна быть 1, поэтому надо искать другое решение.
Есть два варианта этой задачи: Математический, абсолютно точный, идеальный для Дункана МсЛауда. Не интересный. Если Дункан появится, могу послать мылом.
Второй вариант - физический/проверка четности (описанный вверху) Точность решения близка к 1 с любой желаемой точностью.

Для упрощения - прошло 2000 дней (около 6 лет); осталось два заключенных, еще не включавших лампочку. Вероянтость того, что любой из них не попадет в комнату в течении 100 дней - .36 (.99 в 100 степени), для двоих - около 13%. Для 200 дней - 1.6%; для 400 - .026%. Для 1000 дней - вероятность ошибки О малое по сравнению с вероятностью гибели от пожара в тюрьме, удара метеорита и т.п.
Итого 8 лет - вполне реальный срок выхода на свободу с минимум риска.
:)
ilid
Завсегдатай
Сообщения: 255
Зарегистрирован: 19 мар 2003, 13:31

Сообщение ilid »

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