Maths Olympiad Prep

Library / /141 of 220

Algebra Difficulty 6.3 National Olympiad Prove it Ukraine

Positive integer nn has no more than 20202020 digits. Prove that there exist mm such palindromes that their sum equals nn, where m13m \le 13.

A palindrome is a number which is read the same both left to right and right to left, i.e. 10011001, 99 and 767767 are palindromes, while 12121212 and 110110 are not.

Solution

First, we prove a lemma:

Lemma 1. Suppose there is a kk-digit positive integer XX, k>2k > 2. Then such a palindrome can be subtracted from it, that the remaining number consists of no more than 12k+1\lfloor \frac{1}{2}k+1 \rfloor digits.

Proof. Suppose the first k+12\lfloor \frac{k+1}{2} \rfloor digits of XX make up the number A1000A \ne 100\dots0. Then BB, a number formed from (A1)(A-1) by writing the digits in the opposite order (i.e. BB can begin with several zeros). Then, for an even kk, we subtract number (A1)B\overline{(A-1)B}, and for an odd kk, number (A1)B\overline{(A-1)B'}, where BB' is number BB but without the first digit. Then after such subtraction, the first digit on the left, which may be non-zero, is 12k+1\lfloor \frac{1}{2}k+1 \rfloor-th digit. In case if A=1000A=100\dots0, we simply subtract from XX number 99999\dots9, which has one fewer digits.

Lemma is proved.

Lemma 2. A number with no more than three digits can be represented as a sum of no more than three palindromes.

Proof. For two-digit and single-digit numbers, this is obvious. For the three-digit number abcabc, we consider the following cases.

For aca \le c, abc=aba+(ca)abc = aba + (c-a).

For a=c+1a = c+1, abc=cbc+99+1abc = cbc + 99 + 1.

For a>c+1a > c + 1, abc=cbc+(ac)00=cbc+(ac1)9(ac1)+(11a+c)abc = cbc + (a-c)00 = cbc + (a-c-1)9(a-c-1) + (11-a+c).

Lemma is proved.

Now let's calculate how the number of digits will change if we first take a 20202020-digit number, then apply lemma 1 ten times and then lemma 2:
20201011506254128653317953. 2020 \rightarrow 1011 \rightarrow 506 \rightarrow 254 \rightarrow 128 \rightarrow 65 \rightarrow 33 \rightarrow 17 \rightarrow 9 \rightarrow 5 \rightarrow 3.
Thus, we get no more than 1313 palindromes. If the initial number has fewer digits, then the number of palindromes can only decrease.

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.