 All about flooble | fun stuff | Get a free chatterbox | Free JavaScript | Avatars  perplexus dot info  Matching Matchbox Muse (Posted on 2010-03-30) 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 | 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               expectationremaining    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)/1100   next105   print110   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 (0)
Unsolved Problems
Top Rated Problems
This month's top
Most Commented On

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