The Greedy Algorithm

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).