Competition problem — Combinatorics

Library / /176 of 220

Combinatorics Difficulty 6.6 National Olympiad Prove it Ukraine

A palindromic number is a number whose digits stand symmetrically with respect to the center of the number's decimal notation, for instance, $7$ , $1221$ and $57575$ are palindromic, while $1212$ and $3330$ are not. Prove that for any number of pairwise distinct palindromic numbers the sum of their reciprocals is not greater than $11$ .
(Arsenii Nikolaiev)

Solution

Let an arbitrary natural number $n$ and consider all palindromic numbers that have exactly $n$ digits. We consider $n$ odd and $n$ even separately.

When $n = 2m$ , palindrome becomes $a_1a_2\dots a_{m-1}a_m a_m a_{m-1}\dots a_2a_1$ , the only restriction on its digits is $a_1 \neq 0$ . Hence there are $9 \cdot 10^{m-1}$ of them and each is greater than $10^{2m-1}$ . Therefore the sum of reciprocals is not greater than $\frac{9 \cdot 10^{m-1}}{10^{2m-1}} = \frac{9}{10^m}$ . For all $m$ the sum is not greater than
$\sum_{m=1}^{\infty} \frac{9}{10^m} = 9 \cdot \sum_{m=1}^{\infty} \frac{1}{10^m} = 9 \cdot \frac{\frac{1}{10}}{1-\frac{1}{10}} = 9 \cdot \frac{1}{9} = 1.$

When $n = 2m-1$ , palindrome becomes $a_1a_2\dots a_{m-1}a_m a_{m-1}\dots a_2a_1$ , and again the only restriction on its digits is $a_1 \neq 0$ . Hence there are $9 \cdot 10^{m-1}$ of them and each is greater than $10^{2m-2}$ . Therefore the sum of reciprocals is not greater than $\frac{9 \cdot 10^{m-1}}{10^{2m-2}} = \frac{9}{10^{m-1}}$ . For all $m$ the sum is not greater than
$\sum_{m=1}^{\infty} \frac{9}{10^{m-1}} = 90 \cdot \sum_{m=1}^{\infty} \frac{1}{10^m} = 90 \cdot \frac{\frac{1}{10}}{1-\frac{1}{10}} = 90 \cdot \frac{1}{9} = 10.$

Therefore, the sum does not exceed $11$ .

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.