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

[a_shen]

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

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

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

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

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

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

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

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

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

Comments

[janatem.livejournal.com]

Что-нибудь об изначальном распределении шаров известно? Или вся соль в том, что это не так?

[a-shen.livejournal.com]

со стороны противника никаких вероятностей, алгоритм должен работать (с указанными требованиями) при любой последовательности шаров

[http://users.livejournal.com/_winnie/]

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

Я сомневаюсь, что есть работающий алгоритм выбора ледяного шара, если противник кидает двустороннюю честную монетку для выбора ледяного/стеклянного шара с вероятностью 1/2. Очень удивлюсь, что замена честной монеты на псевдослучайную сколь угодно сложную - окажется принципиальной для решения.

[a-shen.livejournal.com]

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

Более тонкий вопрос - если следующие шары на ленте противник выбирает по нашим ходам, то наша задача усложняется (но решение всё равно работает)

[a-shen.livejournal.com]

прошу прощения, не заметил - вычислимость последовательности шаров на ленте не предполагается (игра против вычислимого противника, вообще говоря, может быть легче)

[slazav.livejournal.com]

Не очень понял последнюю фразу про ленту и монету...
И еще непонятно про разные времена таяния: получается, что про любой проехавший нерастаявший шар мы не можем быть уверены, что он не ледяной? А противник может управлять не только материалом, но им временем таянья?

[a-shen.livejournal.com]

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

да - про любой нерастаявший шар мы не можем быть уверены ни в какой момент, что он не ледяной (но мы вполне можем ждать, пока он растает - это не нарушает условий)

[a-shen.livejournal.com]

offtopic - мне тут показали навигатор etrex 20, которой с лёгкостью обнаруживает спутники и даже глонасс ловит, я пробовал туда загрузить отсканированный кусок растровой карты, пользуясь инструкциями, через google maps и совмещение там скана с их картой, но не довёл дело до конца, пора было отдавать устройство. Ты не знаешь, это действует?

[slazav.livejournal.com]

Нет, увы, тут я тоже не специалист...

Я, вроде, видел загруженные растровые карты в новые garmin'ы - но совсем издалека и, кажется, там было что-то типа oregon'а или 62-го. Про etrex 20 в первый раз услышал от тебя.

[edwardahirsch.livejournal.com]

У avsmal eTrex Vista HCx и вроде бы там нет растровых карт (т.е., как минимум, он не нашёл, как бы можно было их использовать).

[slazav.livejournal.com]

etrex, etrex vista и etrex 20 это совсем разные вещи...

[edwardahirsch.livejournal.com]

Как сложно-то всё :) Что брать-то, когда мой 76csx издохнет?

[a-shen.livejournal.com]

etrex 20 мне очень понравился и вроде там утверждается, что с растровыми картами не должно быть проблем - но только я не успел в этом сам убедиться...

[slazav.livejournal.com]

А не знаю. У нас много кто 62-й использует. Oregon и Colorado как-то не пошли, про etrex 20 я только сейчас узнал...
Сам испаользую еще черно-белый map60. etrex vista и etrex legend (со всякими буковками), тоже хорошие (и относительно дешевые), цветной 60-й - тоже хорошо.

[buddha239.livejournal.com]

Сначала подумал, что это невозможно, а потом понял, что это совсем просто.:) С вероятностью 1% взять первый шар. Если не взяли - с вероятностью 1% (можно - 1/99:)) взять ша сразу после того, как первый растает (если растает).:) Если тот "второй" шар не взяли, то с вероятностью 1% (можно - 1/98:)) взять "третий" шар сразу после того, как растает "второй" (если растает). И.т.д. Очевидно, можно считать, что номера "второго", "третьего" и т.д. шаров заданы изначально (иначе все просто усреднитс по этим данным). Для удобства можно еще считать, что "к-ый" шар действительно будет к-ым (так как на остальные мы все равно не смотрим). Тогда получается, что если первый стеклянный шар - "р-тый", то мы возьмем его с вероятностью не больше 1%, (а с вероятностью 99% не возьмем вообще ничего). Если же все шары ледяные, то мы рано или поздно что-то возьмем с вероятностью 1 (в варианте :)) - не позже "сотого" шара:)).

[buddha239.livejournal.com]

Пардон за пропущенные буквы; клавиатура так себе.

[a-shen.livejournal.com]

Спасибо - см. update, где выделена существенная часть задачи и решения (которое в сущности сводится к выбору случайного числа проб перед взятием изделия в тайне)

[http://users.livejournal.com/_winnie/]

А как это работает, если на входе - последовательность шаров, каждый из которых ледяной с вероятностью 1/2 ? Пусть для упрощения они даже тают сразу, как только проехали мимо.

Вот я беру по тем или иным причинам текущий шар, всё что мы видели про предыдущие шары - не даёт информации о том, какой шар нам попался сейчас?

Такое ощущение, что я не понял условие и не увидел какого-то ограничения на противника, выкладыющего шары.

Попробовал составить программку на питоне, которая ведёт как описанный алгоритм, таки в половине случаев она берёт стеклянный шар:

import random

previous_sphere_melted = False

while 1:
  ice = (random.randint(0, 1) == 1) #противник выбирает случайный шар
  
  if previous_sphere_melted: #какой-то шар растаял. таят они сразу после прохождения мимо нас.
    if random.randint(1, 100) == 1: #в 1% случаев...
      print ice
      break
  
  previous_sphere_melted = (ice == True) #таят шары сразу после прохождения мимо нас.

[a-shen.livejournal.com]

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

[(Anonymous)]

Программа неправильная, она не соответствует описанному алгоритму. Если первый шар не взят (вероятность чего 99%) и не расстаял (был стеклянным), то мы уже больше никогда и ничего не возьмем.

[buddha239.livejournal.com]

А разве это запрещено?:)

[(Anonymous)]

Разрешено, конечно. Алгоритм у вас правильный :)
Но некоторые программисты не могут быстро и безошибочно реализовать его на питоне

[buddha239.livejournal.com]

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

[corbulon.livejournal.com]

Непонятно: последовательность шаров на ленте - случайная, с неизвестной, но постоянной вероятностью появления 0 и 1 или другая?
А если случайная и при этом процесс марковский?

[a-shen.livejournal.com]

про последовательность шаров на ленте неизвестно ничего, алгоритм должен обеспечивать выполнение требований при любой последовательности (если не все ледяные, то должен брать ледяной или ничего в итоге не брать с вероятностью 99%, если все ледяные, должен брать рано или поздно с вероятностью 100%)

[marknn.livejournal.com]

Ха, а вот эта статья на самом деле рассматривает очень близкую задачу но слегка в другом контексте (опередить можно ли доверять индивидуальным пользователям в большой группе, если для каждого пользователя можно либо его проверить, либо в слепую принять, с целью чтобы число пропущенных плохих пользователей было маленьким)
и в чуть более общей формулировке http://dl.acm.org/citation.cfm?id=1772779

несмотря на то, что алгоритм, по большому счету тривиальный, аккуратный анализ оказался достаточно сложным в связи с тем что продавец (пользователь) может менять свою стратегию.... Было бы интересно ваше мнение о статье.

[66george.livejournal.com]

А почему никто не пишет популярных книжек по эллиптической геометрии? По Лобачевского есть, встречал по проективной и конформной, а по эллиптической ни разу. Притом, она самая простая.