IARCS home > OLYMPIAD > Archives
The problem next up previous
Next: Input format Up: Nearest fraction Previous: Nearest fraction

The problem

Given an arbitrary fraction ${a}/{b}$ in reduced form whose denominator $b$ is larger than 99, we want to find the pair of fractions in $X$ that are closest to ${a}/{b}$.

In other words, we want to identify fractions ${u}/{v}$ and ${x}/{y}$ in $X$ such that ${u}/{v} < {a}/{b} < {x}/{y}$ with the property that there is no fraction ${u'}/{v'}$ in $X$ such that ${u}/{v} < {u'}/{v'} < {a}/{b}$ and there is no fraction ${x'}/{y'}$ in $X$ such that ${a}/{b} < {x'}/{y'} < {x}/{y}$.

For instance, if ${a}/{b}$ is ${2}/{101}$, then ${u}/{v} = {1}/{51}$ and ${x}/{y} = {1}/{50}$. Here is another example--if ${a}/{b} = {322}/{479}$, then ${u}/{v} = {41}/{61}$ and ${x}/{y} = {39}/{58}$.


Madhavan Mukund 2003-05-22


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