2
$\begingroup$

The question is to determine how many five-digit numbers there are (using the digits 0-9) where each digit can appear up to three times in the number. The total number of numbers that can be made using 0-9 is $10^5$ so that places an upper restriction on the answer. Finding how many there are with no repeated digits is also just a permutation, given by $10!/(10-5)!$. It's also easy to count up how many numbers there are where each digit appears exactly four and exactly five times, and subtract those from $10^5$, which gives 99,540 possible numbers, but I feel this is either wrong or at least a very naive way of doing it. Is there a better way of doing it?

$\endgroup$
1
  • 1
    $\begingroup$ Counting all and subtracting the "bad" ones seems like a sensible strategy. There is a possible complication in that for example $00122$ may not be considered a $5$-digit number by the problem-setter. $\endgroup$ Oct 7, 2014 at 0:38

1 Answer 1

1
$\begingroup$

We should form two cases, one of 0 (because 0 can't be the first one) and one with all numbers 1-9, to find out how many numbers there are that use a digit 3 or more times. Then, we can subtract this from 90,000 (the number of five digit numbers). This will give us the desired number.

Case 1: 0 shows up more than 3 times.

When you think about it, the only way 0 shows up more than three times is if the number is 10,000; 20,000; 30,000; etc., up to 90,000. So we just have to add nine to the following case.

Case 2: Some number 1-9 shows up more than 3 times.

This is slightly more tricky. We start with 1, just to make things easy. But when you really start to think about it, 1's would have to fill 4/5 slots in the number for it to break the rules. Therefore, the numbers (if the 5th number is 2) would be as follows:

11112

11121

11211

12111

21111

and we can do the same thing for every other number, 0 and 2-9. However, 01111 does not count, so we have to make sure to get rid of that one as well. Therefore, there are 8 times 5, or 40 ways this can be done for the number 1 for 2-9, and 4 ways this can be done with 0. Overall, the number 1 can be made in 44 different ways. This is also true for 2, 3, 4, 5, 6, 7, 8, and 9 (try plugging them in above where 1 is now). This gives us 9*44 + 9 ways to break the rules, or 9*45 ways. This comes out to 405 ways.

Subtract this from 90,000 and you will see that there are 89,595 ways to accomplish your task.

$\endgroup$
2
  • $\begingroup$ What if we say that numbers that start with zero are still considered? For example, 00122 is still a valid option. $\endgroup$
    – Philip
    Oct 7, 2014 at 0:59
  • $\begingroup$ That... changes things. In that case, you would have only a single case, as 0 would be no different from any other number. You would have 0000n, 000n0, 00n00, 0n000, and n0000 for all n, 0 through 9. This gives you 5 times per number, so for 10 numbers you would have 50 options for 0. However, we would also have 50 options for all other numbers 1-9, so we would end up with 500 total ways to break the rules. This would give us 89,500 total ways to do it and not break the rules. $\endgroup$ Oct 7, 2014 at 4:31

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .