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

Home > Probability
Pandigital + (Posted on 2017-05-03) Difficulty: 3 of 5
Let p(n) be the probability that a random n-digit integer has all 10 digits occurring each at least once.
Let us allow leading zeroes; e.g. 0000018274 will be included in the set of 10-digit numbers).

So p(9) is 0 , p(10) = 10!/1010 and p(1000) would be very close to 1.

a. What is the smallest n for which p(n) > 1/2?
b. >3/4?
c. >.95?

No Solution Yet Submitted by Ady TZIDON    
No Rating

Comments: ( Back to comment list | You must be logged in to post comments.)
Hints/Tips re: Matrix solution - Diagonalization and a closed form function Comment 3 of 3 |
(In reply to Matrix solution by Brian Smith)

To find a closed form expression for the original probability function, start by diagonalizing T into T = Q * D * Q^-1.

T is a lower-triangular matrix so its eigenvalues are simply the elements on the main diagonal.  The corresponding eigenvectors turn out to be the rows of Pascal's triangle with alternating signs added.  Then Q, D, and Q^-1 are: 
[   1   0   0   0   0   0   0   0   0   0 ]   [0.1  0   0   0   0   0   0   0   0   0 ]   [   1   0   0   0   0   0   0   0   0   0 ]
[  -9   1   0   0   0   0   0   0   0   0 ]   [ 0  0.2  0   0   0   0   0   0   0   0 ]   [   9   1   0   0   0   0   0   0   0   0 ]
[  36  -8   1   0   0   0   0   0   0   0 ]   [ 0   0  0.3  0   0   0   0   0   0   0 ]   [  36   8   1   0   0   0   0   0   0   0 ]
[ -84  28  -7   1   0   0   0   0   0   0 ]   [ 0   0   0  0.4  0   0   0   0   0   0 ]   [  84  28   7   1   0   0   0   0   0   0 ]
[ 126 -56  21  -6   1   0   0   0   0   0 ]   [ 0   0   0   0  0.5  0   0   0   0   0 ]   [ 126  56  21   6   1   0   0   0   0   0 ]
[-126  70 -35  15  -5   1   0   0   0   0 ]   [ 0   0   0   0   0  0.6  0   0   0   0 ]   [ 126  70  35  15   5   1   0   0   0   0 ]
[  84 -56  35 -20  10  -4   1   0   0   0 ]   [ 0   0   0   0   0   0  0.7  0   0   0 ]   [  84  56  35  20  10   4   1   0   0   0 ]
[ -36  28 -21  15 -10   6  -3   1   0   0 ]   [ 0   0   0   0   0   0   0  0.8  0   0 ]   [  36  28  21  15  10   6   3   1   0   0 ]
[   9  -8   7  -6   5  -4   3  -2   1   0 ]   [ 0   0   0   0   0   0   0   0  0.9  0 ]   [   9   8   7   6   5   4   3   2   1   0 ]
[  -1   1  -1   1  -1   1  -1   1  -1   1 ]   [ 0   0   0   0   0   0   0   0   0   1 ]   [   1   1   1   1   1   1   1   1   1   1 ]

Then T^(n) = Q * D^(n) * Q^-1  Focusing on the element (10,1), its closed form valuation is f(n) = -1*0.1^n + 9*0.2^n - 36*0.3^n + 84*0.4^n - 126*0.5^n + 126*0.6^n - 84*0.7^n + 36*0.8^n - 9*0.9^n + 1.  Then the original p(n) = f(n-1).

  Posted by Brian Smith on 2017-05-04 12:23:54
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 (2)
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