Maths Olympiad Prep

Library / Germany TST /6 of 6

Germany TST

Number theory Difficulty 8.7 Shortlist Prove it Germany

Problem:

Let a1⩽a2⩽…a_{1} \leqslant a_{2} \leqslant \ldots be a monotonically increasing sequence of positive integers. A positive integer nn is called reliable if there exists a positive integer index ii with n=iain=\frac{i}{a_{i}}.

Prove: If 2013 is reliable, then 20 is also reliable.

Solution

Solution:

If 2013 is reliable, then there exists a positive integer index ii with i=2013ai⩾20aii=2013 a_{i} \geqslant 20 a_{i}. In particular, the set SS of all positive integers ss for which s⩾20ass \geqslant 20 a_{s} holds is non-empty. Thus SS contains a smallest element jj, and this satisfies on the one hand
j⩾20aj j \geqslant 20 a_{j}
and on the other hand (j−1)∉S(j-1) \notin S. The latter means that either j=1j=1 must hold, or j>1j>1 and j−1<20aj−1j-1<20 a_{j-1}. However, because of aj⩾1a_{j} \geqslant 1, it follows from (2) that j⩾20j \geqslant 20, which rules out the first of these two alternatives; hence it must be that j⩽20aj−1j \leqslant 20 a_{j-1}, and combining this with (2) we obtain the chain of inequalities
j⩾20aj⩾20aj−1⩾j. j \geqslant 20 a_{j} \geqslant 20 a_{j-1} \geqslant j .
This can only hold if equality holds throughout. Because j=20ajj=20 a_{j}, the index jj witnesses that 20 is, as claimed, reliable.

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 translated into English from de; metadata (topic, difficulty) added by this project.