Positive integer has no more than digits. Prove that there exist such palindromes that their sum equals , where .
A palindrome is a number which is read the same both left to right and right to left, i.e. , and are palindromes, while and are not.
Positive integer has no more than digits. Prove that there exist such palindromes that their sum equals , where .
A palindrome is a number which is read the same both left to right and right to left, i.e. , and are palindromes, while and are not.
First, we prove a lemma:
Lemma 1. Suppose there is a -digit positive integer , . Then such a palindrome can be subtracted from it, that the remaining number consists of no more than digits.
Proof. Suppose the first digits of make up the number . Then , a number formed from by writing the digits in the opposite order (i.e. can begin with several zeros). Then, for an even , we subtract number , and for an odd , number , where is number but without the first digit. Then after such subtraction, the first digit on the left, which may be non-zero, is -th digit. In case if , we simply subtract from number , 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 , we consider the following cases.
For , .
For , .
For , .
Lemma is proved.
Now let's calculate how the number of digits will change if we first take a -digit number, then apply lemma 1 ten times and then lemma 2:
Thus, we get no more than palindromes. If the initial number has fewer digits, then the number of palindromes can only decrease.