Skip to main content
### Number and algebra

### Geometry and measure

### Probability and statistics

### Working mathematically

### Advanced mathematics

### For younger learners

# The Greedy Algorithm

#### Fibonacci found an alternative strategy, called the Greedy Algorithm:

#### Choose a fraction of your own and apply the Greedy Algorithm to see if you can finish up with a string of unit fractions.

## You may also like

### Tweedle Dum and Tweedle Dee

### Sum Equals Product

### Special Sums and Products

Or search by topic

Age 11 to 14

Challenge Level

*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!

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

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?

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

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?

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.