Copyright © University of Cambridge. All rights reserved.
'The Greedy Algorithm' printed from http://nrich.maths.org/
This problem follows on from
Keep
it Simple and
Egyptian
Fractions
So far you may have looked at how the Egyptians expressed fractions
as the sum of different unit fractions. You may have started by
considering fractions with small numerators, such as $\frac{2}{5}$,
$\frac{3}{7}$, $\frac{4}{11}$, etc.
But how would the Egyptians have coped with fractions with large
numerators such as $\frac{115}{137}$?
They might have written $\frac{115}{137} = \frac{1}{137} +
\frac{1}{137} + \frac{1}{137}$....
and then used
Jamie's
method to make them all different, but this would have made an
extremely lengthy calculation!
Fibonacci found an alternative strategy, called the Greedy
Algorithm:
At every stage, write down the largest possible unit fraction
that is smaller than the fraction you're working on.
For example, let's start with $\frac{11}{12}$:
The largest possible unit fraction that is smaller than
$\frac{11}{12}$ is $\frac{1}{2}$
$\frac{11}{12} - \frac{1}{2} = \frac{5}{12}$
So $\frac{11}{12} = \frac{1}{2} + \frac{5}{12}$
The largest possible unit fraction that is smaller than
$\frac{5}{12}$ is $\frac{1}{3}$
$\frac{5}{12} - \frac{1}{3} = \frac{1}{12}$
So $\frac{11}{12} = \frac{1}{2} + \frac{1}{3} + \frac{1}{12}$
Choose a fraction of your own and apply the Greedy Algorithm to
see if you can finish up with a string of unit fractions.
Does the greedy algorithm always work?
Can all fractions be expressed as a sum of different unit fractions
by applying the Greedy Algorithm?
Can you convince yourself of this?
Why do you think it is called the Greedy Algorithm? What do these
words mean in a mathematical context?