![[BIO97 Logo]](../../../images/flag97s.gif)
Sponsored by Data Connection.
![[Data Connection logo]](../../../images/dc_logo3.gif){kind=logo}
| |
The British Informatics
Olympiad Sponsored by Data Connection. |
|
 |
The 1997 British Informatics Olympiad Round One Question 3 |
| Question 3 Egyptian fractions |
When ancient Egyptians wrote
fractions they were only able to use ones of the form 1/a,
called unit fractions. An Egyptian wanting to write the
fraction b/c, where b was not 1, had
to write it as the sum of (different) unit fractions. All
fractions b/c (b < c) can
be written as an Egyptian fraction. For example, the fraction 5/6 was written as 1/2 + 1/3, and 6/7 was written as 1/2 + 1/3 + 1/42. Egyptian fractions are not necessarily unique: 6/7 can also be written as 1/2 + 1/4 + 1/14 + 1/28. Since the unit fractions must be different, 2/3 can be written as 1/2 + 1/6, but not 1/3 + 1/3. An Egyptian fraction representing b/c is 'minimal' if it uses the smallest number of unit fractions possible. An Egyptian fraction is 'optimal' if it is minimal, and the smallest unit fraction is as large as possible. There may be several minimal and several optimal Egyptian fractions for a given b/c. For example 19/45 cannot be represented as the sum of two unit fractions, but there are 5 ways of representing it as the sum of 3 unit fractions: 1/3 + 1/12 + 1/180, 1/3 + 1/15 + 1/45, 1/3 + 1/18 + 1/30, 1/4 + 1/6 + 1/180 and 1/5 + 1/6 + 1/18. These five Egyptian fractions are all minimal. Only 1/5 + 1/6 + 1/18 is optimal, since 1/18 is larger than 1/30, 1/45 and 1/180. |
| 3 (a) [23 marks] |
Write a program that inputs two numbers a and b, and calculates an Egyptian fraction representing a/b with no more than a unit fractions. You will only be given fractions with 0 < a < b < 1000. Your program should then output the denominators (bottom parts) of the unit fractions. | |
| There will be ten tests. For each test, if there exists an optimal solution which is the sum of 4 (or fewer) unit fractions, more marks will be given for outputting an optimal solution. | Sample
run |
|
| No unit fraction will need to be smaller than 1/32000. [You can still output denominators greater than 32000, so long as they are no more than 8 digits long.] |
| 3 (b) [2 marks] |
What
fractions do the following Egyptian fractions represent? (i) 1/8 + 1/56 (ii) 1/2 + 1/4 + 1/8 + 1/16 + 1/32 |
| 3 (c) [5 marks] |
Do there exist any fractions for which there is a unique Egyptian fraction? |
| 3 (d) [5 marks] |
How many
different valued fractions (a/b) are there
if 0 < a < b < 1000? [Hint : Remember, for example, that 1/2 and 2/4 have the same value.] |