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 …
Best Answer
$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.