Eva, Per and Anna play with their pocket calculators. They choose different integers and check, whether or not they are divisible by ${11}$. They only look at nine-digit numbers consisting of all the digits ${1, 2, . . . , 9}$. Anna claims that the probability of such a number to be a multiple of ${11}$ is exactly ${1/11}$. Eva has a different opinion: she thinks the probability is less than ${1/11}$. Per thinks the probability is more than ${1/11}$. Who is correct?
Problem
Source: Nordic Mathematical Contest 2002 #4
Tags: number theory, multiple
07.10.2017 11:13
Assume $N$ is a number satisfying the following conditions: $(1) \;\; N$ is a nine digit positive integer consisting of all the nonzero digits 1-9. $(2) \;\; 11|N$. Assume $N$ is a number which satisfies (1)-(2). Hence there are nine nonzero digits $c_0, c_1, \ldots ,c_8$ s.t. $c_i \neq c_j$ for all $0 \leq i < j \leq 8$ with $(3) \;\; N = \sum_{k=0}^8 c_k \cdot 10^k$. Now $11|N$ by (2), which according to (3) means $(4) \;\; N \equiv \sum_{k=0}^8 (-1)^k c_k \pmod{11}$. Set $S_1 = c_1 + c_3 + c_5 + c_7$ and $S_2 = c_0 + c_2 + c_4 + c_6 + c_8$. Then by (4) we obtain $(5) \;\; S_2 \equiv S_1 \pmod{11}$. Moreover we know that $(6) \;\; S_1 + S_2 = \sum_{k=0}^8 c_k = \sum_{n=1}^8 n = 45$. Combining (5) and (6) the result is $45 - S_1 \equiv S_1 \pmod{11}$, i.e. $(7) \;\; S_1 \equiv 6 \pmod{11}$. Futhermore we have $S_1 = c_1 + c_3 + c_5 + c_7 \in [1+2+3+4, 9+8+7+6]$, yielding $(8) \;\; 10 \leq S_1 \leq 30$. Combining (7) and (8) we find that $(9) \;\; S_1 \in \{17,28\}$. We may WLOG assume $c_0 < c_2 < c_4 < c_6 < c_8$ and $(10) \;\; c_1 < c_3 < c_5 < c_7$. According to (10) we have $S_1 = c_1 + c_3 + c_5 + c_7 \geq 1 + c_3 + (c_3 + 1) + (c_3 + 2) = 3c_3 + 4$ and $S_1 = c_7 + c_5 + c_3 + c_1 \leq 9 + c_5 + (c_5 - 1) + (c_5 - 2) = 3(c_5 + 2)$, yielding ${\textstyle (11) \;\; c_3 \leq \frac{S_1 - 4}{3}}$ and ${\textstyle (12) \;\; c_5 \geq \frac{S_1}{3} - 2}$ respectively. Next set $T_1 = c_1 + c_3$ and $T_2 = c_5 + c_7$. Then by (10) we have $T_2 - T_1 = (c_5 - c_1) + (c_7 - c_3) \geq 2+2$, i.e. $(13) \;\; T_2 - T_1 \geq 4$. The fact that $S _1 = T_1 + T_2$ combined with (13) give us $2T_2 = (T_2 + T_1) + (T_2 - T_1) = S_1 + (T_2 - T_1) \geq S_1+4$ and $T_2 = S_1 - T_1 = S_1 - (c_1 + c_3) \leq S_1 - (1 + 2)$ i.e. ${\textstyle (14) \;\; \frac{S_1}{2} + 2 \leq T_2 \leq S_1 - 3}$. Knowing that $T_1 = c_1 + c_3$ and $T_1 + T_2 = S_1$, we obtain $(15) \;\; c_1 + c_3 = S_1 - T_2$. According to (9) we have to consider the following two cases: Case 1: $S_1=28$. Then by (15) $(16) \;\; c_1 + c_3 = 28 - T_2$. Likewise by (14) ${\textstyle T_2 \geq \frac{28}{2} + 2 = 14 + 2 = 16}$, i.e. $c_7 + c_5 \geq 16$, which combined with $c_5 \geq 8$ (from (12)) yields $(c_7,c_5) = (9,8)$, which means $T_2=9+8 =17$ and $T_1 = 28 - 17 = 11$. Consequently $(c_1,c_3,c_5,c_7) = (4,7,8,9), (5,6,8,9)$. Case 2: $S_1=17$. Then by (11) ${\textstyle c_3 \leq \frac{17 - 4}{3} = \frac{13}{3}}$, meaning $c_3 \leq 4$. Moreover by (14) ${\textstyle \frac{17}{2} + 2 = 8,5 + 2 \leq T_2 \leq 17 - 3}$, i.e. $11 \leq T_2 \leq 14$. Thus we have to consider the following four cases: $\bullet \; T_2=11 \;\;\; \Rightarrow \;\;\; T_1=6 \;\;\; \Rightarrow \;\;\; (c_1,c_3,c_5,c_7) = (2,4,5,6)$. $\bullet \; T_2=12 \;\;\; \Rightarrow \;\;\; T_1=5 \;\;\; \Rightarrow \;\;\; (c_1,c_3,c_5,c_7) = (1,4,5,7), (2,3,4,8), (2,3,5,7)$. $\bullet \; T_2=13 \;\;\; \Rightarrow \;\;\; T_1=4 \;\;\; \Rightarrow \;\;\; (c_1,c_3,c_5,c_7) = (1,3,4,9), (1,3,5,8), (1,3,6,7)$. $\bullet \; T_2=14 \;\;\; \Rightarrow \;\;\; T_1=3 \;\;\; \Rightarrow \;\;\; (c_1,c_3,c_5,c_7) = (1,2,5,9), (1,2,6,8)$. Summa summarum, we have a total of 2 + 1 + 3 + 3 + 2 = 11 different quadruples $(c_1,c_3,c_5,c_7)$ satisfying $0 < c_1 < c_3 < c_5 < c_7 < 10$ and $c_1 + c_3 + c_5 + c_7 \in \{17,28\}$. The digits $c_1,c_3,c_5,c_7$ and $c_0,c_2,c_4,c_6,c_8$ be arranged in 4! and 5! ways respectively. Hence there are exactly $11 \cdot 4! \cdot 5!$ which satisfies conditions (1)-(2). Likewise there are 9! different nine digit positive integers with distinct nonzero digits. This means that the probability for such a number to be divisible by 11 is ${\textstyle \frac{11 \cdot 4! \cdot 5!}{9!} = \frac{11}{C(9,4)} = \frac{11}{126} < \frac{11}{121} = \frac{1}{11}}$. In other words, Eva is correct.