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>