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.

Our other blog

Visitors to this blog

Blog Stats

  • 254,536 hits

Wikio Ranking

Wikio - Top Blogs - Sciences

Current Online Readers

Archives

July 2008
M T W T F S S
« Jun   Aug »
 123456
78910111213
14151617181920
21222324252627
28293031  
Follow

Get every new post delivered to your Inbox.

Join 65 other followers