Number theoryDifficulty 6.0National olympiadProve itMongolia
Initially a needle with length l was in vertical position. Can one transfer the needle to horizontal position by passing no more than 2014 lattice points?
Solution
By Chinese remainder theorem the system ⎩⎨⎧n≡p0(modp02)n+1≡p1(modp12)................n+k≡pk(modpk2) has n positive integer solutions for ∀k∈N, where p0,p1,…,pk are different primes of the form 4t+3. From this follows that there is no lattice point in the ring {(x,y)∈R2∣n≤x2+y2≤n+k}. Proceeding by contradiction, if suppose that x2+y2=n+t, 0≤t≤k, x,y∈Z then x2+y2≡pt(modpt2) and x2+y2≡0(modpt), x2+y2≡0(modpt2), pt=4l+3. It implies x2≡−y2(modpt)⇒x≡y≡0(modpt) and we get pt2∣x2+y2. This is a contradiction. If we take k>2l2 then one can locate the needle in the ring {(x,y)∈R2∣n≤x2+y2≤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.