# the greedy algorithm

*The Greedy Algorithm printable sheet*

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?

Is your fraction bigger than $\frac{1}{2}$?

If not, is it bigger than $\frac{1}{3}$?

If not, is it bigger than $\frac{1}{4}$?

...

Now subtract the largest unit fraction you can.

Here's another example of the Greedy Algorithm at work...

$\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}$

If you're not sure which is bigger, you could use a calculator and convert your fractions into decimals.

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

### Why do this problem?

This problem follows on from Keep It Simple and Egyptian Fractions

These three problems together offer students an opportunity to engage with some mathematical ideas in depth and not just with the rather mechanical process of adding and subtracting fractions.

This problem in particular requires students to compare fractions and may deepen their understanding of their relative sizes.

### Possible approach

Students should already have worked with fractions of the form $\frac{1}{n}$, $\frac{2}{n}$ and possibly $\frac{3}{n}$ and $\frac{4}{n}$ in Keep It Simple and Egyptian Fractions .

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

### Key Questions

Is our fraction larger or smaller than $\frac{1}{2}$? How do we know?

....

### Possible support

Students who need support in comparing the size of fractions might have to do some preliminary work on equivalent fractions.

### Possible extension

Does the Greedy Algorithm always result in the sum with the fewest possible terms?

Can anyone find a counter example?

The Eye of Horus: often it was good enough to use only the fractions

that represent $\frac{1}{2}$, $\frac{1}{4}$, $\frac{1}{8}$.... to get a fraction that is close enough to any specific fraction. Suggest that students pick some fractions and convert them to this form of Egyptian fraction.

How close does this method get to the target fraction?

Students might like to research how these particular fractions were written down in pictorial form.