You may also like

Tweedle Dum and Tweedle Dee

Two brothers were left some money, amounting to an exact number of pounds, to divide between them. DEE undertook the division. "But your heap is larger than mine!" cried DUM...

Sum Equals Product

The sum of the numbers 4 and 1 [1/3] is the same as the product of 4 and 1 [1/3]; that is to say 4 + 1 [1/3] = 4 � 1 [1/3]. What other numbers have the sum equal to the product and can this be so for any whole numbers?

Special Sums and Products

Find some examples of pairs of numbers such that their sum is a factor of their product. eg. 4 + 12 = 16 and 4 × 12 = 48 and 16 is a factor of 48.

The Greedy Algorithm

Age 11 to 14 Challenge Level:

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.