Solution to POW-8: Ups at bat

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.