All about flooble | fun stuff | Get a free chatterbox | Free JavaScript | Avatars    
perplexus dot info

Home > Probability
Matching Matchbox Muse (Posted on 2010-03-30) Difficulty: 3 of 5
Professor X smokes a pipe. He carries two identical matchboxes, originally containing 20 matches each. When he lights his pipe, he chooses a matchbox at random and lights his pipe with one match and discards the used match.

There will eventually arise an occasion when he first selects a matchbox with only one match in it. At this point, what is the expected number of matches in the other box?

No Solution Yet Submitted by K Sengupta    
No Rating

Comments: ( Back to comment list | You must be logged in to post comments.)
Solution solution | Comment 2 of 15 |

Keep in mind that when the professor "first selects a matchbox with only one match in it", he is, on that occasion, reducing the number of matches in that box to zero.

The probability that there will be 20 remaining in the other box is that of the first 20 matches all being chosen from the same box, which is 2*(1/2^20).

That there are 19 in the other box is the probability that exactly 1 of the first 20 is from that "other" box and the 21st is from the same box as the majority of the others. The probability of this is 2*C(20,1)*(1/2^21).

That there are 18 in the other box is the probability that exactly 2 of the first 21 were from the "other" box and the 21st is from the same box as the majority. This is 2*C(21,2)*(1/2^22).

In general then, the probability there are 20 - n remaining in the other box is

2*C(19+n,n)*(1/2^(20+n))

The first case, that there are 20 remaining in the "other" box, fits this as C(19,0) = 1.

To get the expected number remaining in the other box, we need multiply each such probability by the given number 20 - n and add all such contributions up.

The probabilities of the exact numbers of matches remaining in the other box are tabulated:

number                       probability               expectation
remaining    rational fraction            decimal       contribution
 20      1/524288                       0.000001907     0.000038147
 19      5/262144                       0.000019073     0.000362396
 18      105/1048576                    0.000100136     0.001802444
 17      385/1048576                    0.000367165     0.006241798
 16      8855/8388608                   0.001055598     0.016889572
 15      5313/2097152                   0.002533436     0.038001537
 14      44275/8388608                  0.005277991     0.073891878
 13      82225/8388608                  0.009801984     0.127425790
 12      2220075/134217728              0.016540848     0.198490173
 11      1726725/67108864               0.025730208     0.283032283
 10      10015005/268435456             0.037308801     0.373088010
 9       13656825/268435456             0.050875638     0.457880739
 8       141120525/2147483648           0.065714365     0.525714923
 7       10855425/134217728             0.080879219     0.566154532
 6       51175575/536870912             0.095321937     0.571931619
 5       57998985/536870912             0.108031528     0.540157640
 4       2029964475/17179869184         0.118159484     0.472637935
 3       1074687075/8589934592          0.125110042     0.375330125
 2       4418157975/34359738368         0.128585321     0.257170641
 1       4418157975/34359738368         0.128585321     0.128585321
 

 
The probabilities do add up to 1 and the expected value comes out to be 172308161025/34359738368 = 5.01482750478317029774188995361328125 (this is the exact terminating decimal, as the denominator is a power of 2).

 

 10   for N=0 to 19
 20     P=2*combi(19+N,N)//2^(20+N)
 30     Expected=Expected+P*(20-N)
 40     Totp=Totp+P
 50     print 20-N,P;
 60     print tab(40);using(1,9),P/1,P*(20-N)/1
100   next
105   print
110   print Totp,Expected,Expected/1
 

Simulation verification:

DEFDBL A-Z
FOR trial = 1 TO 1000000
  mb(0) = 20
  mb(1) = 20
  DO
   r = INT(RND(1) * 2)
   mb(r) = mb(r) - 1
  LOOP UNTIL mb(0) = 0 OR mb(1) = 0
  v = mb(0) + mb(1)
  tot = tot + v
  n = n + 1
  PRINT tot; n, tot / n
NEXT


produces as its last line of output:

5013755  1000000            5.013755

meaning that 5,013,755 matches were left in the "other" boxes when the trial was repeated a million times for a mean of 5.013755.
 
 


  Posted by Charlie on 2010-03-30 15:27:18
Please log in:
Login:
Password:
Remember me:
Sign up! | Forgot password


Search:
Search body:
Forums (0)
Newest Problems
Random Problem
FAQ | About This Site
Site Statistics
New Comments (3)
Unsolved Problems
Top Rated Problems
This month's top
Most Commented On

Chatterbox:
Copyright © 2002 - 2017 by Animus Pactum Consulting. All rights reserved. Privacy Information