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]