You are currently browsing the daily archive for July 31, 2008.

Solutions to POW-8 are in! This one may have stuck in some readers’ craws, since obviously one could just program a computer to solve it by brute force (thus beating the problem with a bat, as John Armstrong quipped to me). I didn’t say you couldn’t do that, but surely one can do it more elegantly?

Solution by Sune Jakobsen: Suppose $.3335 \leq x < .3345$. The (regular) continued fraction for $.3335$ is $1/(2 + 1/(1 + 1/666)),$ and for $.3345$ it’s

$1/(2 + 1/(1 + 1/(94 + 1/(1 + 1/(1 + 1/3))))).$

A rational number $x$ is in the desired range if and only if $x$ is of the form $1/(2 + 1/(1 + 1/y))$, where $y$ is rational and

$94 + 1/(1 + 1/(1 + 1/3)) = 94.5714... < y \leq 666.$

Suppose $\displaystyle y = \frac{m}{n}$ where $\mbox{gcd}(m, n) = 1$. Then $\displaystyle x = \frac{m+n}{3m+2n}$, where $\mbox{gcd}(m+n, 3m+2n) = 1$. We are trying to minimize the denominator $3m + 2n$ under the constraint

$\displaystyle 94.5714... < \frac{m}{n} \leq 666$

and clearly this is minimized when $n = 1$, $m = 95$. So the minimum denominator is $3(95) + 2(1) = 287$, where $x = 96/287 = .33449477...$. $\Box$

Remark: Did you ever wonder why 22/7 is the “canonical” rational approximation to $\pi$? The answer lies in continued fractions. We are looking for rational numbers $m/n$ which are reasonably close to $\pi$, and where $m, n$ are kept within reasonable bounds; continued fractions are tailor-made for exactly this type of problem. The continued fraction representation for $\pi$ is

$3 + 1/(7 + 1/(15 + 1/(1 + 1/(292 + \ldots)))),$

and we get reasonably good rational approximants by truncating just before a reasonably large integer part. Thus, if we truncate just before the “15″, we get 3 + 1/7 = 22/7. If we truncate just before the “292″, we get the much better approximant

$\displaystyle 3 + 1/(7 + 1/(15 + 1)) = \frac{355}{113} = 3.1415929...$.

Sune’s solution above is an application of the same basic idea.

Also solved by Arin Chaudhuri and Nilay Vaish.

• 237,706 hits