Divisibility by 11 of a 9-digit integer.

A number is divisible by 11 if the result of alternatingly adding and subtracting them is divisible by 11. For instance, 182539467 is divisible by 11 because $1 - 8 + 2 - 5 + 3 - 9 + 4 - 6 + 7 = -11$ is.

Thus we wish to divide the digits 1 through 9 into a group of five and a group of four digits, such that $(\text{sum of the five digits}) - (\text{sum of the four digits}) = \text{multiple of 11}.$ The sum of the digits is 45. It is easy to see that our options are limited to $28 - 17$ , $39 - 6$ , and vice versa. There is no way to make four or five of the digits to add up to 6. Therefore we must consider the possible ways in which either $four$ or $five$ of the digits add up to 17. (The other group will automatically add up to 28.)

These are: $12347, 12356; 1259, 1268, 1349, 1358, 1367, 1457, 2348, 2357, 2456.$ Thus there are 11 ways to distribute the digits over groups of four and five with the desired properties. Within each group, the digits can be placed in any order, so that there are $4!5!$ arrangements for each group.

The probability is therefore $\frac{11\cdot4!5!}{9!} = \frac{11}{126},$ making the answer equal to $\boxed{137}$ .

Michelle's number, $N$ , is formed by taking $a_i\in\{1,2,\ldots,9\}$ for $i=0,1,\ldots,8$ , with $a_i\neq a_j$ if $i\neq j$ . Let $a_9=0$ (for ease of notation in the line below).

Her number is then $N=\sum_{i=0}^9 10^i a_i = \sum_{j=0}^4\left(10^{2j+1}a_{2j+1}+10^{2j} a_{2j}\right) = \sum_{j=0}^4 100^j \left(10a_{2j+1}+a_{2j}\right)$ .

Since $100=1$ (mod 11),

$N=\sum_{j=0}^4 \left(10a_{2j+1}+a_{2j}\right)$ (mod 11)

$=10\sum_{j=0}^3a_{2j+1}+\sum_{j=0}^4a_{2j}$ .

This expression must be 0 (mod 11) if 11 divides $N$ . The largest this value can be is $10(9+8+7+6)+(5+4+3+2+1)=315$ . Other values can be found by decreasing the sum of the first group, $\{a_{2j+1}\}_{j=0}^3$ , by 1 and increasing the sum of the second group, $\{a_{2j}\}_{j=0}^4$ , by 1 (e.g. $10(9+8+7+5)+(6+4+3+2+1)$ ), thus changing the value by $-10+1=-9$ , down to the smallest possible value, $10(1+2+3+4)+(5+6+7+8+9)=135$ .

So all possible values of $N$ (mod 11) are $315, 306, 297, 288, \ldots, 198, 189,\ldots, 135$ . Of these, only 297 and 198 are congruent to 0 mod 11.

In order for $10\left(\sum_{j=0}^3a_{2j+1}\right)+\left(\sum_{j=0}^4a_{2j}\right)=10A+B=297$ and $A+B=1+2+\cdots+8+9=45$ , we must have $A=28$ and $B=17$ . There are only two ways $\sum_{j=0}^3a_{2j+1}$ can be 28: $\{a_{2j+1}\}_{j=0}^3=\{9,8,7,4\}$ or $\{a_{2j+1}\}_{j=0}^3=\{9,8,6,5\}$ .

In order for $10\sum_{j=0}^3a_{2j+1}+\sum_{j=0}^4a_{2j}=10A+B=189$ and $A+B=1+2+\cdots+8+9=45$ , we must have $A=17$ and $B=28$ . There are nine possibilities of $\{a_{2j+1}\}_{j=0}^3$ such that $\sum_{j=0}^3a_{2j+1}=17$ : $\{1,2,5,9\}, \{1,2,6,8\}, \{1,3,4,9\}, \{1,3,5,8\}, \{1,3,6,7\}, \{1,4,5,7\}, \{2,3,4,8\}, \{2,3,5,7\}, \{2,4,5,6\}$ (I hope the order gives you some idea of how we know these are the only possibilities).

So there are 11 possible combinations of $\{a_{2j+1}\}_{j=0}^3$ such that $N=0$ (mod 11). There are $\binom{9}{4}=126$ total combinations. Therefore the probability that 11 divides $N$ is $\frac{11}{126}$ .

This is my first time writing a solution, so feedback (on formatting, clarity of explanation, etc.) is welcome.

Generates all and filters off equals [and then check for MOD 11]. When 9! = 362880 is checked to be right, then the program must run correctly.

31680/ 362880 = [(2^6)(3^2)(5)(11)]/ [(2^7)(3^4)(5)(7)] = 11/ [(2)(3^2)(7)] = 11/ 126

11 + 126 = 137