You may also like

problem icon

Chocolate

There are three tables in a room with blocks of chocolate on each. Where would be the best place for each child in the class to sit if they came in one at a time?

problem icon

F'arc'tion

At the corner of the cube circular arcs are drawn and the area enclosed shaded. What fraction of the surface area of the cube is shaded? Try working out the answer without recourse to pencil and paper.

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?

The Greedy Algorithm

Stage: 3 Challenge Level: Challenge Level:3 Challenge Level:3 Challenge Level:3

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.