Maths Olympiad Prep

Library / /19 of 196

Algebra Difficulty 4.5 AIME Prove it Soviet Union

Problem:

nn is a 1717 digit number. mm is derived from nn by taking its decimal digits in the reverse order. Show that at least one digit of n+mn + m is even.

Solution

Solution:

Let the number be nn with digits d1d2d17d_1d_2\ldots d_{17}, so that the reversed number mm has digits d17d16d1d_{17}d_{16}\ldots d_1. Let the digits of n+mn + m be a0a1a17a_0a_1\ldots a_{17}, where a0a_0 may be zero. Let the carry forward when adding digits to get aia_i be ci1c_{i - 1}, so that, in general, ci+di+d18i=ai+10ci1c_i + d_i + d_{18 - i} = a_i + 10 c_{i - 1}. Obviously cic_i is 00 or 11.

Suppose all the digits aia_i are odd (except that a0a_0 may be zero). Now c9+2d9=a9+10c8c_9 + 2d_9 = a_9 + 10 c_8. Since a9a_9 is odd, c9c_9 must be 11. But if we consider c10+d10+d8=a10+10c9c_{10} + d_{10} + d_8 = a_{10} + 10 c_9, we see that since a10a_{10} is odd it is at least 11 and hence d8+d10d_8 + d_{10} is at least 1010. Hence there must be a non-zero carry c9c_9 in c10+d10+d8=a10+10c9c_{10} + d_{10} + d_8 = a_{10} + 10 c_9 irrespective of the value of c10c_{10}.

We can now iterate and conclude successively that c12c_{12}, c14c_{14}, c16c_{16} must be non-zero.

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement reproduced verbatim; metadata (topic, difficulty) added by this project.