Date: Tue, 9 Mar 2000 15:40:07 +0000
From: David L. Arnett
Being somewhat foolish in nature, I tackled this one by hand. I started out by methodically coming up with all possible ways the problem could occur, beginning with k=10. This was easy, as you had to have either xxxxxxxxxx or yyyyyyyyyy. This gives us a probability of 2*(1/2)^10.
Next was k=9. Still easy, but more possibilities: xxxxxxxxxyx,
xxxxxxxxyxx,... yxxxxxxxxxx. The same goes for reversing the
x's and y's. This gives us a probability of 20*(1/2)^11 (the extra 1/2
comes into play as there are now 11 sticks of gum being drawn).
Next was k=8. Somewhat harder (don't worry, I found a pattern I'll
get to soon): xxxxxxxxxyyx, xxxxxxxxyxyx, xxxxxxxxyyxx,
xxxxxxxyxxyx, xxxxxxxyxyxx,... yyxxxxxxxxxx. Once again, the
same goes for reversing the x's and y's. This gives us a probability
of (add it up, but don't use your fingers; you don't have enough)
110*(1/2)^12.
For k=7, the same work provided 440*(1/2)^13.
OK, I'm tired of reversing the x's and y's. Let's drop the factor of 2
by simultaneously lowering the exponent of the (1/2) terms by 1.
Think about it, it works.
This gives us (1/2)^9, 10*(1/2)^10, 55*(1/2)^11, and 220*(1/2)^12 for
k=10, 9, 8, and 7, respectively.
As I went through the possibilities, I also noticed the pattern I was
using could be duplicated mathematically by determining the
multiplier as follows:
For k=8: Sum(a=1,10){a} = 1+2+3+...+10 = 55
For k=7: Sum(a=1,10){Sum(b=1,a){b}} =
(1)+(1+2)+(1+2+3)+...+(1+2+3+...+10) = 220
This technique can be continued through k=1.
As for the exponents, they simply increase by 1 for each value of k.
This gives us final results of:
k=10: 1*(1/2)^9 = 0.001953125
k=9: 10*(1/2)^10 = 0.009765625
k=8: 55*(1/2)^11 = 0.02685546875
k=7: 220*(1/2)^12 = 0.0537109375
k=6: 715*(1/2)^13 = 0.0872802734375
k=5: 2002*(1/2)^14 = 0.122192382812
k=4: 5005*(1/2)^15 = 0.152740478516
k=3: 11,440*(1/2)^16 = 0.174560546875
k=2: 24,310*(1/2)^17 = 0.185470581055
k=1: 48,620*(1/2)^18 = 0.185470581055
---------------
(Check) Total = 1
An interesting note: it is possible to come up with the sums for the
multipliers easily by hand in the following manner (trust me, I didn't
just plug through that many nested sums):
for k=9, we have (for each possible order):
1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 = 10
Now, start with 1 and add the corresponding number from the k=9
sequence to obtain the next number in the k=8 sequence (in this
case, all the numbers added are one):
1 + 2 + 3 + 4 + 5 + 6 + 7 + 8 + 9 + 10 = 55
For k=7, we start with 1, add 2, then add 3, etc. (numbers from the
k=8 sequence):
1 + 3 + 6 + 10 + 15 + 21 + 28 + 36 + 45 + 55 = 220
For k=6, we get:
1 + 4 + 10 + 20 + ...
and so on.
Why does the probability of k=1 equal the probability of k=2?
Because the multiplier for k=1 is twice the multiplier for k=2, and
the exponent for the (1/2) term is raised by one, cancelling each
other out. Why is that? I have no idea. Anyone?