задачка

[avva]

Любопытная задачка, которую советую попробовать решить без бумаги, в уме. Условие похоже на знаменитую задачу Монти Холла, но на самом деле это о другом. Ссылку на то, откуда взял задачу, потом добавлю.

Три двери: за одной машина, за другой ключи от машины, за третьей - козел. Играют два игрока вместе, причем задача одного - найти машину, а другого - ключи. Сначала второго игрока уводят за кулисы, и играет один первый. У него есть две попытки найти машину: открыть одну дверь, если машины за ней нет - тогда еще одну. Если ему удается найти машину, то двери, которые он открыл, закрывают, и вводят второго игрока. Однако им теперь запрещено общаться между собой и вообще как-либо передавать информацию. Второй игрок должен найти ключи, тоже за две попытки.

Только если им удается найти и машину и ключи, игроки получают машину с ключами, а иначе они получают в подарок козла. Можете ли вы найти стратегию, которая позволит им получить машину в 2/3 случаев?

Update: randomisator первым правильно ответил. Я буду скрывать поначалу правильные ответы, но в какой-то момент перестану, так что если не хотите спойлеров, не заглядывайте в комментарии, пока сами не подумаете. Да, добавлю, что такая стратегия действительно есть.

Comments

[lusever.livejournal.com]

Тупо открывать две первые двери напр. слева?

[avva.livejournal.com]

Нет.

[marat-yuldashev.livejournal.com]

Нет.

[marat-yuldashev.livejournal.com]

1/2 получается, 2/3 - нет

[rezoner.livejournal.com]

Единственная информация, которая может быть доступна второму - в каком порядке открывал двери первый. Отсяда и пляшем.

Без потери общности, пусть первый открывает двери в порядке 1,2.

Дальше появляется эффект Монти Холла, и состоит он в том, что если второму игроку предлагают поиграть, то это значит, что машина была с вероятностью 1/2 за первой дверью или за второй. А ключи, соответственно, с вероятностью 1/2 за третьей, 1/4 за первой и 1/4 - за второй.

Значит, вероятность найти машину для первого игрока 2/3, а найти ключи для второго, при оптимальной игре, 1/2+1/4=3/4, и общая их вероятность выиграть - 1/2.

Вообще, поскольку у первого 2/3, трудно найти такую стратегию, которая бы довела вероятность успеха второго до 1. Так что мой ответ - нет.

[avva.livejournal.com]

Разумные рассуждения. И все же кое-что они упускают...

[(Anonymous)]

Первый открывает 1 и 2 дверь, второй, соответственно 2 и 3.

[avva.livejournal.com]

Неа.

[randomisator.livejournal.com]

Первый открывает 1 дверь. Если там козел - открывает 2. Если ключ - открывает 3.
Допустим, первый нашёл машину. Второй открывает 3 дверь. Если там машина - значит ключ за 1 дверью (так как мы уже знаем, что первый нашёл машину, а 3 дверь он открывает только если за 1 ключ). Если там козел - значит первый выиграл сразу и ключ за 2 дверью.

[avva.livejournal.com]

Верно (первое верное решение). Заскриню пока ваш комментарий.

[gershshpraihler.livejournal.com]

первый находит машину с вероятностью 2/3.
они должны договориться так:
первый проверяет первые две двери.
если он находит там ключи, он берёт их и не общаясь передаёт второму.
если не передал, второй идёт прямиком в третью дверь.

[avva.livejournal.com]

Нет, этот и другие "трюки" не проходят, решение "честное". Первый не может второму ничего передавать, естественно.

[grom20.livejournal.com]

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

[avva.livejournal.com]

Не, так не сработает.

[lazyreader.livejournal.com]

Первый игрок всегда открывает сначала первую дверь. Если там ключи - он смотрит вторую; если козёл - третью. С вероятностью 2/3 он находит машину.

Второй использует знание того факта, что первый игрок машину нашёл, раз он, второй, вступил в игру. Второй смотрит сперва за второй дверью. Если там ключи - отлично; если там машина - то (думает второй) первый игрок нашёл ключи за первой дверью, и второй открывает первую; если второй находит за второй дверью козла, то, значит, ключи за третьей.

[avva.livejournal.com]

Ага, все верно. Заскриню на время.

[(Anonymous)]

Хорошо, а может ли первый участник оставить открытую дверь с козлом (если он его найдёт с первой же попытки) и не открывать другую дверь?

[avva.livejournal.com]

Нет, не может (но это ему не помогло бы).

[rezoner.livejournal.com]

А, понятно.
Если в первой ключи - то открывает потом третью.
Если в первой козел - то открывает потом вторую.

Второй участник открывает третью, и если там ничего нет - то открывает первую.

[mudak.livejournal.com]

А вот и нет, хехе.

"Если в первой козел - то открывает потом вторую.
Второй участник открывает третью, и если там ничего нет - то открывает первую."

Опять у второго не 100%.

[withinsmilie.livejournal.com]

первый откывает дверь А, если там козел то открывает дверь Б иначе дверь В
воторой открывает дверь В, если там козел, то открывает А, иначе Б

не знаю, как сформулировать принцип в общем случае, идея в том, что два успешных варианта получиться если ключи за дверью В, а в другом случае "перекрестные" действия, приведут к тому, что если "промахиваются", то оба

[withinsmilie.livejournal.com]

получится, конечно

[spamsink.livejournal.com]

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

[avva.livejournal.com]

Из общего контекста понятно, думаю.

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

первый:
открывает первую дверь. если там козёл, то он открывает вторую дверь. если там ключи, то он открывает третью дверь. если там машина, то он сидит довольный. это у нас получается шанс найти машину 2/3.

второй:
если его пустили играть, значит, он знает, что действия первого принесли результат, и он нашёл машину. он открывает вторую дверь. если там машина, то козёл в первой, а ключи в третьей. если там ключи, то ура. если там козёл, то… блин, вот тут, как ни крути, 50% получается.

[avva.livejournal.com]

Верно.

[griffon.livejournal.com]

Первый открывает первую дверь. Если там машина, то он останавливается. Если козёл, то он открывает вторую дверь, если ключи, то третью. В случае, если первый так и не находит машину, то они проиграли.

Второй открывает третью дверь. Если там ключи, то всё хорошо, если там машина, то он открывает первую, если козёл, то вторую. В предположении, что первый нашёл машину, второй находит ключи всегда.

[avva.livejournal.com]

Верно.

[dmblit.livejournal.com]

Первый открывает первую дверь, дабы не умножать энтропию.
В случае отсутствия там машины действует по ситуации:
- нашел ключ: открыл третью дверь;
- не нашел: открыл вторую.

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


Была замечательная задача про казнь тысячи мудрецов в разноцветных колпаках. Вроде бы, это как раз она ;)

[avva.livejournal.com]

Да, все верно. Кажется, не совсем она, но я точно не помню (про мудрецов и колпаки есть много вариантов).

[esperador.livejournal.com]

А может ли второй игрок из-за кулис каким-либо образом (аплодисменты зрителей и т.п.)определить, одну или две попытки использовал первый? Если да, то решение очевидно: договориться о порядке, в каком будут открываться двери и тогда второй игрок открывает 2 и 3 либо 1 и 3, если первый сделал 1 или 2 попытки соответственно.

Но ведь не может быть все так просто в этом ЖЖ? ) Тогда надо подумать...

[avva.livejournal.com]

Не может :)

[alexeybobkov]

Офигеть. И правда решается.

Первый игрок открывает левую дверь:
- если видит машину (C), он больше ничего не открывает;
- если видит ключи (K), откравает среднюю дверь;
- если видит козла (G), откравает правую дверь.

Таким образом, первый игрок найдет машину (и второй игрок начнёт выбирать) при следующих комбинациях (4 из 6, т.е. в 2/3 случаев):

1) CKG
2) CGK
3) KCG
4) GKC

Второй игрок открывает среднюю дверь. Или он сразу находит ключи (1,4), или находит машину и тогда открывает левую дверь (3), или находит козла и тогда открывает правую дверь (2).

[avva.livejournal.com]

Да, все верно. Красиво, правда?

[izblank.livejournal.com]

Первый открывает 1, а потом, если там ключ, то 2, иначе 3. Второй открывает 3. Если там машина, тогда 2, если козел, тогда 1. То есть, вероятность для первого 2/3, а второй находит ключ с вероятностью 1.

[avva.livejournal.com]

Нет, не работает. Если в 1 машина, в 3 козел, то второй не найдет ключ.

[kapla55.livejournal.com]

В принципе, для знакомых с группами и кольцами задача элементарная.

Есть аналогичная задача:

Четырех мегамозгов по имени А, Б, В, Г приговорили к смерти. Единтсвенная возможность получить помилование, если каждый угадает конверт со своим именем.

Они по очериди заходят в комнату в которой на столе лежат 4 закрытых конверта подписаных 1, 2, 3, 4. Можно открыть не больше двух конвертов. В каждом конверте лежит листок подписаный А, Б, В или Г. Если мегамозг находит свое имя то он выходит в отдельную комнату и не может общаться с остальными. Если хотя бы один не найдет свое имя за 2 попытки, то их всех повесят.

Нужно найти стратегию максимизурующую шанс выжить.
Имеется стратегия дающая 5/12 на выживание.

[prosto-tak.livejournal.com]

А можно решение с группами и кольцами? А то мое решение какое-то не очень продвинутое :)

[zanudka.livejournal.com]

первый всегда открывает первую дверь. если там машина - больше попыток у него нет. если ключи - он открывает вторую дверь; если козёл - третью.
вероятность того, что первый игрок нашёл машину - 2/3.

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

решила на бумаге, увы :)

[avva.livejournal.com]

Все правильно! На бумаге тоже хорошо :)

[bukky-boogwin.livejournal.com]

Перенумеруем двери. Первый открывает дверь 1. Если там ключи, следующей он открывает дверь 2, если козел - дверь 3, если машина - ничего больше не открывает. Второй открывает дверь 2. Если там оказывается козел, то за дверью 1 либо машина, либо ключи, но будь там ключи, первый игрок тоже открыл бы дверь 2, не нашел бы машины (а нашел бы козла), и на там бы все закончилось, так что за дверью 1 машина, а ключи, соответственно, за дверью 3, которую и надлежит открыть второму. Если второму за дверью 2 попадается машина, значит, за дверью 1 либо козел, либо ключи, но будь там козел, первый открыл бы дверь 3, не нашел бы машину (раз она за дверью 2), и на этом тоже все закончилось бы, так что за дверью 1 ключи, и ее-то в этом случае второй и должен открыть. Наконец, если за дверью 2 второй игрок найдет ключи, он просто выиграл. Итог: если первый игрок нашел машину (вероятность чего - как раз 2/3), то второй в любом случае (то есть с вероятностью 1) отыскивает ключи. (2/3)*1=2/3.

[avva.livejournal.com]

Все верно, да.

[vasja-iz-aa.livejournal.com]

второй игрок первым ходом открывает ту дверь, в которую первый игрок пойдет увидив ключ в свой первый ход? Ключ там он может встретить случайно, а два остальных варианта подскажут второй ход, если машина -- то идти в первую дверь первого игрока.

[avva.livejournal.com]

Ага.

[melkore.livejournal.com]

нужно терпеливо ждать, пока козёл проголодается и заблеет. ))

если сурьёзно: рассуждения те же, что в притче о колпаках, только мудрецов два, а цветов - три. первый открывает левую дверь. если там ключи - центральную. если козёл - правую. если машина - пофиг. если второго вызывают, то второй по умолчанию понимает, что первый нашел машину. он открывает центральную дверь и видит там...
если ключи - значит хорошо. если машину - значит ключи в левой. если козла - значит ключи в правой. получается, что у первого шанс 2/3, а у второго твёрдая единица.
честно не смотрел другие ответы, просто приходилось решать у Перельмана такие задачки. )))

[avva.livejournal.com]

:) да, все верно.

[jozhin.livejournal.com]

пронумеруем двери.
первый игрок открывает дверь номер 1. если там козел, он открывает дверь 2, если там ключи - он открывает дверь номер 3.
второй игрок открывает дверь номер 3. если там машина - то ключи за дверью номер 1. если там козел - то ключи за дверью номер 2.

[enot-kurdiuk.livejournal.com]

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