P is a 17 digit positive integer and Q is obtained by writing the digits of P backwards. If neither P nor Q has leading zeroes, can P+Q include no even digits?

Daniel had the start of a solution: If the addition is done in such a manner as to write each sum digit mod 10 (that is, ignore any required carries), then the center digit would need to be an even digit.  But real addition requires the use of carries.  So let's look at the pseudo-sum that ignores carries, and see how the carries can affect it.  The pseudo-sum is palindromic, but to differentiate the left and right let's use what would be subscript 1 for the left side, and subscript 2 for the right side, except to make this non-tedious to write, the subscripts will be ordinary non-subscripted numbers:

The pseudo sum is represented by:

a1, b1, c1, d1, e1, f1, g1, h1, i, h2, g2, f2, e2, d2, c2, b2, a2

where a1 = a2, b2 = c2, etc.

If there is no carry from the sum that makes up h (the same sum makes h1 as h2, as that could be, say, 7+5 vs 5+7), then i is indeed your even digit.

If, however, the sum that makes up each h has a carry, i becomes odd. But then there's also a carry into g1, as the sum that makes up h either has a carry or it doesn't, regardless of whether it makes up h1 or h2.  At that point, either g1 is of opposite parity from g2 (thereby making one of them even), or there's also a carry into g2, from f2.

The same logic is followed down the line, with a carry from f2 to g2 requiring a carry from f1 to e1, requiring (if we don't want an even digit) a carry into e2 from d2, and from d1 into c1, and into c2 from b2, and from b1 into a1.  But at this point there's no option to have a carry into a2, as that's the rightmost digit of the sum.  So if none of the digits considered so far is even, then either a1 or a2 is even as one has a carry going in and the other doesn't and the numbers without carries are the same as they are the result of the same addition mod 10, before the carry.

This was actually a proof from reductio ad absurdem, assuming until the very end that there were no even numbers, but being forced at the end to say that at that point there's no choice but to have one of the digits be even.

As you can see, it doesn't matter whether a (for a1 or a2) has a carry (producing an 18-digit result) or not.

This proof requires that the number of digits be 1 more than a multiple of 4. Not just any odd number of digits will work.  For example 718 + 817 = 1535.

Edited on August 16, 2007, 1:20 am

Posted by Charlie on 2007-08-16 01:05:05