IARCS home > OLYMPIAD > Archives
Nearest fraction next up previous
Next: The problem Up: inoi2003-qpaper Previous: Output format

Nearest fraction

Let $X$ be the set of all fractions in reduced form lying strictly below 0 and 1 whose denominator is less than or equal to 99. In other words,


\begin{displaymath} \frac{n}{d} \mbox{~belongs to~} X \mbox{~provided~} 0 < \frac{n}{d} < 1 \mbox{~and~} d \leq 99 \mbox{~and~} \gcd(n,d) = 1, \end{displaymath}

where $\gcd(x,y)$ denotes the greatest common divisor (or highest common factor) of $x$ and $y$.

For instance, $X$ includes fractions such as ${1}/{3}$, ${11}/{31}$ and ${24}/{37}$ and excludes fractions such as ${4}/{10}$, ${30}/{70}$ (both not in reduced form) and ${2}/{101}$ (denominator too large).


Subsections
Madhavan Mukund 2003-05-22



Copyright (c) IARCS 2003-2024;   Last Updated: 23 May, 2003