perplexus.info :: Probability : All Combos 2

All Combos 2 (Posted on 2024-05-10)

M is an n-digit positive integer composed of a string of random decimal digits (no leading zero) selected from a uniform distribution. For each case below, determine the value of the smallest number of digits associated with a probability of at least 0.5 that M contains:
(A) all of the digits 0 to 9
(B) all of the 2-digit combinations 00, 01, ..., 99
(C) all of the 3-digit combinations 000, 001, ..., 999

No Solution Yet Submitted by Larry

No Rating

Comments: ( Back to comment list | You must be logged in to post comments.)

Part A (spoiler)

| Comment 1 of 3

Solved as a Markov process

Let P(n,k) be the probability of having k distinct digits out of the first n.

Then P(1,1) = 1

P(1,2) = P(1,3) = ... = P(1,10) = 0

P(n+1, 1) = .1 * P(n,1)

P(n+1,2) = .9 *P(n,1) + .2*P(n,2)

P(n+1,3) = .8 *P(n,2) + .3*P(n,3)

...

P(n+1,9) = .2 *P(n,8) + .9*P(n,9)

p(n+1,10) = .1*P(n,9) + P(n,10)

I implemented these formulas in Excel and came up with

p(26,10) = 0.478985

p(27,10) = 0.519634

SO THE ANSWER to Part (A) is 27

I think this same approach will work for part (B) and (C), except that there are 10 times and 100 times as many formulae

Posted by Steve Herman on 2024-05-10 14:20:44

Please log in:

Login:
Password:
Remember me:

Sign up! \| Forgot password

Search:

Search body:

Forums (1)
Newest Problems
Random Problem
FAQ | About This Site
Site Statistics
New Comments (4)
Unsolved Problems
Top Rated Problems
This month's top
Most Commented On

Chatterbox:


perplexus dot info