On 5-Nov-04, at 8:10 AM, Seth Dillingham wrote:
> Here, of course, is the puzzle. Explain how you knew how to win. Tell
> us what you did, and why. What were your odds of winning each round?
Here is how to win...
After you select your shell and 2 disappear, leaving two remaining,
always choose the other shell.
Why?
"( )" denotes a shell. "x" denotes the pebble. (therefore, "(x)"
denotes the shell with the pebble underneath it") Each shell is
indexed with a number below. We'll call them Shell 1 (S1), Shell 2
(S2), Shell 3 (S3), and Shell 4 (S4).
( ) ( ) ( ) (x)
1 2 3 4
You initially have four choices, S1, S2, S3, or S4.
If you initially choose S1, S2 and S3 will disappear.
When you switch your choice to S4, you found the pebble.
If you initially choose S2, S1 and S3 will disappear.
When you switch your choice to S4, you found the pebble.
If you initially choose S3, S1 and S2 will disappear.
When you switch your choice to S4, you found the pebble.
If you initially choose S4, either S1 and S2 will disappear, or S2 and
S3 will disappear.
Regardless of which of S1, S2 or S3 you switch to, you will not find
the pebble.
I'm sure you would feel it's reasonable that it doesn't matter what
order S1...S4 are in or which one you pick first, as long as you always
choose the other remaining shell on your second pick.
Therefore, out of your four choices, 3 will be correct. And thus the
probability of winning each game is 3/4.
Let's look at the cumulative probality over 15 turns. The cumulative
probability is the sum of the probabilities of winning a particular
turn but none of the ones before it.
Let W = the probability you win. P = 3/4.
Let L = the probability you lose. L = 1/4.
The probability of winning the first turn is W.
The probability of losing the first turn but winning the second turn is:
L*W (ie: the probability of losing the first turn and then winning the
second turn. The reason you multiply these numbers is explained by
"The Rule of Product". Google "The Rule of Product" for more
information about this. Note that one of the first hits is from the
head of the math department at the university I'm attending.
http://www.math.uvic.ca/faculty/gmacgill/guide/combargs.pdf)
Note: L*W = 1/4 * 3/4 = 3/16
The probability of losing the first turn and second turn but winning
the third turn is:
L*L*W = 1/4 * 1/4 * 3/4 = 3/64
The probability of losing the first, second and third turns but winning
the fourth turn is:
L*L*L*W - 1/4 * 1/4 * 1/4 * 3/4 = 3/256
.
.
.
The probability of losing the first through 14th turns but winning the
15th turn is:
L*L*L*L*L*L*L*L*L*L*L*L*L*L*W = 3/4^15 =
3/(4*4*4*4*4*4*4*4*4*4*4*4*4*4*4)
So the cumulative probability is:
W + L*W + L*L*W + L*L*L*W + L*L*L*L*W + . . . +
L*L*L*L*L*L*L*L*L*L*L*L*L*L*W
If you put the numbers in a sequence, you would see something like this:
{ 3/4, 3/16, 3/64, 3/256, 3/1024, ...., 3/1073741824 }
This is called a geometric series, because each term differs from the
one before it by the exact same factor (or "ratio"). In this case, the
factor is 1/4. ie: 3/64 = 3/16 * 1/4.
There is a formula for getting the sum of an infinite geometric
series... the formula is:
S = a / ( 1 - r), where a = the initial value, and r = the ratio. In
this series, a = 3/4 and r = 1/4.
Therefore:
S = (3/4) / (1 - 1/4)
= (3/4) / (3/4)
Remember that dividing two fractions is the same as multiplying one by
the reciprocal (reversing the top/bottom order of the fraction) of the
other.
Therefore:
S = (3/4) * (4/3)
= (3*4) / (4*3)
= 12 / 12
S = 1
S, the sum of the infinite series, represents the probability of
winning this game. A probability of 1 means you always win. Now of
course, we're not playing an infinite amount of turns, only 15. But if
you actually went to the trouble of calculating out the sum of that
ugly sequence of 15 probabilities, you'd get a number very very very
close to 1.
The actual probability is:
3/4 + 3/16 + 3/64 + 3/256 + 3/1024 + 3/4096 + 3/16384 + 3/65536 +
3/262144 + 3/1048576 + 3/4194304 + 3/16777216 + 3/67108864 +
3/268435456 + 3/1073741824
There are a number of easy ways to calculate that finite number without
actually doing the math. For example, you could start up a python
interpreter, and enter this at the ">>> " prompt and hit Enter:
3/4.0 + 3/16.0 + 3/64.0 + 3/256.0 + 3/1024.0 + 3/4096.0 + 3/16384.0 +
3/65536.0 + 3/262144.0 + 3/1048576.0 + 3/4194304.0 + 3/16777216.0 +
3/67108864.0 + 3/268435456.0 + 3/1073741824.0
The answer python gave me is: 0.99999999906867743
Or, you could open Microsoft Excel, and enter 0.75 in $A$1. Then enter
=0.25*A1 into $B$2. Then fill that formula down to and including the
15th row by dragging the little box at the bottom right of the
selection box when you have $A$2 selected.
Then select $A$1:$A$15 and click the "Sum" toolbar button (looks like
the Greek letter Sigma). You'll see something like this:
0.75
0.1875
0.046875
0.01171875
0.002929688
0.000732422
0.000183105
4.57764E-05
1.14441E-05
2.86102E-06
7.15256E-07
1.78814E-07
4.47035E-08
1.11759E-08
2.79397E-09
0.999999999
That last number is the sum of the 15 before it. It actually showed
"1" in the 16th row, because the A column wasn't wide enough. If I
made the A column much wider, I'd actually see 0.999999999 as the last
number.
That probability is so overwhelming in your favor if you always switch
your choice when given the opportunity that you could probably play the
game constantly for years or maybe even centuries (don't feel like
calculating that out right now, this is getting long enough) without
not getting at least 9 wins out of 15.
The reason this always works is because there is NO chance involved.
You are not actually making any decision, you are performing a
pre-programmed set of actions, ie: an algorithm. To take all the
thinking out of the game, always pick the same shell first, and then
pick the other remaining shell when given the opportunity. Really, you
can pick whatever shell you want first, but you might as well just
always pick the 1st shell first, it's not going to matter if you always
pick the other remaining shell on your second pick.
Note, any time you're playing a game like this where you have at least
a 50/50 chance on each try, you can guarantee you will always win some
kind of majority of turns given enough turns. Of course, the lower the
odds, the more turns you will need to guarantee yourself that dominant
performance.
I got a little lucky with this problem.
Right now I'm taking a course where we are learning things such as
combinatorials, logic, probabilities, set theory, etc. In my other
math course we are CURRENTLY learning about sequences, series, infinite
series, sums of infinite series, power series, etc. In fact, just 9
days ago on (on October 27th) one of my math professors showed us a
very similar game as a method of demonstrating the sum of an infinite
geometric series. In that game, you had a probability of 1/2 of
winning each turn, and the ratio between your turns was 1/4. (Note: 1/4
= (1/2)*(1/2). The game involved you and another person taking turns
tossing a fair coin. The first person to get heads won. S = (1/2) /
(1 - 1/4) = 1/2 / 3/4 = 4/6 = 2/3. You need more turns to guarantee
you'll win, but the odds are still stacked in the favour of the first
person to toss.).
Thanks for posting the puzzle Seth, now I can say I did some Math 101
and Math 122 homework tonight. ;-)
Jim
--
Jim Roepcke
Roepcke Computing Solutions:
http://www.roepcke.com/
Jim's weblog:
http://jim.roepcke.com/
