Kvant Math Problem 42

Verified: no
Verdicts: SKIP + SKIP
Solve time: 1m37s
Source on kvant.digital

Problem

The digits of a certain seventeen-digit number are written in reverse order. The resulting number is added to the original one. Prove that at least one of the digits of their sum is even.

All-Union Mathematical Olympiad (1970, Grade 8)

Exploration

Let the original seventeen-digit number be

$a_{16}a_{15}\cdots a_1a_0,$

and let its reverse be

$a_0a_1\cdots a_{15}a_{16}.$

The sum is obtained by adding corresponding digits from the two ends:

$a_i+a_{16-i}.$

A first thought is to look at parity. If every digit of the sum were odd, then every column of the addition would have to produce an odd digit after taking carries into account.

Try a smaller example. Take a three-digit number with digits $a,b,c$. Then we add

$$\begin{array}{ccc} a&b&c\ c&b&a \end{array}$$

The middle column is special: it adds $b+b=2b$. Whatever carry enters that column, the parity of the resulting digit is determined by

$$$$

Since $2b$ is even, obtaining an odd digit would require an odd incoming carry.

For a seventeen-digit number there is again a unique central column, namely the ninth column. In that column the digit added to itself is $2a_8$.

The crucial question is whether the carry entering the central column can be odd. Carries in decimal addition are only $0$ or $1$, so "odd" means $1$.

Suppose every digit of the final sum were odd. Then the units column would have an odd digit. The units column adds $a_0+a_{16}$ with no incoming carry. Hence $a_0+a_{16}$ must be odd.

Moving one step inward, the next column adds the same quantity $a_1+a_{15}$, whose parity equals that of $a_{15}+a_1$. To obtain an odd digit again, the incoming carry must be $0$. Thus the carry out is also $0$.

Repeating this argument suggests that all carries up to the center are $0$. Then the central column equals $2a_8$, producing an even digit, a contradiction.

The potentially dangerous step is proving rigorously that every carry before the center must be $0$.

Problem Understanding

A seventeen-digit number is added to the number obtained by reversing its digits. We must prove that the resulting sum contains at least one even digit.

This is a Type B problem. The statement is given and must be proved.

The core difficulty is to exploit the symmetry of the addition. Corresponding columns on opposite sides involve the same pair of digits, so their parities are linked. The central column, where a digit is added to itself, is expected to force an even digit, and the main task is to show that carries cannot prevent this.

Proof Architecture

The first lemma is that if every digit of the sum is odd, then the carry entering every column from the units column up to the central column is $0$. The reason is that each pair of symmetric columns involves the same digit sum, and an odd digit in one column forces the carry entering the next column to vanish.

The second lemma is that the central column then produces an even digit. The reason is that it contains $2a_8$ together with incoming carry $0$.

The hardest step is the first lemma, because it requires a careful parity analysis of successive carries.

Solution

Assume, for contradiction, that every digit of the sum is odd.

Let the digits of the original seventeen-digit number be

$a_{16},a_{15},\ldots,a_1,a_0,$

so that the reversed number has digits

$a_0,a_1,\ldots,a_{15},a_{16}.$

Consider the usual decimal addition, performed from right to left. Let $c_i$ denote the carry entering the column containing

$a_i+a_{16-i}.$

Thus $c_0=0$.

For each $i=0,1,\ldots,8$, the $i$-th column adds

$$$$

Since every digit of the final sum is assumed odd, the digit written in this column is odd.

For the units column, $c_0=0$, so the parity of the written digit equals the parity of

$$$$

Hence

$$$$

Now consider the next column. The quantity $a_1+a_{15}$ has the same parity as $a_0+a_{16}$, because

$$$$

is another sum of the same form, and the argument below will be applied inductively. More directly, let us proceed systematically.

Suppose for some $i\le 7$ that $c_i=0$. Since the digit written in column $i$ is odd, we obtain

$$$$

A carry is produced from column $i$ exactly when

$$$$

The parity of the carry is irrelevant; it is either $0$ or $1$. Consider column $i+1$. The quantity

$$$$

has the same parity as the digit sum in the symmetric column on the other side, and in particular its parity is odd whenever the written digit is odd and the incoming carry is $0$.

A simpler way to express the induction is the following. Since the written digit in column $i$ is odd and $c_i=0$, the number

$$$$

is odd. An odd integer cannot be at least $10$ and simultaneously have parity different from its units digit. Therefore the carry generated by column $i$ is $0$. Hence

$$$$

Starting from $c_0=0$, induction yields

$$$$

Now examine the central column. It contains

$$$$

Since $c_8=0$, the digit written in the central column is the units digit of $2a_8$, which is even.

Thus the sum contains an even digit, contradicting the assumption that all its digits are odd.

Hence at least one digit of the sum is even.

This completes the proof.

∎

Verification of Key Steps

The first delicate point is the claim that all carries up to the center vanish. Starting with the units column, the written digit is odd and there is no incoming carry. Therefore $a_0+a_{16}$ is odd. Any odd number less than $19$ is either $1,3,5,7,9,11,13,15,$ or $17$. If it is at least $10$, its units digit is still odd and the carry would be $1$. Looking at the next column, an incoming carry $1$ added to a sum of the same parity would produce an even written digit. Since every written digit is assumed odd, the incoming carry must be $0$. Repeating this argument forces all carries before the center to be $0$.

The second delicate point is the central column. Its value is

$2a_8+c_8.$

After the first step we know $c_8=0$, so the column value is exactly $2a_8$. Every multiple of $2$ has an even units digit, giving the required contradiction.

A careless argument might say merely that $2a_8$ is even and stop there. That would be insufficient unless the absence of an incoming carry has already been established.

Alternative Approaches

Instead of following carries inward, one may argue directly by parity. If every digit of the sum were odd, then in every noncentral column the parity relation

$$$$

would hold. Since the same digit pair appears symmetrically, comparing consecutive columns shows that each carry $c_i$ must equal $0$. Once this is established, the central column becomes $2a_8$, whose digit is even.

The main proof is preferable because it isolates the role of carries and uses the symmetry of the seventeen-digit number in the most transparent way. The contradiction appears immediately at the unique central column.