Задачка безымянная
 

Раз уж пошли головоломками развлекаться, вот еще одна, можно сказать любимая.

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

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

Для сколько-нибудь математика решить задачку - ничего не стоит. (Вырожденный "нульмерный" случай классической задачи линейных игр). 30секунд - и ответ готов.
Гораздо сложнее выдумать разумное, "на пальцах", "объяснение" правильности такого решения и объяснить его, допустим, жене.

надо менять :)

Чего-то я не уловил хитрость...
игрок указал на любой гараж, ведущий открыл какой-то другой, но пустой.
второй шаг: у игрока теперь выбор из двух вариантов. и вроде как не важно какой был выбор на первом шаге.
вероятность 50%


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

Смотри. В первом шаге у тебя вероятность того, что машина за любой из трех дверей 1/3. Ты выбираешь одну дверь. Значит вероятность, что машина за одной из оставшихся двух 2/3. Практически, тебя спрашивают - открыть одну дверь, или две? :)

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



В одну сляпу все десятки, в другую все единицы.

В одну шляпу десятку, в другую все остальные купюры.

Тогда при 10Х10 и 10Х1 вероятность вытащить десятку составит примерно 73%

"Нутром" чую, что после того, как ведущий открыл одну из дверей, ничего не изменилось: можно настаивать на своём выборе, равно, как и поменять его. :)
Подгоняя же решение под ответ Зубера ( выбрать другую дверь), жене этот выбор можно объяснить следующим образом. Вероятность угадать машину сначала была 33%. После того, как ведущий открыл дверь в пустую комнату вероятность угадать автомобиль со следующей попытки стала уже 50%. Но, упорствуя в своём первоначальном выборе игрок остаётся с теми же 33%, а меняя дверь получает заветные 50% :)

Жена: "С чего это вдруг 33%? Вероятность такая же, как и вероятность того, что, выйдя на улицу, я встречу динозавра - 50%. Потому что или встречу, или нет..." :)

точнее 0,5 * 1 + 0,5*(9/19) примерно равно 73,7%




А про гаражи вот такой у меня ход мыслей:
предположим два варианта расположения машины (такие варианты равновероятны, равно как и третий вариант)
| Х | | |
и
| | | Х |

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

А если гаражей не три а пять и игра идет в 4 тура. тоже надо каждый раз менять свое мнение?



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

/*
* Zuber (c)
*/
#include <stdlib.h>
#include <stdio.h>
#include <time.h>

#define SAMPLE 100000

int main(void){

int ckl;

int correct_nochange;
int correct_change;

int choice;
int car;
int car_counters[3];

correct_nochange = 0;
correct_change = 0;

srand(time(NULL));

for(ckl = 0; ckl < 3; ckl ++){
car_counters[ckl] = 0;
}

for(ckl = 0; ckl < SAMPLE; ckl ++){
car = 1 + (int) (3.0*rand()/(RAND_MAX+1.0));
choice = 1 + (int) (3.0*rand()/(RAND_MAX+1.0));

//printf("%d %d\n", car, choice);

// debugging info
if((0 < car) && (car < 4)){
car_counters[car - 1]++;
}else{
printf("BUG: Illegal car value\n");
exit(0);
}

// sticking with the initial choice
if(car == choice){
correct_nochange++;
}

// changing the decision
switch(choice){
case 1:
if( 2 == car ){
choice = 2;
}else{
choice = 3;
}
break;
case 2:
if( 1 == car ){
choice = 1;
}else{
choice = 3;
}
break;
case 3:
if( 2 == car ){
choice = 2;
}else{
choice = 1;
}
break;
default:
printf("BUG: illegal choice\n");
exit(0);
}

if(car == choice){
correct_change++;
}
}


printf("Results\n");
printf("Generated data:\n");
for(ckl = 0; ckl < 3; ckl ++){
printf("car behind %d: %d\n\n", ckl + 1, car_counters[ckl]);
}
printf("no change of mind: %d (%3.2f)\n", correct_nochange, (float)(correct_nochange)/(float)SAMPLE);
printf("with change of mind: %d (%3.2f)\n", correct_change, (float)correct_change/(float)SAMPLE);

}

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

А зачем методом Монте-Карло решать задачи, которые без проблем решаются "на салфетке" ?

Быть уверенным :). Кстати, на бумажке, народ начнет спорить есть ли зависимость между первым выбором и ворым. А симуляция вопросов не оставит ;).

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

Меняя дверь он получает 67% :)

Идея Зубера была в том, что в начале вероятность угадать 33%, а вероятность не угадать 67%. Соотв. если ты дверь не меняешь, то тебе по любому наплевать чего там откроет ведущий - во втором туре ты остаешься со своими 33% относительно начала игры, только теперь они морально превратились в 50% после того как одна дверь отпала (т.е. в душе/морально ты сомневаешь менять не менять - вот и становится 50% относительно второго тура :)).
Если ты заранее знаешь что дверь меняешь, то чтобы в результате получить машину в первом туре ты должен указать на пустой гараж вероятность чего 67% а второй пустой за тебя 100%-но отметет ведущий. Вот и выходит что если меняешь гараж то вероятность увеличивается до 67% :)

Я не знаю какова там вероятность, но в жизни лифт обнаруживается на первом этаже гораздо чаще чем на том на котором ты живешь :) Потому что на первый его спустить может любой жилец, а на твой поднять только тот кто живет на твоем этаже :) Т.е. как бы в первом случае вероятность в среднем 50% т.е. собственно вас волнует последний человек подымался на лифте или же спускался?? Если спускался то вам повезло :)
На практике вероятность сильно вырастает если вы идете домой утром (когда все приличные люди выходят из дома на работу и спускают лифт :)) и соотв-но вечером наоборот вероятность (встретить лифт на первом этаже) падает ибо большинсвто лифт подымает :)

Программы - это круто, сам программер, имитационное моделирование - тоже круто, но воспользуемся советом ank'a и решим на салфетке:
У меня такая логика.
давайте однократно смоделируем игру. какова вероятность выиграть, если машина в первом гараже. (аналогичную картину получим для второго и третьего гаража.)

игрок может выбрать
в первом туре 1 2 3

ведущий может убрать 2 3 3 2

игрок может выбрать
во втором туре 1 3 1 2 1 2 1 3

итого исходов - 8, удачных 4. вероятность 50%
кол-во удачных исходов при смене мнения - 2
кол-во удачных исходов без смены мнения - 2 , то есть одинаково....

Где я наврал????? откуда 67% ???

Это что за туфта с цифрами? Тут вообще не дано понять где ты наврал, ибо ничего вообще не понятно :) А про 67% (2/3) я выше вроде доходчиво объяснил... поясни в каком месте ты не понял и я попробую как-нидь по другому объяснить :)

Ты не прав по двум причинам:

1) моя програма, написанная выше, методом Монтекарло выдает ресультаты 1/3 и 2/3, в зависимости от (менять и не менять).

2) доходчивое обьяснение. Перед тобои 3 двери. Представь, что второго тура нет. Тебе в первом туре предлагают открыть одну дверь, или две двери. Второй тур есть ни что иное, как открыть 2 двери. Одну (явно неправильную) открывает ведуший. А вторую открываешь ты.

Думаю этим объяснением ты его еще больше запутаешь :)

Поясню еще раз по своему...

Для начала уясним три простые вещи:

1) У вас по любому есть возможность указать на дверь ТОЛЬКО ДВА РАЗА, соответственно только на две двери (можно оба раза на одну и ту же). И главный вопрос - менять вам дверь во второй раз или указать на ту же самую. На какую менять НЕ вопрос потому что за вас уже выберет ведущий 100%!!!

2) Если вы дверь не меняете и хотите при этом выиграть машину, то в первом случае вы должны 100% указать на дверь за которой стоит машина! Потому что во второй раз вы укажите на ту же дверь, ее откроют и там будет машина! :)

3) Если вы дверь меняете и хотите и при этом выиграть машину, то в первом случае вы должны 100% указать на дверь за которой НЕТ машины! Ибо третью дверь (за которой машины 100% нету) за вас "отметет" ведущий между турами и соотв. во втором туре тогда та дверь на которую еще никто не указал является дверью с машиной (при условии что в первом вы указали на дверь без машины).

А теперь вот и посчитаем вероятности при условии что второго тура не будет! :) Вероятность того что вы укажите на дверь с машиной 1/3 (33%), а вероятность того что вы укажите на дверь без машины 2/3 (67%). А теперь вспомним пункт 3) по которому если мы указываем на дверь без машины мы 100% попадем на машину ЕСЛИ ПОМЕНЯЕМ ДВЕРЬ во втором туре! :) Вот вам и ответ! :)

Иезуитство! :)
Тебе предлагают выбрать две двери или одну, но откроешь ты только одну.
Я в прогах ничего не понимаю. :)
В действительности вероятность повышается, если поменять дверь?

Туфта получилась,
пробелы важные схлопнулись, а я так старался, структуру разрисовывал :-((((

точки вместо пробелов:

пусть машина в первом гараже...

игрок может выбрать
в первом туре..................... 1 ..................... 2 .......................... 3

ведущий может убрать ....2.... 3................... 3 .......................... 2

игрок может выбрать
во втором туре ..............1 3 .... 1 2 .............1 2 .........................1 3

надеюсь, теперь будет яснее...

итого исходов - 8, удачных 4. вероятность 50%
кол-во удачных исходов при смене мнения - 2
кол-во удачных исходов без смены мнения - 2 , то есть одинаково....

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

33% и 67% в среднем :)

Давай так,
три двери :
1 ................................ 2 ................................... ......... 3

машина может быть за любой из них. Предположим, что чел выбирает дверь #1 и не меняет своего решения. Он выигрывает только если машина за дверью #1.

М
1.................................2 ................................... .............3
О

Теперь, предположим, что машина не за дверью #1. Она может быть за дверью #2 или за дверью #3, вероятность ентого 2/3.
- (М) (М)
1..............................2... ................................... ............3

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

Не забывай, что между красными и синими ветками в первом случае стоит знак ИЛИ, а не И! Т.е. итогом может быть лишь один из них, а соотв-но исходов итого 6, а не 8 (в цветной ветке либо красный либо синий) и кол-во удачный при смене двери - 2, а без смены двери - 1. Так как в начале у тебя было всего три выбора, то соотв-но и вероятности 2/3 и 1/3 :)

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

исходов как раз восемь, только у них вероятности разные.
но в сумме, с точки зрения игрока, который не знает где машина, вероятности смены и не смены одинаковые
вероятности по исходам в нижней строчке получаюся:
1/12 1/12 1/12 1/12 1/6 1/6 1/6 1/6
для варианта смены решения - это 2, 4, 5 и 7-й варианты, без смены решения - остальные.
то есть 1/12+1/12+1/6+1/6, то есть 6/12 или 50%

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

как в том анекдоте:
Слюшай, я нэ понял, ти за мэня или за мэдвэдя??....

Zuber, как ты (ничего, что на ты?) рассчитываешь вероятность выбора ведущего в случае, если игрок указал на гараж с машиной???...
Что-то я третьего rand() (выбор из двух вариантов) не заметил!!!!



Вот тут-то, наверное, и собака порылась :-))))))

Так не важно какой гараж откроет ведущий 2 или 3 - посмотри на свою картинку - если игрок заранее принял решение НЕ менять дверь, то выиграть он может лишь в одном (из трех) - т.е. красном случае (можно такой же красный нарисовать и по правой стороне первого столбика ЕСЛИ(!) ведущий решит выбрать 3 дверь а не второю :) - так что не важно 2 или 3 дверь откроет ведущий - игрок все равно в итоге останется на цифре 1, так принял решение не менять дверь и в начале выбрал 1.

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

А метод монтекарло есть симуляция. Вероятности высчитываются в самом конце, ишодя из результатов симуляции.

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

В первом случае, игрок угадывает, если остается при своем решении.
Во втором случае он угадывает, если меняет свое решение.

Разговор технарей. :lol: Сейчас вам химик напишет как это "на пальцах". :)
Моя сестра тоже не поняла и я ей объяснял так.
Есть три двери 1, 2, 3. Машина за любой, не важно за какой, пусть будет за 1.
1) Я указываю на дверь 1 (там машина), ведущий открывает пустую, остаётся пустая. При смене двери попадание 0%.
2) Я указываю на дверь 2, ведущий открывает 3, при смене дверей попадание 100%.
3) Я указываю на дверь 3, ведущий открывает 2, при смене дверей попадание 100%
(0% + 100% + 100%) / 3 = 66%

Так? :)

Ага! :)

10 символов

ну хорошо, весь форум меня убедил...
странно, что ank пока молчит...

А чего говорить ?

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

ЗЫ. Если с "нульмерной" задачей разобрались могу дать актуальную формулировку чуть более сложной "одномерной" задачи. Дать ?