Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It only takes a minute to sign up.
Sign up to join this community
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}$
$$ \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}$.
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.
$\endgroup$
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$$
