The alternating sum of the digits of 63195 is $6-3+1-9+5=0$. In general, the alternating sum of the digits of a positive integer is found by taking its leftmost digit, subtracting the next digit to the right, adding the next digit to the right, then subtracting, and so on. A positive integer is divisible by 11 exactly when the alternating sum of its digits is divisible by 11. For example, 63195 is divisible by 11 since the alternating sum of its digits is equal to 0 , and 0 is divisible by 11. Similarly, 92807 is divisible by 11 since the alternating sum of its digits is 22 , but 60432 is not divisible by 11 since the alternating sum of its digits is 9 .

Lynne forms a 7-digit integer by arranging the digits 1, 2, 3, 4, 5, 6, 7 in random order. What is the probability that the integer is divisible by 11 ?
(A) $\frac{1}{35}$
(B) $\frac{5}{42}$
(C) $\frac{3}{35}$
(D) $\frac{1}{42}$
(E) $\frac{4}{35}$
Let the alternating sum of the digits be $S$.

If the 7-digit integer is $a b c d e f g$, then $S=a-b+c-d+e-f+g$.

This sum can be grouped into the digits which contribute positively to the sum, and those which contribute negatively to the sum.

Rewriting the sum in this way, we get $S=(a+c+e+g)-(b+d+f)$.

Taking the 4 digits which contribute positively to $S$ (there are always 4), we let $P=a+c+e+g$. Similarly, taking the 3 digits which contribute negatively to $S$ (there are always 3 ), we let $N=b+d+f$.

Thus, it follows that $S=(a+c+e+g)-(b+d+f)=P-N$.

We determine the largest possible value of $S$ by choosing the 4 largest integers, $4,5,6,7$ (in any order), to make up $P$, and choosing the 3 smallest integers, 1,2,3 (in any order), to make up $N$.

That is, the largest possible alternating sum is $S=(4+5+6+7)-(1+2+3)=16$.

We determine the smallest possible value of $S$ by choosing the 4 smallest integers, 1, 2, 3, 4 (in any order), to make up $P$, and choosing the 3 largest integers, 5,6,7 (in any order), to make up $N$.

That is, the smallest possible alternating sum is $S=(1+2+3+4)-(5+6+7)=-8$.

Since $S$ must be divisible by 11 (with $S \geq-8$ and $S \leq 16$ ), then either $S=11$ or $S=0$.

The sum of the first 7 positive integers is $1+2+3+4+5+6+7=28$, and since each of these 7 integers must contribute to either $P$ or to $N$, then $P+N=28$.

Case 1: The alternating sum of the digits is 11 , or $S=11$

If $S=11$, then $S=P-N=11$. If $P-N$ is 11 (an odd number), then either $P$ is an even number and $N$ is odd, or the opposite is true (they can't both be odd and they can't both be even).

That is, the difference between two integers is odd only if one of the integers is even and the other is odd (we say that $P$ and $N$ have different parity).

However, if one of $P$ or $N$ is even and the other is odd, then their sum $P+N$ is also odd.

But we know that $P+N=28$, an even number.

Therefore, it is not possible that $S=11$.

There are no 7-digit integers formed from the integers 1 through 7 that have an alternating digit sum of 11 and are divisible by 11 .

Case 2: The alternating sum of the digits is 0 , or $S=0$

If $S=0$, then $S=P-N=0$ and so $P=N$.

Since $P+N=28$, then $P=N=14$.

We find all groups of 3 digits, chosen from the digits 1 to 7 , such that their sum $N=14$.

There are exactly 4 possibilities: $(7,6,1),(7,5,2),(7,4,3)$, and $(6,5,3)$.

In each of these 4 cases, the digits from 1 to 7 that were not chosen, $(2,3,4,5),(1,3,4,6),(1,2,5,6)$, and $(1,2,4,7)$, respectively, represent the 4 digits whose sum is $P=14$.

We summarize this in the table below.

| 4 digits whose  sum is $P=14$ | 3 digits whose  sum is $N=14$ | 2 examples of 7-digit  integers created from these |
| :---: | :---: | :---: |
| $2,3,4,5$ | $7,6,1$ | 2736415,3126475 |
| $1,3,4,6$ | $7,5,2$ | 1735426,6745321 |
| $1,2,5,6$ | $7,4,3$ | 2714536,5763241 |
| $1,2,4,7$ | $6,5,3$ | 4615237,7645231 |

Consider the first row of numbers in this table above.

Each arrangement of the 4 digits 2, 3,4, 5 combined with each arrangement of the 3 digits 7,6, 1 (in the required way) gives a new 7 -digit integer whose alternating digit sum is 0 .

Two such arrangements are shown (you may check that $S=0$ for each).

Since there are $4 \times 3 \times 2 \times 1=24$ ways to arrange the 4 digits ( 4 choices for the first digit, 3 choices for the second, 2 choices for the third and 1 choice for the last digit), and $3 \times 2 \times 1=6$ ways to arrange the 3 digits, then there are $24 \times 6=144$ ways to arrange the 4 digits and the 3 digits.

Each of these 144 arrangements is different from the others, and since $P=N=14$ for each, then $S=P-N=0$ and so each of the 144 7-digit numbers is divisible by 11 .

Similarly, there are also 144 arrangements that can be formed with each of the other 3 groups of integers that are shown in the final 3 rows of the table.

That is, there are a total of $144 \times 4=5767$-digit integers (formed from the integers 1 through 7) which are divisible by 11 .

The total number of 7 -digit integers that can be formed from the integers 1 through 7 is equal to the total number of arrangements of the integers 1 through 7 , or $7 \times 6 \times 5 \times 4 \times 3 \times 2 \times 1=5040$. Therefore, when the digits 1 through 7 are each used to form a random 7 -digit integer, the probability that the number formed is divisible by 11 is $\frac{576}{5040}=\frac{4}{35}$.

ANSWER: (E)