хорошо забытое старое

и задачки для интервью.
User avatar
Abappy
Уже с Приветом
Posts: 2555
Joined: 26 Sep 2002 15:45
Location: North-East of NA

хорошо забытое старое

Post by Abappy »

Сразу прошу прощения у всех, кто эту задачку (в её классической формулировке) помнит. Но мне нужно проиллюстрировать пример для дискуссии, а она идеально к нему подходит.

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

Вопрос - куда лететь имеет больше смысла и почему.
User avatar
Binom
Уже с Приветом
Posts: 3924
Joined: 06 Jul 2009 01:09
Location: TAS → DFW

Re: хорошо забытое старое

Post by Binom »

На другую.
Существо же знает (оно же знает все-все-все?), что на той, куда они собрались, ничего нет, ну уж раз собрались, пусть летят, но чтобы еще и на остальные 999 999 997 зря не катались бы, написало, что они не то, что надо. Ну и вообще раз оно капризное, то решило "а пусть как они прогуляются", но чтобы долго не загулялись, то списочек неправильных планет и выдало - пожалело.
А если бы имело бы смысл лететь на ту, куда собрались лететь, то существо бы со своим списком и не лезло бы, раз они правильно лететь собрались. Всемогущее и всезнающее существо же просто капризное, а не вредитель, нет?
Я вот как то так думаю. :oops:
User avatar
Abappy
Уже с Приветом
Posts: 2555
Joined: 26 Sep 2002 15:45
Location: North-East of NA

Re: хорошо забытое старое

Post by Abappy »

Binom wrote: Всемогущее и всезнающее существо же просто капризное, а не вредитель, нет?
А кто его знает ... психология всемогущих и всезнающих существ дело тонкое. Для простоты будем считать что этим фактором стоит пренебречь.
vaduz
Уже с Приветом
Posts: 27652
Joined: 15 Jul 2002 17:05
Location: MD

Re: хорошо забытое старое

Post by vaduz »

Пофиг, до тех пор, пока степень капризности существа не оговорена.

Поскольку, например, его капризом может быть появление в тот момент, когда земляне собрались на планету с жизнью и перенаправление их на планету со смертельной ловушкой.
User avatar
venco
Уже с Приветом
Posts: 2001
Joined: 10 Nov 2004 00:34
Location: MD

Re: хорошо забытое старое

Post by venco »

vaduz wrote:Пофиг, до тех пор, пока степень капризности существа не оговорена.

Поскольку, например, его капризом может быть появление в тот момент, когда земляне собрались на планету с жизнью и перенаправление их на планету со смертельной ловушкой.
+1
User avatar
Rios
Уже с Приветом
Posts: 163
Joined: 26 Apr 2006 10:33
Location: YRV -> MSC -> NYC -> MD -> SFBA

Re: хорошо забытое старое

Post by Rios »

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

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

Edit: цифры, система Кирка - вероятность 1/(миллиярд-1), вторая система которая осталась после исключения всех кроме двух - вероятность 1/2. Думаю теперь Спок даст правильный совет :)
Last edited by Rios on 24 Jan 2011 18:54, edited 1 time in total.
“The only way to get something to turn up when you need it is to need it to turn up.” (c) Terry Pratchett
User avatar
Binom
Уже с Приветом
Posts: 3924
Joined: 06 Jul 2009 01:09
Location: TAS → DFW

Re: хорошо забытое старое

Post by Binom »

vaduz wrote:Пофиг, до тех пор, пока степень капризности существа не оговорена.

Поскольку, например, его капризом может быть появление в тот момент, когда земляне собрались на планету с жизнью и перенаправление их на планету со смертельной ловушкой.
Как это не оговорена? По условию оно дает список 100%-но безнадежных планет. Было бы иначе, то в условии было бы «якобы безнадежных» планет, и не спрашивалось бы «на какую из двух остающихся планет лететь?», а был бы вопрос «может ли капитан верить существу в том, что все те планеты безжизненны?».
User avatar
venco
Уже с Приветом
Posts: 2001
Joined: 10 Nov 2004 00:34
Location: MD

Re: хорошо забытое старое

Post by venco »

Binom wrote:
vaduz wrote:Пофиг, до тех пор, пока степень капризности существа не оговорена.

Поскольку, например, его капризом может быть появление в тот момент, когда земляне собрались на планету с жизнью и перенаправление их на планету со смертельной ловушкой.
Как это не оговорена? По условию оно дает список 100%-но безнадежных планет.
Не оговорено по какой причине была сообщена эта информация.
Сравните два экстремальных варианта:
1. Существо решило обязательно после выбора капитаном следующей планеты сообщить список из 999999997 безжизненных планет из остальных.
Этот вариант эквивалентен задаче Монти Холла, и выгодно поменять свой выбор.
2. Существо решило сообщить список из 999999997 безжизненных планет только если капитан выберет планету с жизнью.
Очевидно, в этом случае менять выбор бессмысленно.
User avatar
Binom
Уже с Приветом
Posts: 3924
Joined: 06 Jul 2009 01:09
Location: TAS → DFW

Re: хорошо забытое старое

Post by Binom »

venco wrote:
Binom wrote:
vaduz wrote:Пофиг, до тех пор, пока степень капризности существа не оговорена.

Поскольку, например, его капризом может быть появление в тот момент, когда земляне собрались на планету с жизнью и перенаправление их на планету со смертельной ловушкой.
Как это не оговорена? По условию оно дает список 100%-но безнадежных планет.
Не оговорено по какой причине была сообщена эта информация.
Сравните два экстремальных варианта:
1. Существо решило обязательно после выбора капитаном следующей планеты сообщить список из 999999997 безжизненных планет из остальных.
Этот вариант эквивалентен задаче Монти Холла, и выгодно поменять свой выбор.
2. Существо решило сообщить список из 999999997 безжизненных планет только если капитан выберет планету с жизнью.
Очевидно, в этом случае менять выбор бессмысленно.
Да, согласна. Если вариант 2, выбор менять нельзя (для первой планеты вероятность – 1, а для второй – 0). А если вариант 1, то вероятность и там и там ½. В таком случае, если причина не известна, значит рассматриваем оба варианта, и тогда для выбраной планеты вероятность ¾, а для второй – ¼. Вывод: планету не менять.
Офф. Ну и от везения тоже, многое зависит. Вон в Израиле, кажется, как-то два раза подряд в лотерее выпали одни и те же номера, а то какой –то дядька как-то, забыла, где выиграл миллион или даже несколько, но продолжил зачеркивать номера и в следующем розыгрыше снова выиграл что-то около миллиона. Правда, в случае с лотереей после каждого розыгрыша «счет обнуляется», и вероятность каждый раз 1/n, а не 1/(n-1), 1/(n-2) и так далее до 1/2 и потом 1/1, как в случае с планетами.
Мне же с моим «везением», даже если у меня вероятность (n-1)/n, а кого-то 1/n, то 100% выиграет тот второй, так что всякие лотерии не мой шанс разбогатеть, только «непосильным трудом» (с). Так и в случае с планетами: мне бы пришлось не то что две, а весь миллиард планет скрупулезно облетать.
User avatar
Abappy
Уже с Приветом
Posts: 2555
Joined: 26 Sep 2002 15:45
Location: North-East of NA

Re: хорошо забытое старое

Post by Abappy »

venco wrote:Не оговорено по какой причине была сообщена эта информация.
Сравните два экстремальных варианта:
1. Существо решило обязательно после выбора капитаном следующей планеты сообщить список из 999999997 безжизненных планет из остальных.
Этот вариант эквивалентен задаче Монти Холла, и выгодно поменять свой выбор.
2. Существо решило сообщить список из 999999997 безжизненных планет только если капитан выберет планету с жизнью.
Очевидно, в этом случае менять выбор бессмысленно.
venco - в этом собственно и вопрос - мы _не_знаем_ зачем существо этот список сообщило, что делать то ? :)
User avatar
venco
Уже с Приветом
Posts: 2001
Joined: 10 Nov 2004 00:34
Location: MD

Re: хорошо забытое старое

Post by venco »

Тогда приходится угадывать логику существа. Например, учесть, что на первую планету им позволили прилететь ничего не сообщив, что намекает на второй вариант поведения, т.е. с первой планетой не угадали - пусть летят, а во второй раз - угадали, давай их запутаем. Но тогда непонятно, что мешает просто соврать в списке. Откуда взялась уверенность, что в списке правдивая информация?
User avatar
Abappy
Уже с Приветом
Posts: 2555
Joined: 26 Sep 2002 15:45
Location: North-East of NA

Re: хорошо забытое старое

Post by Abappy »

venco wrote:Тогда приходится угадывать логику существа. Например, учесть, что на первую планету им позволили прилететь ничего не сообщив, что намекает на второй вариант поведения, т.е. с первой планетой не угадали - пусть летят, а во второй раз - угадали, давай их запутаем. Но тогда непонятно, что мешает просто соврать в списке. Откуда взялась уверенность, что в списке правдивая информация?
информация в списке правдивая по условиям задачи. Про мотивы существа по тем же условиям задачи ничего не известно. Зато известно, что существо капризное :umnik1:
User avatar
Binom
Уже с Приветом
Posts: 3924
Joined: 06 Jul 2009 01:09
Location: TAS → DFW

Re: хорошо забытое старое

Post by Binom »

venco wrote:Тогда приходится угадывать логику существа. Например, учесть, что на первую планету им позволили прилететь ничего не сообщив, что намекает на второй вариант поведения, т.е. с первой планетой не угадали - пусть летят, а во второй раз - угадали, давай их запутаем. Но тогда непонятно, что мешает просто соврать в списке. Откуда взялась уверенность, что в списке правдивая информация?
Ну тогда просто остается тупо облетать каждую планету. :pain1:
User avatar
venco
Уже с Приветом
Posts: 2001
Joined: 10 Nov 2004 00:34
Location: MD

Re: хорошо забытое старое

Post by venco »

Тогда я бы не менял выбора, а следующей проверил неупомянутую планету.
User avatar
venco
Уже с Приветом
Posts: 2001
Joined: 10 Nov 2004 00:34
Location: MD

Re: хорошо забытое старое

Post by venco »

Binom wrote:
venco wrote:Сравните два экстремальных варианта:
1. Существо решило обязательно после выбора капитаном следующей планеты сообщить список из 999999997 безжизненных планет из остальных.
Этот вариант эквивалентен задаче Монти Холла, и выгодно поменять свой выбор.
2. Существо решило сообщить список из 999999997 безжизненных планет только если капитан выберет планету с жизнью.
Очевидно, в этом случае менять выбор бессмысленно.
Да, согласна. Если вариант 2, выбор менять нельзя (для первой планеты вероятность – 1, а для второй – 0). А если вариант 1, то вероятность и там и там ½.
Я могу предложить ещё вариант, при котором вероятность для первой планеты - 0. ;)
В таком случае, если причина не известна, значит рассматриваем оба варианта, и тогда для выбраной планеты вероятность ¾, а для второй – ¼.
Тут надо ещё учесть нашу априорную оценку вероятностей, что существо ведёт себя по какому-либо варианту, и обработать Байесом.
User avatar
Binom
Уже с Приветом
Posts: 3924
Joined: 06 Jul 2009 01:09
Location: TAS → DFW

Re: хорошо забытое старое

Post by Binom »

Binom wrote:
venco wrote:Тогда приходится угадывать логику существа. Например, учесть, что на первую планету им позволили прилететь ничего не сообщив, что намекает на второй вариант поведения, т.е. с первой планетой не угадали - пусть летят, а во второй раз - угадали, давай их запутаем. Но тогда непонятно, что мешает просто соврать в списке. Откуда взялась уверенность, что в списке правдивая информация?
Ну тогда просто остается тупо облетать каждую планету. :pain1:
Update.
Но скорее всего, оно не врет, если эта задача по аналогии с задачей Монти Холла. Ведь на шоу Монти Холл не обманывает, хотя может быть и рад бы соврать, но же он открывает дверь и все видят, что там коза. Так и здесь – оно дало список, считай открыло двери (т.е. подразумевается, что существо капризное, но не врун), как в рассказе у не_помню_кого (думала Рэй Бредбери, но недавно там искала, и у него не нашла, может Гарри Гаррисон?) про мешок, он не врал, но просто не говорил ничего, если его об этом не спрашивали.
User avatar
Binom
Уже с Приветом
Posts: 3924
Joined: 06 Jul 2009 01:09
Location: TAS → DFW

Re: хорошо забытое старое

Post by Binom »

venco wrote:Тут надо ещё учесть нашу априорную оценку вероятностей, что существо ведёт себя по какому-либо варианту, и обработать Байесом.
:yad:
вот так примерно? только в миллиард раз больше?
You do not have the required permissions to view the files attached to this post.
User avatar
vlad12345
Уже с Приветом
Posts: 605
Joined: 14 Feb 2002 10:01
Location: Russia

Re: хорошо забытое старое

Post by vlad12345 »

Abappy wrote:информация в списке правдивая по условиям задачи.
Что-то не нахожу, где это видно в условиях задачи. Вообще-то в задаче Монти Холла довольно много дополнительных подробностей, вот например как в википедии описывается
A fully unambiguous, mathematically explicit version of the standard problem is:
Suppose you're on a game show and you're given the choice of three doors [and will win what is behind the chosen door]. Behind one door is a car; behind the others, goats [unwanted booby prizes]. The car and the goats were placed randomly behind the doors before the show. The rules of the game show are as follows: After you have chosen a door, the door remains closed for the time being. The game show host, Monty Hall, who knows what is behind the doors, now has to open one of the two remaining doors, and the door he opens must have a goat behind it. If both remaining doors have goats behind them, he chooses one [uniformly] at random. After Monty Hall opens a door with a goat, he will ask you to decide whether you want to stay with your first choice or to switch to the last remaining door.
Поскольку в задаче с существом ничего такого не дано, то, имхо, и пользы от его информации ничуть не больше, как если бы оно сообщило, ну например, что его зовут Вася Пупкин. А потому не стоит обращать на него внимание и продолжать следовать до того выбранному маршруту - наверняка он был как-то оптимизирован исходя из реальных критериев и не имеет смысла отклоняться из-за чьих-то капризов.
User avatar
Abappy
Уже с Приветом
Posts: 2555
Joined: 26 Sep 2002 15:45
Location: North-East of NA

Re: хорошо забытое старое

Post by Abappy »

vlad12345 wrote:
Abappy wrote:информация в списке правдивая по условиям задачи.
Что-то не нахожу, где это видно в условиях задачи. Вообще-то в задаче Монти Холла довольно много дополнительных подробностей
В условиях задачи сказано "список безжизненных планет" (а не список планет, которые по утверждению существа безжизненны). А задача да - базируется на задаче Монти Холла (собственно я честно в начале это и сказал). Остающийся открытым вопрос - что делать с неизвестным фактором ? :)
User avatar
Binom
Уже с Приветом
Posts: 3924
Joined: 06 Jul 2009 01:09
Location: TAS → DFW

Re: хорошо забытое старое

Post by Binom »

Еще раз почитала про Парадокс Монти Холла здесь.
По теории вероятностей, вроде да, надо менять. (1/3 vs 2/3 в случае с козлами и 1/1000000000 vs 999999999/1000000000 в случае с планетами).
А по логике, когда перед вами выбор из 2 вариантов, а не из 3 (или миллиарда), то это уже новый выбор, и вероятность у каждого ½.
Придется на досуге на практике проверить, что реально работает: теория вероятностей или житейская логика. Там в комментах народ говорит, проверяли, и таки да, надо менять.
User avatar
Abappy
Уже с Приветом
Posts: 2555
Joined: 26 Sep 2002 15:45
Location: North-East of NA

Re: хорошо забытое старое

Post by Abappy »

Binom wrote:А по логике, когда перед вами выбор из 2 вариантов, а не из 3 (или миллиарда), то это уже новый выбор, и вероятность у каждого ½.
если бы Вас заставили забыть - какой выбор Вы сделали перед этим, то выбор был бы новым, а так - Вы знаете какой был старый выбор :)
User avatar
Rios
Уже с Приветом
Posts: 163
Joined: 26 Apr 2006 10:33
Location: YRV -> MSC -> NYC -> MD -> SFBA

Re: хорошо забытое старое

Post by Rios »

Коли уж пошла такая пьянка. Тоже нашумевшее, но может кто пропустил:
I have two children, one of whom is a son born on a Tuesday. What is the probability that I have two boys?
Follow up: http://en.wikipedia.org/wiki/Boy_or_Girl_paradox

Вероятности не такая уж и интуинтивная вешь, местами.
“The only way to get something to turn up when you need it is to need it to turn up.” (c) Terry Pratchett
User avatar
Rios
Уже с Приветом
Posts: 163
Joined: 26 Apr 2006 10:33
Location: YRV -> MSC -> NYC -> MD -> SFBA

Re: хорошо забытое старое

Post by Rios »

deleted
Last edited by Rios on 25 Jan 2011 21:06, edited 1 time in total.
“The only way to get something to turn up when you need it is to need it to turn up.” (c) Terry Pratchett
Hamster
Уже с Приветом
Posts: 11475
Joined: 20 Nov 2000 10:01
Location: Escondido, CA

Re: хорошо забытое старое

Post by Hamster »

Rios wrote:I have two children, one of whom is a son born on a Tuesday. What is the probability that I have two boys?
50%
Протоукр
User avatar
Binom
Уже с Приветом
Posts: 3924
Joined: 06 Jul 2009 01:09
Location: TAS → DFW

Re: хорошо забытое старое

Post by Binom »

Abappy wrote:
Binom wrote:А по логике, когда перед вами выбор из 2 вариантов, а не из 3 (или миллиарда), то это уже новый выбор, и вероятность у каждого ½.
если бы Вас заставили забыть - какой выбор Вы сделали перед этим, то выбор был бы новым, а так - Вы знаете какой был старый выбор :)
Но тогда это уже задача из области психологии. :)

Return to “Головоломки”