1983 USAMO Problems/Problem 5

Problem

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$ .

Solution

Let $I$ be an open interval of length $1/n$ and $F_n$ the set of fractions $p/q\in I$ with $p,q\in\mathbb{Z}$ , $\gcd(p,q)=1$ and $1\leq q\leq n$ .

Assume that $\frac{p}{q}\in F_n$ . If $k\in\mathbb{Z}$ is such that $1\leq kq\leq n$ , and $p'\in\mathbb{Z}$ is such that $\gcd(p',kq)=1$ , then $\left|\frac{p}{q}-\frac{p'}{kq}\right|\geq\frac{1}{kq}\geq \frac{1}{n}$ Therefore $\frac{p'}{kq}\notin I\supset F_n$ . This means that $\frac{p}{q}$ is the only fraction in $F_n$ with denominator $q$ or multiple of $q$ .

Therefore, from each of the pairs in $P=\left\{(k,2k):\ 1\leq k\leq \left\lfloor\frac{n+1}{2}\right\rfloor\right\}$ at most one element from each can be a denominator of a fraction in $F_n$ .

Hence $|F_n|\leq |P|\leq\frac{n+1}{2}$

1983 USAMO (Problems • Resources)
Preceded by Problem 4	Followed by Last Question
1 • 2 • 3 • 4 • 5
All USAMO Problems and Solutions

Page

Toolbox

Search

1983 USAMO Problems/Problem 5

Problem

Solution

See Also