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 . The (regular) continued fraction for is and for it’s

A rational number is in the desired range if and only if is of the form , where is rational and

Suppose where . Then , where . We are trying to minimize the denominator under the constraint

and clearly this is minimized when , . So the minimum denominator is , where .

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

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

.

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

Also solved by Arin Chaudhuri and Nilay Vaish.

### Like this:

Like Loading...

*Related*

## 1 comment

Comments feed for this article

April 26, 2009 at 10:49 pm

Name that fraction « Antimatroid, The[...] asking the question, what’s given ? Now, the Topological Musings guys wrote up a walk through on how to end up at the solution of by way of mathematical analysis, but it is [...]