The British Informatics Olympiad Sponsored by Data Connection.

The 1997 British Informatics Olympiad Round One Question 3

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. No unit fraction will need to be smaller than 1/32000.

There are many ways to solve this question. A simple solution is possible if we assume that we will never need more than 4 unit fractions and no denominator will exceed 32000. A first approach to the problem could be as follows. Check if the solution is already Egyptian (which will be the case if a divides b). Otherwise, try 2, then 3, then 4 combinations of unit fractions. Constraints can be found to limit the number of combinations that need to be investigated, such as making them increase and stopping searching when no solution is possible.

This approach solves the problem quickly if a solution with 2 unit fractions exists - needing to investigate fewer than 1000 numbers. The search space increases over a thousand times for each additional unit fraction - making it feasible to search for 3 (of the order of millions of combinations) but practically impossible to find solutions requiring 4 unit fractions in the two minutes available for programs to run.

The search can be speeded up considerably. Let the solution be (C1+...Cn)/D, where each Ci divides D. It can be assumed that D is a multiple of B, and each Ci is a distinct divisor of D. This can result in a very much smaller search space, particularly if B is a large prime number. An upper limit on D might be as large as A*B, so valid or optimal solutions may be missed by, for example, constraining D<=32000; nevertheless, this method makes the search method very much faster.

Search is used in the example solution program for 3(a), which can be run in a Java-enabled browser. It was also the method chosen by Stephen Williams, who got the highest mark (20 out of 23) for this question, and you can view his program q3a.pas or download a zip archive containing a PC/DOS executable.

A rather different approach can find solutions very quickly, but does not guarantee that they will be optimal. a/b can be written as the sum of a unit fractions of 1/b. This is not an Egyptian fraction (the unit fractions must be distinct), but it can be converted into an Egyptian fraction using these rules:

• common factors: if some c<=a divides b, c unit fractions can be written as 1/(b/c)
• splitting: 2/b, where b is odd, can be written as 1/c + 1/d where c=(b+n)/2 and d=b(b+n)/2n and n is odd (at least one solution, n=1, exists).

Repeated application of these rules will reduce a/b to an Egyptian fraction. However, for large b, the unit fractions may be very small (potentially to small to be represented as the reciprocal of a 32-bit integer), and there may be many (there will be no more than a). This provides a fast, but non-optimal solution.

Marking

All ten tests in this section have multiple solutions. For each test only the optimal solutions are given. For the first seven tests, the program gets two marks for finding these optimal solutions and one mark for a non-optimal solution. (Examples of likely non-optimal solutions to Tests 5, 6 and 7 are given in brackets.)

If alternative solutions are produced they should be checked by calculator. A solution to the input "a b" is valid if a/b is equal to the sum of the reciprocals of the numbers output. Additionally, the numbers output must all be different, and should have no more than 8 digits.

Mark tests 1-7 as follows:
[2] If the answer given is one of the optimal solutions.
[1] If the answer given is valid but not optimal.

[2] Test 1: 1 20    20

[2] Test 2: 36 612  17

[2] Test 3: 2 15    12 20

[2] Test 4: 2 37    19 703

[2] Test 5: 27 441  28 49 196
                    (17 417 347361)

[2] Test 6: 4 109   30 545 654
                    (28 1018 1553468)

[2] Test 7: 59 211  4 36 633 3798
                    6 9  633 3798
                    (4 34 4783 68626484)

For the final three tests any valid solution scores all [3] marks. An additional non-optimal solution is given for test 8, and test 10 has four equally valid optimal solutions. If other output is produced, use a calculator to check that it is a valid solution to within rounding error.

[3]  Test 8:  101 103    2 3 7 238 5253
                         (2 3 7 228 164388)

[3]  Test 9:  907 911    2 4 5 22 10021 18220

[3]  Test 10:  523 547   2 3 9 90 2735 4923
                         2 3 10 45 2735 4923
                         2 3 15 18 2735 4923
                         2 4 5 180 2735 4923

3 (b) [2 marks] What fractions do the following Egyptian fractions represent?

(i) 1/8 + 1/56 = 1/7 [1 mark]
(ii) 1/2 + 1/4 + 1/8 + 1/16 + 1/32 = 31/32 [1 mark].

3 (c) [5 marks] Do there exist any fractions for which there is a unique Egyptian fraction?

A total of five marks may be obtained by making the following points.

[1] No.

[1] All fractions (b/c) can be written as an Egyptian fraction.

[1] Every unit fraction can be written as an Egyptian fraction with more than one term.

[2] If we have an Egyptian fraction we can make an equivalent Egyptian fraction by expanding its smallest unit fraction into an Egyptian fraction of more than one term.

3 (d) [5 marks] How many different valued fractions (a/b) are there if 0 < a < b < 1000?

The calculation of this quantity can be done using a simple program. For each combination 0 < a < b < 1000, a/b should only be counted if there is no integer c > 1 that divides both b and a -- if there is, it will have the same value as (a/c)/(b/c) and will have been counted.

There are many ways of finding the greatest common divisor. A very simple and fast algorithm is that of Euclid. This uses the fact that
GCD(a, b) = GCD(b mod a, a)
where 0 < a < b. Repeating this formula will lead to the first number being zero and the second the GCD. This is implemented by the following Java code:

  public int greatestCommonDivisor(int a, int b) {
    if (a == 0)
      return b;
    else
      return greatestCommonDivisor(b % a, a);
  }

The problem can be solved by a simple main procedure, also given in Java:

  public void run() {
    int a, b;
    int count = 0;
    for( b = 2; b < 1000; b++ ) for( a = 1; a < b; a++ )
      if (greatestCommonDivisor(b, a) == 1) count++;
    out.println(count);
  }

A solution using these procedures can be run in a Java-capable browser: example solution of part 3(d).

Marking

[5] 303791

(Supplementary: 304191 scores [4] marks.)
This is the case for 0 < a < b <= 1000.

• Example solution program for 3(a) and for 3(d).
• Question statement
• Index of BIO'97 Round One questions
• BIO'98 sample paper