Maths Olympiad Prep

Library / /38 of 69

Number theory Difficulty 6.0 National olympiad Prove it Mongolia

Initially a needle with length ll was in vertical position. Can one transfer the needle to horizontal position by passing no more than 20142014 lattice points?

Solution

By Chinese remainder theorem the system
{np0(modp02)n+1p1(modp12)................n+kpk(modpk2) \left\{ \begin{array}{l} n \equiv p_0 \pmod{p_0^2} \\ n + 1 \equiv p_1 \pmod{p_1^2} \\ \text{................} \\ n + k \equiv p_k \pmod{p_k^2} \end{array} \right.
has nn positive integer solutions for kN\forall k \in \mathbb{N}, where p0,p1,,pkp_0, p_1, \dots, p_k
are different primes of the form 4t+34t + 3. From this follows that there is no
lattice point in the ring {(x,y)R2nx2+y2n+k}\{(x, y) \in \mathbb{R}^2 \mid n \le x^2 + y^2 \le n + k\}. Proceeding
by contradiction, if suppose that x2+y2=n+tx^2 + y^2 = n + t, 0tk0 \le t \le k, x,yZx, y \in \mathbb{Z} then
x2+y2pt(modpt2)x^2 + y^2 \equiv p_t \pmod{p_t^2} and x2+y20(modpt)x^2 + y^2 \equiv 0 \pmod{p_t}, x2+y2≢0(modpt2)x^2 + y^2 \not\equiv 0 \pmod{p_t^2}, pt=4l+3p_t = 4l + 3. It
implies x2y2(modpt)xy0(modpt)x^2 \equiv -y^2 \pmod{p_t} \Rightarrow x \equiv y \equiv 0 \pmod{p_t} and we get pt2x2+y2p_t^2 \mid x^2 + y^2. This is
a contradiction. If we take k>l22k > \frac{l^2}{2} then one can locate the needle in the ring
{(x,y)R2nx2+y2n+k}\{(x, y) \in \mathbb{R}^2 \mid n \le x^2 + y^2 \le n + k\} and it is possible to rotate the needle
inside the ring not passing a lattice point.

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 and solution reproduced as published; topic and difficulty added by this site.