Category: праздники

Category was added automatically. Read all entries about "праздники".

задача по мотивам рассуждения Петера Гача

Мы стоим у ленты транспортёра, по которой мимо нас проезжают одинаковые на вид шары. Они могут быть стеклянными или ледяными. Когда шар мимо нас проезжает, мы можем его взять себе, на этом игра заканчивается, мы выигрываем, если шар ледяной, и проигрываем, если стеклянный. Уже проехавшие шары мы взять не можем, но видим, какие из них растаяли (ледяной шар обязательно растает рано или поздно, и мы это увидим - но время это неизвестно, и для разных шаров может быть разным).

Требуется придумать вероятностный алгоритм с такими свойствами:

1) для любой последовательности шаров на ленте вероятность того, что мы возьмём стеклянный шар, не больше 1%

2) Если все шары ледяные, то с вероятностью 1 мы рано или поздно возьмём шар (и он окажется ледяным, так что мы выиграем)

Лента может быть произвольной, но наша монета гарантированно честная (при любой ленте)
---
(Математический вопрос, из которого это происходит: построить вероятностный алгоритм, который с вероятностью 99% печатает бесконечную последовательность натуральных чисел, не ограниченную никакой всюду определённой вычислимой функцией)

P.S. Решение buddha239, приведённое в одном из комментариев, наводит на мысль, что формулировка задачи недостаточно очищена, чтобы условие и решение выглядели просто. Мы можем взять любой шар, но можем также и не взять шар, а вместо этого наблюдать за ним, пока он не растает (если этого не случится никогда, то требования выполняются). Тем самым задача сводится к такой:

Мы покупаем пиротехнику для праздника у ненадёжного продавца. Он предлагает нам изделие, мы можем либо купить его, либо потребовать, чтобы его при нас запустили. Если не сработает, то разоблачённый продавец закрывает лавку. Если сработает, то это изделие, естественно, уже больше использовать нельзя, но можно получить у продавца новое изделие. Требуется вероятностная стратегия наших действий, при которой [1] мы всегда либо разоблачаем продавца, либо уносим некоторое (неопробованное) изделие с собой, и [2] при любой стратегии продавца (вероятностной или детерминированной) вероятность унести неисправное изделие не больше 1/100.

Проверка изделия соответствует тому, что мы обратили внимание на какой-то шар и ждём его таяния.

В такой формулировке, видимо, решение уже придумать совсем просто.

наверно, снова

мне будут справедливо указывать, что нехорошо цитировать такого типа записи, но тем не менее:

"СО СТАРЫМ НОВЫМ ГОДОМ!

maccolit
January 14th, 1:09
Загадка календаря - что мы празднуем?
То есть, сегодня было бы 1 января, если бы мы не сменили календарь и продолжали бы жить по юлианскому?
Точно так же, как мы праздновали октябрьскую революцию 7 ноября, хотя она была 25 октября?

Следовательно, юлианский Новый год был бы у нас на 2 недели РАНЬШЕ, чем 1 января грегорианского. Как октябрьский переворот. Он раньше был, чем мы его потом праздновали.

Почему, чёрт возьми, мы празднуем его на 2 недели ПОЗЖЕ?"