2
$\begingroup$

How many numbers with six digits(Basically from 100 000 to 999 999) have exactly two equal digits and the rest are all different?

What I tried: first digit can't be a zero, so the number would have 5 digits.

I have at least 2 cases, the repeated digit is in the first slot or on another

first slot has the repeated digit:

I have 9 numbers to place on the first slot(an on the other repeated digit), and then I have 5C1 places to put the second repeated number, then I have 9*8*7*6 ways to place the other numbers. So first case:9 * 5 * 9A4 = 136080

not first slot has the repeated digit:

5C2 places to put the repeated digits(all except the first) and I have 10 digits to use, then I have two cases. I can have the number 0(zero) or not(this will cause trouble because I can't place the number 0 on the first slot, so I divided in two more cases)

There is not a zero: Easy, 8A4(8*7*6*5)

There is a zero: Hmmm, the first digit can't be a zero, so I have 8(I have 8 because I can't use the number 0 nor the repeated number) options left, then for the other 3 places I want to have a zero, otherwise I was just repeating the last case,I want 3 numbers, have a zero, so I want to pick two numbers, 7C2(7 possibilities, because out of 10 I used 0, the repeated and the first slot number), okay I have 3 numbers without order, so I do 3! or 3A3 to arrange them.

So the second case: 5C2 * 10 [8A4 + 8*7C2*3!] = 268800

So my solutions: 136080 + 268800 = 404880

However there is another solution that seems to be correct but gives a different result : 5C2 * 9A4 + 9[5C1*9A4 + 5C2*8*8*7*6] = 408240 Explaining briefly: 5C2 * 9A4, this case, the repeated number is 0, and is not on the first slot.

9*5C1*9A4, this case ocuppy the first slot(repeated number), I have 9 numbers/possibilities for the first slot and the repeated number, then 9 numbers left for all the other places 9A4

9*5C2*8*8*7*6, 9 numbers for the two choosen spots(not the first slot, there are 9 numbers and not 10, because that case is already done, it's the first case), then for the first slot I can't have number zero so 8, then for the other 3 slots I have 8*7*6, so that's the thought process.....

Which is the correct one, or are both wrong?

$\endgroup$
4
  • $\begingroup$ I might be wrong but to my mind its $10P5=30240$ $\endgroup$ – Rhys Hughes Nov 16 '18 at 23:03
  • 2
    $\begingroup$ Does $001234$ count as a six-digit number? $\endgroup$ – Barry Cipra Nov 16 '18 at 23:04
  • $\begingroup$ Please edit your question to show what you have attempted and explain where you are stuck so that you receive responses that address the specific difficulties you are encountering. This tutorial explains how to typeset mathematics on this site. $\endgroup$ – N. F. Taussig Nov 16 '18 at 23:20
  • $\begingroup$ Thanks, there's what I have attempted $\endgroup$ – Nuno Mateus Nov 17 '18 at 0:48
2
$\begingroup$

The second solution is correct.

Let's look at the first solution.

first slot has the repeated digit:

I have 9 numbers to place on the first slot(an on the other repeated digit), and then I have 5C1 places to put the second repeated number, then I have 9*8*7*6 ways to place the other numbers. So first case:9 * 5 * 9A4 = 136080

Looks ok.

not first slot has the repeated digit:

5C2 places to put the repeated digits(all except the first) and I have 10 digits to use, then I have two cases. I can have the number 0(zero) or not(this will cause trouble because I can't place the number 0 on the first slot, so I divided in two more cases)

There is not a zero: Easy, 8A4(8*7*6*5)

Why? This case only seems to select 4 of the 5 distinct digits. I think it should be 9A5 in your notation.

There is a zero: Hmmm, the first digit can't be a zero, so I have 8(I have 8 because I can't use the number 0 nor the repeated number) options left, then for the other 3 places I want to have a zero, otherwise I was just repeating the last case,I want 3 numbers, have a zero, so I want to pick two numbers, 7C2(7 possibilities, because out of 10 I used 0, the repeated and the first slot number), okay I have 3 numbers without order, so I do 3! or 3A3 to arrange them.

So far this is conditioned on the first digit not being repeated and one of the digits being a zero. You haven't chosen the repeated number, so the first digit has 9 possibilities. Then there are 4 distinct digits to select, one of which is 0, giving 9*8C3*4!.

So the second case: 5C2 * 10 [8A4 + 8*7C2*3!] = 268800

This should be 5C2 * (9A5 + 9*8C3*4!) = 272160.

Then the overall result is 136080 + 272160 = 408240, in agreement with the second approach.

As a bonus, here's a simpler solution.

Ignore for the time being the restriction that the first digit cannot be zero. We pick the two positions which have the repeat in 6C2 ways, and then we pick the five distinct values as 10A5. Now, by symmetry, exactly 1/10 of the patterns we've generated start with a zero, so the final solution is 6C2 * 10A5 * 9/10 = 408240.

$\endgroup$
5
  • $\begingroup$ Wow thanks for the amazing answer I'm in a hurry so i'll question better later, but in your simpler solution, I understand that out of 10 digits one is 0, but so chance of not being a 0 is 9/10.... but this doesn't seem correct at all, because that's not the only restriction, once you have a total of 5 places(with different numbers), shouldn't it be like1-1/(5*10) instead of 9/10? $\endgroup$ – Nuno Mateus Nov 19 '18 at 7:56
  • $\begingroup$ Nevermind I got it $\endgroup$ – Nuno Mateus Nov 19 '18 at 15:13
  • $\begingroup$ Thanks for the answer, I understand now clearly what I did wrong. A quick question, I'm learning combinatorics in high school and these kind of exercises are the "ending point" of this subject , however It's the one I have the most curiosity to learn so I'd like to read a book about it, in your solution the "9/10" trick is completely new to me, does it come from your intuiton/classes, or did you read really good book? So do you advice any? I'm willing to read Principles And Techniques In Combinatorics,Chen Chuan-Chong I understand a bit about graph theory* $\endgroup$ – Nuno Mateus Nov 19 '18 at 23:12
  • $\begingroup$ That was a flash of inspiration. I don't think I've ever formally studied combinatorics: I've taught myself bits which I found useful for tackling programming challenges like Project Euler. The only book on the subject I have is Partitions by Andrews and Eriksson. I don't know how far you'd be able to get through it without having to read up other stuff on Wikipedia, but as a high school student you probably have loads of free time ;-) and it's a cheap paperback. $\endgroup$ – Peter Taylor Nov 20 '18 at 7:31
  • $\begingroup$ Sorry, correction: the title is Integer Partitions. $\endgroup$ – Peter Taylor Nov 20 '18 at 7:43

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.