IMO'97 (Mar del Plata, Argentina) - Solutions

Problem 1

(a) Let ABC be a right-angled triangle whose vertices have integer coordinates and whose legs lie along edges of the squares with <A=90o, AB=m and AC=n. Let us consider the mxn rectangle ABCD as shown in the figure.

figure

For an arbitrary polygon P let us denote by S1(P) the total area of the black part of P and by S2(P) the total area of its white part.

When m and n are of the same parity the colouring of the rectangle ABCD is centrally symmetric about the midpoint of the hypotenuse BC. Hence S1(ABC) = S1(BCD) and S2(ABC) = S1(BCD). Therefore

f(m, n) = | S1(ABC) - S2(ABC) | = 1/2 | S1(ABCD) - S2(ABCD) |.

Hence f(m, n) = 0 for m, n both even and f(m, n) = 1/2 for m, n both odd.

(b) If m, n are both even or both odd the results follows from (a). Suppose now that m is odd and n is even. Consider a point L on AB such that AL = m -1 as shown below.

Since m - 1 is even we have f(m - 1, n) = 0, i.e., S1(ALC) = S2(ALC). Therefore

f(m, n) = | S1(ABC) - S2(ABC) | = | S1(LBC) - S2(LBC) |

=<Area LBC = n/2 =<1/2 max {m, n}

figure

(c) Let us compute f(2k + 1,2k). As in (b) we will consider a point L on AB such that AL = 2k. As f(2k, 2k) = 0 and S1(LBC) = S2(ALC) we have

f(2k + 1,2k) = | S1(LBC) - S2(LBC) |.

The area of the triangle LBC is k. Suppose without loss of generality that the diagonal LC is all black (see figure below). Then the white part of LBC consists of several triangles BLN2k, M2k-1L2k-1N2k-1, ... , M1L1N1, each of them being similar to BAC. Their total area is

expresion

expresion.

Therefore

expresion

and thus

expresion

This function takes arbitrarily large values.

figure

Problem 2

figure

Let us denote the diameters which are perpendicular bisectors of AB and AC by b and c respectively. Let us fix an orientation for arcs. Then the notation arcPQ defines a unique arc on the circle.

Let X, Y be the second intersections of the circle with the lines BV and CW respectively. Then the chord CY is the mirror image of the chord AU in c.

Thus arcYC = arcAU. Similarly arcXB = arcAU. Then arcXB = arcYC and hence the line segments BX and YC are symmetric with respect to the diameter d which passes through the midpoint of BY, with X being the mirror image of C and Y being the mirror image of B.

As the point T lies on the line d, the perpendicular bisector of both BY and CX, we have TB = TY and TC = TX.

Then AU = BX = BT + TX = BT + CT.

 

Problem 3

For any permutation pi= ( y1, y2, ... , yn ) of ( x1, x2, ... , xn ) denote by S(pi) the value of the sum y1 + 2y2 + ... + nyn. Let r = (n + 1)/2. It has to be shown that |S(pi)| =<r for some permutation pi.

Let pi0 be the identity permutation pi0 = ( x1, ... , xn ) and let ~pibe the reverse permutation ~pi= ( xn , ... , x1 ). If |S(pi0)| =<r or |S(~pi)| =<r, the claim is true. Assume for the sequel that |S(pi0)| > r and |S(~pi)| > r. Note that

S(pi0) + S(~pi) = ( x1 + 2x2 + ... + nxn ) + ( xn + 2xn-1 + ... + nx1 ) = (n + 1)( x1 + ... + xn ),

and hence | S(pi0) + S(~pi) | = n + 1 = 2r. Since each one of the numbers S(pi0) and S(~pi) exceeds r in absolute value, they must have opposite signs. Accordingly, one of them is grater than r and the other one is smaller than -r.

Starting from pi0, we are able to obtain any permutation by successive transpositions of neighbouring elements. In particular, there exists a chain of permutations pi0, pi1, ... , pim such that pim = ~piand, for each i in{0, ... , m-1}, the permutation     pii+1 arises from pii by interchanging two of its neighbouring terms.

This means that if pii = ( y1 , ... , yn) and pii+1 = ( z1 , ... , zn), then there is an index k in{1, ... , n - 1} such that

zk = yk+1 ,    zk+1 = yk ;       zj = yj     for jother thank, k + 1.

And since the numbers xi do not exceed r in absolute value,

| S(pii+1) - S(pii) | = | kzk + (k + 1)zk+1 - kyk (k + 1)yk+1 |
= | yk - yk+1 | =<| yk | + | yk+1 | =<2r.

This shows that the distance between any two successive numbers in the sequence S(pi0), S(pii) , ... , S(pim) is not greater than 2r.

Recall that the numbers S(pi0) and S(pim), regarded as points of the real line, lie putside the interval [-r, r], on distinct sides of it. It follows that at least one of the numbers S(pii) has to hit an interval. Thus we have S(pii) =<r for a certain pii, and the assertion is proved.

 

Problem 4

(a) Let n > 1 be an integer. Suppose that a silver n x n matrix A exists. Let x be a fixed element of {1, 2, ... , 2n -1} which does not appear on the diagonal of A. (Such an element exists, since there are only n elements on the diagonal but 2n - 1 elements in total.) The union of the ith row and the ith column we shall call it ith cross. The element x appears in each cross exactly once. If x is the (i , j)th entry of A, then it belongs to the ith cross and also to the jth cross. In this case we say that these crosses are x-linked. (For example, in the matrix A below the 1st and the 4th crosses are 6-linked.) This implies that all n crosses are partitioned into pairs of x-linked ones, and therefore n is even. But 1997 is an odd number.

(b) For n = 2

matrix A 2x2 = [ 1 2 \ 3 1 ]

is a silver matrix. For n = 4 we have already several of them, for example

matrix A 4x4 = [ 1 2 5 6 \ 3 1 7 5 \ 4 6 1 2 \ 7 4 3 1 ] , matrix B 4x4 = [ 1 2 4 5 \ 3 1 6 7 \ 7 5 1 3 \ 6 4 2 1 ]

The construction of A can be generalized. Suppose that an n x n silver matrix exists. Then 2n x 2n silver matrix D can be constructed as follows:

matrix D 2x2 = [ A B \ C A ]

where B is the n x n matrix obtained from A by adding 2n to each entry, and C is the matrix obtained from A by adding 2n to each entry, and C is the matrix obtained from B by replacing all its diagonal entries by 2n. This matrix will be again a silver matrix. To prove this let us consider the ith cross of D. Suppose that i =<n; the other case is similar. This cross is composed of the ith cross of A, the ith row of B and the ith column of C. The ith cross of A contains numbers {1, 2, ... , 2n -1}. The ith row of B and the ith column of C together contain the numbers {2n, 2n + 1 , ... , 4n - 1}.

 

Problem 5

Let a, b be a solution, let d be the greatest common divisor of a and b and let a = du, b = dv, with integers u, v being coprime, The given equation is equivalent to

(du)dv2 = (dv)u. (1)

Comparing the exponents dv2 and u in (1), we distinguish three cases.

Case 1. dv2 = u. Then (1) implies u = v. Since u, v are coprime, we get u = v = 1; and dv2 = u yields d = 1. Hence a = b = 1, which is a solution.

Case 2. dv2 > u. Rewriting (1) as

ddv2-u . udv2 = vu, (2)

we see that udv2 divides vu. Since u, v are coprime, u =1 and (2) becomes

ddv2-1 = v. (3)

Now, if d =1 then by (3) v = 1 and the inequality dv2 > u fails to hold. And for d >=2 we have

ddv2-1 >= 22v2-1 >= 22v-1 > v     for v = 1, 2, 3, ... ;

The last inequality is easily verified by induction on v. This contradicts (3) and shows that there are no solutions in this case.

Case 3. dv2 < u. (Hence u > d.) Rewriting (1) as

udv2 = du-dv2 . vu, (4)

We see that vu divides udv2. Since u, v are coprime, v = 1 and (4) becomes

ud = du-d. (5)

The exponentiation bases in (5) satisfy the inequality u > d; hence the exponents satisfy the opposite inequality d < u - d.

By (5), any prime divisor p is of d is also a divisor of u. Taking y, z to be the greatest exponents with py | u, pz | d, we obtain from (5) yd = z(u - d), which shows that y > z. Thus d divides u, so u = kd or a certain integer k. Note that k >=3 because u>2d. Substituting u = kd into (5), we get

k = dk-2. (6)

It follows that d cannot be 1. Therefore d >=2.

If k = 3, then by (6) d = 3, whence u = 9, a = 27, b = 3.
If k = 4, then by (6) d2 = 4, whence d = 2, u = 8, a = 16, b = 2.
If k >=5, then dk-2 >=2k-2 > k (by easy induction) and (6) fails.

Thus, the equation has three solutions: (a, b) = (1, 1), (27, 3) and (16, 2).

 

Problem 6

If n = 2k + 1 is any odd integer greater than 1, then every representation of n in the given form has a "1" as one of its summands. Deleting we obtain a representation of the number 2k. And conversely, by attaching a "1" to a representation of 2k we obtain a representation of 2k + 1. The correspondence that results is obviously bijective. The recursion formula follows:

f (2k + 1) = f (2k). (1)

Further, if n = 2k is any positive even integer, then every representation of n in the given form is one of the following two types: either it contains some terms equal to 1 or it does not contain such terms. In the first case we can delete one "1" to obtain a representation of 2k - 1: as before, we see that there is a bijection between the "first-type" representations of 2k and all representations of 2k - 1. In the case of a "second-type" representation (with no terms equal to 1), we can divide all its terms by 2 and obtain a representation of k; and also this correpondence is bijective. The second recursion formula follows:

f (2k) = f (2k - 1) + f (k). (2)

Both of these formulae hold for any integer k>=1. Obviously, f(1) = 1. Let us additionally define f(0) = 1; then the formula (1) holds for k = 0 as well. It follows from (1) and (2) that the function f is non-decreasing.

According to (1), the number f(2k - 1) in the formula (2) can be replaced by f(2k - 2), yielding the equation

f (2k) - f (2k - 2) = f (k)     for k = 1, 2, 3, ... .

Taking any integer n>=1 and summing these equations up over k = 1 , ... , n, we obtain the following formula:

f (2n) = f (0) + f (1) + ... + f(n)      for n = 1, 2, 3, ... . (3)

We pass the two-sided estimation of the sequence ( f(2n): n = 1, 2, 3, ... ). The upper estimate is easy: in the formula (3) all the summands are not greater than the last one. And since 2 = f(2) =< f(n) for n>=2, we get

f (2n) = 2 + ( f (2) + ... + f(n) ) =< 2 + (n - 1) f(n)

=< f(n) + (n - 1) f(n) = nf(n)      for n = 2, 3, 4, ... .

Consequently,

f(2n) =< 2n-1 . f(2n-1) =< 2n-1 . 2n-2 . f(2n-2) =< 2n-1 . 2n-2 . 2n-3 . f(2n-3)

=< ... =< 2(n-1) + (n -2) + ... + 1 . f(2) = 2n (n-1)/2 . 2.

And since 2n (n-1)/2 . 2 < 2n2/2 for n>=3, the upper estimate results.

To work out the lower estimate, we first show that

f (b + 1) - f(b) >= f(a + 1) - f(a) (4)

whenever b >= a >= 0 are integers of the same party. Indeed: if a and b are both even, then in view of (1) we have zeros on both sides of (4); and if a and b are odd, then by (2) we get f(b + 1) - f(b) = f( (b + 1)/2 ), f(a + 1) - f(a) = f( (a + 1)/2 ) and the inequality in (4) holds because the function f is non-decreasing.

Let us take any integers r >= k >= 1, r even, and substitute subsequently in (4) the numbers a = r - j, b = r + j for j = 0, ... , k - 1. Then add the inequalities that result, to obtain

f (r + k) - f(r) >= f(r + 1) - f(r - k + 1).

Since r is even, we have f(r + 1) = f(r), and hence

f (r + k) + f(r - k + 1) >= 2 f(r)      for k = 1, ... , r..

Summing these inequalities up over k = 1 , ... , r we get

f(1) + f(2) + ... + f(2r)>=2r f(r).

In view of (3) the sum on the left-hand side is equal to f(4r) - 1. Thus

f(4r) >= 2r f(r) + 1 > 2r f(r)      for every integer r>=2.

Taking r = 2m-2 we hence obtain

f (2m) > 2m-1 f (2m-2). (5)

To ensure that r = 2m-2 is even, m ought to be an integer greater than 2; note, however, that (5) is also true for m = 2.

Finally, let n be any integer greater than 1. If l is a positive integer such that 2l =< n, then applying the inequality (5) for m = n, n-1, ... , n - 2l + 2 we get

f (2n) > 2n-1 . f (2n-2) > 2n-1 . 2n-3 . f (2n-4) > 2n-1 . 2n-3 . 2n-5 . f (2n-6)

> ... > 2(n-1) + (n -3) + ... + (n - 2l + 1) . f (2n-2l) = 2l (n - l) . f (2n - 2l).

Now, if n is even, take l = n/2; and if n is odd, take l = (n - 1)/2. The resulting inequalities are:

f(2n) > 2n2/4 . f(20) = 2n2/4      for n even,

f(2n) > 2(n2 - 1)/4 . f(21) = 2(n2 - 1)/4 . 2 > 2n2/4      for n odd.

We have obtained the required lower estimate for every integer n >=2. (It is also valid for n = 1, as can be verified directly.)