# How many ways a 9 digit number can be formed using the digits 1 t0 9 without repetition such that it is divisble by $11$.

How many ways a 9 digit number can be formed using the digits 1 t0 9 without repetition such that it is divisible by $11$.

My attempt- A number is divisible by 11 if the alternating sum of its digit is divisible by 11?

The other thing to notice is as it is a 9 digit number formed by digits 1 to 9, exactly once each digit from 1 to 9 will appear in the number.

Basically, the question boils down to how many ways we can arrange 123456789 so that the alternating sum of the digit is divisible by 11.

I am not able to proceed further. Any help would be appreciated.

Since the raw digit sum of $1..9$ will be $45$, an odd number, we clearly can't have two equal sums for the even-position and odd-position digits. So we need to have one set of digits sum to $17$ and the others to $28$, so that the difference is divisible by $11$.

This can be done either way around; $28$ as the sum of the four even-position digits or the sum of the five odd-position digits.

Making 28 with only four digits is the more restrictive case. The only options are {9,8,7,4} and {9,8,6,5}. With five digits there are more choices: {9,8,7,3,1}, {9,8,6,4,1}, {9,8,6,3,2}, {9,8,5,4,2}, {9,7,6,5,1}, {9,7,6,4,2}, {9,7,5,4,3}, {8,7,6,5,2}, {8,7,6,4,3}.

So we have 11 ways of dividing the digits suitably, and in each case we can permute the five odd-position digits freely and similarly the four even-position digits. So the number of possibilities is: $$11\cdot 5!\cdot 4! = 11\times 120\times 24 = 31680$$

As a sanity check, this total is reasonably close to $\frac{9!}{11}$, ie. one-eleventh of the total permutations of the digits.

Let's denote such a number by $\overline{a_9 a_8\cdots a_1}$ you get $$\sum_{i=1}^9 a_i = \sum_{i=1}^9 i = 45.$$ Furthermore we can indeed use the alternating sum to check divisibility by $11$. This can be expressed as $$(a_1+a_3+a_5+a_7+a_9) - (a_2+a_4+a_6+a_8) \equiv 0 \pmod{11}.$$ Since we already know the total sum of the digits we can simplify this somewhat to $$(45 -(a_2+a_4+a_6+a_8)) - (a_2+a_4+a_6+a_8) \equiv 0 \pmod{11},$$ which again simplifies to $$a_2+a_4+a_6+a_8 \equiv 6 \pmod{11}.$$ Now we want to find the amount of distinct solutions this equation has, where we choose $a_2,a_4,a_6,a_8$ distinct and decreasing from $\{1,\dots 9\}$. I don't know a more clever trick than simply checking, which is not that difficult in this case.

• Clearly $a_2+a_4+a_6+a_8 = 6$ has no solutions.

• The equation $a_2+a_4+a_6+a_8 = 17$ has nine solutions and this is the most work.

• The equation $a_2+a_4+a_6+a_8 = 28$ only has two solutions, namely $\left\{\{9, 8, 7, 4\}, \{9, 8, 6, 5\}\right\}.$
• The equation $a_2+a_4+a_6+a_8 = 6+11k$ for $k\geq 3$ has no solutions since the maximum $9+8+7+6=30$ is already too small.

We get a total of $11$ choices of digits. For all these choices we can arrange $a_2,a_4,a_6,a_8$ in $4!$ ways and $a_1,a_3,a_5,a_7,a_9$ in $5!$. The total number of solutions is $$11\cdot 4! \cdot 5! = 31680.$$

Denote by $a_1a_2...a_9$ such a number. Let $a=\sum_{i=0}^4 a_{2i+1}$ and $b=\sum_{i=1}^4 a_{2i}$, then $b-a$ is a multiple of 11. Note that since $a+b=1+2+...+9=45$ is odd necessarily $b-a$ is odd. So $a-b=11$ or $a-b=33$.

1. Case $b-a =11$

If we add the equation $a+b=45$ we obtain $b=28$, and $a=17$. Now it is easy to write down all solutions.

1. Case $b-a = 33$

Then by adding $a+b=45$ we obtain $b=39$, and $a=6$. This is not possible since $1+2+..+4$ is already way too big.

• Of course the second case is not feasible, but worth noting for completeness. – Joffan Jun 30 '16 at 9:01
• yes thats true. – math635 Jun 30 '16 at 9:02
• @Why are you considering only positive multiple of 11? What about -11? – Babai Jun 30 '16 at 9:08
• (+1) But actually, $b-a=\pm11$, not simply $11$. (Re "Now it is easy to write down all solutions.", this is true once one notices that 1+2+3+4+5 is already 15 hence there are very few solutions... but my impression is that some further indications might be useful to the OP.) – Did Jun 30 '16 at 9:09
• @Did Correct. Joffan whereas has considered the $b-a=-11$ where he considered 28 as sum of five odd digits. – Babai Jun 30 '16 at 9:17

$$1+2+...+9=\frac{9\cdot10}{2}=45\\(x_1+x_3+x_5+x_7+x_9)-(x_2+x_4+x_6+x_8)=11m$$ $m$ must be $1$ or $3$ since 45 is odd and $3$ is discarded immediately so we have $$\begin{cases}X+Y=45\\X-Y=11\end{cases}$$ Hence $X=28$ and $Y=17$ We work with $28$.

1) With $9$ and $8$ one has $x_1+x_2=11$ and $x_1+x_2+x_3=11$ (because $28-(9+8)=11$).

$x_1+x_2=7+4=6+5$ give $2$ cases.

$x_1+x_2+x_3=7+3+1=6+4+1=6+3+2=5+4+2$ give $4$ cases.

2) With $9$ and $7$ without $8$ one has $x_1+x_2=12$ and $x_1+x_2+x_3=12$.

$x_1+x_2=12$ no cases since $6+5=11\lt12$.

$x_1+x_2+x_3=6+5+1=6+4+2=5+4+3$ give $3$ cases.

With $9$ and $6$ without $7$ and $8$ is not possible because $9+6=15$ and $5+4=9\lt 13$.

3) With $8$ and $7$ without $9$ one has $x_1+x_2$ not possible and

$x_1+x_2+x_3=6+5+2=6+4+3$ give $2$ cases.

Hence there are $2+4+3+2=11$ possible cases each of these corresponding to permutations of $5$ and $4$ digits.

Thus there are $11\cdot4!\cdot5!=\color{red}{31680}$ possibilities.