?

Log in

задачка - Поклонник деепричастий [entries|archive|friends|userinfo]
Anatoly Vorobey

[ website | Website ]
[ userinfo | livejournal userinfo ]
[ archive | journal archive ]

Links
[Links:| English-language weblog ]

задачка [июл. 17, 2009|08:55 pm]
Anatoly Vorobey
Любопытная задачка, которую советую попробовать решить без бумаги, в уме. Условие похоже на знаменитую задачу Монти Холла, но на самом деле это о другом. Ссылку на то, откуда взял задачу, потом добавлю.

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

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

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

Comments:
Страница 1 из 2
<<[1] [2] >>
[User Picture]From: lusever
2009-07-17 06:18 pm
Тупо открывать две первые двери напр. слева?
(Ответить) (Thread)
[User Picture]From: avva
2009-07-17 06:20 pm
Нет.
(Ответить) (Parent) (Thread)
[User Picture]From: marat_yuldashev
2009-07-17 06:23 pm
Нет.
(Ответить) (Thread)
[User Picture]From: marat_yuldashev
2009-07-17 06:28 pm
1/2 получается, 2/3 - нет
(Ответить) (Parent) (Thread) (Развернуть)
[User Picture]From: rezoner
2009-07-17 06:27 pm
Единственная информация, которая может быть доступна второму - в каком порядке открывал двери первый. Отсяда и пляшем.

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

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

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

Вообще, поскольку у первого 2/3, трудно найти такую стратегию, которая бы довела вероятность успеха второго до 1. Так что мой ответ - нет.
(Ответить) (Thread)
[User Picture]From: avva
2009-07-17 06:35 pm
Разумные рассуждения. И все же кое-что они упускают...
(Ответить) (Parent) (Thread)
(Скрытый комментарий)
From: (Anonymous)
2009-07-17 06:33 pm
Первый открывает 1 и 2 дверь, второй, соответственно 2 и 3.
(Ответить) (Thread)
[User Picture]From: avva
2009-07-17 06:35 pm
Неа.
(Ответить) (Parent) (Thread)
[User Picture]From: randomisator
2009-07-17 06:36 pm
Первый открывает 1 дверь. Если там козел - открывает 2. Если ключ - открывает 3.
Допустим, первый нашёл машину. Второй открывает 3 дверь. Если там машина - значит ключ за 1 дверью (так как мы уже знаем, что первый нашёл машину, а 3 дверь он открывает только если за 1 ключ). Если там козел - значит первый выиграл сразу и ключ за 2 дверью.
(Ответить) (Thread)
[User Picture]From: avva
2009-07-17 06:37 pm
Верно (первое верное решение). Заскриню пока ваш комментарий.
(Ответить) (Parent) (Thread)
From: gershshpraihler
2009-07-17 06:36 pm
первый находит машину с вероятностью 2/3.
они должны договориться так:
первый проверяет первые две двери.
если он находит там ключи, он берёт их и не общаясь передаёт второму.
если не передал, второй идёт прямиком в третью дверь.
(Ответить) (Thread)
[User Picture]From: avva
2009-07-17 06:40 pm
Нет, этот и другие "трюки" не проходят, решение "честное". Первый не может второму ничего передавать, естественно.
(Ответить) (Parent) (Thread)
[User Picture]From: grom20
2009-07-17 06:40 pm
Договариваются, первый открывает сначала среднюю, если там ключи, то открывает например правую дверь, если козел, то левую.
второй аналогично смотрит среднюю, но действует наоборот
(Ответить) (Thread)
[User Picture]From: avva
2009-07-17 06:42 pm
Не, так не сработает.
(Ответить) (Parent) (Thread)
From: lazyreader
2009-07-17 06:41 pm
Первый игрок всегда открывает сначала первую дверь. Если там ключи - он смотрит вторую; если козёл - третью. С вероятностью 2/3 он находит машину.

Второй использует знание того факта, что первый игрок машину нашёл, раз он, второй, вступил в игру. Второй смотрит сперва за второй дверью. Если там ключи - отлично; если там машина - то (думает второй) первый игрок нашёл ключи за первой дверью, и второй открывает первую; если второй находит за второй дверью козла, то, значит, ключи за третьей.
(Ответить) (Thread)
[User Picture]From: avva
2009-07-17 06:42 pm
Ага, все верно. Заскриню на время.
(Ответить) (Parent) (Thread)
From: (Anonymous)
2009-07-17 06:46 pm
Хорошо, а может ли первый участник оставить открытую дверь с козлом (если он его найдёт с первой же попытки) и не открывать другую дверь?
(Ответить) (Thread)
[User Picture]From: avva
2009-07-17 07:36 pm
Нет, не может (но это ему не помогло бы).
(Ответить) (Parent) (Thread)
[User Picture]From: rezoner
2009-07-17 06:51 pm
А, понятно.
Если в первой ключи - то открывает потом третью.
Если в первой козел - то открывает потом вторую.

Второй участник открывает третью, и если там ничего нет - то открывает первую.
(Ответить) (Thread)
From: mudak
2009-07-17 06:56 pm
А вот и нет, хехе.

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

Опять у второго не 100%.
(Ответить) (Parent) (Thread) (Развернуть)
[User Picture]From: withinsmilie
2009-07-17 06:52 pm
первый откывает дверь А, если там козел то открывает дверь Б иначе дверь В
воторой открывает дверь В, если там козел, то открывает А, иначе Б

не знаю, как сформулировать принцип в общем случае, идея в том, что два успешных варианта получиться если ключи за дверью В, а в другом случае "перекрестные" действия, приведут к тому, что если "промахиваются", то оба
(Ответить) (Thread)
[User Picture]From: withinsmilie
2009-07-17 06:52 pm
получится, конечно
(Ответить) (Parent) (Thread)
[User Picture]From: spamsink
2009-07-17 06:53 pm
Из условия неочевидно, что игроки до начала игры могут обсуждать, как им действовать.
(Ответить) (Thread)
[User Picture]From: avva
2009-07-17 07:23 pm
Из общего контекста понятно, думаю.
(Ответить) (Parent) (Thread)
[User Picture]From: _1313
2009-07-17 06:54 pm
первый:
открывает первую дверь. если там козёл, то он открывает вторую дверь. если там ключи, то он открывает третью дверь. если там машина, то он сидит довольный. это у нас получается шанс найти машину 2/3.

второй:
если его пустили играть, значит, он знает, что действия первого принесли результат, и он нашёл машину. он открывает вторую дверь. если там машина, то козёл в первой, а ключи в третьей. если там ключи, то ура. если там козёл, то… блин, вот тут, как ни крути, 50% получается.
(Ответить) (Thread)
[User Picture]From: avva
2009-07-17 07:34 pm
Верно.
(Ответить) (Parent) (Thread) (Развернуть)
[User Picture]From: griffon
2009-07-17 07:05 pm
Первый открывает первую дверь. Если там машина, то он останавливается. Если козёл, то он открывает вторую дверь, если ключи, то третью. В случае, если первый так и не находит машину, то они проиграли.

Второй открывает третью дверь. Если там ключи, то всё хорошо, если там машина, то он открывает первую, если козёл, то вторую. В предположении, что первый нашёл машину, второй находит ключи всегда.
(Ответить) (Thread)
[User Picture]From: avva
2009-07-17 07:33 pm
Верно.
(Ответить) (Parent) (Thread)
[User Picture]From: dmblit
2009-07-17 07:09 pm
Первый открывает первую дверь, дабы не умножать энтропию.
В случае отсутствия там машины действует по ситуации:
- нашел ключ: открыл третью дверь;
- не нашел: открыл вторую.

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


Была замечательная задача про казнь тысячи мудрецов в разноцветных колпаках. Вроде бы, это как раз она ;)
(Ответить) (Thread)
[User Picture]From: avva
2009-07-17 07:33 pm
Да, все верно. Кажется, не совсем она, но я точно не помню (про мудрецов и колпаки есть много вариантов).
(Ответить) (Parent) (Thread)
[User Picture]From: esperador
2009-07-17 07:30 pm
А может ли второй игрок из-за кулис каким-либо образом (аплодисменты зрителей и т.п.)определить, одну или две попытки использовал первый? Если да, то решение очевидно: договориться о порядке, в каком будут открываться двери и тогда второй игрок открывает 2 и 3 либо 1 и 3, если первый сделал 1 или 2 попытки соответственно.

Но ведь не может быть все так просто в этом ЖЖ? ) Тогда надо подумать...
(Ответить) (Thread)
[User Picture]From: avva
2009-07-17 07:33 pm
Не может :)
(Ответить) (Parent) (Thread)
[User Picture]From: alexeybobkov
2009-07-17 07:36 pm
Офигеть. И правда решается.

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

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

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

Второй игрок открывает среднюю дверь. Или он сразу находит ключи (1,4), или находит машину и тогда открывает левую дверь (3), или находит козла и тогда открывает правую дверь (2).
(Ответить) (Thread)
[User Picture]From: avva
2009-07-17 07:39 pm
Да, все верно. Красиво, правда?
(Ответить) (Parent) (Thread) (Развернуть)
[User Picture]From: izblank
2009-07-17 07:50 pm
Первый открывает 1, а потом, если там ключ, то 2, иначе 3. Второй открывает 3. Если там машина, тогда 2, если козел, тогда 1. То есть, вероятность для первого 2/3, а второй находит ключ с вероятностью 1.
(Ответить) (Thread)
[User Picture]From: avva
2009-07-17 08:17 pm
Нет, не работает. Если в 1 машина, в 3 козел, то второй не найдет ключ.
(Ответить) (Parent) (Thread) (Развернуть)
From: kapla55
2009-07-17 08:06 pm
В принципе, для знакомых с группами и кольцами задача элементарная.

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

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

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

Нужно найти стратегию максимизурующую шанс выжить.
Имеется стратегия дающая 5/12 на выживание.
(Ответить) (Thread)
[User Picture]From: prosto_tak
2009-07-18 02:39 am
А можно решение с группами и кольцами? А то мое решение какое-то не очень продвинутое :)
(Ответить) (Parent) (Thread)
[User Picture]From: zanudka
2009-07-17 08:15 pm
первый всегда открывает первую дверь. если там машина - больше попыток у него нет. если ключи - он открывает вторую дверь; если козёл - третью.
вероятность того, что первый игрок нашёл машину - 2/3.

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

решила на бумаге, увы :)
(Ответить) (Thread)
[User Picture]From: avva
2009-07-17 08:17 pm
Все правильно! На бумаге тоже хорошо :)
(Ответить) (Parent) (Thread)
[User Picture]From: bukky_boogwin
2009-07-17 08:40 pm
Перенумеруем двери. Первый открывает дверь 1. Если там ключи, следующей он открывает дверь 2, если козел - дверь 3, если машина - ничего больше не открывает. Второй открывает дверь 2. Если там оказывается козел, то за дверью 1 либо машина, либо ключи, но будь там ключи, первый игрок тоже открыл бы дверь 2, не нашел бы машины (а нашел бы козла), и на там бы все закончилось, так что за дверью 1 машина, а ключи, соответственно, за дверью 3, которую и надлежит открыть второму. Если второму за дверью 2 попадается машина, значит, за дверью 1 либо козел, либо ключи, но будь там козел, первый открыл бы дверь 3, не нашел бы машину (раз она за дверью 2), и на этом тоже все закончилось бы, так что за дверью 1 ключи, и ее-то в этом случае второй и должен открыть. Наконец, если за дверью 2 второй игрок найдет ключи, он просто выиграл. Итог: если первый игрок нашел машину (вероятность чего - как раз 2/3), то второй в любом случае (то есть с вероятностью 1) отыскивает ключи. (2/3)*1=2/3.
(Ответить) (Thread)
[User Picture]From: avva
2009-07-17 09:07 pm
Все верно, да.
(Ответить) (Parent) (Thread)
From: vasja_iz_aa
2009-07-17 08:45 pm
второй игрок первым ходом открывает ту дверь, в которую первый игрок пойдет увидив ключ в свой первый ход? Ключ там он может встретить случайно, а два остальных варианта подскажут второй ход, если машина -- то идти в первую дверь первого игрока.
(Ответить) (Thread)
[User Picture]From: avva
2009-07-17 09:07 pm
Ага.
(Ответить) (Parent) (Thread)
[User Picture]From: melkore
2009-07-17 09:10 pm
нужно терпеливо ждать, пока козёл проголодается и заблеет. ))

если сурьёзно: рассуждения те же, что в притче о колпаках, только мудрецов два, а цветов - три. первый открывает левую дверь. если там ключи - центральную. если козёл - правую. если машина - пофиг. если второго вызывают, то второй по умолчанию понимает, что первый нашел машину. он открывает центральную дверь и видит там...
если ключи - значит хорошо. если машину - значит ключи в левой. если козла - значит ключи в правой. получается, что у первого шанс 2/3, а у второго твёрдая единица.
честно не смотрел другие ответы, просто приходилось решать у Перельмана такие задачки. )))
(Ответить) (Thread)
[User Picture]From: avva
2009-07-17 09:14 pm
:) да, все верно.
(Ответить) (Parent) (Thread)
From: jozhin
2009-07-17 09:24 pm
пронумеруем двери.
первый игрок открывает дверь номер 1. если там козел, он открывает дверь 2, если там ключи - он открывает дверь номер 3.
второй игрок открывает дверь номер 3. если там машина - то ключи за дверью номер 1. если там козел - то ключи за дверью номер 2.
(Ответить) (Thread)
[User Picture]From: enot_kurdiuk
2009-07-17 09:34 pm
Договариваются, какие два двери открывает каждый из них и в каком порядке. Если второй может знать, сколько дверей открывал первый, то он точно будет знать, где машина (если первый ее нашел). Ему остается только забрать ключи из одной из двух оставшихся.
(Ответить) (Thread)
Страница 1 из 2
<<[1] [2] >>