You may also like

problem icon

Do Unto Caesar

At the beginning of the night three poker players; Alan, Bernie and Craig had money in the ratios 7 : 6 : 5. At the end of the night the ratio was 6 : 5 : 4. One of them won $1 200. What were the assets of the players at the beginning of the evening?

problem icon

Plutarch's Boxes

According to Plutarch, the Greeks found all the rectangles with integer sides, whose areas are equal to their perimeters. Can you find them? What rectangular boxes, with integer sides, have their surface areas equal to their volumes?

problem icon

3388

Using some or all of the operations of addition, subtraction, multiplication and division and using the digits 3, 3, 8 and 8 each once and only once make an expression equal to 24.

The Greedy Algorithm

Age 11 to 14 Challenge Level:

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 Alison'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?