Permutation with Condition

Question

The numbers 1-9 are drawn from a hat at random. Without repetition of numbers, how many numbers (with all digits drawn-- eg. 987654321) would be divisible by 11?

First I recalled that a number is divisible by 11 if the number's alternating digits minus the other digits are equal to a number divisible by 11.

Honestly, I did a bit of guess and check to follow and found that 948576321 was an answer divisible by 11. Therefore if I rearranged 9,8,7,3, and 1 (the leading alternating numbers) it would bring the same result. So I solved the permutation to receive 120 possible combinations. I then took the permutation of 4,5,6, and 2 and received a total of 24 combinations.

I multiplied these two answers together to get a grand total of 2880 combinations that would be divisible by 11.

Is this the correct answer? Please help, and thanks in advance! :)

Answer 1

The correct answer is 31680. Your combination of alternating numbers (9, 8, 7, 3, 1) is only one out of 11 possibilities:

1. 1, 2, 3, 4, 7
2. 1, 2, 3, 5, 6
3. 1, 3, 7, 8, 9
4. 1, 4, 6, 8, 9
5. 1, 5, 6, 7, 9
6. 2, 3, 6, 8, 9
7. 2, 4, 5, 8, 9
8. 2, 4, 6, 7, 9
9. 2, 5, 6, 7, 8
10. 3, 4, 5, 7, 9
11. 3, 4, 6, 7, 8

So we end up with $11 \cdot 5! \cdot 4! = 11 \cdot 120 \cdot 24 = 31680$.

Answer 2

Here’s a systematic approach; it’s still a bit tedious in spots, but not unreasonably so.

The sum of all $9$ digits is $45$. You need to split the digits into a set $A$ of $5$ digits, those in the odd-numbered positions, and a set $B$ of $4$ digits, those in the even-numbered positions, whose sums differ by a multiple of $11$. If $a$ is the sum of the digits in $A$ and $b$ the sum of the digits in $B$, then $a-b$ is a multiple of $11$, and $a+b=45$.

Clearly $b=45-a$, so $a-b=a-(45-a)=2a-45$. The smallest possible value of $a$ is $1+2+3+4+5=15$, and the largest is $9+8+7+6+5=35$, so $-15\le a-b\le25$. The multiples of $11$ in that range are $-11,0,11$, and $22$. However, $2a-45$ is clearly odd, so in fact the only possible values of $a-b$ are $-11$ and $11$.

• If $a-b=2a-45=-11$, then $a=17$.
• If $a-b=2a-45=11$, then $a=28$.

What sets of $5$ digits sum to $17$? Since $1+2+3+4+5=15$, we either increase $5$ by $2$ to get the set $\{1,2,3,4,7\}$ or increase $4$ and $5$ by $1$ each to get the set $\{1,2,3,5,6\}$; anything else produces either too big a sum or duplicated digits.

It’s a bit harder to enumerate the sets that sum to $28$, because there are more of them. A good starting point is the fact that $9+8+7+6+5=35$, which is $7$ too large. First note that we need to have at least one of $8$ and $9$: $7+6+5+4+3=25$ is too small. What can we do without the $9$? $8+7+6+5+4=30$, so, much as in the previous case, our only choices are to subtract $2$ from $4$ to get the set $\{8,7,6,5,2\}$ or subtract $1$ each from $4$ and $5$ to get $\{8,7,6,4,3\}$. Every other set will include the $9$.

Let’s try next for the ones that include $9$ but not $8$. $9+7+6+5+4=31$; we can subtract $3$ from the $4$, the $5$, or the $6$ to get the sets $\{9,7,6,5,1\}$, $\{9,7,6,4,2\}$, and $\{9,7,5,4,3\}$. A little experimentation shows that trying to reduce the sum by $3$ by subtracting $2$ from one digit and $1$ from another produces nothing new.

The last batch will be those containing both $9$ and $8$. If we keep the $7$ as well, we already have a total of $9+8+7=24$, and the only two digits that supply the missing $4$ are $1$ and $3$, giving us the set $\{9,8,7,3,1\}$. If we start with $9,8$, and $6$, we can get the missing $5$ from either $1$ and $4$ or $2$ and $3$, giving us the sets $\{9,8,6,4,1\}$ and $\{9,8,6,3,2\}$. If start with $9,8$, and $5$, the only way to get the missing $6$ is with $2$ and $4$, giving us the set $\{9,8,5,4,2\}$. And $9+8+4+3+2=26$ is too small, so we’ve found all of the possibilities for the set $A$.

As you already observed, we can permute $A$ and $B$ arbitrarily, so each choice of $A$ yields $5!4!$ numbers, and there are $11$ possibilities for $A$, for a grand total of $11\cdot5!4!=31,680$ numbers.

Answer 3

Every number of the form $x*11$ is divisible by 11. Now you must think about $x$.

$x$ must be such that $(x)*11$ is a number with 9 digits! If it is useful for you I can explain it more.