Maths Olympiad Prep

Library / Ukrainian National Mathematical Olympiad /162 of 201

Ukrainian National Mathematical Olympiad

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, 77, 12211221 and 5757557575 are palindromic, while 12121212 and 33303330 are not. Prove that for any number of pairwise distinct palindromic numbers the sum of their reciprocals is not greater than 1111.
(Arsenii Nikolaiev)

Solution

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

When n=2mn = 2m, palindrome becomes a1a2…am−1amamam−1…a2a1a_1a_2\dots a_{m-1}a_m a_m a_{m-1}\dots a_2a_1, the only restriction on its digits is a1≠0a_1 \neq 0. Hence there are 9⋅10m−19 \cdot 10^{m-1} of them and each is greater than 102m−110^{2m-1}. Therefore the sum of reciprocals is not greater than 9⋅10m−1102m−1=910m\frac{9 \cdot 10^{m-1}}{10^{2m-1}} = \frac{9}{10^m}. For all mm the sum is not greater than
∑m=1∞910m=9⋅∑m=1∞110m=9⋅1101−110=9⋅19=1. \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−1n = 2m-1, palindrome becomes a1a2…am−1amam−1…a2a1a_1a_2\dots a_{m-1}a_m a_{m-1}\dots a_2a_1, and again the only restriction on its digits is a1≠0a_1 \neq 0. Hence there are 9⋅10m−19 \cdot 10^{m-1} of them and each is greater than 102m−210^{2m-2}. Therefore the sum of reciprocals is not greater than 9⋅10m−1102m−2=910m−1\frac{9 \cdot 10^{m-1}}{10^{2m-2}} = \frac{9}{10^{m-1}}. For all mm the sum is not greater than
∑m=1∞910m−1=90⋅∑m=1∞110m=90⋅1101−110=90⋅19=10. \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 1111.

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

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