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?

  1. Simon
    April 12, 2014 at 7:18 am

    Hi, I’m no mathematician but 1771561 is 11 to the power of 6, so is clearly divisible by 11, but 1 – 6 + 5 – 1 + 7 – 7 + 1 = 0 So am I missing something?
    How does this relate to your divisibility rule above?

    • Anonymous
      April 12, 2014 at 7:48 am

      Zero is divisible by 11.

  1. No trackbacks yet.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: