?

Log in

No account? Create an account
задачка - Поклонник деепричастий [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 из 3
<<[1] [2] [3] >>
[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)
Страница 1 из 3
<<[1] [2] [3] >>