## Probability and Divisibility by 11

Seven different playing cards, with values from ace to seven, are shaken in a hat, then taken out singly and then placed in a row.  What is the probability that this seven-digit number is divisible by 11?

The probability above is computed by the usual quotient

 $P = \displaystyle{\frac{\text{favorable cases}}{\text{possible cases}}},$

where there are $7! = 7 \cdot 6 \cdot 5 \cdot 4 \cdot 3 \cdot 2 \cdot 1 = 5040$ possible numbers of seven digits with each of the digits different to each other, and member of the set $\{ 1, 2, 3, 4, 5, 6, 7\}$.  The number of favorable cases is given by how many of the possible cases are actually divisible by 11.  Finding those favorable cases by hand is an extremely tedious task, of course.  Can we find a more elegant—and faster—way to compute the number of favorable cases?  The trick is based on using the right test of divisibility by 11.

An example of test of divisibility by 11 goes like this: Take the digits in a right-to-left  order, alternatively subtracting and adding.  Only if the final result is divisible by 11 will the original number be divisible by 11.

For example, for the 7-digit number $1354267$, the divisibility test gives $7 - 6 + 2 - 4 + 5 - 3 + 1 = 2$, which is not divisible by 11 (therefore, neither is $135426$).

A few useful facts:

• Let us represent our particular seven-digit numbers by $ABCDEFG$, where each letter goes for a different digit of the set $\{ 1, 2, 3, 4, 5, 6, 7\}$.
• The test of divisibility by 11 on the previous number calls for the computation of
 $G - F + E - D + C - B + A = (A + C + E + G) - (B + D + F).$
• Notice that $1 + 2 + 3 + 4 + 5 + 6 + 7 = 28$, an even number.
• Remember the rules of addition of even and odd numbers:
 $\begin{array}{rl} even + even &= even \\ odd + odd &= even \\ even + odd &= odd \end{array}$
• The latter two facts above imply that $A + C + E + G$ and $B + D + F$ both have the same parity (they are either both even or both odd at the same time).
• As a consequence of the last fact, the subtraction $(A + C + E + G) - (B + D + F)$ has to be an even number too!
• The largest possible value for the test of divisibility by 11 in our numbers, $(A + C + E + G) - (B + D + F)$, happens for numbers where $A$, $C$, $E$ and $G$ are largest; that is, they are the permutations of the four digits $\{ 4, 5, 6, 7 \}$. This value is, of course, $(7 + 6 + 5 + 4) -( 1+ 2 +3) = 22 -6 =16.$
• The smallest possible value for the test of divisibility by 11 in our numbers happens for numbers where $B$, $D$ and $F$ are largest; that is, they are permutations of the three digits $\{ 5, 6, 7\}$.  This value is, of course, $(1 + 2 + 3 + 4) - (5 + 6 + 7) = 10-18 = -8$.
• In our case, there are then only thirteen different possible tests of divisibility by 11: $\{ -8, -6, -4, -2, 0 , 2, 4, 6, 8, 10, 12, 14, 16\}$.  Of these, only one is divisible by 11: the “zero”.

You should have all the needed information to finish this problem.  How many numbers of the form $ABCDEFG$ give us a “zero” when we perform the divisibility-by-11 test?  From here, it should not be too hard to compute the probability.

Let $x = A + C + E + G$, and $y = B + D + F$.  We are looking for $x$ and $y$ satisfying the linear system:

 $\begin{cases} x + y &= 28 \\ x - y &=0 \end{cases}$

The solution gives $A + C + E + G = B + D + F = 14$.  We are very close to the punch line.

For example, all the possible triples $(B, D, F)$ satisfying $B+D+F = 14$ are given below:

 $\begin{array}{cccc} \{ 1, 6, 7 \} & \{ 2,5,7\} & \{ 3,4,7\} & \{3,5,6 \} \end{array}$

Let us work with one of those triples, say $\{ 1, 6, 7\}$. The possible seven-digit numbers that we can come up with for this choice of $\{ B, D, F\}$ are $3! = 3 \cdot 2 \cdot 1 = 6$:

 $\begin{array}{|c|c|c|} \hline B & D & F \\ \hline 1 & 6 & 7 \\ \hline 1 & 7 & 6 \\ \hline 6 & 1 & 7 \\ \hline 6 & 7 & 1 \\ \hline 7 & 1 & 6 \\ \hline 7 & 6 & 1 \\ \hline \end{array}$

We still need to fill in the values for $\{ A, C, E, G\}$. In the case we are exploring, we notice that there are $4! = 4 \cdot 3 \cdot 2 \cdot 1 = 24$ possibilities for each of the 6 choices above. For instance, if $B=1$, $D=6$ and $F=7$, we would have the numbers

 $\begin{array}{|c|c|c|c|c|c|c|} \hline A & \boldsymbol{B} & C & \boldsymbol{D} & E & \boldsymbol{F} & G \\ \hline 2 & \boldsymbol{1} & 3 & \boldsymbol{6} & 4 & \boldsymbol{7} & 5 \\ \hline 2 & \boldsymbol{1} & 3 & \boldsymbol{6} & 5 & \boldsymbol{7} & 4 \\ \hline 2 & \boldsymbol{1} & 4 & \boldsymbol{6} & 3 & \boldsymbol{7} & 5 \\ \hline 2 & \boldsymbol{1} & 4 & \boldsymbol{6} & 5 & \boldsymbol{7} & 3 \\ \hline 2 & \boldsymbol{1} & 5 & \boldsymbol{6} & 3 & \boldsymbol{7} & 5 \\ \hline 2 & \boldsymbol{1} & 5 & \boldsymbol{6} & 4 & \boldsymbol{7} & 3 \\ \hline \vdots & \boldsymbol{1} & \vdots & \boldsymbol{6} & \vdots & \boldsymbol{7} & \vdots \\ \hline 5 & \boldsymbol{1} & 4 & \boldsymbol{6} & 3 & \boldsymbol{7} & 2\\ \hline \end{array}$

So, what is the probability we are looking for?