Holiday parcel puzzle

PerlMonks Santa (or s/Santa/friend of yours/g on PM, depending on your religious views) has given you a challenge:

You have three (3) nicely wrapped up parcels in front of you. They look, smell, weigh etc. exactly the same. Except two hold a blank scrap of paper, one of them holds a coupon for 1000XP and instant sainthood on PerlMonks (thats the one you desired for years!).

But given that you can only select ONE of the parcels at random, your changes of gratification are slim.

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?

Take an educated guess and write it down.

Now, write two scripts, one where you stick to your initial decision, one where you switch. Loop a sufficient number of times (say 10000) to get some statistical significance. Did your guesses match your expectation? So, if you encounter this challenge in real life, what would be the best strategy?

Ok, here's the scripts, statistical results and the answer i came up with:

First, the script where we stick to out decision:

#!/usr/bin/perl
use strict;
use warnings;

my $runs = 10000;
my $luck = 0;

for(1..$runs) {
    # Generate the lucky parcel
    my $hasxp = int(rand(3)) + 1;
    
    # Now, select one parcel from the 3 at random
    my $parcel = int(rand(3)) + 1;
    
    # We stick to our decision, so we don't care
    # what happens to the other parcels
    
    # Now, see if we were lucky:
    if($parcel == $hasxp) {
        $luck++;
    }
}

# print out the end result in percent
print "You were lucky " . int($luck * 100 / $runs) . "% of the time st
+icking to your initial decision.\n";
[download]

Next, we just add some parcel switcheroo to the first script to simulate impartial Santa and your decision to switch. Here's the script:

#!/usr/bin/perl
use strict;
use warnings;

my $runs = 10000;
my $luck = 0;

for(1..$runs) {
    # Generate the lucky parcel
    my $hasxp = int(rand(3)) + 1;
    
    # Now, select one parcel from the 3 at random
    my $parcel = int(rand(3)) + 1;
    
    # ** Now, the computer removes one of the empty parcels and we sel
+ect the remaining one **
    
    # First, make a "list" of parcels and remove the one the user is h
+olding
    my $all = '123';
    $all =~ s/$parcel//;
    
    # Now, randomly select one of the remaining ones and check
    # if it's empty and *not* currently held by the user
    while(1) {
        my $gone = int(rand(3)) + 1;
        
        # Check if we can remove that one from the list
        next if($gone == $parcel); # can't remove, held by the user
        next if($gone == $hasxp); # don't remove the lucky one
        
        $all =~ s/$gone//; # Remove it and finish
        last;
    }
    
    # Given that we eliminated two parcels from a list of three,
    # there is one left the user *can* select, so let's do it
    $parcel = $all;
    
    # Now, see if we were lucky:
    if($parcel == $hasxp) {
        $luck++;
    }
}

# print out the end result in percent
print "You were lucky " . int($luck * 100 / $runs) . "% of the time ch
+anging your decision.\n";
[download]

And, tadaa, here are the statistical results i came up with:

You were lucky 33% of the time sticking to your initial decision.
You were lucky 66% of the time changing your decision.
[download]

Given the results, the correct strategy when encountering this situation is: Always change your decision!

I hope this little holiday themed puzzle was enjoyable.

Happy Holidays!

BREW /very/strong/coffee HTTP/1.1
Host: goodmorning.example.com

418 I'm a teapot

Comment on Holiday parcel puzzle Select or Download Code

Replies are listed 'Best First'.
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]
Re^2: Holiday parcel puzzle by cavac (Prior) on Dec 22, 2011 at 18:01 UTC
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
<Reveal this spoiler or all in this thread> 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]
Re^2: Holiday parcel puzzle by cavac (Prior) on Dec 22, 2011 at 20:17 UTC
Nice one. Actually, way nicer than mine. BREW /very/strong/coffee HTTP/1.1 Host: goodmorning.example.com 418 I'm a teapot	[reply]
Re^3: Holiday parcel puzzle by Not_a_Number (Prior) on Dec 22, 2011 at 20:34 UTC
So do I win the 1000XP? :-)	[reply]
Re^4: Holiday parcel puzzle by cavac (Prior) on Dec 22, 2011 at 20:52 UTC
Re^2: Holiday parcel puzzle by JavaFan (Canon) on Dec 22, 2011 at 22:33 UTC
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";` [download]	[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]
Re^2: Holiday parcel puzzle by cavac (Prior) on Dec 22, 2011 at 22:16 UTC
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]
Re^3: Holiday parcel puzzle by aaron_baugher (Curate) on Dec 23, 2011 at 00:12 UTC
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. Aaron B. My Woefully Neglected Blog, where I occasionally mention Perl.	[reply]
Re^3: Holiday parcel puzzle by JavaFan (Canon) on Dec 23, 2011 at 01:28 UTC
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^4: Holiday parcel puzzle by Don Coyote (Hermit) on Dec 27, 2011 at 12:14 UTC
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% [download]	[reply] [d/l]
Re^2: Holiday parcel puzzle by cavac (Prior) on Dec 29, 2011 at 22:49 UTC
You are right, of course. And your solution is guaranteed to always be mathematically correct, since you don't depend on random numbers to approximate the result. Nice! BREW /very/strong/coffee HTTP/1.1 Host: goodmorning.example.com 418 I'm a teapot	[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 <Reveal this spoiler or all in this thread> no data structures required I think. Happy Xmas & New Year! Don	[reply] [d/l]
Re^2: Holiday parcel puzzle by cavac (Prior) on Dec 29, 2011 at 22:43 UTC
Interesting solution. Guess mine was a bit too complicated. BREW /very/strong/coffee HTTP/1.1 Host: goodmorning.example.com 418 I'm a teapot	[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]
Re^2: Holiday parcel puzzle by tobyink (Canon) on Jan 10, 2012 at 16:07 UTC
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]
Re^2: Holiday parcel puzzle by cavac (Prior) on Jan 10, 2012 at 16:16 UTC
Usually this only happens when that "nearly impossible thing" is something that you don't want to happen. Like, there's only a 1000000:1 chance that whatever magic you are trying to do will rip apart the fabric of reality and let unspeakable things from the dungeon dimensions in... "Believe me, Mike, I calculated the odds of this succeeding against the odds I was doing something incredibly stupid� and I went ahead anyway." (Crow in "MST3K The Movie")	[reply]
Re^3: Holiday parcel puzzle by tweetiepooh (Hermit) on Jan 23, 2012 at 16:44 UTC
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]