Consider an open interval of length $1/n$ on the real number line, where $n$ is a positive integer. Prove that the number of irreducible fractions $p/q$, with $1\le q\le n$, contained in the given interval is at most $(n+1)/2$.
Problem
Source: USAMO 1983 Problem 5
Tags: AMC, USA(J)MO, USAMO, number theory unsolved, number theory