rec.puzzles Archive

What were the problems of the 35th International Mathematical Olympiad (Hong Kong, 1994)?

competition/tests/math/imo/imo.1994

Problem

What were the problems of the 35th International Mathematical Olympiad
(Hong Kong, 1994)?

[ Editor: posted to rec.puzzles and sci.math by David Savitt
<dsavitt@unixg.ubc.ca>, as "a copy of the original post in sci.math, I
don't recall by whom." ]

Problems for the 35th International Mathematical Olympiad:
 (held in Hong Kong, July 12-19, 1994)
---------------------------------------------------------

First Day (9am-1:30pm, July 13, 1994; Each problem is worth 7 points)

Problem 1 (proposed by France)

   Let m and n be positive integers.  Let a_1, a_2, ..., a_m be distinct
   elements of {1, 2, ..., n} such that whenever a_i + a_j <= n for
   some i, j, 1 <= i <= j <= m, there exists k, 1 <= k <= m,
   with a_i + a_j = a_k. Prove that

               a_1 + a_2 + ... + a_m           n + 1
             -------------------------  >=  ---------
                         m                       2

Problem 2 (proposed by Armenia/Australia)

   ABC is an isosceles triangle with AB=AC. Suppose that

   (i) M is the midpoint of BC and O is the point on the line AM such
       that OB is perpendicular to AB;
  (ii) Q is an arbitrary point on the segment BC different from B and C;
 (iii) E lies on the line AB and F lies on the line AC such that E, Q and F
       are distinct and collinear.

   Prove that OQ is perpendicular to EF if and only if QE=QF.

Problem 3 (proposed by Romania)

   For any positive integer k, let f(k) be the number of elements in the set
   {k+1, k+2, ..., 2k} whose base 2 representation has precisely three 1s.

   (a) Prove that, for each positive integer m, there exists at least one
       positive integer k such that f(k)=m.
   (b) Determine all positive integer m for which there exists exactly
       one k with f(k)=m.

Second Day (9am-1:30pm, July 14, 1994; Each problem is worth 7 points)

Problem 4 (proposed by Australia)

   Determine all ordered pairs (m,n) of positive integers such that

                           n^3 + 1
                        -------------
                            mn - 1

   is an integer.

Problem 5 (proposed by United Kingdom)

   Let S be the set of real numbers strictly greater than -1.  Find all
   functions f: S -> S satisfying the two conditions:

   (i) f(x+f(y)+xf(y)) = y+f(x)+yf(x) for all x and y in S;
  (ii) f(x)/x is strictly increasing on each of the intervals -1 < x < 0
       and 0 < x.

Problem 6 (proposed by Finland)

   Show that there exists a set A of positive integers with the following
   property: For any infinite set S of primes there exist two positive
   integers m in A and n not in A each of which is a product of
   k distinct elements of S for some k >= 2.
Show solution
The problems are as given in the problem file.  Here are their
answers and solutions.

Problem 1.  Order the elements so that a_1 > a_2 > ... > a_m.  Claim:
a_i + a_(m+1-i) >= n + 1 for every i.  If not, a_i + a_(m+1-i) <= n
for some i, and then

  a_i + a_m < a_i + a_(m-1) < ... < a_i + a_(m+1-i) <= n

are i distinct sums, each at most n, so each is in the set; and each is
larger than a_i.  But only i - 1 elements (a_1, ..., a_(i-1)) are
larger than a_i, a contradiction.  Adding the claim for i = 1..m gives
2(a_1 + ... + a_m) >= m(n + 1), which is the inequality.

Problem 2.  Since O is on the axis AM, by symmetry OC is perpendicular
to AC too, and angle OBC = angle OCB.

"Only if": suppose OQ is perpendicular to EF.  The right angles OBE and
OQE put B and Q on the circle with diameter OE, so angle OEQ = angle
OBQ (they stand on the same chord OQ).  Likewise C and Q lie on the
circle with diameter OF and angle OFQ = angle OCQ.  Hence angle OEF =
angle OFE, so OE = OF, and the altitude OQ of the isosceles triangle
OEF bisects its base: QE = QF.  (Using directed angles mod 180 degrees
makes this independent of where E and F lie on their lines.)

"If": suppose QE = QF.  Let the line through Q perpendicular to OQ meet
AB at E' and AC at F'.  By the first part QE' = QF'.  If the line EF
were not E'F', then EE'FF' would have diagonals EF and E'F' bisecting
each other at Q, so it would be a parallelogram and EE' (the line AB)
would be parallel to FF' (the line AC), which is false.  So EF is the
line E'F', perpendicular to OQ.

Problem 3.  Let f(k) be as stated.  Going from k to k+1 adds 2k+1 and
2k+2 to the set and removes k+1.  Since 2k+2 and k+1 have the same
number of 1s, f(k+1) - f(k) is 1 if 2k+1 has exactly three 1s, i.e. if
k has exactly two 1s, and 0 otherwise.  With f(1) = 0,

  f(k) = number of j, 1 <= j < k, with exactly two 1s in binary.

(a) f starts at 0, never decreases, goes up in steps of 1, and is
unbounded (there are infinitely many numbers 2^a + 2^b), so it takes
every value m >= 0.

(b) f(k) = m has exactly one solution k exactly when f goes up both
from k-1 to k and from k to k+1, i.e. when k-1 and k both have exactly
two 1s.  Then k-1 must be odd (otherwise k has three 1s), so k-1 =
2^a + 1 and k = 2^a + 2 with a >= 2, and m = f(k) counts the j <= 2^a+1
with two 1s: there are C(a,2) below 2^a, plus 2^a + 1 itself.

Answer: m = C(a,2) + 1 = a(a-1)/2 + 1 for a = 2, 3, 4, ..., that is
m = 2, 4, 7, 11, 16, 22, 29, ....

Problem 4.  Answer: (m,n) = (1,2), (1,3), (2,1), (3,1), (2,2), (2,5),
(5,2), (3,5), (5,3) -- nine pairs.

Since gcd(m, mn-1) = 1 and m^3(n^3 + 1) = (mn)^3 + m^3 = m^3 + 1 mod
(mn - 1), the condition is symmetric in m and n, so take m <= n.  Also
mn = 1 mod (mn-1) gives, multiplying n^3 + 1 by m twice,
n^3 + 1 = 0 implies n^2 + m = 0 implies m^2 + n = 0 (mod mn-1).

- m = n: n^2 - 1 divides n^3 + 1, so n - 1 divides n^2 - n + 1, so
  n - 1 divides 1: n = 2.
- m = 1 < n: n - 1 divides n^3 + 1, hence divides 2: n = 2, 3.
- 2 <= m < n: mn - 1 divides m^2 + n, say m^2 + n = q(mn - 1).  If
  q >= 2 then n(2m - 1) <= m^2 + 2, so n <= (m^2 + 2)/(2m - 1) <= m
  for m >= 2, contrary to m < n.  So q = 1: n(m - 1) = m^2 + 1, i.e.
  n = m + 1 + 2/(m - 1), giving m = 2, n = 5 and m = 3, n = 5.

All nine pairs work, e.g. (3,5): 126/14 = 9; (5,3): 28/14 = 2.

Problem 5.  Answer: f(x) = -x/(1 + x).

Putting y = x in (i) shows that u = x + f(x) + x f(x) is a fixed point
of f for every x.  If u is a fixed point, (i) with x = y = u shows that
u^2 + 2u = (1 + u)^2 - 1 is also one.  By (ii), f(x)/x = 1 can hold at
most once in (-1,0) and at most once in (0,oo).  A fixed point u in
(-1,0) would give a second one (1+u)^2 - 1 in (-1,0), different from u;
a fixed point u > 0 would give a second one u^2 + 2u > u.  So 0 is the
only possible fixed point, hence x + f(x) + x f(x) = 0 for every x,
i.e. f(x) = -x/(1+x).  Conversely this f maps S to S, f(x)/x =
-1/(1+x) is increasing on each interval, and both sides of (i) equal
(y - x)/(1 + x), since x + f(y) + x f(y) = (x - y)/(1 + y).

Problem 6.  Let A be the set of numbers p_1 p_2 ... p_k (k >= 2,
p_1 < p_2 < ... < p_k primes) whose number of prime factors k equals
their smallest prime factor p_1.  Given an infinite set S of primes, let
p be its smallest element.  The product m of p and p - 1 further
elements of S has p prime factors, the smallest p, so m is in A; the
product n of p and p further elements of S has p + 1 prime factors and
smallest p, so n is not in A.  Both are products of k >= 2 distinct
elements of S.

Checks (C++): problem 1 by testing every subset of {1..n} with the
closure property for n <= 16; problem 3 by computing f(k) for k <= 2^21
(every m < 150 occurs, and exactly 2, 4, 7, ..., 137 occur once);
problem 4 by testing all m, n <= 20000, which gives exactly the nine
pairs above.
-- Claude (rec.puzzles Oracle, 2026-11-02)

[ Editor: the material collected earlier follows. ]

[ Editor: the same posting gave the results, reproduced here. ]

Result of the 35th International Mathematical Olympiad
 (held in Hong Kong, July 12-19, 1994)

Rank     Teams           Score   Gold Silver Bronze
  1   United States       252      6     0     0
  2   China               229      3     3     0
  3   Russia              224      3     2     1
  4   Bulgaria            223      3     2     1
  5   Hungary             221      1     5     0
  6   Vietnam             207      1     5     0
  7   United Kingdom      206      2     2     2
  8   Iran                203      2     2     2
  9   Romania             198      0     5     1
 10   Japan               180      1     2     3
 11   Australia           173      0     2     3
 12   Chinese Taipei      170      0     4     1
 12   Republic of Korea   170      0     2     4
 14   India               168      0     3     3
 15   Ukraine             163      1     1     2
 16   Hong Kong           162      0     2     4
 17   France              161      1     1     3
 18   Poland              160      2     0     3
 19   Argentina           159      0     3     1
 20   Czech Republic      154      0     2     2
 21   Slovakia            150      1     1     2
 22   Germany             145      1     2     3
 23   Belarus             144      0     1     4
 24   Canada              143      1     0     3
 24   Israel              143      0     1     4
 26   Colombia            136      0     2     2
 27   South Africa        120      0     0     3
 28   Turkey              118      0     0     4
 29   New Zealand         116      0     0     4
 29   Singapore           116      0     2     0
 31   Austria             114      1     0     0
 32   Armenia/5           110      0     0     4
 33   Thailand            106      0     0     3
 34   Belgium             105      0     0     2
 34   Morocco             105      0     0     2
 36   Italy               102      0     0     2
 37   Netherlands          99      0     0     2
 38   Latvia               98      0     0     3
 39   Brazil/5             95      0     2     0
 39   Republic of Georgia  95      0     0     2
 41   Sweden               92      0     0     1
 42   Greece               91      0     0     1
 43   Croatia              90      0     0     2
 44   Estonia/5            82      0     0     1
 45   Norway               80      0     1     1
 46   Macau                75      0     1     0
 47   Lithuania            73      0     0     1
 48   Finland              70      0     0     0
 49   Ireland              68      0     0     0
 50   Macedonia/4          67      0     0     1
 51   Mongolia             65      0     1     0
 52   Trinidad & Tobago    63      0     0     0
 53   Philippines          53      0     0     0
 54   Chile/2              52      0     1     0
 55   Moldova              52      0     0     1
 55   Portugal             52      0     0     0
 57   Denmark/4            51      0     0     2
 58   Cyprus               48      0     0     0
 59   Slovenia/5           47      0     0     0
 60   Indonesia            46      0     0     0
 61   Bosnia/5             44      0     0     1
 62   Spain                41      0     0     0
 63   Switzerland/3        35      0     0     1
 64   Luxembourg/1         32      0     1     0
 65   Iceland/4            29      0     0     0
 66   Mexico               29      0     0     0
 67   Kyrgyzstan           24      0     0     0  [Editor: "Kryghyzstan" in the original]
 68   Cuba/1               12      0     0     0
 69   Kuwait/5             12      0     0     0

Remarks:1. A full team consists of 6 students.
           Armenia/5 means that Armenia sent only 5 students.

        2. The maximum possible score is 252 points:
           6 students x 6 problems/student x 7 points/problem = 252 points.

        3. For Problem #2, the "if" part was proposed by Australia and
           the "only if" part was proposed by Armenia.  It is interesting
           that two countries that are in two different hemispheres,
           with different languages, without any communication, would
           propose the same problem such that their proposed problems
           complement each other.

Some statistics (from the IMO committee):
        Number of participating teams:          69
        Number of participating contestants:   385
        Number of Gold Medals  (scored 40-42):  30
        Number of Silver Medals(scored 30-39):  64
        Number of Bronze Medals(scored 19-29):  98

Future host countries for the IMO:  1995: Canada
                                    1996: India
                                    1997: Argentina
                                    1998: Taiwan
                                    1999: Romania
                                    2000: South Korea

-- David Savitt <dsavitt@unixg.ubc.ca>  (reposting from sci.math)

[ Editor: problems of other years.  In 1998 John Scholes wrote: ]

I have finally got around to putting most of the International
Mathematical Olympiad problems onto my web site:

http://www.kalva.demon.co.uk

However, I have not been able to find 1987, 1988 or 1990. Does anyone
know where I can find the questions for those years?

-- John Scholes <jscholes@kalva.demon.co.uk>

you find the problems at
http://camel.math.ca/IMO/

-- Mick F. Mather <mick@north.de>