Probability that a number is divisible by 11

The digits $1, 2, \cdots, 9$ are written in random order to form a nine digit number. Then, the probability that the number is divisible by $11$ is $\ldots$

I know the condition for divisibility by $11$ but I couldn't guess how to apply it here.

Please help me in this regard. Thanks.


Consider using the alternating sum division rule. We need to have the sum of $5$ digits - the sum of $4$ digits to equal a number divisible by $11$. Denote the sum of $5$ digits by $O$ and the sum of the 4 digits as $E$.

Thus, we want $O - E = (45 - E) - E = 45 - 2E$ (sum of digits 1-9 is $45$) to be divisible by $11$. Further, since $45 - 2E$ is odd, we know it cannot be $22$. So we have $45 - 2E$ could possibly equal $33,11,-11$, or $-33$. Note $33$ is not possible since $E \geq 1 + 2 + 3 + 4 > 6$, and $-33$ isn't possible because $E \leq 6 + 7 + 8 + 9 < 39$.

For $E$ to satisfy $45 - 2E = - 11$, we must have that $E = 28$. Since $6 + 7 + 8 + 9 = 30$, we can quickly see that the only possibilities are $\{4,7,8,9\}$ and $\{5,6,8,9\}$.

For $E$ to satisfy $45 - 2E = 11$, we must have that $E = 17$. We wish to find distinct integers $a,b,c,d$ between $1$ and $9$ such that $a + b + c + d = 17$. This can be solved with combinatorics, though here it might be easier to enumerate. To make this easier, consider the possible combinations of $x,y,z,w$ solving $x + (x + y) + (x + y + z) + (x + y + z + w) = 17$, where $x = a$, $y = b - a$, $z = c - b$, $w = d - c$, and $x,y,z,w \geq 1$. We can normalize each variable (ex: $x' = x - 1$) to find the equation $x' + (x' + y') + (x' + y' + z') + (x' + y' + z' + w') = 7$, or $4x' + 3y' + 2z' + w' = 7$, where $x',y',w',z' \geq 0$. There aren't very many possible combinations, and enumerating gives us $11$ different combinations. However, we have to watch out for the few cases where we have a number bigger than $9$; there are exactly two of these cases, which is $\{1,2,4,10\}$ and $\{1,2,3,11\}$.

We now have $2$ ways to get $45 - 2E = 28$, and $9$ ways to get $45 - 2E = 17$. Thus we have a total of $11$ possible ways to select the set of $4$ digits. However, we need to consider permutations, so we multiply $11$ by $5!$ and $4!$ to get $31680$ permutations divisible by $11$. Dividing by the total number of permutations $9!$ gives us a probability of approximately $.0873015873$


A number is divisible by 11 if and only if the sum of the odd-position digits and the even-position digits differ by a multiple of 11. Now, the sum of the digits from 1 to 9 is odd, so the difference in any such number must be either 11 or 33. The only subsets of $\{1,2,3,4,5,6,7,8,9\}$ where the difference between the subset and its complement is $33$ have six or more elements; this is impossible, since there are 5 odd-position digits and 4 even-position digits. Thus the two sets of digits differ by 11, and then the larger sum is $28$ and the smaller is $17$.

So we want collections of 4 or 5 integers from $\{1,2,3,4,5,6,7,8,9\}$ whose sum is $28$. There are eleven such (it's pretty straightforward to simply enumerate these by hand): \begin{align*} &\{4, 7, 8, 9\}, \{5, 6, 8, 9\}, \{1, 3, 7, 8, 9\}, \{1, 4, 6, 8, 9\}, \\ &\{1, 5, 6, 7, 9\}, \{2, 3, 6, 8, 9\}, \{2, 4, 5, 8, 9\}, \{2, 4, 6, 7, 9\}, \\ &\{2, 5, 6, 7, 8\}, \{3, 4, 5, 7, 9\}, \{3, 4, 6, 7, 8\}. \end{align*} Each of these yields $24\cdot 120$ possible numbers (arrange the 5-set any way you want, and the 4-set any way you want), for a total of $11\cdot 24\cdot 120 = 31680$ possibilities. (Note that this corresponds roughly to the numeric estimate of $0.08$ given in the comments).


since $10 = -1 \pmod {11}$, a number $abcdefghi$ is a multiple of $11$ if and only if $(a+c+e+g+i)-(b+d+f+h)$ is a multiple of $11$.

Since $(a+c+e+g+i)+(b+d+f+h) = 45 = 1 \pmod {11}$, this is equivalent to $1-2(b+d+f+h) = 0 \pmod {11}$, and to $(b+d+f+h) = 6 \pmod {11}$.

So we want to know, when is the sum of $4$ numbers randomly taken in $\{1 ; \ldots ; 9 \}$ is congruent to $6$ modulo $11$.

Clearly, if we were picking our four numbers in $\{1 ; \ldots ; 11\}$ (or $\{0 ; \ldots ; 10 \}$), the sum is uniformly distributed mod $11$ (if we add $3$ to each number, it's like adding $1$ to the sum). Which means there are $\frac 1 {11}\binom {11}4 = 30$ good quadruplets there.

Out of all of those we are only interested in those that don't use $10$ nor $11$.

Let's count how many use $10$ :

A quadruplet that use $10$ and that sums to $6$ is $10$ plus a triplet that sums to $7$ and that doesn't use $10$.
Once again we count the total number of triplets that sum to $7$, but we again have extra triplets, those that contain $10$.

We can continue like this, to remove the extra triplets we have to remove pairs that sum to $8$, and finally remove from those pairs the pair $\{10 ; 9 \}$.

So we get $\frac 1 {11}(\binom {11}3 - \binom {11}2 + \binom {11}1) = 11$ quadruplets that sum to $6$ and use $10$, which means there are $\frac 1 {11}(\binom {11}4 - \binom {11}3 + \binom {11}2 - \binom {11}1) = 19$ quadruplets that sum to $6$ and don't use $10$.

Now, we count the quadruplets that use $11$. The same thing happens the same way, even at the last step (because $4 \times 11 \neq 6 \neq 4 \times 10)$.

Had we wanted to count the number of quadruplets that don't use $7$, then we would have a difference at the end (because $7 \times 4 = 28 = 6$): none of the pairs that sum to $3$ contained a $7$ in the first place, so we don't count that last $\frac 1{11}\binom {11}1$.
Or said another way, the sum of quadruplets that don't use $10$ is almost uniform : it hits every sum $19$ times except $4 \times 10 = 7$, who is hit $20$ times (for a total of $210$, and there are $210$ quadruplets that don't use $10$).

Finally we want to count how many quadruplets sum to $6$ and use both $10$ and $11$. Those are the number of pairs that sum to $7$ and don't use $10$ nor $11$. There are $5$ pairs that sum to $7$, one of which uses $10$ and one of which uses $11$ (none use both because $10+11 \neq 7$)

So that's a total of $3$ quadruplets that sum to $6$ and use both $10$ and $11$.

The final number is $30 - 11 - 11 + 3 = 11$ quadruplets that sum to $6$ and don't use $10$ or $11$.

Since there are $126$ quadruplets that don't use $10$ or $11$, the final probability is $\frac {11}{126}$