Dean's World

That Annoying Brainteaser

Dean

Yes, you really should switch, and no, it's not a trick question. If you still don't believe it, you should click here and read.

If you still don't believe it: work it out with a friend.

It's counter-intuitive. That doesn't make it wrong.

All Related Posts (on one page) | Some Related Posts:

The New Tuskegee Experiments
From The Mailbag: Explaining the BS Theory
Conflicts of Interest...
HIV Discussion: Supplemental Materials
That Annoying Brainteaser
The Brainteaser That Changed My World...
A Conversation
HIV Skepticism
Scientific Dissenters

Posted by Dean | Permalink | Technorati Trackbacks

(link)

Kacie Landrum (mail) (www):

Um, Dean, the link's not working for me.

1.7.2005 12:49pm

(link)

Dean Esmay (www):

Oops. Try again.

1.7.2005 12:58pm

(link)

Robb Allen (mail) (www):

I've had success in arguing the extreme case of a billion doors. You select one of the billion, Monty opens 999,999,998 other doors. The remaining two are now your choice. What's the odds that you picked the right one the very first time? 1 in 1,000,000,000. That would mean the odds of the unchosen door are 999,999,999 in 1,000,000,000. Would you switch then? Of course.

However, the choice of the two doors is a 50/50 choice but the statistics on if you chose the correct door the first time still put it out of your favor. Both events must be considered at that point to understand the reason behind the statistic.

I have a feeling I'm not making it any easier for anyone, am I?

1.7.2005 1:05pm

(link)

Drew Vogel (mail) (www):

It was a great brain teaser. I got it wrong, of course. I tried it on my dad, who's usually pretty good with that sort of thing. He got it wrong, too. But he thought about it first, and answered tentatively. Like Dean said in the original post, I was absolutely certain about my wrong answer. So I guess he did better than me.

1.7.2005 1:46pm

(link)

Mark Jaquith (www):

Well, it sounds too easy, so why would someone ask? You're looking for it to be a trick.

1.7.2005 2:09pm

(link)

Michael Demmons (mail) (www):

Well, this'll sure come in handy the next time I play Russian Roulette!

1.7.2005 2:15pm

(link)

David Gillies (mail):

Here's my C++ version of the simulator:

/*

Monte Carlo simulation of the Let's Make a Deal three-door
conundrum.

N.B. A good quality random number generator is required.
System-supplied rand() will not do as low-order bits are
being masked and standard LCG's are correlated in low-order
bits. The rand48 routines are better but are still LCG's at
heart. Suggestion: read Numerical Recipes (Press, Teukolsky,
Flannery and Vetterling) or Knuth II (Seminumerical Algorithms).

Compile:

g++ monty.c -o monty

If you have Bill Chambers' ranyyc library:

g++ monty.c -DHAVE_RANYYC -lranyyc -o monty

Usage: monty [-i |—iterations [-s|—switch]
[-v|—verbose]

e.g. monty -sv -i 300

David Gillies 2003

Placed in the public domain.

*/

#include
#include
#include
#include
#include

#ifdef HAVE_RANYYC // which you probably don't
#include
#define RANDOM_SEED srandomm
#define RANDOM_DRAW randomm
#else
/* need a better RNG here - lrand48() not really good enough */
#define RANDOM_SEED srand48
#define RANDOM_DRAW lrand48
#endif

int main(int argc,char *argv[])
{
char doors[4]={0},
switcharr1[4][2]={{0,0},{2,3},{1,3},{1,2}},
switcharr2[7]={0,0,3,2,0,0,1};
int i,c;
unsigned long ran1=0,ran2,ran3,final,wins=0,iters=1000;
bool switchdoor=false,verbose=false;

// get command-line switches

while(1)
{
int optix=0;

static struct option longopts[]=
{{"iterations",required_argument,0,0},
{"switch",no_argument,0,0},
{"verbose",no_argument,0,0},
{0,0,0,0}};

c=getopt_long(argc,argv,"i:sv",longopts,&optix);

if(c==-1)
break;

switch(c)
{
case 0:
{
switch(optix)
{
case 0:
{
iters=strtoul(optarg,(char**)0,10);
if(iters==0)
iters=1000;
break;
}

case 1:
{
switchdoor=true;
break;
}

case 2:
{
verbose=true;
break;
}
}
break;
}

case 'i':
{
iters=strtoul(optarg,(char**)0,10);
if(iters==0)
iters=1000;
break;
}

case 's':
{
switchdoor=true;
break;
}

case 'v':
{
verbose=true;
break;
}

default:
{
printf("Usage: monty [-i |—iterations [-s|—switch] [-v|—verbose]\n");
exit(1);
break;
}
}
};

RANDOM_SEED(time(0));

for(i=0;i {
// pick door with prize
doors[ran1]=0;
ran1=RANDOM_DRAW();
ran1%=3;
ran1++;
doors[ran1]=1;

if(verbose)
printf("Door %d has prize\n",ran1);

// generate contestant's choice

ran2=RANDOM_DRAW();
ran2%=3;
ran2++;

if(verbose)
printf("Picked door %d\n",ran2);

// pick door to be opened by host

/* N.B. if the first choice is the prize door, then either of
the two others can be opened. If not, then only one
can be (this is the heart of the solution) */

if(doors[ran2]==1)
ran3=switcharr1[ran1][RANDOM_DRAW()&1];
else
ran3=switcharr2[ran1*ran2];

if(verbose)
printf("Opened door %d\n",ran3);

// switch or not depending on policy

if(switchdoor)
final=switcharr2[ran2*ran3];
else
final=ran2;

if(verbose)
{
if(switchdoor)
printf("Switch to door %d\n",final);
else
printf("Stick with door %d\n",final);
}

if(final==ran1)
{
wins++;
if(verbose)
printf("WIN\n\n");
}
else
{
if(verbose)
printf("LOSE\n\n");
}
}

printf("TOTAL WINS: %d/%d\n",wins,i);
}

1.7.2005 2:36pm

(link)

Cynical Nation (mail) (www):

All right, no one else has posted it, so I guess I'll have to. :-)

There is another brainteaser that has always fascinated me just as much as the Monty Hall problem. It involves an island of blue-eyed and brown-eyed people.

Here's the background. There is an isolated island with 200 inhabitants. 100 of them have brown eyes, and 100 have blue eyes.

Blue eyes are considered a sign of the Devil, and if anyone learns he has blue eyes, he is obliged to kill himself at midnight that night.

In general, however, people don't know their own eye color. There are no mirrors or reflective surfaces on the island, and the subject is taboo.

Also, we assume it's a close-knit community, where everyone sees everyone else every day. We also assume that everyone is honor-bound to follow tradition and custom.

So one day an anthropologist comes to the island to study them for a time. His stay on the island is uneventful until the day he leaves. Then, as he's getting on the boat to leave, he casually mentions to the islanders "I saw a blue-eyed person today." Then he leaves.

The question is, what happens as a consequence of the anthropologist's remarks, and when, and why?

I have to confess that I'm less satisfied/convinced of the answer to this one than I am the Monty Hall problem, but it still makes for great discussion. Has anyone heard this? I'll post the answer (ROT13'd) in a follow-up post.

1.7.2005 2:41pm

(link)

Veeshir (mail):

Robb, that proof made lots of sense. I'm just not sure that it translates well with a much larger doors-opened/doors chosen ratio but I have a feeling it does. Counter-intuitively to me at least.

My roommate and I are going to test it with three doors. If it works, and I'm sure it will, it's going to drive me crazy. I really don't like it when I can't figure out logic and math questions.

I'm not sure what that says about me considering the point of the first post.

1.7.2005 2:46pm

(link)

Cynical Nation (mail) (www):

Here is the "answer" to the blue-eyed/brown-eyed puzzle I just posted, ROT13'd, of course.

Ba zvqavtug bs gur uhaqerqgu avtug nsgre gur naguebcbybtvfg yrnirf, nyy 100 oyhr-rlrq crbcyr pbzzvg fhvpvqr. Jul?

Yrg'f svefg ybbx ng gur yvzvgvat pnfr. Yrg'f fnl gurer'f bayl bar oyhr-rlrq crefba ba gur vfynaq, naq uvf anzr vf Wbua. Nf sne nf Wbua xabjf, gurer ner *ab* oyhr-rlrq crbcyr ba gur vfynaq. Jura ur urnef gur naguebcbybtvfg'f erznex gung ur fnj n oyhr-rlrq crefba, ur'f qvfgenhtug, orpnhfr ur xabjf ur zhfg or gur bar. Gung avtug ng zvqavtug, ur qbrf uvzfrys va.

Abj yrg'f ybbx ng gur pnfr jurer jr unir *gjb* oyhr-rlrq crbcyr: Wbua naq Ovyy. Nf sne nf rnpu bs gurz xabj, gur bgure bar vf gur bayl oyhr-rlrq crefba ba gur vfynaq. Jura Wbua urnef gur naguebcbybtvfg'f erznex, ur guvaxf, "Cbbe Ovyy! Gung fhpxf sbe uvz. V thrff ur'yy xvyy uvzfrys gbavtug." Ovyy, bs pbhefr, unf gur fnzr gubhtug nobhg Wbua. Gurl obgu ernpg va ubeebe gur arkg zbeavat, ubjrire, jura gurl frr gur bgure crefba vf fgvyy nyvir. Gur bayl ernfba gung pbhyq or vf gung gurer jnf npghnyyl n *frpbaq* oyhr-rlrq crefba ba gur vfynaq. Fvapr obgu Wbua naq Ovyy bayl frr bar oyhr-rlrq crefba, gurl pbapyhqr, pbeerpgyl, gung gurl ner gur bgure, naq gurl obgu xvyy gurzfryirf ba zvqavtug bs gur frpbaq avtug.

Vaqhpgviryl, lbh pna frr ubj guvf jbexf. Vs gurer jrer guerr oyhr-rlrq crbcyr, gurl'q haqretb gur fnzr cebprff naq gur guerr bs gurz (Wbua, Ovyy naq Grq) jbhyq nyy xvyy gurzfryirf ba zvqavtug bs gur guveq qnl.

Frr? Ner l'nyy pbaivaprq? V'ir fgvyy tbg fbzr vffhrf jvgu guvf bar. :-)

1.7.2005 2:51pm

(link)

Oscar:

This is known in the bridge world as the principle of restricted choice. If you picked a bad door, then Monty has no choice which door to show you.

1.7.2005 2:58pm

(link)

David Gillies (mail):

I'd completely forgotten I'd already emailed Dean my code the first time round!

1.7.2005 3:08pm

(link)

Dave00 (mail) (www):

Relativity is counter-intuitive too...

BTW, that's a great explination.

1.7.2005 3:25pm

(link)

htom (mail):

It took me a while to understand the Monty Hall problem. It's not a simple probability thing, it's a conditional. I'll contribute two links:

http://mathforum.org/dr.math/faq/faq.monty.hall.html

http://math.ucr.edu/~jdp/Monty_Hall/Monty_Hall.html

Think of it this way. It's a variation on the old three shell &pea game, played on a glass table. The dealer puts the pea, you both shuffle the shells about, and you chose one but don't lift. You have a 1:3 chance of being right. The dealer looks, and reveals one of the shells as empty. Should you switch?

Wait a mo, though. Instead of his looking and then chosing to show one, how about you can instead choose the other two shells? You'd have 2:3 odds -- what the dealer had.

But that's what the reveal does; it collapses the 2:3 probability into the remaining shell, because it's not possible for it to be in the empty shell, it's more likely to be in the "change to" shell.

1.7.2005 3:27pm

(link)

dave frey (mail) (www):

For some reason it's helpful to me to realize that as soon as I made my initial choice, there was a 2/3 chance that I had chosen the wrong door. Opening one of the remaining 2 doesn't change that at all: there was always a 2/3 chance that I chose the wrong door from the start; therefore I should switch.

1.7.2005 3:41pm

(link)

Matthew B. (mail) (www):

I sent this brainteaser to many friends, some of whom correctly determined the answer. One who did not is the chair of the physics department at a well known university. Anyway, I had more than passing familiarity with probability since I played lots of wargames that depended on the roll of the dice. Anyway, the problem boils down to the following:

Chance of picking correct door equals 1 minus the product of the chances of NOT picking the correct door. First choice has a 2/3 chance of being wrong. If you don't switch doors, that chance remains the same. However, if you switch doors, you now have an separate 1/2 chance of picking correctly(or incorrectly). The odds work out this way:

1 - (2/3)(1/2) = 1 - (1/3) = 2/3 chance of picking the correct door if you switch your choice.

1.7.2005 3:58pm

(link)

Sandi (www):

I am terrible at brain teasers. After mulling it over for way too long and getting nowhere, and wanting to believe that the chances were better by switching, I googles "three door problem," which yielded 481 results. All give the same examples, and a few with computer testing programs. Then when I hit link 12, I came across one that used cards instead of doors—BINGO! I am probably the last to get it, but just in case anyone else is as slow as me, this was so much easier to understand.

Here was an easier way for me to get it using 1000 talbes with 2 black and 1 red card instead of doors.

Imagine three thousand card tables. On each of the tables, a dealer has randomly arranged one red card and two black cards, face down. At each table, you randomly put a marker labeled "1" on one of the cards, representing your first choice.

It is obvious that about one thousand markers will be on red cards and about two thousand will be on black cards, from simple chance.

At each table, the dealer turns over a card that is both black and not under the marker. Now each table contains one face-up black card, one card with a marker, and one remaining face-down card. You put a marker labeled "2" on that last card at each table, indicating it is the second choice.

It is obvious that the cards under the "1" markers have not changed, so one thousand of them are still red. And two thousand are still black.

Since each second-choice card must be red if the first-choice is black and vice-versa, about two thousand of the second-choice cards must be red. Switching must give a two-thirds chance of getting the red card simply because two thousand of the three thousand cards under the "2" markers are red.

Actually I was still having a problem picturing it in my mind untill I realized that of the 6000 were not marked with a 1 (2000 red and 4000 black), the dealer removed 1000 black leaving 2000 red and 3000 black (2/3), which is much better than those marked with a '1' of which 1000 red and 2000 black (1/3).

Ok, so I am slow, but now I understand perfectly. :)

1.7.2005 4:02pm

(link)

Sandi (www):

Err easier way for me to get it using 3000 talbes, not 1000.

1.7.2005 5:18pm

(link)

silvermine (mail) (www):

This one made me nuts in college. It actually took me a while to convince some very brainy portions of my family. ;)

1.7.2005 6:24pm

(link)

Dean Esmay (www):

Cynical: I guess I have a problem with your brainteaser because it seems like a psychological game, and I don't think the average person would assume himself to be blue-eyed.

1.7.2005 8:25pm

(link)

Monomer:

The 100-98 incorrect choices makes it clear to me, though I have a hard time explaining it in words. But choose one choice from 100, and remove it from being again chosen, by Monty, for awhile. Then immediately make Monty reveal one incorrect choice from the remaining 99. Now you get to choose whether the correct choice is yours or in the smaller group remaining. Each choice of the remaining smaller group now has a 1/99 chance of being correct [all the choices now remaining there + your 1]. But your original choice had a 1/100 chance. Therefore you must switch to choosing one choice from the remaining 1/99 chance of being correct group.

You must switch whenever you are asked to, the later the better. By the time 98 consequitive choices have turned up negative, you really must switch. {Does the remaining choice-to-switch-to have a 1 - [1/100 - 1/98!] chance of being correct, ! = factorial? I don't know. Anyway the remaining choice you can switch to is almost assured of being correct.}

By inference or analogy, Monty removing one [wrong] choice of 2 from the pool of remaining choices increases the still remaining choice which you did not choose originally to a stronger chance of being correct than your original choice, regardless of what the exact chances turn out to be. The other choice-pool remaining is always more valuable than your original choice if at least some possibility of the other choice-pool being correct, or containing the correct choice, has increased over its initial chance, which was the same as yours. Turning up negatives or incorrect choices within the remaining set of choices always makes the chance of it containing the correct choice greater than your initial choice. The probablility of each choice in the remaining set or pool of choices being correct is always greater than your original choice.

1.7.2005 9:09pm

(link)

Jerry Kindall (www):

Monte Carlo simulation

Surely you must use a Monty Hall simulation!

1.8.2005 12:02am

(link)

Joe Peden:

Mr.Jimm has a knock-out answer at Patterico's site to the 3 door version. He simply asks, if you originally could choose only one door, but now Monty gives you the chance to in effect choose two instead, why not take the two?

When Monty opens one door, and allows you to choose again, he is now allowing you to pick two doors, in effect allowing you two chances -- which, naturally, didn't help me either at first. You originally had a 1/3 chance, which didn't change until another door was opened and you took the second option, two doors.

1.9.2005 5:47am