**POLYA029: 2002 International Mathemtical Olympiad (Glasgow)**

Many thanks to Jean-Pierre Ehrmann for sending the following IMO problems.

**First day (24th July)**

**Problem 1: Let n be a positive integer. Let T be the set of points
(x , y) in the plane where x and y are non-negative integers and x+y<n.
Each point of T is coloured red or blue. If a point (x , y) is red, then
so are all points (x' , y') of T with both x'<=x and y'<=y. Define
an X-set to be a set of n blue points having distinct x-coordinates, and
a Y-set to be a set of n blue points having distinct y-coordinates. Prove
that the number of X-sets is equal to the number of Y-sets.**

**[JPE,7/30/02]: **let u(x) = number of blue points
(x,.) v(y) = number of blue points (.,y).

The number n_X of X_sets id u(0)u(1)...u(n-1); the number
n_Y of Y_sets is v(0)v(1)...v(n-1).

If there exists a red point (x,y) with x+y=n-1 then clearly
n_X=n_Y=0.

Elsewhere, let's call extremal a red point (x,y) such
as (x+1,y) and (x,y+1) are blue.

If P = (x,y) is extremal then u(x)=v(y); hence, if we
change the colour of P, n_X and n_Y will increase in the same ratio.

Iterating this process, all the points will become blue;
hence both n_X and n_Y will become n!.

--------------------------------------------------------------------------------------------------------------------------------------

**Problem 2: Let BC be a diameter of the circle T with centre O. Let
A be a point on T such that 0 deg < angle(AOB) < 120 deg. Let D be
the midpoint of the arc AB not containing C. The line through O parallel
to DA meets the line AC at J. The perpendicular bisector of OA meets T
at E and and F. Prove that J is the incentre of triangle CEF.**

**[JPE, 7/29/02]: **Both triangles AOE and AOF are
equilateral hence CJ bissects ECF. EAF = 120; ECF = 60. OD and AJ
are perpendicular to AB, hence AJ = OD and E,O,J,F are concyclic (on the
circle (A,R)). Hence EJF = EOF = 120. As ECF = 60, EJF = 120 and CJ bissects
ECF, the result follows.

**[ND, 7/29/02]: **Since EF is perpendicular bisector
of AO then A is the mid point of the arc EAF and AE = AF = R. Hence
CA is bisector of triangle CEF and in order to prove that J is the
incenter of CEF it is sufficient to prove that AJ = AE = AF = R.
But OD is perpendicular bisector of AB and parallel to AC. The quadrilateral
ADAJ is parallelogram and hence AJ = DO = R.

----------------------------------------------------------------------------------------------------------------------------------------
**Problem 3: Find all pairs of integers m,n >= 3 such that there exist
infinitely many positive integers a for which**
**(a^m + a - 1)/(a^n + a^2 - 1) is an integer.**

**[SCL, 7/30/02]: **Observation: (a^2-a+1)(a^3+a^2-1)=a^5+a-1,
so the pair [m=5,n=3] produces only integers.
**[JPE, 7/31/02]: **Let A(x)=x^m+x-1; B(x)=x^n+x^2-1;
A(x)=B(x)Q(x)+R(x) where Q,R are poynomial with integer coefficients, deg(R)<n.

There exists infinitely many values of a or which B(a)
divise R(a); as, for a large enough B(a)>R(a), it follows that R is identically
0.

Hence the polynomial B divides the polynomial A.

A(x)-x^(m-n)B(x)=(1-x)C(x) where C(x)=x^(m-n+1)+x^(m-n)-1;
as B(1)<>0, it follows that B(x) divides C(x) and m>=2n-1.

Let D(x) = C(x)-x^(m-2n+1)B(x) =x^(m-n)-x^(m-2n+3)+x^(m-2n+1)-1.
B divides D.

If n>3, D(x)=x^(m-2n+3)(x^(n-3)-1)+x^(m-2n+1)-1=(x-1)U(x)
where U(x)>0 for x>0.This is impossible because B has a root in ]0,1[.

Hence n=3 and x^3+x-1 divides D(x)=x^(m-5)-1. As B has
a root in ]0,1[, we have necessarily m=5.

If we notice that x^5+x-1=(x^3+x^2-1)(x^2-x+1), we can
conclude that the only solution is m=5, n=3

----------------------------------------------------------------------------------------------------------------------------------------
**Second day (25th July)**

**Problem 4: Let n be an integer greater than 1. The positive divisors
of n are d_1, d_2, ..., d_k where 1 = d_1 < d_2 < ... < d_k =
n. Define D = d_1d_2 + d_2d_3 + ... + d_{k-1}d_k.**
**(a) Prove that D < n^2.**
**(b) Determine all n for which D is a divisor of n^2.**

**[JPE, 7/29/02]: **(a) as d[j]d[k+1-j]=n, we have
d[k+1-j]<=n/j and d[k-j]d[k+1-j]<=n^2/j-n^2/(j+1). Hence D<=n^2(1-1/k)<n^2.

(b) If k>2, then D>d[k-1]d[k]=n^2/d[2]. As n^2 has no
divisor in the open interval ]n^2/d[2],n^2[, D is not a divisor of n^2.
If k=2 (ie if n is prime) D=n divides n^2. Hence D is a divisor of n^2
<=> n is prime

-------------------------------------------------------------------------------------------------------------------------------------------
**Problem 5: Find all functions f from the set R of real numbers to
itself such that**
**(f(x) + f(z))(f(y) + f(t)) = f(xy - zt) + f(xt + yz)**
**for all x,y,z,t in R.**

**[JPE, 7/29/02]: **If f is constant, then f=0 or1/2.
Let's suppose now that f is not constant.

With y=t=0, we get f(0)=0; with z=t=0, we get f(xy)=f(x)f(y);
hence f(1)=1and, if x <>0, f(x)<>0 (because f(x)f(1/x)=1).

With x=0,y=t=1, we get f(-z)=f(z); hence f(x)=f(|x|)=f(root(|x|)^2>0
if x<>0.

With t=x,z=y, we get f(x^2+y^2)=(f(x)+f(y))^2.
(1)

By (1), f(x^2+y^2)>f(x^2)=f(x)^2 for y<>0; hence f
is increasing for x>0.

As f(n-1)+f(n+1)=2(f(n)+1), it follows, by induction,
that, for any integer n, f(n)=n^2. Hence, for any rationnal r=p/q, f(r)=f(p)/f(q)=r^2.

If, for some x>0, f(x)<x^2; taking for r a rationnal
number such as f(x)<r<x^2, we have f(r)=r^2<f(x)^2. Contradiction.

Same way, f(x)>x^2 cannot occur for x>0.

Conclusion : the solutions are the constants 0,1/2 and
the fonction f(x)=x^2.

--------------------------------------------------------------------------------------------------------------------------------------------
**Problem 6: Let T_1, T_2, ..., T_n be circles of radius 1 in the
plane, where n >= 3. Denote their centres by O_1, O_2, ..., O_n respectively.
Suppose that no line meets more than two of the circles. Prove that**
**sum_{1 <= i <= j <= n} 1 / (O_iO_j) <= (n-1)pi/4.**

**[JPE, 8/6/02]:** First, notice that if i,j,k are
distinct, the distance from O[j] to the line O[i]O[k] must be >2; hence
Ang(O[j]O[i]O[k])>=sin Ang(O[j]O[i]O[k]) > 2/O[i]O[j].

Let S[i] = sum(1/O[i]O[j], j=1..n, j<>i).

Suppose that U[1],..,U[n] is a permutation of O[1],...,O[n]
such asU[1]=O[i] and Ang(U[2]U[1]U[k]) increases with k.

We have

sum(1/U[1]U[j], j=2..(k-1)) < 1/2 Ang(U[2]U[1]U[k])
and

sum(1/U[1]U[j], j=(k+1)..n) < 1/2 Ang(U[k]U[1]U[n])
;

hence, for 2<=k<=n, S[i] -1/U[1]U[k] < 1/2 Ang(U[2]U[1]U[n])
;

if we add these inequalities, we get

(1) : S[i] < (n-1)/2/(n-2) Ang(U[2]U[1]U[n]) .

The half-lines starting from O[i] and tangents to the
circle (O[j],1)intercept on the circle (O[i],1) an arc with length 2 arcsin
1/O[i]O[j]. IfA[i,j] is the union of this arc and of his symetric wrtO[i],
the measure of A[i,j] is at least 4/O[i]O[j]; as the sets A[i,j], with
fixed i, cannot intersect, it follows that

(2) : S[i]<=Pi/2.

Suppose now, that O[1],...,O[p] are the vertices of the
convex hull ofO[1],...,O[n], ie O[p+1],..,O[n] lie inside this convex hull.

As the sum of the angles at O[1],..,O[p] of the convex
hull is (p-2) Pi, itfollows from (1) thatS[1]+...+S[p] < (n-1)(p-2)/(n-2)
Pi/2.

If follows from (2) that S[p+1]+...+S[n] <= (n-p)Pi/2
<(n-p)(n-1)/(n-2)Pi/2.

Hence S[1]+...+S[n] < (n-1) Pi/2 andsum(1/O[i]O[j],
1<=i<j<=n) < (n-1)Pi/4.

**Return to [Polya
Home Page] [Members]
[Problem Center]
[Inventory]
[Reserve Area]**