For a 5N-digit base-2N positive integer X, determine the probability (in terms of N) that X contains each of the digits from 0 to 2N-1 at least twice but at most thrice.
Note: N is a positive integer ≥ 2, and X does not contain any leading zero.
a) Well, the total number of all possible numbers is (2N)^(5N)
b) Half of the N of the 2N digits must appear twice, and the other half must appear three times. How many ways can we select the N digits that appear three times? Well, it is C(2N,N)
c) And how many ways can the digits (0,0,1,1,...N,N) Union ((N+1),(N+1),(N+1),(N+2), ... 2N, 2N, 2N) be arranged?
It is (5N)!/(2!)^N*(3!)^N = (5N!)/12^N
d) Putting it all together, probability is
C(2N,N) * ((5N!)/12^N) / ((5N)^(2N))
e) If N = 1, this formula gives (2 * 5*4*3*2/12)/32 = 20/32, which is the right answer. so maybe I've done it right,
There may be a way to simplify the formula, but I don't see it immediately.
/**********************************************/
Correction: I just noticed that the leading digit cannot be zero.
This eliminates 1 out of every 2N otherwise acceptable numbers,
so the correct formula is really (2N-1)/(2N) * C(2N,N) * ((5N!)/12^N) / ((5N)^(2N)).
If N = 1, this reduces the probability in half, down to 10/32
/******************************************/
Correction # 2 : Ignore correction #1. The requirement that the leading digit cannot be zero reduces both the numerator and the denominator by the same percentage, (2N-1)/N. Thus the original formula, C(2N,N) * ((5N!)/12^N) / ((5N)^(2N)), is correct.
If N = 1, the probability is 10/16, as originally given.
The 10 numbers that satisfy are 11000, 10100, 10010, 10001,
11100, 11010,11001, 10110, 10101, and 10011, out of the 16 numbers between 16 and 31.
Edited on June 20, 2010, 1:33 am
Edited on June 20, 2010, 9:13 pm
Solution? (spoiler)
