Drexel dragonThe Math ForumDonate to the Math Forum

Ask Dr. Math - Questions and Answers from our Archives
_____________________________________________
Associated Topics || Dr. Math Home || Search Dr. Math
_____________________________________________

Unit Fractions and the Greedy Algorithm


Date: 12/27/2000 at 07:28:12
From: Tok Foon
Subject: Express 2000/2001 using unit fractions

Dear Dr. Math,

I've found many ways to express 1999/2000 as a sum of distinct 
positive unit fractions. For example, two of the many possible ways 
are 1/10 + 1/50 + 1/250 + 1/2000 and 1/10 + 1/50 + 1/400 + 1/500.

I tried, but don't seem to be able to express 2000/2001 as a sum of 
distinct positive unit fractions. I'm beginning to wonder if there is 
any solution.

Hope someone can help.


Date: 12/27/2000 at 11:01:55
From: Doctor Rob
Subject: Re: Express 2000/2001 using unit fractions

Thanks for writing to Ask Dr. Math, Tok Foon.

Sorry, but the two sums you gave add up to 249/2000, not to 1999/2000. 
 You apparently left off 1/2 + 1/4 + 1/8 from the front of each sum.

What you ask can always be done. One way is to use the Greedy 
Algorithm. For the first fraction, choose the largest unit fraction 
not greater than the target number. Subtract that, and repeat. This 
method will always terminate.

For example, for 1999/2000, the largest unit fraction not greater than 
it is 1/2. Then:

     1999/2000 - 1/2 = 999/2000

Next, the largest unit fraction not greater than 999/2000 is 1/3, and:

      999/2000 - 1/3 = 997/6000

Continuing in this way, you get:

     1999/2000 = 1/2 + 1/3 + 1/7 + 1/43 + 1/18619 + 1/781998000

This won't always give you the shortest sum, or the one with the 
smallest denominators, but it will always work.

There are always infinitely many ways to write any fraction as a sum 
of distinct unit fractions. For example, you can always replace the 
smallest fraction in the sum, 1/A, by

     1/A = 1/(2*A) + 1/(3*A) + 1/(6*A)

and get a different, larger set of fractions with the same sum.

Now try 2000/2001 again.

- Doctor Rob, The Math Forum
  http://mathforum.org/dr.math/   
    
Associated Topics:
High School Puzzles
Middle School Fractions
Middle School Puzzles

Search the Dr. Math Library:


Find items containing (put spaces between keywords):
 
Click only once for faster results:

[ Choose "whole words" when searching for a word like age.]

all keywords, in any order at least one, that exact phrase
parts of words whole words

Submit your own question to Dr. Math

[Privacy Policy] [Terms of Use]

_____________________________________
Math Forum Home || Math Library || Quick Reference || Math Forum Search
_____________________________________

Ask Dr. MathTM
© 1994-2013 The Math Forum
http://mathforum.org/dr.math/