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

• What do you mean with "written in random to form a none digit number"? A number consisting of all those digits written in random order? Or each digit is randomly drawn from that set? Or something else? – celtschk Oct 13 '16 at 20:30
• a funny question. Of course it can't be $\frac 1{11}$ because $9!$ isn't divisible by $11$. – mercio Oct 13 '16 at 21:41
• @Felix Marin - Just want to point out that answers should be given in the Answer box, not in comments. Then you would also have the oppertunity to expand on how you arrived at the answer. – Jens Oct 13 '16 at 21:43
• @DavidRicherby : "Obviously", a distribution is chosen uniformly randomly from the space of all distributions (relevant to this problem). It's right there in the white space between the words of the Question... – Eric Towers Oct 14 '16 at 16:09
• @DavidRicherby Do you really need a clarification for a distribution over a finite set? – yo' Oct 14 '16 at 16:13

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$

• That's the Answer in the most simplest way.thanks – Navin Oct 13 '16 at 23:43
• @Servaes thank you, updated – nivekgnay Oct 14 '16 at 16:16
• @nivekgnay Rather funny but your probability looks like a phone number, and I think it has the precise number of digits to be one, a mobile phone number that is. Vodafone numbers used to be 087 xxxx xxx before you could swap networks and keep your old number that is. – snulty Oct 14 '16 at 16:26
• It's interesting to note that .0873015873 is very, very close to the naive answer of "1 in 11", or 0.09090909... – Mason Wheeler Oct 14 '16 at 18:06

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

• thanks for the answer.out of curiosity I wished to know that is there some way to arrive at the answer without doing much experimentation because it is quite possible to overlook one possible case – Navin Oct 13 '16 at 22:07

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

$$\bbox[8px,border:1px groove navy]{\mbox{I'm posting this answer to comply with the OP and}\ \color{#66f}{\texttt{@Jens}}\ \mbox{petition}\ }$$

It changes slightly between several 'runs' remaining close to $\color{#f00}{0.08\ldots}$.

$\texttt{javascript}$ code $\left(~\mbox{it runs in a terminal as}\quad \texttt{node div11.js}~\right)$:

// div11.js Felix Marin
"use strict";
var        ITER = 362880*10; // Total number of iterations.
// Note that 9! = 362880
var           n = null;
/***************************************************************/
var randomDig19 = (function()
{
var        d = [1,2,3,4,5,6,7,8,9];
var disorder = function () { return Math.random() - 0.5; };

return function ()
{
return Number(d.sort(disorder).join(""));
};
})();
/***************************************************************/
var total = 0;

for ( n = 0 ; n < ITER ; ++n ) {
if ((randomDig19() % 11) === 0) ++total;
}

console.log("Result " + total/ITER);

/*
http://math.stackexchange.com/questions/1967378/probability-that-a-number-is-divisible-by-11#1967378
*/

Result 0.0875449184303351

It changes slightly between several 'runs' remaining close to $\color{#f00}{0.08\ldots}$.

• You could just calculate the exact number of permutations that were divisible by 11. In this case it'd be much faster too since you choose ten times as many random numbers as there are actual cases! – RemcoGerlich Oct 14 '16 at 10:45
• @RemcoGerlich The random solution could be more reliable (if less accurate), because it is easier to get right than to actually ensure you counted every permutation exactly once. It is, at least, an important double check. – Yakk Oct 14 '16 at 14:08
• @Yakk There is a simple algorithm to enumerate permutations. Actually, there are many in a recent volume of Knuth's TAOCP, but enumeration in lexicographic order is particularly easy to discover, and to implement. On the other hand, it's a bit tricky to get a correct fast implementation of a random permutation. – Jean-Claude Arbaut Oct 14 '16 at 19:12
• @Jean-ClaudeArbaut list<X> permute( list<X> x ) { list<X> r; while (!x.empty()) { auto i = random_upto(x.size()); r.insert(x[i]); x.erase(i); } return r; } is a simple and robust shuffling of a list? I'll admit the permute is merely generator<list<X>> permutions( list <X> x ) { for( i index in x ) { for (auto sublist in permutations( x without index i ) ) { yield sublist with x[i] inserted before i; } }, but I'd argue the first is easier to check correctness, and the second is a pain without coroutines or generators. – Yakk Oct 14 '16 at 19:59

The rule of divisibility by $$11$$ is as follows: The difference between the sum of digits at odd places and the sum of the digits at even places should be $$0$$ or a multiple of $$11$$.

We also know that the sum of all the digits will be $$45$$ as $$1 + 2 + ... + 9 = 45$$.

Let $$x$$ denote sum of digits at even position s and $$y$$ denote sum of digits at odd places, or vice versa.

Case 1 (difference is $$0$$):

$$x + y = 45$$

$$x - y = 0$$

Thus, $$2x = 45$$, or $$x = 22.5$$ which cannot be obtained.

Case 2 (difference is $$11$$):

$$x + y = 45$$

$$x - y = 11$$

Thus, $$2x = 56$$, or $$x = 28$$ and $$y = 17$$. This is a valid possibility.

Case 3 (difference is $$22$$):

$$x + y = 45$$

$$x - y = 22$$

Thus, $$2x = 67$$, or $$x = 33.5$$, which cannot be obtained.

As you can see, the difference between the sum of the digits at odd places and the sum of the digits at even places must be $$11$$.

Now, imagine that there are $$9$$ placeholders (representing the $$9$$ digits of the $$9$$-digit number). Either the sum of the digits at odd places ($$5$$ odd places) should be $$28$$, or the sum of the digits at even places ($$4$$ even places) should be $$28$$.

We write down the possibilities:

$$2$$ ways to express $$28$$ as a sum of $$4$$ numbers between $$1$$ and $$9$$.

$$9$$ ways to express $$28$$ as a sum of $$5$$ numbers between $$1$$ and $$9$$.

In the first case, there are $$4!$$ ways of arranging the $$4$$ numbers (that add up to $$28$$) and $$5!$$ ways of arranging the $$5$$ other numbers (that add up to $$17$$). Hence, no. of ways$$= 2 * 4! * 5!$$

In the second case, there are $$5!$$ ways of arranging the $$5$$ numbers ( that add up to $$28$$) and $$4!$$ ways of arranging the $$4$$ other numbers (that add up to $$17$$). Hence, no. of ways$$= 9 * 5! * 4!$$

Total favourable possibilities$$= 2 * 4! * 5! + 9 * 5! * 4!$$ $$= 4! * 5! * (2 + 9)$$ $$= 4! * 5! * 11$$

Also, total no. of ways of arranging $$9$$ numbers to form a $$9$$-digit number = $$9!$$

Hence, probability$$=P= (4! * 5! * 11)/9!$$ $$= 11/126$$