7
$\begingroup$

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.

$\endgroup$
5
$\begingroup$

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.

$\endgroup$
7
$\begingroup$

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. $$

$\endgroup$
3
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Of course the second case is not feasible, but worth noting for completeness. $\endgroup$ – Joffan Jun 30 '16 at 9:01
  • $\begingroup$ yes thats true. $\endgroup$ – math635 Jun 30 '16 at 9:02
  • $\begingroup$ @Why are you considering only positive multiple of 11? What about -11? $\endgroup$ – Babai Jun 30 '16 at 9:08
  • 1
    $\begingroup$ (+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.) $\endgroup$ – Did Jun 30 '16 at 9:09
  • $\begingroup$ @Did Correct. Joffan whereas has considered the $b-a=-11$ where he considered 28 as sum of five odd digits. $\endgroup$ – Babai Jun 30 '16 at 9:17
1
$\begingroup$

$$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.

$\endgroup$

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.