# IMO 2004 ShortList Problems and Solutions

Algebra
A1. Let n 3 be an integer and t1 ; t2 ; : : : ; tn positive real numbers such that n2 + 1 > (t1 + t2 + + tn ) 1 1 + + t1 t2 + 1 tn : i<j<k n.

Show that ti ; t

j ; tk are the side lengths of a triangle for all i; j; k with 1 Solution. By symmetry, it su? ces to show that t1 < t2 + t3 . One has
n n X X1 X =n+ ti t i=1 i=1 i 1 i<j

n

ti tj + tj ti + 1 (t2 + t3 ) + t1 X ti tj + tj ti :

= n + t1

1 1 + t2 t3

1 i<j n (i;j)6=(1;2);(1;3)

By the AM– GM inequality, p ti tj 2 ; t2 + t3 2 t2 t3 ; and + 2 for all i; j. tj ti t2 t3 p Thus, setting a = t1 = t2 t3 > 0 and using the hypothesis, we obtain p n n X X1 t1 t2 t3 n 2 2 ti n +1> n + 2p +2 +2 2 = 2a + + n2 t t1 2 a t2 t3 i=1 i=1 i 1 1 + t2 t3 p

4:

p p Hence 2a + 2=a 5 < 0, which implies 1=2 < a = t1 = t2p < 2. So t1 < 2 t2 t3 , and one t3 more application of the AM– GM inequality yields t1 < 2 t2 t3 t2 + t3 , as needed. Comment. It is not hard to determine the greatest number f (n) such that, for P P positive t1 ; : : : ; tn , the inequality n ti n 1=ti < f (n) implies that each three of the i=1 i=1 p ti ’ are the side lengths of a triangle. The answer is f (n) = (n + 10 3)2 , and the proof s is fairly standard. A2. An in…nite sequence a0 ; a1 ; a2 ; : : : of real numbers satis…es the condition an = jan+1 an+2 j for every n 0,

with a0 and a1 positive and distinct. Can this sequence be bounded? First solution. The answer is no; such a sequence is unbounded. All terms of (an ) are nonnegative; note also that no two consecutive terms of fan g are equal. Otherwise, if an = an+1 = c for some n, then an 1 = 0, an 2 = an 3 = c. Proceeding backwards in the same fashion, we obtain that either a0 and a1 are equal (to c), or one of them is 0, contrary to the hypothesis. Now we see that an > 0 for all n. 1

By de…nition, an+2 = an+1 + an or an+2 = an+1 an for n = 0; 1; 2; : : : ,

according as an+2 > an+1 or an+2 < an+1 . If the …rst recursion holds for all su? ciently large n, the sequence is clearly unbounded. So assume there are in…nitely many occurrences of the second recursion, the one with minus sign. These occurrences must be “isolated” because an+2 = an+1 an and an+3 = an+2 an+1 imply an+3 = an < 0, , which is impossible. Consider two consecutive occurrences of the minus sign recursion: ap+1 = ap ap 1 and ap+k+1 = ap+k ap+k 1 . We have k 2 by the remark above. Also, ap > ap+1 ; ap+1 < ap+2 < < ap+k
1

< ap+k ;

ap+k > ap+k+1 :

Let ap = , ap+1 = . By easy induction, ap+j = Fj 1 + Fj for j = 1; : : : ; k, where F0 = 0, F1 = 1, Fi+2 = Fi+1 + Fi . In particular, ap+k = Fk 1 + Fk , and ap+k+1 = ap+k ( Fk = ; ap+k
3 1

= (Fk
2

1

+ Fk )

(Fk

2

+ Fk

1

)

+ Fk

; if k 3, if k = 2. p, so there

In each case, ap+k+1 . It follows easily from here that an ap+1 for each n is a positive constant C such that an C for all n. Then, …nally ap+k = Fk
1

+ Fk

F1 + F2 =

+

+ C;

implying that (an ) is unbounded. Second solution. Since an+1 = an + an 1 for an+1 > an and an+1 = an an 1 for an+1 < an , we observe that an < an 1 implies an+1 > an 1 . Hence the sequence (bm ) obtained from (an ) by removing all terms an with an 1 > an < an+1 , is strictly increasing. So the result clearly follows from the observation that bm+1 bm bm bm 1 for all m 2. To prove this, let bm+1 = an+2 , so that an+2 > an+1 . If an+1 > an , we have bm = an+1 and bm 1 an 1 (since either bm 1 = an 1 or bm 1 = an > an 1 ). Then bm+1 bm = an+2 an+1 = an = an+1 an
1 1

= bm an
1

an

1

bm

bm 1 :
1

Likewise, if an+1 < an , we have bm = an and bm bm 1 = an 2 > an 1 ). In this case, bm+1 bm = an+2 an = an+1 = an an

(since either bm an bm

= an

1

or

1

= bm

1

bm 1 :

Third solution. It su? ces to prove that fan g is bounded away from 0 by a positive constant C (see the end of the …rst solution). Notice that: If an+1 < an for some n 2 2, then an+1 = an 2 . (1)

Indeed, an+1 < an means that an+1 = an an 1 ; and since there are no consecutive occurrences of the minus sign recursion, we have an = an 1 + an 2 . Hence an+1 = an 2 . Now, a constant C > 0 with the stated property clearly exists if an+1 > an for all n 2. Otherwise choose n 2 so that an+1 < an , and let an 2 = A. We claim that ak A for all k n; this is enough to complete the solution. The claim holds for k = n; n + 1; n + 2. This is because an+1 = an 2 = A by (1); also, an+1 < an implies an = an 1 + an 2 > A and an+2 = an+1 + an = an 2 + an > A. Assume by contradiction that ak < A for some k n, and let k be the least index with this property. Then k n + 3 and ak 1 A > ak by the minimum choice of k. But then, in view of (1), ak 3 = ak < A. Since k 3 n, this contradicts the minimality of k. Comment by the proposer. The following statements are equivalent for a sequence a0 ; a1 ; : : : ; an ; : : : of real numbers satisfying an = jan+1 an+2 j for n 0: i) the sequence is bounded; ii) the function f de…ned by f (n; k) = an ak (an ak ), for n; k 0, is identically zero; iii) the sequence is of the form : : : ; 0; a; a; 0; a; a; 0; a; a; : : : with a 0. A3. Does there exist a function s : Q ! f 1; 1g such that if x and y are distinct rational numbers satisfying xy = 1 or x + y 2 f0; 1g, then s(x)s(y) = 1? Justify your answer. Solution. Such a function exists (and is unique up to sign; see the comment below). Let x = a=b be a positive rational; here a; b are coprime positive integers. Consider the sequence of consecutive remainders given by the Euclidean algorithm for the ordered pair (a; b). If (u mod v) denotes the least nonnegative remainder of u modulo v, this sequence can be written as r0 = a; r1 = b; r2 = (a mod b); : : : ; ri+1 = (ri
1

mod ri ); : : : ; rn = 1; rn+1 = 0: (1)

The index n = n(x) of the last nonzero remainder rn = 1 is uniquely determined by x, so t(x) = ( 1)n(x) is a well-de…ned function from the positive rationals into f 1; 1g. Now de…ne s : Q ! f 1; 1g by 8 >s(x) = t(x) for x 2 Q, x > 0; < s(x) = s(x) = t( x) for x 2 Q, x < 0; > : s(0) = 1: We prove that s has the desired properties. Let x and y be distinct rational numbers. If x + y = 0, let x > 0 and y < 0 (x and y are nonzero). Then, by the de…nition, s(x) = t(x), s(y) = t( y) = t(x), hence s(x)s(y) = 1. If xy = 1 then x and y are of the same sign and neither equals 1 or 1. Suppose …rst that x = a=b > 0, y = b=a > 0, with a; b coprime positive integers; one may also assume that a > b. The Euclidean algorithm for the ordered pair (a; b) starts a; b; (a mod b); : : : . On the other hand, the algorithm for the pair (b; a) gives b; a; b; (a mod b); : : : , because 3

a > b implies r2 = (b mod a) = b. Each term in (1) depends only on the previous two, so the sequence for x has length by 1 less than the sequence for y, that is, n(y) = n(x) + 1. Hence t(y) = t(x), and so s(y) = s(x), as needed. Now the case of negative x; y follows from the de…nition. If x + y = 1, then at least one of x; y is positive and neither is 1=2. Assuming that x = a=b > 0, with a; b positive and coprime, we have y = (b a)=b. Let y < 0; then s(y) = t( y) = t((a b)=b). For the pairs (a; b) and (a b; b), the respective sequences (1) are a; b; (a mod b); : : : and a b; b; (a b mod b); : : : . But a > b clearly implies (a b mod b) = (a mod b), so the two sequences coincide from the second term on. Hence they have the same length. Thus t(a=b) = t((a b)=b) and s(x)s(y) = 1. If y > 0, one may suppose that 0 < x < 1=2 < y < 1; note that in this case 2a < b. Since a < b and b a < b, the sequences (1) for (a; b) and (b a; b) are a; b; a; (b mod a); : : : and b a; b; b a; (b mod b a); : : : . Observe now that (b mod b a) = a: indeed, a is congruent to b modulo b a, and a is less than b a in view of 2a < b. So in the last sequence we have r3 = a, and the next term is r4 = (b a mod a). But if b > a, then clearly (b a mod a) = (b mod a). Thus the sequence for y is b a; b; b a; a; (b mod a); : : : , and it follows that n(y) = n(x) + 1. Hence s(x)s(y) = 1, and the proof is complete. Comment. The construction may seem unexpected only at …rst glance. Assume that s is a function with the stated properties. Let x = a=b > 1, where a; b are coprime positive integers, a > b. Since x 6= 1; 1=2, we have s(x 1) = s(1 x) = s(x); that is, subtracting 1 does not change s(x) as long as x > 1. If x is not an integer, there is a unique positive integer q such that x q 2 (0; 1). This is the quotient from the …rst step a = bq + r of the Euclidean algorithm for the pair (a; b). So s(x) = s(r=b) = s(b=r), meaning that the length of the Euclidean algorithm (more exactly, its parity) determines uniquely the value of s(x). Not only this observation provides insight into how a function with the stated properties can be constructed. Essentially speaking, the argument above is the inductive step of an easy proof showing that if s is any function satisfying the given conditions, then s(x) = ( 1)n(x) s(0) for each positive rational x. So the value of s(0) determines s uniquely. A4. Find all polynomials P (x) with real coe? cients which satisfy the equality P (a b) + P (b c) + P (c a) = 2P (a + b + c)

for all triples a; b; c of real numbers such that ab + bc + ca = 0. First solution. The solutions are the polynomials P (x) = x2 + x4 , with ; 2 R. Let P (x) satisfy the given equation. If a = b = 0 then ab + bc + ca = 0 for each c 2 R, so we obtain P (0 0) + P (0 c) + P (c 0) = 2P (0 + 0 + c), or P (0) + P ( c) = P (c) for all real c. Setting c = 0 gives P (0) = 0, so P ( c) = P (c) for all c 2 R. Hence P is even and must have the form P (x) = an x2n + an 1 x2n 2 + + a1 x2 , with a1 ; : : : ; an 2 R. Now we prove that the degree 2n of P is at most 4.

4

For any real numbers u and v, the triple a = uv; b = (1 u)v; c = (u2 u)v u)v = 0. The equation yields u + 1)v for all u; v 2 R.

satis…es ab + bc + ca = (a + b)c + ab = v(u2 P (2u 1)v + P (1 u2 )v + P (u2

u)v + uv(1

2u)v = 2P (u2

Let us …x u and regard this as a polynomial identity with variable v. Equating the leading coe? cients of both sides, we obtain (2u 1)2n + (1 u2 )2n + (u2 2u)2n = 2(u2 u + 1)2n for all u 2 R.

Now set u = 2 to obtain 52n + 32n + 82n = 2 72n , implying 82n < 2 72n . However, one has 82n > 2 72n already for n = 3 (82 3 > 256000 > 235298 = 2 72 3 ), and still more for larger n. Hence n 2, meaning that P (x) = x2 + x4 for some ; 2 R. Every such polynomial satis…es the given equation. To verify this, observe that any linear combination of solutions is a solution. So it su? ces to check x2 and x4 . For x2 , this follows from the identity (a b)2 + (b c)2 + (c a)2 2(a + b + c)2 = 6(ab + bc + ca). For x4 , let x = a b, y = b c, z = c a and note that by checking x2 we just proved x2 + y 2 + z 2 = 2(a + b + c)2 . Then, since x + y + z = 0, the desired equality is obtained as follows: 1 2 (x + y 2 + z 2 ) = (a + b + c)2 ; 2 (xy)2 + (yz)2 + (zx)2 = (xy + yz + zx)2 2xyz(x + y + z) = (a + b + c)4 ; xy + yz + zx = x4 + y 4 + z 4 = (x2 + y 2 + z 2 )2 2 (xy)2 + (yz)2 + (zx)2 = 2(a + b + c)4 :

Second solution. As in the …rst solution, we …rst prove that P (0) = 0 and that P is even. Hence there is a polynomial Q with real coe? cients such that P (x) = Q(x2 ), x 2 R. The equation becomes Q (a b)2 + Q (b c)2 + Q (c a)2 = 2Q (a + b + c)2 for a; b; c 2 R with ab + bc + ca = 0. Let ab + bc + ca = 0, and denote x = a b, y = b c, z = c a. Since x + y + z = 0 and (a + b + c)2 = a2 + b2 + c2 , one has x2 + y 2 + z 2 = 2(a2 + b2 + c2 ) 2(ab + bc + ca) = 2(a2 + b2 + c2 ) = 2(a + b + c)2 ; 1 1 (a + b + c)2 = (x2 + y 2 + z 2 ) = (x2 + y 2 + ( x y)2 ) = x2 + xy + y 2 : 2 2 The equation gives Q x2 + Q y 2 + Q (x + y)2 = 2Q x2 + xy + y 2 . Now set y = x: 2Q(x2 ) + Q(4x2 ) = 2Q(3x2 ): (1)

We obtained (1) for values of x such that there are a; b; c 2 R satisfying x = a b, x = b c and ab + bc + ca = 0. Butp easy computation shows that such a triple a; b; c an p p exists for each real x: a = x + jxj= 3, b = jxj= 3, c = jxj= 3 x. So (1) is true for 5

every x 2 R. It implies that 2Q(x) + Q(4x) = 2Q(3x) for all nonnegative x, of which there are in…nitely many. Because Q is a polynomial, we conclude that 2Q(x) + Q(4x) = 2Q(3x) for all x 2 R. (2)

Now let Q(x) = bn xn + bn 1 xn 1 + + b1 x + b0 . Since (2) is a polynomial identity, comparing the coe? cients of both sides leads to 2bi + 4i bi = 2 3i bi for i = 0; 1; : : : ; n. Therefore (4i 2 3i + 2)bi = 0 for all i = 0; 1; : : : ; n. And because 4i 2 3i + 2 > 0 if i > 2, all coe? cients bi with i > 2 are zeros. We also know that b0 = 0 in view of Q(0) = P (0) = 0, so Q(x) = x + x2 for some real ; . Consequently P (x) = x2 + x4 , and only the veri…cation remains. Third solution. For every real x the triple (a; b; c) = (6x; 3x; 2x) satis…es the condition ab + bc + ca = 0. For this triple the equation gives P (3x) + P (5x) + P ( 8x) = 2P (7x) If P (x) = P ai xi , this implies 3i + 5i + ( 8)i 2 7i ai = 0 for all i = 0; 1; 2; : : : . for all x 2 R.

The expression in the brackets is negative for odd i, and positive for i = 0 and for all even i 6. Only for i = 2 and i = 4 this expression is 0. It follows that P (x) = x2 + x4 , with ; 2 R. As before, only the veri…cation remains. A5. Let a; b; c > 0 and ab + bc + ca = 1. Prove the inequality r r r 1 3 1 3 1 3 1 + 6b + + 6c + + 6a : b c abc a
1 (u 3

3 1 + v + w) (u3 + v 3 + w3 ), First solution. By the power mean inequality 3 the left-hand side does not exceed r r 3 3 1 1 1 3 3 ab + bc + ca p + 6b + + 6c + + 6a = p + 6(a + b + c): (1) 3 3 b c abc 3 a 3

q

The condition ab + bc + ca = 1 enables us to write a+b = Hence 4 ab + bc + ca 1 +6(a+b+c) = +3[(a+b)+(b+c)+(c+a)] = abc abc 3 (ab)2 + (bc)2 + (ca)2 : abc 1 c ab = ab (ab)2 ; abc b+c = 1 a bc = bc (bc)2 ; abc c+a = 1 b ca = ca (ca)2 : abc

Now, we have 3 (ab)2 + (bc)2 + (ca)2 (ab + bc + ca)2 = 1 by the well-known inequality 3(u2 + v 2 + w2 ) (u + v + w)2 . Hence an upper bound for the right-hand side of (1) 6

p p is 3= 3 abc. So it su? ces to check 3= 3 abc 1=(abc), which is equivalent to (abc)2 This follows from the AM– GM inequality, in view of ab + bc + ca = 1 again: ab + bc + ca (abc) = (ab)(bc)(ca) = 3 p Clearly, equality occurs if and only if a = b = c = 1= 3.
2 3

1=27.

1 3

3

=

1 : 27

Second solution. Given the conditions a; b; c > 0 and ab + bc + ca = 1, the following more general result holds true for all t1 ; t2 ; t3 > 0: 3abc(t1 + t2 + t3 ) 2 + at3 + bt3 + ct3 : 1 2 3 3 r
3

(2)

The original inequality follows from (2) by setting r r 13 1 13 1 t1 = + 6b; t2 = + 6c; 3 a 3 b 1 1 + bc + at3 ; 1 9 3

1 t3 = 3

1 + 6a: c

In turn, (2) is obtained by adding up the three inequalities 3abct1 3abct2 1 1 + ca + bt3 ; 2 9 3 3abct3 1 1 + ab + ct3 : 3 9 3

By symmetry, it su? ces to prove the …rst one of them. Since 1 bc = a(b + c), the AM– GM inequality gives r t3 at3 t3 3 1 1 (1 bc) + =a b+c+ 3a bc 1 = 3at1 : bc bc bc Hence 3abct1 bc(1 pletes the proof: 3abct1 bc) + at3 , and one more application of the AM– GM inequality com1 2 3 1 bc + bc + at3 1 3

bc(1

bc) + at3 = bc 1 bc)
2

bc + ( 2 3 2

1 1 1 + bc + at3 = + bc + at3 : 1 1 3 9 3

A6. Find all functions f : R ! R satisfying the equation f x2 + y 2 + 2f (xy) = f (x + y)
2

for all x; y 2 R. 4t

Solution. We start with the substitution z = x + y, t = xy. Observe that z 2 and set g(t) = 2f (t) 2t to obtain the equivalent f z 2 + g(t) = f (z)
2

for all t; z 2 R with z 2 7

4t.

(1)

Note that if z 2 4t then the corresponding (real) x; y exist (the roots of the quadratic 2 z + t); therefore (1) is indeed equivalent to the original equation. Suppose that f satis…es (1) and let g(0) = c. Equation (1) with t = 0 gives f (z 2 + c) = f (z) An immediate consequence is f (x) 0 for x c. (3) In particular, (3) shows that c 0. If g is a constant function, then g(t) = g(0) = c for all t, so f (t) = t + c=2. Now (2) yields c = 0, hence f (x) = x, which is a solution. If g is not constant, the key step is to prove that (in contrast) f is constant from some point onwards. It su? ces to …nd positive and M such that each number in the interval [ ; 2 ] is expressible in the form g(u) g(v) with u; v M . Indeed, suppose this is true p and take y > x 2 M such that y 2 x2 2 [ ; 2 ]. By assumption, y 2 x2 = g(u) g(v) for some u; v M , which is the same as x2 + g(u) = y 2 + g(v). Since x2 4M 4u, 2 2 y 2 4M 4v, (1) leads to f (x) = f (y) . Now notice that M can be increased from the very beginning (if needed) to ensure additionally M c2 =4. Then x; y c, and (3) p implies f (x) = f (y). Hence the function f ( x) is periodic on [4M; +1), with period p any number in the interval [ ; 2 ]. It p an easy conclusion that then f ( x) is constant is on [4M; +1), and f is constant on [2 M ; +1), as claimed. To …nd the necessary and M , recall that pis not constant and choose a; b such that g p p g(a) g(b) = d > 0. Take u maxf2 jaj; 2 jbj; cg = K and let v = u2 + d. Then u2 + g(a) = v 2 + g(b), u2 4a, v 2 4b and v > u c, so (1) and (3) yield f (u) = f (v). But if so, g(u) g(v) = 2[f (u) u] 2[f (v) v] = 2(v u), and g(u) g(v) = 2(v u) = 2(v 2 u2 ) 2(g(a) g(b)) 2d p = = = h(u): v+u v+u u + u2 + d
2

for all z 2 R.

(2)

Now let h(K) = 2 , and let L > K be such that h(L) = (such an L exists, because the range of h on [K; +1) is (0; h(K)]). For each T 2 [ ; 2 ] there is a u 2 [K;p such L] that h(u) = u, and hence T can be written as g(u) g(v) with K u <p = u2 + d v p p for some u 2 [K; L]. Since u2 + d < u + d, one may choose M = L + d to ensure u; v M . Thus the desired and M do exist. So there are N > 0 and 2 R such that f (x) = for x N . Taking su? ciently large z in (2) gives = 2 , so = 0 or = 1. We also see from (2) that f ( z) = f (z) for all z. Hence jf j = 1 on ( 1; N ]. Then g(t) = 2f (t) 2t 2 2t for t N, implying that g(t) assumes arbitrarily large values on ( 1; N ]. So for every z 2 R one can …nd t N < 0 such that z 2 + g(t) N . Then f (z 2 + g(t)) = ; on the other hand 2 2 f (z 2 + g(t)) = f (z) by (1), implying f (z) = = 2 . Hence jf (z)j = for all z 2 R. If = 0, we obtain f (x) 0, which is a solution. Let = 1; then c = 2f (0) = 2 (because c 0). Suppose that f (t) = 1 for some t. No z 2 R can satisfy z 2 = t g(t) 4t, 2 or else (1) would imply f (z) = f (z 2 + g(t)) = f (t) = 1, a contradiction. Hence either t g(t) < 0, or 0 t g(t) < 4t. Now, g(t) = 2 2t, and we infer that either 8

t < 2=3 or t > 2. The second case is impossible, because (3) and c = 2 show that f (x) = 1 for x 2. Therefore f takes on value 1 on a subset of the interval ( 1; 2=3). Conversely, it is not hard to verify that for every set X ( 1; 2=3) the function f de…ned by f (x) = 1 for x 2 X and f (x) = 1 for x 62 X is a solution. Summarizing, the solutions are f (x) = x, f (x) 0 and the in…nitely many functions just de…ned. A7. Let a1 ; a2 ; : : : ; an be positive real numbers, n > 1. Denote by gn their geometric mean, and by A1 ; A2 ; : : : ; An the sequence of arithmetic means de…ned by a1 + a2 + + ak Ak = ; k = 1; 2; : : : ; n: k Let Gn be the geometric mean of A1 ; A2 ; : : : ; An . Prove the inequality r Gn gn nn + n+1 An G n and establish the cases of equality. Solution. Observe that, for each k = 1; 2; : : : ; n, ak kAk = Ak (k 1)Ak Ak
1

=k

(k

1)

Ak 1 ; Ak

here we let A0 = 0 for convenience. The key step is reformulating the problem in terms of the variables Ak 1 ; k = 2; : : : ; n: x1 = 1; xk = Ak We have v v s r u n u n q u Y ak uY A 1 A2 : : : A n gn n2 n Gn n2 n n 2 = = =t = t [k (k 1)xk ]: x2 x3 xn 1 ; n n An An Gn Ak k=1 k=1 Therefore nn r Gn gn 2 + = n n x2 x2 3 An G n q v u n uY n xn 1 + t [k n
k=1

(k

1)xk ]:

(1)

We can now complete the solution in a number of di¤erent ways. First way. Apply the AM– GM inequality to both summands in the left-hand side of (1), recalling that x1 = 1. For the …rst summand, this yields " # q n q X 1 n(n + 1) 2 n2 n(n+1)=2 n n n x2 x2 xn 1 = n x1 x2 x2 xn 1 x1 + (k 1)xk 3 3 n n 2 k=2 n+1 1 X = + (k 2 n k=1
n

1)xk ;

9

with equality if and only if xk = 1, k = 1; 2; : : : ; n. Also, v u n n X uY n+1 n t [k (k 1)xk ] 1 [k (k 1)xk ] = n k=1 2 k=1

1X (k n k=1
n

1)xk ;

with equality if and only if k (k 1)xk = 1 for each k, that is, xk = 1 for k = 1; 2; : : : ; n. Combining these results, we conclude that r gn Gn + n + 1; nn An G n with equality if and only if a1 = a2 = = an . Second way. We apply H?lder’ inequality s v u n+1 n+1 Xp uX n t n 1j 2j : : : nj
j=1 j=1 1j kj k;n+1

1j

n+1 X j=1

2j

n+1 X j=1

nj :

(2)

More precisely, let

=1 for j = 1; 2; : : : ; n + 1; q = n xk 1 ; for k = 2; : : : ; n and j = 1; 2; : : : ; n; k =k (k 1)xk ; for k = 2; : : : ; n:

The right-hand side of (2) is the same as the left-hand side of (1). Also, q n+1 n+1 X X n xk 1 + k (k 1)xk ; k = 2; : : : ; n: 1j = n + 1; kj = n k
j=1 j=1

To …nish the proof, it remains to observe that for k = 1; 2; : : : ; n, q q n n xk 1 + k (k 1)xk = n n xn k+1 xk 1 + k (k 1)xk 1 k k (n k + 1)x1 + (k 1)xk + k The conclusion about equality is the same: a1 = a2 = = an .

(k

1)xk = n + 1:

Comment by the proposer. Yet another way (not a short one) to establish (1) is using multivariable calculus techniques. Generally speaking, calculus approaches to the problem do not seem to yield an immediate proof. The idea of an appropriate variable change is not straightforward, so examining special cases deserves attention. The case n = 2 can be handled directly and does not provide insight into the general setting. However, n = 3 is much more signi…cant. The inequality reduces to s s 9a(a + b) 6bc 39 + 3 4 2 2(a + b + c) (a + b)(a + b + c) for all positive a; b; c. This is already a challenging problem. 10

Combinatorics
C1. There are 10001 students at an university. Some students join together to form several clubs (a student may belong to di¤erent clubs). Some clubs join together to form several societies (a club may belong to di¤erent societies). There are a total of k societies. Suppose that the following conditions hold: (i) Each pair of students are in exactly one club. (ii) For each student and each society, the student is in exactly one club of the society. (iii) Each club has an odd number of students. In addition, a club with 2m + 1 students (m is a positive integer) is in exactly m societies. Find all possible values of k. Solution. Let us write n instead of 10001 for the sake of clarity. We count in two ways the ordered triples (a; C; S), where a is a student, C a club and S a society such that a 2 C and C 2 S. Such pairs will be called acceptable. Fix a student a and a society S. By (ii), there is a unique club C such that (a; C; S) is an acceptable triple. Since the ordered pair (a; S) can be chosen in nk ways, there are nk acceptable triples. Fix a club C with jCj members. By (iii), C is in exactly (jCj 1)=2 societies, so there are jCj(jCj 1)=2 acceptable triples with second coordinate C. So if C is the set of all P clubs, we have C2C jCj(jCj 1)=2 acceptable triples. Thus our double counting gives nk = P P jCj Now, (i) implies = n , that is, 1)=2 = n(n 1)=2. It folC2C 2 C2C jCj(jCj 2 lows that nk = n(n 1)=2, so k = (n 1)=2 is the only possible value of k. The answer for n = 10001 is 5000. C2. Let n and k be positive integers. There are given n circles in the plane. Every two of them intersect at two distinct points, and all points of intersection they determine are pairwise distinct. Each intersection point must be colored with one of n distinct colors so that each color is used at least once and exactly k distinct colors occur on each circle. Find all values of n 2 and k for which such a coloring is possible. Solution. The answer is: 2 k n 3 and 3 k n. We label 1 through n the n circles as well as the n colors. For any coloring of the intersection points, let F (i; j) be the set of colors of the common points of circles i and j (it may have one or two elements). Clearly k n for each n; also, k 2 for n 2 (if k = 1, all intersection points are of the same color, while the number of colors is n 2). 11 X jCj(jCj
C2C

1)

2

:

We …rst show that k = 2 is an acceptable value only for n = 2 and n = 3. If n = 2, setting F (1; 2) = f1; 2g gives an acceptable coloring. Let there exist an acceptable coloring for k = 2 and a certain n 3. To each circle assign the two-element set of colors present on it. Each of the n colors occurs in at least two of these two-element sets (each colored point lies on two circles). Hence each color belongs to exactly two sets, that is, it occurs on exactly two circles. For i = 2; : : : ; n, choose one intersection point of the circles 1 and i. These n 1 points have pairwise distinct colors, or else some color would occur on more than two circles. Therefore n 1 2, and since n 3, we obtain n = 3. An acceptable coloring for k = 2 and n = 3 is F (1; 2) = f3g, F (2; 3) = f1g, F (3; 1) = f2g. Now we show that there is an acceptable coloring whenever 3 k n. It is convenient to prove a slightly stronger statement by induction on k: For n k 3 there exists an acceptable coloring such that color i occurs on circle i for each i = 1; : : : ; n. The base case is to show that k = 3 is acceptable for all n 3. An example for n = 3 is F (1; 2) = f1; 2g, F (2; 3) = f2; 3g, F (3; 1) = f3; 1g. If n > 3, set F (1; 2) = f1; 2g; F (i; i + 1) = fig for 1 < i < n 1; F (n and F (i; j) = fng for the remaining pairs (i; j), 1 1; n) = fn i < j n. 2; n 1g

This coloring is acceptable: colors 1; 2; n occur on circles 1 and 2; colors i 1; i; n occur on circle i for 2 < i < n 1; colors n 2; n 1; n occur on circles n 1 and n. In addition, color i occurs on circle i for each i. Assume that the claim is true for some k 3 and let n k + 1. Since n 1 k 3, there is a coloring for the circles 1; : : : ; n 1 and the colors 1; : : : ; n 1 such that exactly k colors occur on each circle, and circle i contains color i, i = 1; : : : ; n 1. We now color the intersection points of circle n with the remaining circles. For each i = 1; : : : ; n 1, choose one of the two common points of circles i and n and color it with color n. Thus exactly k + 1 colors occur on circle i for each i = 1; : : : ; n 1; note that colors i and n are present there. Next, for i = 1; : : : ; k, color with color i the second common point of circles i and n (this makes sense, because n k + 1). There are exactly k + 1 colors on circle n now, namely colors 1; : : : ; k and n. No new color was added to any of the …rst n 1 circles. Finally, let us color with color n all remaining intersection points of circle n with the …rst n 1 circles. Color n was present on each circle before this last step, hence no change occurs with the set of colors on each circle. The coloring obtained meets all requirements, and the induction is complete. C3. The following operation is allowed on a …nite graph: Choose an arbitrary cycle of length 4 (if there is any), choose an arbitrary edge in that cycle, and delete it from the graph. For a …xed integer n 4, …nd the least number of edges of a graph that can be obtained by repeated applications of this operation from the complete graph on n vertices (where each pair of vertices are joined by an edge). Solution. The least number of edges of such a graph is n. For brevity, we call admissible each graph that can be obtained from the complete graph Kn on n vertices by applying the operation from the problem statement. Also, a 12

graph is called: connected, if every two vertices in it are joined by a path; bipartite, if its vertices can be partitioned into two sets V1 and V2 such that each edge connects a vertex in V1 to a vertex in V2 . Suppose the operation is performed on a graph G, removing its edge AB from the 4-cycle ABCD in G. Denote the new graph by H. We claim that: (i) If G is connected, then so is H. (ii) If G is not bipartite, then neither is H. For (i), suppose that two vertices X; Y are joined by a path in G. If does not contain the removed edge AB, then it also joins X and Y in H. Otherwise consider the path in H obtained from by replacing AB with the remaining three edges AC, CD and DB of the 4-cycle ABCD. The new path joins X and Y in H, and (i) follows. To prove (ii), assume on the contrary that the vertices of H can be partitioned into two sets V1 and V2 such that each edge connects a vertex in V1 to a vertex in V2 . Since the edges BC, CD and DA are still present in H, we see that A; C must belong to one of V1 and V2 , and B; D to the other. But then the same partition V1 ; V2 of vertices would make G bipartite, which is a contradiction. The complete graph Kn is connected. Also, Kn is not bipartite (because, for instance, it contains triangles). Hence any admissible graph H is connected and not bipartite. In particular, H must contain a cycle, because a graph without cycles is bipartite. Now it follows easily that an admissible graph has at least n edges. Indeed, a connected graph on n vertices must have at least n 1 edges. On the other hand, a connected graph on n vertices with exactly n 1 edges is a tree, and hence contains no cycle. So a lower bound for the number of edges is n. We now show that, for n 4, the operation can actually produce a graph with exactly n edges, starting from Kn . Consider the graph on n 4 vertices A1 ; : : : ; An 3 ; X; Y; Z in which Z is joined by an edge to each of the remaining vertices, and also X and Y are joined by an edge. This graph can be obtained from Kn by repeated applications of the operation in the following succession: Remove the edges Ai Aj (1 Remove the edges XAi (1 Remove the edges Y Aj (1 i<j i j n n n 3) in any order, from the cycles Ai XY Aj .

3) in any order, from the cycles XY ZAj . 3) in any order, from the cycles Y XZAj .

This construction completes the proof: the least possible number of edges of an admissible graph is indeed n. Comment. The proposer’ formulation is: s

13

In a certain country there are n towns, where n 4. Initially there are no roads connecting the towns. A road may be built between towns A and B if there exist two other towns X and Y such that: there is no road between towns A and X; there is no road between towns X and Y ; there is no road between towns Y and B. What is the maximum number of roads that can be built? C4. Consider a matrix of size n n whose entries are real numbers of absolute value not exceeding 1, and the sum of all entries is 0. Let n be an even positive integer. Determine the least number C such that every such matrix necessarily has a row or a column with the sum of its entries not exceeding C in absolute value. Solution. The least value of C is n=2. To begin with, de…ne the matrix(aij )i;j n as follows: 8 >1 if i; j n=2, < ai;j = 1 if i; j > n=2, > : 0 otherwise

The sum of all entries of aij is 0, and all row sums and column sums are equal to n=2. Hence C cannot be less than n=2. We show now that every n n matrix in question has a row sum or a column sum in the interval [ n=2; n=2]. Suppose on the contrary that each row sum and each column sum of the given matrix is either greater than n=2, or less than n=2. There is no loss of generality in assuming that at least n=2 row sums are positive, because changing the signs of all entries does not a¤ect the whole setting. Select n=2 arbitrary rows with positive sums. They form a submatrix M of size n n=2 of the given matrix, the sum SM of whose entries is greater than n2 =4 by our assumption. Take a column of M with a positive sum. Each of its n=2 entries do not exceed 1, hence their sum does not exceed n=2. In order that SM > n2 =4, at least n=2 columns of M must have positive sums. So let us choose n=2 columns of M with positive sums; label them c1 ; : : : ; cn=2 . Let N be the submatrix of the original matrix composed of the columns that contain c1 ; : : : ; cn=2 . Since the entries outside of M are at least 1 each, the sum of every column in N is greater than n=2, so also greater than n=2. It follows that the sum SN of the entries in N is greater than n2 =4. But then the sum of all entries in the union M [ N of M and N is greater than n2 =4, too. Indeed, SM > n2 =4 and SN > n2 =4; also, the sum of all entries in the intersection M \ N of M and N is at most n2 =4 (M \ N is an n=2 n=2 submatrix with entries not exceeding 1). Therefore SM [N = SM + SN SM \N > n2 =4. Now look at the entries that are neither in M nor in N . There are n2 =4 of them, each one at least 1; so their sum is at least n2 =4. It follows that the sum of all entries in the original matrix is positive, a contradiction. 14

C5. Let N be a positive integer. Two players A and B, taking turns, write numbers from the set f1; : : : ; N g on a blackboard. A begins the game by writing 1 on his …rst move. Then, if a player has written n on a certain move, his adversary is allowed to write n + 1 or 2n (provided the number he writes does not exceed N ). The player who writes N wins. We say that N is of type A or of type B according as A or B has a winning strategy. (a) Determine whether N = 2004 is of type A or of type B. (b) Find the least N > 2004 whose type is di¤erent from the one of 2004. Solution. The given N is of type B if and only if it has zeros at all odd positions in its binary representation, counted from right to left. Suppose a number n 2 f1; : : : ; N g is written on the blackboard at some instance of the game. We call n winning or losing according as the player to move next in this situation can force a win or not. For example, 1 is winning if and only if N is of type B (because it is A who writes 1). Let N = ak ak 1 : : : a1 be the binary representation of N ; note that ak = 1. Set N0 = 0; N1 = ak = 1; N2 = ak ak 1 ; : : : ; Nk and consider the intervals Ij = fn 2 N j Nj
1 1

= ak ak

1

: : : a2 ; Nk = ak ak

1

: : : a1 = N;

<n

Nj g;

j = 1; : : : ; k:

For numbers in the last interval Ik , all moves are forced and amount to adding 1. For numbers in the remaining intervals, both adding 1 and doubling are possible. Observe that doubling a number from Ij 1 yields an even number from Ij , for all j = 2; : : : ; k. We will prove that exactly one of the following holds true for each interval Ij , j = 1; : : : ; k: ( ) All even numbers in Ij are winning, and all odd numbers are losing. ( ) All odd numbers in Ij are winning and all even numbers are losing. ( ) All numbers in Ij are winning. To begin with, it is clear that the last interval Ik is of type if N is odd, and of type if N is even. Now consider an interval Ij with j 2. Suppose Ij is of type and take a number n 2 Ij 1 . Doubling n yields an even number from Ij , which is winning. It follows that n is winning if and only if n + 1 is losing. In particular, the greatest number Nj 1 in Ij 1 is winning (losing) if and only if the …rst number in the next interval Ij is losing (winning). Thus Ij 1 inherits the alternating winning and losing pattern from Ij ; meaning that Ij 1 is also of type . Let Ij be of type . When doubled, any number from Ij 1 yields an even number from Ij , which is losing. Hence all numbers in Ij 1 are winning, that is, Ij 1 is of type . Suppose …nally that Ij is of type . Then doubling a number from Ij 1 is a losing move, so a number n in Ij 1 is winning if and only if n + 1 is losing. The greatest number Nj 1 in Ij 1 is losing, because it is followed by the …rst number in Ij , where every number is 15

winning. The parity of Nj 1 determines the type of Ij 1 : type , if Nj 1 is odd, and type , if Nj 1 is even. If some Ij is of type , then so are all previous intervals. In particular, this applies to I1 = f1g: Being odd, 1 is therefore losing. In this case, N is of type A (because B will lose the game). If no interval Ij is of type , the observations above show that Ik ; Ik 1 ; : : : , in this order, are of types ; ; ; ; : : : . For this to happen, it is necessary and su? cient that Nk = N; Nk 2 ; Nk 4 ; : : : are all even, which is equivalent to a1 = a3 = a5 = = 0. In this case 1 falls in an interval of type or type ; by the de…nitions, in both cases 1 is winning, implying that N is of type B (B wins the game). The conclusion follows: N is of type B if and only if its binary digits at odd positions from right to left are all zeros. The binary representation of 2004 is 2004 = 11111010100, so 2004 is of type A. The least N > 2004 with zeros at odd positions from right to left is 100000000000 = 211 = 2048. Thus the answer to part (b) is 2048. C6. For an n n matrix A, let Xi be the set of entries in row i, and Yj the set of entries in column j, 1 i; j n. We say that A is golden if X1 ; : : : ; Xn ; Y1 ; : : : ; Yn are distinct sets. Find the least integer n such that there exists a 2004 2004 golden matrix with entries in the set f1; 2; : : : ; ng. Solution. The least n with this property is 13. If there is a 2004 2004 golden matrix with entries in f1; 2; : : : ; ng, then X1 ; : : : ; X2004 , Y1 ; : : : ; Y2004 are distinct subsets of f1; 2; : : : ; ng, hence 4008 2n . Therefore n 12. We claim that actually n 13. Assume on the contrary that there exists a 2004 2004 golden matrix with entries in S = f1; 2; : : : ; 12g. Let A = fX1 ; : : : ; X2004 ; Y1 ; : : : ; Y2004 g, X = fX1 ; : : : ; X2004 g, Y = fY1 ; : : : ; Y2004 g. Since S has 212 = 4096 subsets, note that exactly 4096 4008 = 88 of them do not occur in A. Observe also that Xi \ Yj 6= ; for all 1 i; j 2004, (1)

because row i and column j have a common entry. Suppose that jXi [ Yj j 5 for some pair of indices i; j (jBj stands for the number of elements of B). Then the complement S n (Xi [ Yj ) of Xi [ Yj has at least 27 = 128 subsets, and, by (1), none of them is in A, a contradiction. It follows from (1) that either all row sets or all column sets are of size greater than 3, say all row sets. Denote k = min1 i 2004 jXi j, choose i so that jXi j = k, and consider the subsets of S n Xi whose size is less than k. None of them is in X (because k is the minimum size of a row set) nor in Y (because they do not intersect Xi ). If k = 4 then S n Xi has 8 + 8 + 8 + 8 = 93 > 88 subsets of size 0; 1; 2; 3. They do not occur 0 1 2 3 in A, a contradiction. Likewise, for k = 5 there are 7 + 7 + 7 + 7 + 7 = 99 > 88 0 1 2 3 4 subsets of S n Xi whose size is less than 5, proving that k = 5 is also impossible.

16

Hence k 6, so that X contains no subsets of S with size less than 6. But at most 88 of the subsets just mentioned are not in A. Hence at least 12 12 12 12 12 12 + + + + + 0 1 2 3 4 5 88 = 1498

subsets of S with size less than 6 are in Y. Their complements have size greater than 6, and none of them belongs to X in view of (1) (the complement of a set in Y cannot be in X ). Thus more than 2 1498 = 2996 subsets of S are not row sums, which is impossible (4096 2996 < 2004). We proved that n 13. Let us now consider the sequence of matrices de…ned by A1 = 1 2 1 3 and Am = Am Am
1 1

Am Bm

1 1

for m = 2; 3; : : : ,

where Bm 1 is the 2m 1 2m 1 matrix with entries all equal to m + 2. For each m 1, Am is a 2m 2m matrix with entries in f1; 2; : : : ; m + 2g. Moreover, Am is golden. This is true for A1 . Assume that Am 1 is a golden matrix, with pairwise distinct row and column sets X1 ; : : : ; X2m 1 ; Y1 ; : : : ; Y2m 1 (subsets of f1; 2; : : : ; m + 1g). Then the row and column sets of Am are X1 ; : : : ; X2m 1 ;X1 [ fm+2g; : : : ; X2m 1 [ fm+2g; Y1 ; : : : ; Y2m 1 ;Y1 [ fm+2g : : : ; Y2m 1 [ fm+2g; and they are also pairwise distinct. Now let n = 2m 1 + j, where 1 j 2m 1 . It is clear that the n n submatrix of Am in the upper left-hand corner is golden. Thus n n golden matrices with entries from f1; 2; : : : ; m + 2g exist for each n 2 (2m 1 ; 2m ]. Since 210 < 2004 < 211 , there exists a 2004 2004 golden matrix with entries in the set f1; 2; : : : ; 13g. C7. Determine all m n rectangles that can be covered with “hooks”made up of 6 unit squares, as in the …gure:

Rotations and re? ections of hooks are allowed. The rectangle must be covered without gaps and overlaps. No part of a hook may cover area outside the rectangle. Solution. Consider a covering of an m n rectangle satisfying the conditions. For any hook A, there is a unique hook B covering the “inside” square of A with one of its “endmost” squares. In turn, the “inside” square of B must be covered by an “endmost” square of A. Thus, in a tiling, all hooks are matched into pairs. There are only two possibilities to place B so that it does not overlap with A and no gap occurs. In one case, 17

A and B form a 3 4 rectangle; in the other, their union is an octagonal shape, with side lengths 3, 2, 1, 2, 3, 2, 1, 2. So an m n rectangle can be covered with hooks if and only if it can be covered with the 12-square tiles shown above. Suppose that such a tiling exists; then mn is divisible by 12. We now show that one of m and n is divisible by 4. Assume on the contrary that this is not the case; then m and n are both even, because mn is divisible by 4. Imagine the rectangle divided into unit squares, with the rows and columns formed labeled 1; : : : ; m and 1; : : : ; n. Write 1 in the square (i; j) if exactly one of i and j is divisible by 4, and 2, if i and j are both divisible by 4. Since the number of squares in each row and column is even, the sum of all numbers written is even. Now, it is easy to check that a 3 4 rectangle always covers numbers with sum 3 or 7; and the other 12-square shape always covers numbers with sum 5 or 7. Consequently, the total number of 12-square shapes is even. But then mn is divisible by 24, and hence by 8, contrary to the assumption that m and n are not divisible by 4. Notice also that neither m nor n can be 1, 2 or 5 (any attempt to place tiles along a side of length 1, 2 or 5 fails). We infer that if a tiling is possible, then one of m and n is divisible by 3, one is divisible by 4, and m; n 62 f1; 2; 5g. Conversely, if these conditions are satis…ed, the tiling is possible (using only 3 4 rectangles at that). This is immediate if 3 divides m and 4 divides n (or vice versa). Let m be divisible by 12 and n 62 f1; 2; 5g (or vice versa). Then n can be represented as the sum of several 3’ and several 4’ Hence the rectangle can be partitioned into m 3 and s s. m 4 rectangles, which are easy to cover, only with 3 4 tiles again. Comment. Here is one more proof that one of m and n is divisible by 4 (the essential part of the problem ). Depending on how a 12-square tile (of whichever type) is placed on the grid plane, exactly one of the following two situations occurs: (a) The tile has 4 columns, each of length 3, and 3 or 4 rows, each of length 2 or 4; (a) The tile has 4 rows, each of length 3, and 3 or 4 columns, each of length 2 or 4. Suppose a tiling is possible; then mn is divisible by 12. If the number of tiles is even, then mn is divisible by 24, and one of m; n is divisible by 4. Let there be an odd number of tiles. Then one of the situations (a), (b) occurs an odd number of times, say (a). Color black every fourth column. Each (a)-tile covers 3 black squares, and each (b)-tile covers an even number of black squares. Thus the total number of black squares is odd, implying that the column length is odd. So the row length must be divisible by 4. C8. For a …nite graph G, let f (G) be the number of triangles and g(G) the number of tetrahedra formed by edges of G. Find the least constant c such that g(G)3 c f (G)4 for every graph G.

Solution. Label v1 ; : : : ; vn the vertices of a given graph G and denote by E the set of its edges. We …rst work out a relation between f (G) and jEj, the cardinality of E. 18

Assume that the vertex vi has degree xi : there are xi edges emanating from vi . Denote the set of their second endpoints by Ai ; jAi j = xi . Let yi and zi be the numbers of triangles and tetrahedra with vi as a vertex, respectively. Then
n X i=1

xi = 2jEj;

n X i=1

yi = 3f (G);

n X i=1

zi = 4g(G):

Let Ei be the set of all edges with both endpoints in Ai . Each of these edges corresponds uniquely to a triangle with one vertex at vi . So yi = jEi j. Since jAi j = xi , there xi are at most xi edges in Ei , implying yi . Consequently, 2 2 s p p p xi xi p yi = jEi j yi jEi j jEj p 2 2 (because Ei E and
xi 2

x2 =2). Summation over i yields i i. e. f (G)2

3f (G)

This relation holds for any graph, in particular for the graph Gi with set of vertices Ai and set of edges Ei . Therefore f (Gi )2 2 jEi j3 9 for i = 1; : : : ; n.

p 2jEj jEj p ; 2

2 3 jEj : 9

Each of the f (Gi ) triangles in Gi (formed by edges from Ei , with endpoints in Ai ) corresponds uniquely to a tetrahedron with a vertex at vi . Hence zi = f (Gi ), and so zi = f (Gi )1=3 f (Gi )2=3 By summation over i again, 4g(G) f (G)
1=3

f (Gi )1=3

2 9

1=3

jEi j

f (G)1=3

2 9

1=3

yi :

2 9

1=3

3f (G);

i. e.

g(G)3

3 f (G)4 : 32

Thus c = 3=32 is a constant as needed. It is the least such constant, as can be seen by considering the complete graph Kn on n vertices. As n approaches in…nity, the ratio 3 4 g(Kn )3 =f (Kn )4 = n n approaches 3=32, so the bound 3=32 is sharp. 3 4 Comment by the proposer. Let Nk be the number of k-cliques in a …nite graph. 3 2 3 2 3 N and N4 N 4 . Continuing inductively, one can prove We have shown that N3 9 2 32 3 that k! k Nk+1 N k+1 (k + 1)k k for any graph (regardless of the number of vertices). This might be considered as an alternative version of the problem. 19

EST1. Determine all m n rectangles that can be covered with “hooks” made up of 6 unit squares, as in the …gure:

Rotations and re? ections of hooks are allowed. The rectangle must be covered without gaps and overlaps. No part of a hook may cover area outside the rectangle. Solution. The answer is: 4k 3` and 12k a, a 6. By joining two hooks appropriately, we can obtain a 4 3 rectangle. Consequently, all rectangles of size 4k 3` are coverable, k; ` 2 N. On the other hand, we also observe that all rectangles of size 12k 3, 12k 4, 12k 6 and 12k 8 are coverable, too. The …rst two of them produce a 12k 7 rectangle. Adding strips of size 12k 3, we cover all rectangles of size 12k (6 + 3`), 12k (7 + 3`) and 12k (8 + 3`) which implies that all rectangles 12k a with a 6 are coverable. Suppose now that we have a covering of an m n rectangle satisfying the conditions. For any hook A, there is a unique hook B covering the “inside” square of A. Call B the neighbor of A. Clearly the inside square of A must be covered by one of the “endmost” squares of B. It is simple to check that there are only 3 possibilities to place B so that it does not overlap with the original hook A. In one case, A and B form the union of two 2 3 rectangles; in another case, a rectangle 4 3 is obtained, as explained above. The third case is impossible since a lonely square between the two hooks remains uncovered. In both possible cases, the original hook A is the neighbor of its neighbor B. Hence all the hooks can be divided into pairs of neighbors. Thus the total number of hooks is even, so the number mn of squares in the covered rectangle is divisible by 12. We now show that one of m and n is divisible by 4. Assume on the contrary that this is not the case; then m and n are both even (mn is divisible by 4) and congruent to 2 modulo 4. Imagine the rectangle divided into unit squares, with the rows and columns formed labeled 1; : : : ; m and 1; : : : ; n (from top to bottom and from left to right). Place a bullet on the square in row i and column j if exactly one of i and j is divisible by 4, as shown in the …gure. Each of the two possible shapes formed by two neighboring hooks covers 12 unit squares. Wherever they are, a straightforward veri…cation shows that the shape covers either 3 or 5 bullets. Consequently, each pair of neighboring hooks covers an odd number of bullets.

1

On the other hand, if m = 4u + 2, n = 4v + 2, the total number of bullets placed is u(3v + 2) + v(3u + 2) = 2(3uv + u + v + 2), an even number. Hence the total number of shapes formed by two neighboring hooks is even. One infers that the total number mn of unit squares is divisible by 24 and thus also by 8. This contradicts the assumption that neither m nor n is divisible by 4. So let m = 4k, without loss of generality. If m is not divisible by 3 then n is (because mn is), and we have a rectangle of size 4k 3l. If m is divisible by 3, then the rectangle is of size 12k a. It remains to show that a cannot be 1, 2 or 5. Of course, no hook can be placed correctly on strips of width 1 or 2. To cover a 12k 5 rectangle, one should cover its boundary strip S with length 5. But no matter how a shape of two neighboring hooks is placed on squares of S, uncoverable parts of the rectangle arise. Comment for the PSC. I am ready to restore the original exposition. It is probably personal, but I got confused when reading the proposed text as to how the “markings” are counted.

2

Geometry
G1. Let ABC be an acute-angled triangle with AB 6= AC. The circle with diameter BC intersects the sides AB and AC at M and N, respectively. Denote by O the midpoint of BC. The bisectors of the angles BAC and MON intersect at R. Prove that the circumcircles of the triangles BMR and CNR have a common point lying on the line segment BC. First solution. Since OM = ON, the bisector of 6 MON coincides with the perpendicular bisector of MN . So in 4AMN the bisector of 6 MAN and the perpendicular bisector of the side MN meet at R. Then, as is well known, R lies on the circumcircle of the triangle. (One needs to note that AM 6= AN; indeed, 6 AMN = 6 C and 6 ANM = 6 B from the cyclic quadrilateral BCNM, and 6 B 6= 6 C by hypothesis.) Let the bisector of 6 BAC meet BC at L. It is easy to see that L is a common point of the circles (BMR) and (CNR). This means to show that the quadrilaterals BLRM and CLRN are cyclic, which is equivalent to 6 ARM = 6 ABC and 6 ARN = 6 ACB. But 6 ABC = 6 ANM and 6 ACB = 6 AMN, as mentioned above, so the question reduces to
6

ARM = 6 ANM,
6

ARN = 6 AMN.

These angle equalities follow from the cyclic quadrilateral AMRN, and the solution is complete.

Second solution. Denote by T the midpoint of MN . Since 4ABC and 4ANM are similar, with respective medians AO and AT , we have 6 BAO = 6 CAT . Thus the bisector AR of 6 BAC also bisects 6 OAT . Therefore RT AT = . RO AO Furthermore, using again the fact that AT and AO are respective medians in similar triangles, one has AT MN MT MT = = = . AO BC BO MO 20

We conclude that MR bisects 6 OMN. Now, 6 BMO = 6 B (O is the center of the circle (BCNM)). Combined with 6 AMN = 6 C, this yields 6 OMN = 6 A and hence 6 BMR = 6 B + 6 A/2 = 6 CLR. So B, L, R, M are concyclic. Likewise, C, L, R, N are concyclic. Comment. Both solutions use the fact that R is on the line segment AL (not on its extension beyond L), which is easy to justify. It is not hard to guess that L is a common point of the circles (BMR) and (CNR). By similar triangles or by the power-of-a-point theorem, we see that AM · AB = AN · AC, implying that A is the radical center of the circles (BCNM), (BMR) and (CNR). One infers from here that AR is the radical axis of (BMR) and (CNR). So if the other common point of these two circles is on BC, it can be only the intersection of AR and BC, that is, L. Such an argument was included in the proposer’s solution although, formally speaking, it is not a part of the proof. The proposer also notices that the result remains valid for any circle passing through B and C, with the center of that circle as O instead of the midpoint of BC. G2. The circle Γ and the line do not intersect. Let AB be the diameter of Γ perpendicular to , with B closer to than A. An arbitrary point C 6= A, B is chosen on Γ. The line AC intersects at D. The line DE is tangent to Γ at E, with B and E on the same side of AC. Let BE intersect at F , and let AF intersect Γ at G 6= A. Prove that the re?ection of G in AB lies on the line CF . Solution. Let CF meet Γ at H. Since AB ⊥ , the problem is equivalent to showing that GH k . This is true if and only if 6 AGH = 6 DF A; but 6 AGH = 6 ACH = 6 DCF by inscribed and vertical angles, so an equivalent statement is 6 DCF = 6 DF A. Because the triangles DCF and DF A share a common angle at D, the latter reduces to proving that these triangles are similar (with respective vertices in this order). This holds true if and only if DC/DF = DF/DA, i. e. DF 2 = DA · DC.

21

Observe now that DE 2 = DA · DC by the power-of-a-point theorem. Hence the question reduces to proving that DE = DF , that is, 6 DEF = 6 DF E. Let AB meet at X. Then 6 F XB = 90? ; also, 6 AEB = 90? (AB is a diameter of Γ). Hence A, F, X, E are concyclic, and so 6 XF E = 6 EAB. Finally, 6 DEF = 6 EAB by the tangent-chord theorem, and the desired equality 6 DEF = 6 DF E follows. G3. Let O be the circumcenter of an acute-angled triangle ABC with 6 B < 6 C. The line AO meets the side BC at D. The circumcenters of the triangles ABD and ACD are E and F , respectively. Extend the sides BA and CA beyond A, and choose on the respective extensions points G and H such that AG = AC and AH = AB. Prove that the quadrilateral EF GH is a rectangle if and only if 6 ACB ? 6 ABC = 60? . Solution. Let 6 ABC = β, 6 ACB = γ, where β < γ. Since 4ABC is acute with O its circumcenter, 6 OAC = 90? ? β. Then 6 ADB = 6 OAC + 6 ACD = 90? ? β + γ > 90? , so that 4ABD is obtuse and 4ACD is acute. Hence F is inside 4ACD and E is outside 4ABD; O and E are on di?erent sides of AB. Because F and O are the circumcenters of 4ACD and 4ABC, we have
6

F AC = 90? ? 6 ADC = γ ? β,
6

F DC = 90? ? 6 OAC = β.

Hence F D k AB; analogously, ED k AC. Denote by P the intersection of AD and GH. Then 6 P AH = 6 OAC = 90? ? β. On the other hand 6 P HA = 6 ABC = β, because 4ABC and 4AHG are congruent. Thus 6 AP H = 90? , meaning that AD⊥GH. But EF is the perpendicular bisector of AD, so AD⊥EF . It follows that GHkEF . So the corresponding sides of 4AHG and 4DEF are parallel. Then HE and GF either intersect on AD, or they are parallel to AD. The lines EF and GH are perpendicular to AD, so EF GH is a rectangle if and only if the second alternative holds. In view of DEkAH and DF kAG, this is the case if and only if the (similar) triangles AHG and DEF are congruent; i. e., if and only if DF = AG. Because F is the circumcenter of 4ACD and AG = AC, the latter is in turn equivalent to AC = CF = AF ; that is, to ACF being an equilateral triangle. Since 4ACF is isosceles (with base AC), it is equilateral if and only if 6 F AC = 60? . And since 6 F AC = γ ? β, the claim follows. G4. In a convex quadrilateral ABCD the diagonal BD does not bisect the angles ABC and CDA. The point P lies inside ABCD and satis?es
6

P BC = 6 DBA and
6

P DC = 6 BDA.

Prove that ABCD is a cyclic quadrilateral if and only if AP = CP . First solution. Since P is interior to ABCD, it follows that 6 DBA < 6 DBC if and only if 6 BDA < 6 BDC. So one may assume without loss of generality that P lies in the triangles ACD and BCD. 22

Assume that the quadrilateral ABCD is cyclic. Let the lines BP and DP meet AC at K and L, respectively. It follows from the given equalities and 6 ACB = 6 ADB, 6 ABD = 6 ACD that the triangles DAB, DLC and CKB are similar. This implies 6 P LK = 6 P KL, so P K = P L. The triangles ADL and BDC are also similar, hence AL AD KC = = , BC BD BC yielding AL = KC. Combined with the conclusions above, this implies that the triangles ALP and CKP are congruent. Hence AP = CP . Conversely, assume that AP = CP . Let the circumcircle of the triangle BCP meet the lines CD and DP again at X and Y , respectively. The triangles ADB and P DX are similar, implying that ADP and BDX are also similar. Therefore BX BD XD = = . AP AD PD Moreover, the triangles DP C and DXY are similar, which gives YX XD = . CP PD Since AP = CP , it follows from (1) and (2) that BX = Y X. Hence
6

(1)

(2)

DCB = 6 XY B = 6 XBY = 6 XP Y = 6 P DX + 6 P XD = 6 ADB + 6 ADB = 180? ? 6 BAD.

The above equality means that ABCD is a cyclic quadrilateral. Second solution. Assume ?rst that the points A, B, C, D are concyclic. Let the lines BP and DP meet the circumcircle of ABCD again at E and F , respectively. Then d d d d it follows from the given conditions that AB = CF and AD = CE, so BF k AC and DE k AC. Therefore BF ED is an isosceles trapezoid (or a rectangle) whose diagonals meet at P . Thus P lies on the diameter of the circumcircle which is perpendicular to AC. Hence AP = CP . Assume in turn that AP = CP . Without loss of generality, let P lie in the triangles ACD and BCD. Let BP and DP meet AC at K and L, respectively. The points A and C are isogonal conjugates with respect to the triangle BDP , which implies that 6 AP K = 6 CP L. Since AP = CP , we infer that K and L are symmetric with respect to the perpendicular bisector p of AC. Let E be the re?ection of D in p. Then E lies on the line BP , and the triangles AP D and CP E are congruent. Thus 6 BDC = 6 ADP = 6 BEC, which means that the points B, C, E, D are concyclic. Moreover, A, C, E, D are also concyclic. So ABCD is a cyclic quadrilateral. 23

G5. Let A1 A2 . . . An be a regular n-gon. The points B1 , . . . , Bn?1 are de?ned as follows: ? If i = 1 or i = n ? 1, then Bi is the midpoint of the side Ai Ai+1 ; ? If i 6= 1, i 6= n ? 1 and S is the intersection point of A1 Ai+1 and An Ai , then Bi is the intersection point of the bisector of the angle Ai SAi+1 with Ai Ai+1 . Prove the equality
6

A1 B1 An + 6 A1 B2 An + · · · + 6 A1 Bn?1 An = 180? .

Solution. We ?rst establish the following lemma. Lemma. Let ABCD be an isosceles trapezoid with bases AB and CD. The diagonals AC and BD intersect at S. Let M be the midpoint of BC, and let the bisector of the angle BSC intersect BC at N. Then 6 AMD = 6 AND. Proof of the lemma. It su?ces to show that the points A, D, M, N are concyclic. Let the nonparallel lines AD and BC meet at X, and let XA = XB = a, XC = XD = b. By the bisector property and parallel lines, BN/CN = BS/CS = AB/CD = a/b, and so (BN + CN)/CN = (a + b)/b. Since BN + CN = BC = a ? b, an easy computation gives XN = (2ab)/(a + b). We also have XM = (a + b)/2, hence XM · XN = XA · XD. Therefore A, D, M, N are concyclic, as needed. ?

Denote by Ci the midpoint of the side Ai Ai+1 , i = 1, . . . , n ? 1. For 1 < i < n ? 1, the quadrilateral A1 Ai Ai+1 An is either an isosceles trapezoid with nonparallel sides A1 An and Ai Ai+1 , or a rectangle. In the ?rst case we obtain 6 A1 Bi An = 6 A1 Ci An by the lemma; in the second case Bi = Ci , so the same is true. Thus the sum in consideration equals Σ = 6 A1 C1 An + 6 A1 C2 An + · · · + 6 A1 Cn?1 An . Because A1 A2 . . . An is a regular n-gon, for each i = 2, . . . , n ? 1 the triangles A1 Ci An and An+2?i C1 An+1?i are congruent (a rotation about the center of the n-gon carries the ?rst one to the second). Hence 6 A1 Ci An = 6 An+2?i C1 An+1?i for i = 2, . . . , n ? 1, and so Σ = 6 A1 C1 An + 6 An C1 An?1 + · · · + 6 A3 C1 A2 , a quantity equal to 180? . 24

G6. Let P be a convex polygon. Prove that there is a convex hexagon which is contained in P and which occupies at least 75 percent of the area of P. First solution. Some three vertices A, B, C of P determine a triangle ABC of maximum area contained in P. Draw parallels to BC, CA, AB through A, B, C, respectively, and denote the triangle thus obtained by A1 B1 C1 . Since each triangle with vertices in P has area at most the area of ABC, the entire polygon P is contained in A1 B1 C1 . Next, draw lines of support of P parallel to BC, CA, AB and not intersecting the triangle ABC. They determine a convex hexagon Ua Va Ub Vb Uc Vc containing P, with Vb , Uc ∈ B1 C1 , Vc , Ua ∈ C1 A1 , Va , Ub ∈ A1 B1 . Each of the line segments Ua Va , Ub Vb , Uc Vc contains points of P. Choose such points A0 , B0 , C0 on Ua Va , Ub Vb , Uc Vc , respectively. The convex hexagon AC0 BA0 CB0 is contained in P, because the latter is convex. We prove that AC0 BA0 CB0 has area at least 3/4 the area of P. For clarity, consider an arbitrary triangle XY Z, with a parallel KL drawn to its side XY and a point M on KL. Let ZK/ZX = λ (0 < λ < 1). Writing [Q] for the area of the polygon Q, we have [KLZ] = λ2 [XY Z]. Also, the altitudes of the triangles XY M and XY Z to their common side XY are in ratio 1 ? λ. Hence [XY M] = (1 ? λ)[XY Z], [XY LK] = (1 ? λ2 )[XY Z]. Apply this observation to the triangles BCA1 , CAB1 , ABC1 and the points A0 , B0 , C0 on Ua Va , Ub Vb , Uc Vc , with A1 Ua /A1 B = λa , B1 Ub /B1 C = λb , C1 Uc /C1 A = λc . Taking into account that [A1 BC] = [B1 CA] = [C1 AB] = [ABC], we have [AC0 BA0 CB0 ] [ABC] + (1 ? λa )[ABC] + (1 ? λb )[ABC] + (1 ? λc )[ABC] = [Ua Va Ub Vb Uc Vc ] [ABC] + (1 ? λ2 )[ABC] + (1 ? λ2 )[ABC] + (1 ? λ2 )[ABC] a b c 4 ? (λa + λb + λc ) = . 4 ? (λ2 + λ2 + λ2 ) a b c Since Ua Va Ub Vb Uc Vc contains P, it su?ces to show that the last ratio is at least 3/4. For λa , λb , λc ∈ (0, 1), a short computation shows that the latter is equivalent to the ? ¤ evident 3 (λa ? 2/3)2 ) + (λb ? 2/3)2 + (λc ? 2/3)2 ≥ 0. This completes the solution.

Second solution. Take any two parallel lines of support s, t touching P at S, T . The segment ST partitions P into two convex polygons P 0 and P 00 . Let K, L be points on the boundary of P such that the segment KL is parallel to ST and has length ST /2. We claim that the trapezoid SKLT has area at least 3/4 the area of P 0 . This yields the result because the same argument, applied to P 00 , produces another trapezoid, of area at least 3/4 the area of P 00 . Combining the two trapezoids, we obtain a hexagon as needed. Draw the lines of support of P through K and L, and let them intersect at Z. We assume for de?niteness that K is closer to the line s than L. Let ZK meet s at X, let ZL meet t at Y , and let the line through Z, parallel to ST , meet s and t at A and B, respectively. Clearly P 0 is contained in the pentagon SXZY T , so it su?ces to show that 3 [SKLT ] ≥ [SXZY T ]. 4 25 (1)

Denote AZ = a, BZ = b, and let the distances from the points K, X, Y , S to the line AB be k, x, y, s. Taking U, V on AB so that s k KU k LV k t, we obtain a+b ak bk = KL = U Z + ZV = + . 2 x y The areas we are about to compare are expressed by 3 [SKLT ] = (a+b)(s?k), 4 [SXZY T ] = [SABT ]?[AXZ]?[BY Z] = (a+b)s? ax by ? , 2 2 (2)

so the claimed inequality (1) comes down to ax + by ? 2(a + b)k ≥ 0. (3)

On computing k from (2) and plugging into (3), a short calculation shows that the lefthand side of (3) is equal to ab(x ? y)2 (ay + bx)?1 , which is nonnegative. G7. For a given triangle ABC, let X be a variable point on the line BC such that C lies between B and X and the incircles of the triangles ABX and ACX intersect at two distinct points P and Q. Prove that the line P Q passes through a point independent of X. Solution. The proof uses the following observation: Lemma. In a triangle ABC, let K, L be the midpoints of the sides AC, AB, respectively, and let the incircle of the triangle touch BC, CA at D, E, respectively. Then the lines KL and DE intersect on the bisector of the angle ABC.

Proof of the lemma. One can assume that AB 6= BC, or else the claim is obvious. Let KL and the bisector b of 6 ABC meet at S. Since KL k BC, we have 6 LSB = 6 CBS = 6 LBS. Hence LB = LS, and L is equidistant from A, B and S. Then S lies on the circle with diameter AB, and so 6 ASB = 90? . 26

Now let DE and b meet at T . Note that the incenter I of 4ABC is between B and T ; also, T 6= E, since AB 6= BC. The triangles DEC and ABI give 6 DEC = 90? ? 6 C/2, 6 AIB = 90? + 6 C/2. If T is interior to the line segment DE, as in the ?gure, we obtain 6 AIT + 6 AET = 180? , so the quadrilateral AIT E is cyclic. Otherwise I and E are on the same side of AT , and we have 6 AIT = 90? ? 6 C/2 = 6 AET . So the points A, I, T and E are concyclic in all cases. Since 6 AEI = 90? , it follows that 6 AT I = 90? . We proved that 6 ASB = 6 AT B. Therefore S and T coincide, meaning that KL, DE and b intersect at one point. ? Let the incircles of 4ABX and 4ACX touch BX at D and F , respectively, and let them touch AX at E and G, respectively. Clearly DE and F G are parallel, being perpendicular to the bisector of 6 AXB. If the line P Q intersects BX and AX at M and N, respectively, then MD2 = MP · MQ = MF 2 , NE 2 = NP · NQ = NG2 by the power-of-a-point theorem. Thus MD = MF , N E = NG. It follows that P Q is parallel to DE and F G and equidistant from them. The midpoints of AB, AC and AX lie on the same line m, parallel to BC. Applying the lemma to 4ABX, we conclude that DE passes through the common point U of m and the bisector of 6 ABX. Analogously, F G passes through the common point V of m and the bisector of 6 ACX. Therefore P Q, which is parallel to DE and F G and equidistant from them, passes through the midpoint W of the line segment UV . Now, U and V do not depend on X, and hence neither does W . G8. A cyclic quadrilateral ABCD is given. The lines AD and BC intersect at E, with C between B and E; the diagonals AC and BD intersect at F . Let M be the midpoint of the side CD, and let N 6= M be a point on the circumcircle of the triangle ABM such that AN/BN = AM/BM . Prove that the points E, F and N are collinear. Solution. To start with, note that there is a unique point N 6= M on the circle (ABM) such that AN/BN = AM/BM. If λ = AM/BM 6= 1 then M and N are common points of the circle (ABM) and the locus of points X such that AX/BX = λ. This locus is known to be a circle intersecting the line segment AB (the Apollonius circle of AB with respect to the ratio λ), which proves the existence and the uniqueness of N. Clearly, N also exists and is unique if AM/BM = 1. Note in addition that M and N are on di?erent sides of AB.

27

Consider the circumcircles of the triangles ABE and ABF . Denote by P and Q, respectively, their second points of intersection with the line EF . The problem is equivalent to showing that N lies on the line P Q. We prove that in fact N coincides with the midpoint S of the line segment P Q. Observe ?rst that E, F, P, S, Q lie in this order on P Q, and that P Q intersects the side AB. The cyclic quadrilaterals AP BE, AQBF and ABCD yield AP E = 6 ABE = 6 ABC = 180? ? 6 ADC, AQP = 6 AQF = 6 ABF = 6 ABD = 6 ACD,
6 6

and it follows that AP Q and ADC are similar triangles. Since AS and AM are respective medians in them, we have AS/AM = P Q/DC. By symmetry, the triangles BP Q and BCD are also similar, and arguing about their medians BS and BM gives BS/BM = P Q/CD. We conclude that AS/BS = AM/BM. Moreover, it also follows from the two pairs of similar triangles that 6 ASP = 6 AMD, 6 BSP = 6 BMC. So
6

ASB = 6 ASP + 6 BSP = 6 AMD + 6 BMC = 180? ? 6 AMB,

meaning that S lies on the circle (ABM). Clearly S 6= M. Now, the points N 6= M and S 6= M both lie on the circumcircle of 4ABM and satisfy AN/BN = AM/BM, AS/BS = AM/BM. By the uniqueness of N, they coincide, which completes the solution.

28

Number Theory
N1. Let (n) denote the number of positive divisors of the positive integer n. Prove that there exist in…nitely many positive integers a such that the equation (an) = n does not have a positive integer solution n. First solution. If (an) = n for some n 2 N, then a = (an)= (an), so the equation k= (k) = a has a solution in positive integers k. Thus it is su? cient to show that if p 5 is a prime, then the equation k= (k) = pp 1 does not have positive integer solutions. We use the following observation: p (n) 2 n for all n = 1; 2; : : : . (1) p p Indeed, let n have k divisors in [1; n]. Then the p number of its divisors in ( n; n] is at most k, because if d is a divisor of n greater than n then n=d is a positive divisor of n p p less than n. Hence (n) 2k 2 n. Assume on the contrary that for some prime p 5 the equation k= (k) = pp 1 has a positive integer solution k. Then k is divisible by pp 1 , and so k = p s, where p 1 and p does not divide s. Hence p s = pp 1 : ( + 1) (s) If = p 1, (2) gives s = p (s), so p divides s, a contradiction. Therefore Suppose that p + 1. By (1) and (2), p s pp 1 ( + 1) s s p = = : p (s) 2 2 s (2) p.

However, for all p 5 and p + 1 one has 2( + 1) < p p+1 (an easy induction on , with base = p + 1). It follows that s < 1, a contradiction again. Only the case = p remains, where (2) becomes ps = (p + 1) (s). In particular, p p divides (s), so p (s) 2 s. Now, using (1) again, we obtain p This implies p p 2 s s s= p s 2s 2(p + 1) = : (s) p 5.

4(p + 1)=p, which is impossible for p

Second solution. We prove that for a prime p 5 the equation pp 1 n = n does not have a positive integer solution. Recall that if m = p1 1 : : : pk k is the prime factorization of m, then (m) = ( 1 + 1) ( k + 1). The following simple inequalities are used below; all of them follow by straightforward induction: 29

(i) p (ii) p > (iii) p

+ 1, for p + p, for p 2 + 1, for p

2 and 3 and 3;

1; 2; 1 or p = 2; 3.

We argue by contradiction. If pp 1 n = n, note …rst that p divides n. Otherwise n = pp 1 n = pp 1 (n) = p (n), so n is divisible by p contrary to the assumption. Let n = p p1 1 : : : pk k be the prime factorization of n. Then pp 1 n = p +p 1 p1 1 : : : pk k , and the equation becomes ( + p)(
1

+ 1)

(

k

+ 1) = p p1 1 : : : pk k : = 1, or else the expression on

Now, (i) and (ii) show that the above can hold only if the left is smaller. For = 1, one has (p + 1)(
1

+ 1)

(

k

+ 1) = pp1 1 : : : pk k :

Suppose that pi 3 for some i. In view of (iii), replacing pi i by 2 i + 1 does not increase the right-hand side; and neither does replacing all remaining pj j by j + 1 in view of (i). This implies (p + 1)( i + 1) p(2 i + 1). The same conclusion follows if there is an i such that pi = 2 and i 3 (by (iii) and (i) again). However, the inequality (p + 1)( i + 1) p(2 i + 1) is clearly impossible for i 1 and p 2. We infer that n does not have prime divisors other than p and 2. Moreover, the exponent of 2 in the prime factorization of n is at most 2. Hence the equation simpli…es to (p + 1)( + 1) = p2 for some 2. But in this case p must divide + 1, implying p 1 > 2, a contradiction. Comment. Choosing a of the form a = pp 1 simpli…es the proof, but this is not the only option. For instance, if p is a prime greater than 3, then a = 6p is also a solution. N2. The function equality from the set N of positive integers into itself is de…ned by the (n) =
n X k=1

(k; n);

n 2 N;

where (k; n) denotes the greatest common divisor of k and n. a) Prove that (mn) = (m) (n) for every two relatively prime m; n 2 N. b) Prove that for each a 2 N the equation (x) = ax has a solution. c) Find all a 2 N such that the equation (x) = ax has a unique solution. Solution. a) Let m; n PN be relatively prime. Then (k; mn) = (k; m)(k; n) for 2 P each k 2 N, hence (mn) = mn (k; mn) = mn (k; m)(k; n). To each k 2 f1; : : : ; mng k=1 k=1 assign the unique ordered pair hr; si of integers satisfying r k (mod m), s k (mod n), 1 r m, 1 s n. This mapping is a bijection. Indeed, the number of pairs hr; si 30

such that 1 r m, 1 s n equals mn; and if k1 k2 (mod m) and k1 k2 (mod n) for k1 ; k2 2 f1; : : : ; mng, then k1 k2 (mod mn), implying k1 = k2 . Also, (k; m) = (r; m) and (k; n) = (s; n) for each k 2 f1; : : : ; mng and its respective pair hr; si. Hence (mn) =
mn X k=1

(k; m)(k; n) =

1 r m 1 s n

X

(r; m)(s; n) =

m X r=1

(r; m)

n X s=1

(s; n) = (m) (n):

a positive integer. Each summand in Pnb) Let n = p , where `p is a `prime and k=1 (k; n) has the form p , and p occurs as many times as there are integers between 1 and p which are divisible by p` but not by p`+1 . For ` = 0; 1; : : : ; 1, the number of ` ` 1 such integers is p p . It follows that (n) = (p ) = p +
1 X `=0

p` (p

`

p

` 1

) = ( + 1)p

p

1

:

(1)

For any a 2 N, choose p = 2 and = 2a 2 to obtain 22a 2 = a 22a 2 . So x = 22a 2 is a solution of the equation (x) = ax. c) Setting = p in (1), we see that (pp ) = pp+1 for every prime p. Therefore, if a 2 N has an odd prime divisor p, then x = 22(a=p) 2 pp satis…es the equation (x) = ax. Indeed, by a) and (1), (22(a=p) 2 pp ) = (22(a=p) 2 ) (pp ) = 2a 2(a=p) 3 p+1 2 p = a22(a=p) 2 pp : p

The solutions x = 22(a=p) 2 pp and x = 22a 2 are di¤erent, because p is odd. Hence if (x) = ax has a unique solution then a = 2 for some = 0; 1; 2; : : : . We now prove that the converse is also true. Consider any solution x of (x) = 2 x and let x = 2 `, where 0 and ` is odd. By a) and (1) again, 2
+

` = 2 x = (x) = (2 `) = (2 ) (`) = ( + 2)2

1

(`):

Notice that (`) is odd for all odd ` by the de…nition of , being the sum of an odd number of odd summands. Hence (`) divides `. On the other hand, (`) > ` for ` > 1, which implies ` = 1 = (`). This yields = 2 +1 2 = 2a 2, the solution already obtained in b). So (x) = ax has a unique solution if and only if a = 2 for some = 0; 1; 2; : : : . Comment. It is easy to observe that is closely related to Euler’ function ', which s provides P approach to part of the problem from a more general viewpoint. Each suman mand in n (k; n) is a divisor d of n, occurring as many times as there areP numbers cok=1 P prime to n=d in f1; : : : ; n=dg, i. e., '(n=d) times. So (n) = djn d'(n=d) = n djn '(d)=d. Since ' is known to be multiplicative, part a) can be obtained in a variety of ways. Also, it is easy to express (n) in terms of the prime factorization of n. N3. A function f from the set of positive integers N into itself is such that for all m; n 2 N the number (m2 + n)2 is divisible by f 2 (m) + f (n). Prove that f (n) = n for each n 2 N. 31

Solution. For m = n = 1, the given relation implies that f 2 (1) + f (1) is a (positive) divisor of (12 + 1)2 = 4. The equation t2 + t = 4 has no integer roots; also, f 2 (1) + f (1) is greater than 1. Thus f 2 (1) + f (1) = 2, so that f (1) = 1. Now apply the hypothesis with m = 1 to obtain f (n) + 1 divides (n + 1)2 for all n 2 N: Similarly, taking n = 1 yields f 2 (m) + 1 divides (m2 + 1)2 for all m 2 N. (2) (1)

To prove that f is the identity function, it su? ces to …nd in…nitely many k such that f (k) = k. Indeed, suppose that this is true, and …x an arbitrary n 2 N. For each k satisfying f (k) = k, the number k 2 + f (n) = f 2 (k) + f (n) divides (k 2 + n)2 by hypothesis. On the other hand, (k 2 + n)2 can be written as (k 2 + n)2 = [(k 2 + f (n)) + (n f (n))]2 = A(k 2 + f (n)) + (n f (n))2

for some integer A. Hence (n f (n))2 is divisible by k 2 + f (n) for all k with the property that f (k) = k. Since there are in…nitely many such k by assumption, we conclude that (n f (n))2 = 0. It follows that f (n) = n for all n 2 N, as claimed. Hence the solution will be complete if we prove that f (p 1) = p 1 for each prime p. Indeed, f (p 1) + 1 divides p2 by (1), so f (p 1) + 1 = p or f (p 1) + 1 = p2 . Suppose that f (p 1) + 1 = p2 . Then, by (2), (p2 1)2 + 1 is a divisor of ((p 1)2 + 1)2 . But for p > 1 one has (p2 1)2 + 1 > (p 1)2 (p + 1)2 ; [(p 1)2 + 1]2 [(p 1)2 + (p 1)]2 = (p 1)2 p2 :

This is a contradiction, and the claim follows. Comment by the proposer. A possible version of the question is: Find all functions f : N ! N such that for all m; n 2 N the number (m2 + n)2 is divisible by f 2 (m) + f (n). N4. Let k be a …xed integer greater than 1, and let m = 4k 2 5. Show that there exist positive integers a and b such that the sequence (xn ) de…ned by x0 = a; x1 = b; xn+2 = xn+1 + xn for n = 0; 1; 2; : : : ;

has all of its terms relatively prime to m. Solution. One may take a = 1, b = 2k 2 + k 2b = 4k 2 + 2k 4 2k + 1 (mod m); 4b2 32 2. Since 4k 2 5 (mod m), we obtain 4b + 4 (mod m):

4k 2 + 4k + 1

4k + 6

The last congruence gives b2 b + 1 (mod m), because m is odd. In particular, b is coprime to m. Now an easy induction shows that xn bn (mod m) for all n 0, which is clear for n = 0; 1. Assuming the claim true for indices less than a certain n 2, we obtain xn = xn in view of b2
1

+ xn

2

bn

1

+ bn

2

bn 2 (b + 1)

bn 2 b2

bn (mod m);

b + 1 (mod m). It remains to notice that bn and m are coprime for all n.

Comment by the proposer. Here is the p motivation of the solution above. The 1 Fibonacci recursion has characteristic roots 2 (1 5) in the real domain. To consider the same in the ringp integers modulo m, we need divisibility by 2 (i. e. m being odd) and of the existence of 5 (i. e. 5 being a quadratic residue modulo m). Both of these properties p are ensured by m having the form 4k 2 5. Thep 5 is 2k, or any integer congruent to 2k modulo m. p simplify division by 2, we take 5 to be 2k + m; then the characteristic To 1 root 1 (1 + 5) is represented by 2 (1 + 2k + m) = 2k 2 + k 2 = b. Then, considering 2 the Fibonacci recursion with x0 = 1, x1 = b, we see that modulo m the sequence (xn ) is just (bn ). N5. We call a positive integer alternative if its decimal digits are alternatively odd and even. Find all positive integers n such that n has an alternative multiple. Solution. A positive integer n has an alternative multiple if and only if n is not divisible by 20. If n is divisible by 20 then its last two decimal digits are even, hence no alternative multiple exists. The remaining n have alternative multiples. We consider separately the powers of 2 and the numbers of the form 2 5n . In the sequel, uk jj a means that uk is the highest power of u dividing a. Lemma 1. Each power of 2 has an alternative multiple with an even number of digits. Proof of Lemma 1. It su? ces to construct an in…nite sequence fan g1 of decimal n=1 digits such that an n + 1 (mod 2); 22n
1

jj a2n

1

: : : a1 ;

22n+1 jj a2n a2n

1

: : : a1

for each n. Start with a1 = 2, a2 = 7. If the sequence is constructed up to a2n , set a2n+1 = 4. Then a2n+1 is even and 22n+1 jj a2n+1 a2n : : : a1 = 4 102n + a2n a2n
1

: : : a1 ;

because 22n+1 jj a2n a2n 1 : : : a1 by the inductive hypothesis, and 22n+2 jj 4 102n . Denote a2n+1 : : : a1 = 22n+1 A, with A odd. Now, a2n+2 must be odd and such that 22n+3 jj a2n+2 a2n+1 : : : a1 = a2n+2 102n+1 + a2n+1 a2n : : : a1 = 22n+1 [a2n+2 52n+1 + A]; which holds whenever 5a2n+2 + A 4 (mod 8). The solutions of the last congruence are odd, since A is odd. In addition, a solution a2n+2 can be chosen from f0; 1; : : : ; 7g. The construction is complete. } 33

Lemma 2. Each number of the form 2 5n , n = 1; 2; : : : , has an alternative multiple with an even number of digits. Proof of Lemma 2. We construct an in…nite sequence fbn g1 of decimal digits such n=1 that bn n + 1 (mod 2) and 2 5n divides bn : : : b1 for each n. One can start with b1 = 0, b2 = 5. Suppose that b1 ; : : : ; bn are constructed, and let bn : : : b1 = 5` B, where ` n and B is not divisible by 5. The next digit bn+1 must be such that bn+1 n + 2 (mod 2) and 5n+1 divides bn+1 bn : : : b1 = bn+1 10n + bn : : : b1 = 5n [bn+1 2n + 5`
n

B]:

We pass on to the case of a general n = 2 5 k, where k is coprime to 10. If n is not divisible by 20 then 2 5 is a power of 2, a power of 5, or a number of the form 2 5 . By Lemmas 1 and 2, in all cases 2 5 has an even alternative multiple M with an even number 2m of digits. Clearly, all integers of the form M M : : : M are alternative multiples of 2 5 , too. We prove that some of them is a multiple of n = 2 5 k. Consider the numbers C` = 1 + 102m + + 102m(` 1) ; ` = 1; 2; : : : ; k + 1: Some two of them, C`1 and C`2 with `1 < `2 , are congruent modulo k by the pigeonhole principle. Hence k divides their di¤erence C`2 C`1 = C`2 `1 102m`1 . And because k is coprime to 10, it follows that k divides C`2 `1 . Now it is straightforward that C`2 `1 M , a number of the form M M : : : M , is an alternative multiple of n. N6. Given an integer n > 1, denote by Pn the product of all positive integers x less than n and such that n divides x2 1. For each n > 1, …nd the remainder of Pn on division by n.

The latter is true whenever bn+1 2n + B is divisible by 5. Now, the system of simultaneous congruences bn+1 n + 2 (mod 2), bn+1 2n + B 0 (mod 5) has a solution by the Chinese remainder theorem, since 2n and 5 are coprime. Also, a solution bn+1 can be chosen in f0; 1; : : : ; 9g, as needed. }

Solution. If n = 2, the product Pn equals 1. Assume that n > 2, and let Xn be the set of solutions of the congruence x2 1 (mod n) in f1; 2; : : : ; n 1g. Note that Xn is closed under multiplication and its elements are coprime to n. Also, 1 and n 1 belong to Xn for n > 2. If these are the only elements of Xn , their product is 1 modulo n. Suppose now that Xn contains more than two elements. Choose x1 2 Xn , x1 6= 1, and set A1 = f1; x1 g. There are elements of Xn outside A1 ; let x2 be any of them, and let A2 = A1 [ fx2 ; x1 x2 g = f1; x1 ; x2 ; x1 x2 g. Here and further on all products are taken modulo n. Observe that A2 is is closed under multiplication and contains 22 = 4 numbers. Suppose that for some k > 1 we have de…ned a 2k -element subset Ak of Xn which is closed under multiplication. Check if there are elements of Xn outside Ak ; if so, choose one of them, xk+1 , and put Ak+1 = Ak [ fxxk+1 j x 2 Ak g. It is easy to check that the sets Ak and fxxk+1 j x 2 Ak g are disjoint, and thus Ak+1 Xn has 2k+1 elements. Also, Ak+1 is closed under multiplication. Since Xn is …nite, we conclude that Xn = Am for some m. 34

Now, observe that the product of elements in A2 equals 1, and by construction the same is true for Ak with k > 2. In particular, the product of elements of Am = Xn is 1, so Pn = 1. We now identify when Xn contains more than two elements. Suppose that n = ab, where a > 2 and b > 2 are coprime. By the Chinese remainder theorem, one can …nd integers x and y satisfying x 1 (mod a); x 1 (mod b) and y 1 (mod a); y 1 (mod b):

We may take 1 x; y < ab = n, and since x2 1 (mod n), y 2 1 (mod n), we see that x; y 2 Xn . Also, it is easy to see that 1, x and y are pairwise noncongruent modulo n, because a > 2, b > 2 and n > 2. Thus Xn has more than two elements. The same holds true if n = 2k for some k > 2: then 1, 2k 1 and 2k 1 + 1 are distinct elements of Xn . In all remaining cases, Xn has exactly two elements. This is clear for n = 4. Next, suppose that n = pk for some odd prime p and some positive integer k. Since the greatest common divisor of x 1 and x + 1 is coprime to n, the relation x2 1 (mod n) implies x 1 (mod n) or x 1 (mod n). So the only elements of Xn are 1 and n 1. This also occurs if n = 2pk for some odd prime p and some k > 0. Summing up, we conclude that Xn consists of exactly two elements, 1 and n 1, if n = 2, n = 4, n = pk and n = 2pk for some odd prime p and some positive integer k. In all these cases, Pn = n 1. For the remaining integers n > 1, there are more than two elements in Xn , and hence Pn = 1. Comment by the proposer: The result is a special case of the fact that in a …nite abelian group with more than two elements of order 2 the product of the elements of order 2 is the identity. N7. Let p be an odd prime and n a positive integer. In the coordinate plane, eight distinct points with integer coordinates lie on a circle with diameter of length pn . Prove that there exists a triangle with vertices at three of the given points such that the squares of its side lengths are integers divisible by pn+1 . Solution. A point with integer coordinates will be called an integer point. It is clear that if A and B are integer points then AB 2 is a positive integer. The highest power of the given prime p dividing AB 2 is denoted by (AB) (i. e. (AB) = k if AB 2 is divisible by pk but not by pk+1 ). Note also that if S is the area of a triangle with vertices at integer points, then 2S is an integer. The solution below is based on the following formulas involving the area S of a triangle ABC whose circumcircle has diameter pn : 2AB 2 BC 2 + 2BC 2 CA2 + 2CA2 AB 2 AB 4 BC 4 AB 2 BC 2 CA2 = (2S)2 p2n : CA4 = 16S 2 ; (1) (2)

Lemma. Let A; B and C be integer points on a circle of diameter pn . Then either at least one of (AB); (BC); (CA) is greater than n, or (AB); (BC); (CA) are the numbers n; n; 0, taken in some order. 35

Proof of the lemma. Let m = minf (AB); (BC); (CA)g. By (1), p2m divides (2S)2 , so pm divides 2S. Combined with (2), this implies (AB) + (BC) + (CA) 2m + 2n. Let (AB) n, (BC) n, (CA) n. Then (AB) + (BC) + (CA) m + 2n, and hence 2m + 2n m + 2n, which means that m = 0. So one of (AB); (BC); (CA) is 0, and it is clear that the other two are equal to n. } n Next, we prove that among every four integer points on a circle of diameter p there exist two, P and Q, such that (P Q) n + 1. Assume that this is false for some points A; B; C; D occurring on such a circle in this order. The lemma implies that takes on value 0 for two segments determined by A; B; C; D without common endpoints, and value n for the remaining 4 segments. So we may assume that there are positive integers a; b; c; d; e; f not divisible by p such that AB 2 = a, CD2 = c, BC 2 = bpn , DA2 = dpn , AC 2 =p n , BD2p f pn .p ep = Then Ptolemy’ theorem for the inscribed quadrilateral ABCD s p 2 p n ac bd). Squaring both sides, we obtain ac p p2n ( ef = bd) , so yields p = p ( ef p 2 p p ( ef bd)2 is rational.p However, ( ef bd) = ef + bd p bdef , and this can be 2 p a rational number only if bdef is an integer. But then ( ef bd)2 itself is an integer, p 2 p bd) implies that p2n divides ac, a contradiction. and ac = p2n ( ef Now label the eight given points A1 ; A2 ; : : : ; A8 , draw the line segments they determine, and color black all segments Ai Aj such that (Ai Aj ) n + 1. The number of black segments with endpoint Ai will be called the degree of Ai . Case 1: There is a point of degree at most 1, say A8 . Then at least 6 of the remaining points are not connected to A8 by a black segment. Let such points be A1 ; A2 ; : : : ; A6 . It is a popular fact that if the line segments joining 6 points are colored in two colors then this coloring contains a triangle with sides of the same color. Here this implies that either some triangle with vertices among A1 ; A2 ; : : : ; A6 has three black sides, and the claim follows, or some triangle has three uncolored sides, say A1 A2 A3 . But in the latter case the four points A1 ; A2 ; A3 ; A8 do not determine any black segment, a contradiction. Case 2: All points have degree 2. Clearly, then the black segments partition into cycles. The proof is complete if there is a black cycle of length 3, so let all cycles have length at least 4. Then there are two possibilities: two 4-cycles, say A1 A2 A3 A4 and A5 A6 A7 A8 , or one 8-cycle, A1 A2 A3 A4 A5 A6 A7 A8 . In both cases, the four points A1 ; A3 ; A5 ; A7 do not determine any black segment, a contradiction. Case 3: There is a point of degree at least 3, say A1 . Suppose that A1 A2 , A1 A3 and A1 A4 are black. We claim that at least one segment among A2 A3 , A3 A4 , A4 A2 is black, which will complete the solution. If not, by the lemma (A2 A3 ); (A3 A4 ) (A4 A1 ) are n; n; 0, taken in some order. Assuming that (A2 A3 ) = 0, denote by S the area of the triangle A1 A2 A3 and look again at the formulas (1) and (2). By (1), 2S is not divisible by p. On the other hand, since (A1 A2 ) n + 1 and (A1 A3 ) n + 1, (2) shows that 2S is divisible by p, a contradiction. Comment by the proposer. Let p be a prime of the form p = 4k + 1. Consider the circle with diameter OA, where O(0; 0) and A(pn ; 0). For i = 1; : : : ; n there 2 are integers xi ; yi not divisible by p such that pi = x2 + yi . It is easy to check that i (pn i x2 ; pn i xi yi ) is an integer point on the given circle, i = 1; : : : ; n. Therefore eight i points on a circle with diameter pn do exist for large n. 36

### Appen B - Common Problems & Solutions (2005-04)

IMO 2005 ShortList Probl... 暂无评价 51页 免费 Software performance ant.....Appen B - Common Problems & Solutions (2005-04) 隐藏>> 附录B 一般问题与...

shortlist | fm2016 shortlist | fm2017 shortlist | shortlist ntu | fm2015shortlist | staff shortlist | fdtd solutions | solutions |