Maths Olympiad Prep

Library / /365 of 520

Number theory Difficulty 7.2 National olympiad, round 2 Prove it

A flea moves in the positive direction on the real Ox axis, starting from the origin. He can only jump over distances equal with 2\sqrt 2 or 2005\sqrt{2005}. Prove that there exists n0n_0 such that the flea can reach any interval [n,n+1][n,n+1] with nn0n\geq n_0.

Solution

1. Assume the contrary: Suppose there does not exist an n0 n_0 such that the flea can reach any interval [n,n+1][n, n+1] with nn0 n \geq n_0 . This means there are infinitely many intervals [n,n+1][n, n+1] that the flea cannot jump into.

2. Define sequences: Let (xn)n0(x_n)_{n \geq 0} be the infimum of these intervals. Since there are infinitely many such intervals, xn x_n \to \infty .

3. Greatest reachable point: Let (yn)n0(y_n)_{n \geq 0} be the greatest number of the form aX+bY aX + bY (where X,YN X, Y \in \mathbb{N} ) such that yn<xn y_n < x_n . Clearly, yn y_n \to \infty .

4. **Representation of yn y_n **: We can write yn=aun+bvn y_n = a u_n + b v_n for some un,vnN u_n, v_n \in \mathbb{N} . Since yn y_n \to \infty , at least one of un u_n or vn v_n must tend to infinity. Without loss of generality, assume vn v_n \to \infty .

5. Density argument: Since abQ \frac{a}{b} \notin \mathbb{Q} , by a form of Kronecker's theorem, the set {au+bvuN,vZ} \{ au + bv \mid u \in \mathbb{N}, v \in \mathbb{Z} \} is dense in R\mathbb{R}. Therefore, we can choose u>0 u > 0 and vZ v \in \mathbb{Z} such that 0<auvb<1 0 < au - vb < 1 .

6. **Choosing N N **: Since vn v_n \to \infty , we can choose N N such that vN>v v_N > v . Hence, yN+(auvb) y_N + (au - vb) is a position where the flea can jump.

7. Analyzing the jump:
- If yN+(auvb)xN y_N + (au - vb) \geq x_N , then yN+(auvb)[xN,xN+1] y_N + (au - vb) \in [x_N, x_N + 1] , which contradicts our assumption that the flea cannot land in [xN,xN+1][x_N, x_N + 1].
- If yN+(auvb)<xN y_N + (au - vb) < x_N , then yN<yN+(auvb)<xN y_N < y_N + (au - vb) < x_N , which contradicts the fact that yN y_N is the greatest number of the form aX+bY aX + bY less than xN x_N .

8. Conclusion: Both cases lead to a contradiction, so our initial assumption must be false. Therefore, there exists n0 n_0 such that the flea can reach any interval [n,n+1][n, n+1] with nn0 n \geq n_0 .

\blacksquare

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: NuminaMath-1.5, licensed Apache-2.0. Statement and solution reproduced as published; topic and difficulty added by this site.