MathDB

Number of lines through origin and precisely one other point

Source: Baltic Way 2011

November 6, 2011

analytic geometryprobabilityinequalitiesnumber theoryrelatively primecombinatorics proposedcombinatorics

Problem Statement

Let

n

be a positive integer. Prove that the number of lines which go through the origin and precisely one other point with integer coordinates

(x,y),0\le x,y\le n

, is at least

\frac{n^2}{4}