Beefy Boxes and Bandwidth Generously Provided by pair Networks
Your skill will accomplish
what the force of many cannot
 
PerlMonks  

Holiday parcel puzzle

by cavac (Chaplain)
on Dec 22, 2011 at 17:42 UTC ( #944817=perlmeditation: print w/ replies, xml ) Need Help??

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:

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
Re: Holiday parcel puzzle
by choroba (Abbot) 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.

      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
Re: Holiday parcel puzzle
by Not_a_Number (Parson) 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! :)

      Nice one. Actually, way nicer than mine.

      BREW /very/strong/coffee HTTP/1.1
      Host: goodmorning.example.com
      
      418 I'm a teapot

        So do I win the 1000XP?

        :-)

      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";
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.

      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

        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.

        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.
Re: Holiday parcel puzzle
by Don Coyote (Monk) 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

      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
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%

      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
Re: Holiday parcel puzzle
by tweetiepooh (Friar) 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.
      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.

      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")
        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.

Log In?
Username:
Password:

What's my password?
Create A New User
Node Status?
node history
Node Type: perlmeditation [id://944817]
Front-paged by Arunbear
help
Chatterbox?
and the web crawler heard nothing...

How do I use this? | Other CB clients
Other Users?
Others lurking in the Monastery: (14)
As of 2014-07-24 18:25 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?

    My favorite superfluous repetitious redundant duplicative phrase is:









    Results (165 votes), past polls