Copyright © University of Cambridge. All rights reserved.

'The Greedy Algorithm' printed from http://nrich.maths.org/

Show menu


It is called the Greedy Algorithm because at each step the algorithm chooses greedily to take away the largest possible unit fraction.

In order for this to work, for us to finish up with a string of unit fractions, we need to know that we'll be able to stop at some point...

The key is noticing that each step reduces the numerator of the remaining fraction (after the largest unit fraction has been subtracted).

e.g.1   Starting with $\frac{4}{5}$:

$\frac{4}{5} - \frac{1}{2} = \frac{3}{10}$

$\frac{3}{10} - \frac{1}{4} = \frac{1}{20}$

So $\frac{4}{5} = \frac{1}{2} + \frac{1}{4} + \frac{1}{20}$


e.g.2   Starting with $\frac{23}{25}$:

$\frac{23}{25} - \frac{1}{2} = \frac{21}{50}$

$\frac{21}{50} - \frac{1}{3} = \frac{13}{150}$

$\frac{13}{150} - \frac{1}{12} = \frac{1}{300}$

So $\frac{23}{25} = \frac{1}{2} + \frac{1}{3} + \frac{1}{12} + \frac{1}{300}$


Each step reduced the numerator of the remaining fraction to be expanded. But how can we be sure this will always happen?

Starting with $\frac{x}{y}$, we can find the two unit fractions $\frac{1}{a}$ and $\frac{1}{a-1}$ between which $\frac{x}{y}$ lies:

$\frac{1}{a}\leq\frac{x}{y}<\frac{1}{a-1}$

So $\frac{1}{a}$ is the largest unit fraction that we can subtract from $\frac{x}{y}$.

Subtracting $\frac{1}{a}$ from $\frac{x}{y}$ leaves us with $\frac{ax-y}{ay}$

We know that $\frac{x}{y}<\frac{1}{a-1}$

Hence  $x(a - 1) < y$
so  $ax - x < y$
so  $ax - y < x$

Since $ax - y < x$ 

$\frac{ax-y}{ay}$ will have a smaller numerator than $\frac{x}{y}$

so when we subtract the largest unit fraction from $\frac{x}{y}$ we will be left with a fraction with a smaller numerator.

As we repeat the process the numerator will get smaller and smaller until it eventually reaches 1 (when we will be left with a unit fraction).


I used the dictionary to find out what an algorithm was. It said
"A finite set of unambiguous instructions performed in a set sequence to achieve a goal, especially a mathematical rule or procedure used to compute a desired result. Algorithms are the basis for most computer programming."
This means that it is a set of instructions that you follow, that finish in a specific number of moves.