1

What I'm looking for here is not the answer, but a way to approach this question to get to the answer.

Actually, there are some answers where this question was posted, but they are hard to understand. I do see that apparently the answer lies in the fact that you can sum pairs of numbers that add up to 9. E.g., if we have the set {0, 1, 2, 3, 4, 5, 6, 7, 8, 9}, you can sum (0 + 9 = 9), (1 + 8 = 9), ..., (9 + 0 = 9). Also, not summing them but pairing them also produces a number that is divisible by 9 (09), (18), ..., (90). Seems like magic :-) But how to go from here?

Please if you could, explain in simplest terms possible.

Garth Marenghi
  • 1,115

2 Answers2

3

For any collection of $8$ digits $a_1\dots a_8$, either all permutations of them will yield one number that will be divisible by $9$ or none of them will. This is because a number is divisible by $9$ if and only if the sum of its digits is divisible by $9$.

So, the first answer you need to get is:

How many collections of $8$ distinct digits are there if their sum must be divisible by $9$?

To answer this question, first note that the sum of the available $10$ digits is $45$. Now, you have to take $2$ of the numbers away, and the sum must be divisible by $9$. You can see that:

  • The minimum sum you can remove is $1$
  • The maximum is $17$

Which means the new sum will be somewhere between $28$ and $44$, and there is only one number divisible by $9$ in that range.

After you answer the first question, the rest should be easy pickings. For each collection of $8$ digits, there are $8!$ numbers they produce. The only thing you need to be careful is whether the collection includes $0$ or not. If it does, $7!$ of the resulting numbers (those with $0$ in their first place) will be $7$ digit numbers, while the remaining $7\cdot 7!$ will be $8$ digit numbers.

5xum
  • 123,496
  • 6
  • 128
  • 204
  • So we have 10 numbers: {0, 1, 2, 3, 4, 5, 6, 7, 8, 9}. Their sum is 45. But we want 8 numbers, and the sum of those 8 numbers must still be divisible by 9. So we must remove two elements. How come the minimum sum is 1? If I would take two numbers away, then it would be a pair of numbers that add up to 9. 0 and 9 for example. – Garth Marenghi Sep 09 '16 at 09:12
  • @GarthMarenghi No no, the minimum sum of the numbers removed is $1$ (taking away $0$ and $1$). This means the maximum sum of the remaining numbers is $44$. – 5xum Sep 09 '16 at 09:13
  • I'm so sorry, I know you try and I don't want to get on your nerves, but.. If you'd remove 0 and 1, than you are left with {2, 3, 4, 5, 6, 7, 8, 9} whose sum is 44, not divisible by 9. I keep misreading "Now, you have to take 2 of the numbers away, and the sum must be divisible by 9". We just took two numbers away, but their sum is not divisible by 9. – Garth Marenghi Sep 09 '16 at 09:18
  • @GarthMarenghi Yes. What I am trying to say is you must satisfy both conditions. You need to find two numbers you take away so that the remaining sum is divisible by $9$. And since you know the remaining sum will be somewhere between $28$ and $44$, that isn't as hard, because you know what the remaining sum must therefore be... – 5xum Sep 09 '16 at 09:20
  • Thank you for your effort! – Garth Marenghi Sep 09 '16 at 10:14
3

Observe that $0+1+2+3+4+5+6+7+8+9=45$.

We need to remove $2$ digits, while keeping the sum of the remaining $8$ digits divisible by $9$.

The options are:

  • Remove $[0,9]$ and keep $[1,2,3,4,5,6,7,8]$
  • Remove $[1,8]$ and keep $[0,2,3,4,5,6,7,9]$
  • Remove $[2,7]$ and keep $[0,1,3,4,5,6,8,9]$
  • Remove $[3,6]$ and keep $[0,1,2,4,5,7,8,9]$
  • Remove $[4,5]$ and keep $[0,1,2,3,6,7,8,9]$

Now, simply add up the amount of $8$-unique-digit numbers for each option:

  • With $[1,2,3,4,5,6,7,8]$ we can generate $8!=40320$ such numbers
  • With $[0,2,3,4,5,6,7,9]$ we can generate $8!-7!=35280$ such numbers
  • With $[0,1,3,4,5,6,8,9]$ we can generate $8!-7!=35280$ such numbers
  • With $[0,1,2,4,5,7,8,9]$ we can generate $8!-7!=35280$ such numbers
  • With $[0,1,2,3,6,7,8,9]$ we can generate $8!-7!=35280$ such numbers

Hence the total amount of $8$-unique-digit numbers divisible by $9$ is:

$$40320+35280+35280+35280+35280=181440$$

barak manos
  • 43,109