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-2018;   Last Updated: 23 May, 2003