A $17$-digit number and the number formed by reversing its digits are added together. Show that the sum has a even digit.

Question

A $17$ digit number is chosen, and it's digits are reversed, forming a new number. These two numbers are added together. Show that there sum has at least one even digit.

The solution given in the book is as follows:

Suppose there were a $17$-digit integer whose reversed sum contained no even digit. For convenience, we number the columns of digits from right to left and consider the usual addition algorithm. The ninth digit of our number will be added to itself. This would produce an even digit in the answer, unless there is a "carry" from $8$th column. But if there is such a carry, then there must be one also from the $10$th column to the $11$th column (the $10$th column is identical is identical to the $8$th except for the order of the digits). Hence the $7$th column has digits of the same parity, and requires a carry from the sixth column. Proceeding similarly we find that there is a carry in each odd numbered column . But there cannot be a carry into the 1st column , so we have a contradiction.

However, I am not getting the part of the solution where it says, "Hence the $7$th column has digits of the same parity, and requires a carry from the sixth column." I am not getting this part ...

Answer 1

$E$ indicates even; $O$ indicates odd; $d_{n}$ indicates digit $n$; column $k$ indicates the column number (with $1$ being the rightmost column and $17$ being the leftmost column); $\checkmark$ indicates that the condition of at least $1$ even digit in the sum has been satisfied.

$$\begin{array}{|c|c|} \hline &d_1& d_2& d_3& d_4& d_5& d_6& d_7& d_8& d_9&d_{10}& d_{11}& d_{12}& d_{13}& d_{14}& d_{15}& d_{16}& d_{17}\\ \hline &d_{17}& d_{16}& d_{15}& d_{14}& d_{13}& d_{12}& d_{11}& d_{10}& d_9&d_8& d_7& d_6& d_5& d_4& d_3& d_2& d_1\\ \hline A& & & & & & & & &E& &\\ \hline B& & & & & & & & & E& \\ \hline C& & & & & & & E& & O& \\ \hline D& & & & & & & O& & O& &E\\ \hline X& & & & & & & O& & O& & E&\\ \hline F& & & & & E& & O& & O& & O\\ \hline G& & & & & O& & O& & O& & O& &E\\ \hline H& & & & & O& & O& & O& & O& &E\\ \hline I& & & E& & O& & O& & O& & O& &O\\ \hline ...& & & & & & & & & & & & &\\ \hline N& O& & O& & O& & O& & O& & O& & O& & O& &\color{red}E\\ \hline \end{array}$$

$A = $ no carry $\rightarrow \checkmark$

$B = $ even carry from column $8 \rightarrow \checkmark$

$C = $ odd carry from column $8 \rightarrow$ odd carry from column $10$ and $d_7$ and $d_{11}$ have different parity $\rightarrow \checkmark$

$D = $ odd carry from column $8 \rightarrow$ odd carry from column $10$ and $d_7$ and $d_{11}$ have same parity $\rightarrow d_7 + d_{11}$ is even and no carry from column $6 \rightarrow \checkmark$

$X = $ odd carry from column $8 \rightarrow$ odd carry from column $10$ and $d_7$ and $d_{11}$ have same parity $\rightarrow d_7 + d_{11}$ is even and even carry from column $6 \rightarrow \checkmark$

$F = $ odd carry from column $8 \rightarrow$ odd carry from column $10$ and $d_7$ and $d_{11}$ have same parity $\rightarrow d_7 + d_{11}$ is even and odd carry from column $6 \rightarrow$ odd carry from column $12$ and $d_5$ and $d_{13}$ have different parity $\rightarrow \checkmark$

$G = $ odd carry from column $8 \rightarrow$ odd carry from column $10$ and $d_7$ and $d_{11}$ have same parity $\rightarrow d_7 + d_{11}$ is even and odd carry from column $6 \rightarrow$ odd carry from column $12$ and $d_5$ and $d_{13}$ have same parity $\rightarrow d_5 + d_{13}$ is even and no carry from column $4 \rightarrow \checkmark$

$H = $ odd carry from column $8 \rightarrow$ odd carry from column $10$ and $d_7$ and $d_{11}$ have same parity $\rightarrow d_7 + d_{11}$ is even and odd carry from column $6 \rightarrow$ odd carry from column $12$ and $d_5$ and $d_{13}$ have same parity $\rightarrow d_5 + d_{13}$ is even and even carry from column $4 \rightarrow \checkmark$

$I = $ odd carry from column $8 \rightarrow$ odd carry from column $10$ and $d_7$ and $d_{11}$ have same parity $\rightarrow d_7 + d_{11}$ is even and odd carry from column $6 \rightarrow$ odd carry from column $12$ and $d_5$ and $d_{13}$ have same parity $\rightarrow d_5 + d_{13}$ is even and odd carry from column $4 \rightarrow$ odd carry from column $14$ and $d_{3}$ and $d_{15}$ have different parity $\rightarrow \checkmark$

Do you see the pattern?

If we continue as above, we will eventually reach a point where if there is no carry to column $1$, there will be an even digit in column $1$. However, there can't be a carry to column $1 \implies$ the digit in column $1$ has to be even. Hence, we will always have at least $1$ even digit in the sum.

Answer 2

I don't like this solution because it expects you to guess what it means by "proceeding similarly", and also because it leaves out a bit of subtle reasoning. Here are the two general claims it uses repeatedly. (Note that we need to use Claim 1 to prove Claim 2, or add some other kind of argument; the solution ignores this entirely.)

Claim 1. If there is a carry into the $k^{\text{th}}$ column (from the $(k-1)^{\text{th}}$) then there must also be a carry into the $(18-k)^{\text{th}}$ (from the $(17-k)^{\text{th}}$).

Proof. The $k^{\text{th}}$ and $(18-k)^{\text{th}}$ columns are adding the same digits $a$ and $b$ in different order. If $a+b$ is even, then to get an odd digit in the answer, both columns need a carry (to get $a+b+1$). If $a+b$ is odd, then to get an odd digit in the answer, neither column needs a carry.

Claim 2. If there is a carry out of the $k^{\text{th}}$ column (into the $(k+1)^{\text{th}}$) then there must also be a carry out of the $(18-k)^{\text{th}}$ (into the $(19-k)^{\text{th}}$).

Proof. Again, both the $k^{\text{th}}$ and the $(18-k)^{\text{th}}$ columns are adding the same digits $a$ and $b$; also, by Claim 1, they are both or neither getting carries. So we get the same result ($a+b$ or $a+b+1$) when adding the columns. If that result is $10$ or larger, there is a carry out of both columns; otherwise, there is a carry out of neither column.

---

Now the reasoning goes: to prevent an even result in column $9$, there must be a carry from $8$ to $9$. By Claim 2, since there is a carry out of $8$, there is a carry out of $10$, into $11$.

By Claim 1, since there is a carry into $11$, there is a carry into $7$, from $6$. By Claim 2, since there is a carry out of $6$, there is a carry out of $12$, into $13$.

By Claim 1, since there is a carry into $13$, there is a carry into $5$, from $4$. By Claim 2, since there is a carry out of $4$, there is a carry out of $14$, into $15$.

By Claim 1, since there is a carry into $15$, there is a carry into $3$, from $2$. By Claim 2, since there is a carry out of $2$, there is a carry out of $16$, into $17$.

By Claim 1, since there is a carry into $17$, there is a carry into $1$. From where? Contradiction.