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 . 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.
Recent Comments