|
Re: Holiday parcel puzzle
by choroba (Cardinal) on Dec 22, 2011 at 17:55 UTC
|
See also Monty_Hall_problem. I heard it at a lecture, but cannot remember when, where (Vienna?) and from whom. | [reply] |
|
|
Ah, THAT is the technical term for it :-)
I learned about the problem by reading Friedrich Schiel's BAfH stories (similar to Simon's BOFH stories, but in german language and in an University setting).
BREW /very/strong/coffee HTTP/1.1
Host: goodmorning.example.com
418 I'm a teapot
| [reply] |
Re: Holiday parcel puzzle
by Not_a_Number (Prior) on Dec 22, 2011 at 20:12 UTC
|
Update: Added spoiler tags
Update 2: Looking now at the OP's much more verbose code, I wonder if mine is not too concise, especially if the aim is to convince someone who doubts the actual odds.
Anyway, it was enough to convince me! :)
| [reply]
[d/l] |
|
|
| [reply] |
|
|
So do I win the 1000XP?
:-)
| [reply] |
|
|
|
|
The problem with your "concise" solution is that it's unclear whether your program matches the problem description. If you don't care about the latter, here's an even more concise one:
use 5.010;
say "Please wait while I run a simulation ....";
sleep 5;
say "Elves have wrapped a billion parcels, calling FedEx ....";
sleep 10;
say "Not switching wins 33.3% of the time";
say "Switching wins 66.7% of the time";
| [reply]
[d/l] |
Re: Holiday parcel puzzle
by JavaFan (Canon) on Dec 22, 2011 at 21:38 UTC
|
You select one. Then Santa removes one of the other ones. He also promises you that the one he removed was in fact one of the empty ones. You have now the chance to either stick to the one you selected or switch to the remaining one still on the table (giving the one you currently hold back to Santa).
How are your chances if you stick to the parcel you selected at the start? How are your chances if you switch to the one Santa has left on the table?
Old problem, beaten to death long before the internet existed.
The classical answer is to switch.
However, there's more to say. With your wording of the problem, there isn't enough information to say whether you should switch or not. See, only after you've picked it's revealed that Santa offers you a choice. Which means that Santa may be biased -- perhaps he only offers you a choice if you've picked the top prize, assuming you know about Monty Hall and switch (the financial crisis has reached the North Pole after all).
Now, if it's a given that Santa will always reveal an empty price after your first choice, it's better to switch, increasing your chance of winning from 1/3 to 2/3. But if we do not know what Santa's strategy will be, we cannot know whether switching will increase our chance to win is.
| [reply] |
|
|
I knew that many of you would already know the answer. The idea was for people who didn't know to try to come up with a Perl program to solve this problem.
I thought it was a good way to come up with different ways to solve a mathematical problem.
Edit: JavaFan, could you help me out on that one: English is not my native language, so i'm not really sure where my wording failed. Any suggestions on improving it?
BREW /very/strong/coffee HTTP/1.1
Host: goodmorning.example.com
418 I'm a teapot
| [reply] |
|
|
Your wording is fine now, so maybe you already edited it. The key, as JavaFan said, and your post now includes, is that Santa always removes an empty package before giving you the choice of swapping. If he just removed a package randomly, then there would be no point in swapping, because there would be a 1/3 chance that you would be giving up the prize, 1/3 that you would gain it, and 1/3 that Santa would have removed it. Santa is basically allowing you to trade your one package for both of his, while guaranteeing that the prize will be in play. You'd always trade one package for two. It doesn't matter whether he removes an empty one, or trades them both for your one and lets you open both, discarding at least one empty one.
I've had to get out a deck of cards, pulling out a Queen and two Aces, to demonstrate this to people who insisted the odds had to change because the circumstances changed. "Look, let's go through all the possibilities. You're trying to pick the Queen. I deal out Q A A. If you pick the first card, you lose if you switch. But if you pick the second or third card, I discard the other Ace, and you win by switching, so you win 2/3 of the time. Now let's try it with A Q A....." It really doesn't take long, because there are only nine different combinations. Probabilities just aren't taught anymore.
| [reply] |
|
|
It's not a matter of just using the wrong words. There's an unstated assumption.
The point is, that to know switching gives a benefit, the candidate must know that Santa will always discard an unpicked, empty, price, and offer you a chance to switch. If Santa barges in, offer you a pick of three, and after your pick he says "well, what if I tell you that this unpicked price is empty, will you switch?", then it may very well be that Santa only offers you a choice if you have initially picked the top price.
Perhaps one should describe the game as:
Santa offers you three parcels. One parcel is filled with chocolate and beer, the others have a goat inside. But from the outside, they all look equal. You get to pick a parcel, but before opening it, regardless which one you picked, Santa will open one of the unpicked parcels, and it will always be a goat. Santa will then always offer you to switch.
| [reply] |
|
|
Re: Holiday parcel puzzle
by JavaFan (Canon) on Dec 28, 2011 at 01:17 UTC
|
It's funny that when people "tackle" the Monty Hall problem with a program, they tend to write one that uses a simulation, running thousands (if not more) of test runs. And that while it's easy to brute-force it, as there are at most 108 cases to examine (3 places for the main prices, 3 initial picks, 2 possible doors for Monty to pick, switch/not-switch).
use 5.010;
my @doors = (1 .. 3);
my $switch_wins = 0;
my $switch_losses = 0;
my $noswitch_wins = 0;
my $noswitch_losses = 0;
#
# Place a price
#
foreach my $price (@doors) {
#
# Pick a door
#
foreach my $pick (@doors) {
#
# Monty's pick
#
my @monty_choices = grep {$_ != $price && $_ != $pick} @doors;
foreach my $monty_pick (@monty_choices) {
#
# Switch or not?
#
foreach my $switch (0, 1) {
#
# If switching, find final door
#
my $final_pick;
if ($switch) {
($final_pick) =
grep {$_ != $pick && $_ != $monty_pick} @doors;
}
else {
$final_pick = $pick;
}
my $prob = 1 / @monty_choices;
if ($switch) {
$switch_wins += $prob if $final_pick == $price;
$switch_losses += $prob if $final_pick != $price;
}
else {
$noswitch_wins += $prob if $final_pick == $price;
$noswitch_losses += $prob if $final_pick != $price
+;
}
}
}
}
}
printf "Switching: win percentage = %.2f%%\n",
100 * $switch_wins / ($switch_wins + $switch_losses);
printf "No switching: win percentage = %.2f%%\n",
100 * $noswitch_wins / ($noswitch_wins + $noswitch_losses);
__END__
Switching: win percentage = 66.67%
No switching: win percentage = 33.33%
| [reply]
[d/l] |
|
|
| [reply] |
Re: Holiday parcel puzzle
by Don Coyote (Hermit) on Dec 27, 2011 at 12:48 UTC
|
Hi Cavac,
Can I just say I've really enjoyed thinking this one over. Thanks for posting. Now I have already come across this puzzle before and knew what the best option would be. However I have never until now really delved into the math and certainly never tried to apply such a problem into code. I may try and do so with other problems I come across, as an ongoing training technique.
At first I thought I was going to have to use arrays and hashes or a mixture of the two. However after thinking about it and trying to reduce the significance of the array/hash values, and coding, I came up with what I think is a fairly straight forward conditional routine that tests for both the punter sticking and changing after each initial guess.
I made an effort to approach the problem as if I had never seen it before and did not know the outcome already too. I hope that the module retains it's integrity for that
no data structures required I think. Happy Xmas & New Year! Don
| [reply]
[d/l] |
|
|
| [reply] |
Re: Holiday parcel puzzle
by tweetiepooh (Hermit) on Jan 10, 2012 at 15:51 UTC
|
Bah statistics; as any Terry Pratchett fan will tell you a 1000000:1 shot will succeed 9 times out of 10. | [reply] |
|
|
I dunno - I once calculated the odds of a 1000000:1 shot actually succeeding. I can't remember what it worked out at, but it wasn't good.
| [reply] |
|
|
| [reply] |
|
|
In the story it's something they do want to happen. The chance that the shot will succeed so they make things harder and harder 'til they reckon they have made the odds right.
| [reply] |