Maths Olympiad Prep

Library / /6 of 6

Number theory Difficulty 8.7 Shortlist Prove it Germany

Problem:

Let a1a2a_{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=2013ai20aii=2013 a_{i} \geqslant 20 a_{i}. In particular, the set SS of all positive integers ss for which s20ass \geqslant 20 a_{s} holds is non-empty. Thus SS contains a smallest element jj, and this satisfies on the one hand
j20aj j \geqslant 20 a_{j}
and on the other hand (j1)S(j-1) \notin S. The latter means that either j=1j=1 must hold, or j>1j>1 and j1<20aj1j-1<20 a_{j-1}. However, because of aj1a_{j} \geqslant 1, it follows from (2) that j20j \geqslant 20, which rules out the first of these two alternatives; hence it must be that j20aj1j \leqslant 20 a_{j-1}, and combining this with (2) we obtain the chain of inequalities
j20aj20aj1j. 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,000 problems in a working order, from AMC 10 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.