tceic.com

简单学习网 让学习变简单

简单学习网 让学习变简单

- IMO_Shortlist_2009
- 2000 IMO shortlist译文
- IMO ShortList 2003 with solutions
- IMO预选题1988(shortlist)
- IMO 2005 ShortList Problems and Solutions
- IMO ShortList Problems and Solutions
- IMO预选题1982(shortlist)
- IMO 2004 ShortList Problems and Solutions
- IMO预选题1989(shortlist)
- IMO预选题1983(shortlist)
- IMO 2004 ShortList Problems and Solutions
- IMO预选题1985(shortlist)
- IMO预选题1984(shortlist)
- IMO预选题1988(shortlist)
- IMO预选题1986(shortlist)

Duˇ san Djuki? c Vladimir Jankovi? c Ivan Mati? c Nikola Petrovi? c

IMO Shortlist 2005

From the book ”The IMO Compendium”

Springer

c 2006 Springer Science+Busi

ness Media, Inc. All rights reserved. This work may not be translated or copied in whole or in part without the written permission of the publisher (Springer Science+Business Media, Inc. 233, Spring Street, New York, NY 10013, USA), except for brief excerpts in connection with reviews or scholary analysis. Use in connection with any form of information storage and retrieval, electronic adaptation, computer software, or by similar or dissimilar methodology now known or hereafter developed is forbidden. The use in this publication of trade names, trademarks, service marks, and similar items, even if they are not identi?ed as such, is not to be taken as an expression of opinion as to whether or not they are subject to proprietary rights.

1 Problems

1.1 The Forty-Sixth IMO M? erida, Mexico, July 8–19, 2005

1.1.1 Contest Problems First Day (July 13) 1. Six points are chosen on the sides of an equilateral triangle ABC : A1 , A2 on BC ; B1 , B2 on CA; C1 , C2 on AB . These points are vertices of a convex hexagon A1 A2 B1 B2 C1 C2 with equal side lengths. Prove that the lines A1 B2 , B1 C2 and C1 A2 are concurrent. 2. Let a1 , a2 , . . . be a sequence of integers with in?nitely many positive terms and in?nitely many negative terms. Suppose that for each positive integer n, the numbers a1 , a2 , . . . , an leave n di?erent remainders on division by n. Prove that each integer occurs exactly once in the sequence. 3. Let x, y and z be positive real numbers such that xyz ≥ 1. Prove that y5 ? y2 z5 ? z2 x5 ? x2 + + ≥ 0. x5 + y 2 + z 2 y 5 + z 2 + x2 z 5 + x2 + y 2 Second Day (July 14) 4. Consider the sequence a1 , a2 , . . . de?ned by an = 2 n + 3 n + 6 n ? 1 (n = 1, 2, . . . ).

Determine all positive integers that are relatively prime to every term of the sequence. 5. Let ABCD be a given convex quadrilateral with sides BC and AD equal in length and not parallel. Let E and F be interior points of the sides

2

1 Problems

BC and AD respectively such that BE = DF . The lines AC and BD meet at P , the lines BD and EF meet at Q, the lines EF and AC meet at R. Consider all the triangles P QR as E and F vary. Show that the circumcircles of these triangles have a common point other than P . 6. In a mathematical competition 6 problems were posed to the contestants. Each pair of problems was solved by more than 2/5 of the contestants. Nobody solved all 6 problems. Show that there were at least 2 contestants who each solved exactly 5 problems. 1.1.2 Shortlisted Problems 1. A1 (ROM) Find all monic polynomials p(x) with integer coe?cients of degree two for which there exists a polynomial q (x) with integer coe?cients such that p(x)q (x) is a polynomial having all coe?cients ±1. 2. A2 (BUL) Let R+ denote the set of positive real numbers. Determine all functions f : R+ → R+ such that f (x)f (y ) = 2f (x + yf (x)) for all positive real numbers x and y . 3. A3 (CZE) Four real numbers p, q, r, s satisfy p+q+r+s=9 and p2 + q 2 + r2 + s2 = 21.

Prove that ab ? cd ≥ 2 holds for some permutation (a, b, c, d) of (p, q, r, s). 4. A4 (IND) Find all functions f : R → R satisfying the equation f (x + y ) + f (x)f (y ) = f (xy ) + 2xy + 1 for all real x and y . 5. A5 (KOR)IMO3 Let x, y and z be positive real numbers such that xyz ≥ 1. Prove that x5 ? x2 y5 ? y2 z5 ? z2 + + ≥ 0. x5 + y 2 + z 2 y 5 + z 2 + x2 z 5 + x2 + y 2 6. C1 (AUS) A house has an even number of lamps distributed among its rooms in such a way that there are at least three lamps in every room. Each lamp shares a switch with exactly one other lamp, not necessarily from the same room. Each change in the switch shared by two lamps changes their states simultaneously. Prove that for every initial state of the lamps there exists a sequence of changes in some of the switches at the end of which each room contains lamps which are on as well as lamps which are o?.

1.1 Copyright c : The Authors and Springer

3

7. C2 (IRN) Let k be a ?xed positive integer. A company has a special method to sell sombreros. Each customer can convince two persons to buy a sombrero after he/she buys one; convincing someone already convinced does not count. Each of these new customers can convince two others and so on. If each one of the two customers convinced by someone makes at least k persons buy sombreros (directly or indirectly), then that someone wins a free instructional video. Prove that if n persons bought sombreros, then at most n/(k + 2) of them got videos. 8. C3 (IRN) In an m × n rectangular board of mn unit squares, adjacent squares are ones with a common edge, and a path is a sequence of squares in which any two consecutive squares are adjacent. Each square of the board can be colored black or white. Let N denote the number of colorings of the board such that there exists at least one black path from the left edge of the board to its right edge, and let M denote the number of colorings in which there exist at least two non-intersecting black paths from the left edge to the right edge. Prove that N 2 ≥ 2mn M . 9. C4 (COL) Let n ≥ 3 be a given positive integer. We wish to label each side and each diagonal of a regular n-gon P1 . . . Pn with a positive integer less than or equal to r so that: (i) every integer between 1 and r occurs as a label; (ii) in each triangle Pi Pj Pk two of the labels are equal and greater than the third. Given these conditions: (a) Determine the largest positive integer r for which this can be done. (b) For that value of r, how many such labellings are there? 10. C5 (SMN) There are n markers, each with one side white and the other side black, aligned in a row so that their white sides are up. In each step, if possible, we choose a marker with the white side up (but not one of outermost markers), remove it and reverse the closest marker to the left and the closest marker to the right of it. Prove that one can achieve the state with only two markers remaining if and only if n ? 1 is not divisible by 3. 11. C6 (ROM)IMO6 In a mathematical competition 6 problems were posed to the contestants. Each pair of problems was solved by more than 2/5 of the contestants. Nobody solved all 6 problems. Show that there were at least 2 contestants who each solved exactly 5 problems. 12. C7 (USA) Let n ≥ 1 be a given integer, and let a1 , . . . , an be a sequence of integers such that n divides the sum a1 + · · · + an . Show that there exist permutations σ and τ of 1, 2, . . . , n such that σ (i) + τ (i) ≡ ai (mod n) for all i = 1, . . . , n. 13. C8 (BUL) Let M be a convex n-gon, n ≥ 4. Some n ? 3 of its diagonals are colored green and some other n ? 3 diagonals are colored red, so that

4

1 Problems

no two diagonals of the same color meet inside M . Find the maximum possible number of intersection points of green and red diagonals inside M. 14. G1 (GRE) In a triangle ABC satisfying AB + BC = 3AC the incircle has center I and touches the sides AB and BC at D and E , respectively. Let K and L be the symmetric points of D and E with respect to I . Prove that the quadrilateral ACKL is cyclic. 15. G2 (ROM)IMO1 Six points are chosen on the sides of an equilateral triangle ABC : A1 , A2 on BC ; B1 , B2 on CA; C1 , C2 on AB . These points are vertices of a convex hexagon A1 A2 B1 B2 C1 C2 with equal side lengths. Prove that the lines A1 B2 , B1 C2 and C1 A2 are concurrent. 16. G3 (UKR) Let ABCD be a parallelogram. A variable line l passing through the point A intersects the rays BC and DC at points X and Y , respectively. Let K and L be the centers of the excircles of triangles ABX and ADY , touching the sides BX and DY , respectively. Prove that the size of angle KCL does not depend on the choice of the line l. 17. G4 (POL)IMO5 Let ABCD be a given convex quadrilateral with sides BC and AD equal in length and not parallel. Let E and F be interior points of the sides BC and AD respectively such that BE = DF . The lines AC and BD meet at P , the lines BD and EF meet at Q, the lines EF and AC meet at R. Consider all the triangles P QR as E and F vary. Show that the circumcircles of these triangles have a common point other than P . 18. G5 (ROM) Let ABC be an acute-angled triangle with AB = AC , let H be its orthocenter and M the midpoint of BC . Points D on AB and E on AC are such that AE = AD and D, H, E are collinear. Prove that HM is orthogonal to the common chord of the circumcircles of triangles ABC and ADE . 19. G6 (RUS) The median AM of a triangle ABC intersects its incircle ω at K and L. The lines through K and L parallel to BC intersect ω again at X and Y . The lines AX and AY intersect BC at P and Q. Prove that BP = CQ. 20. G7 (KOR) In an acute triangle ABC , let D, E , F , P , Q, R be the feet of perpendiculars from A, B , C , A, B , C to BC , CA, AB , EF , F D, DE , respectively. Prove that p(ABC )p(P QR) ≥ p(DEF )2 , where p(T ) denotes the perimeter of triangle T . 21. N1 (POL)IMO4 Consider the sequence a1 , a2 , . . . de?ned by an = 2 n + 3 n + 6 n ? 1 (n = 1, 2, . . . ).

Determine all positive integers that are relatively prime to every term of the sequence.

1.1 Copyright c : The Authors and Springer

5

22. N2 (NET)IMO2 Let a1 , a2 , . . . be a sequence of integers with in?nitely many positive terms and in?nitely many negative terms. Suppose that for each positive integer n, the numbers a1 , a2 , . . . , an leave n di?erent remainders on division by n. Prove that each integer occurs exactly once in the sequence. 23. N3 (MON) Let a, b, c, d, e and f be positive integers. Suppose that the sum S = a + b + c + d + e + f divides both abc + def and ab + bc + ca ? de ? ef ? f d. Prove that S is composite. 24. N4 (COL) Find all positive integers n > 1 for which there exists a unique integer a with 0 < a ≤ n! such that an + 1 is divisible by n!. 25. N5 (NET) Denote by d(n) the number of divisors of the positive integer n. A positive integer n is called highly divisible if d(n) > d(m) for all positive integers m < n. Two highly divisible integers m and n with m < n are called consecutive if there exists no highly divisible integer s satisfying m < s < n. (a) Show that there are only ?nitely many pairs of consecutive highly divisible integers of the form (a, b) with a|b. (b) Show that for every prime number p there exist in?nitely many positive highly divisible integers r such that pr is also highly divisible. 26. N6 (IRN) Let a and b be positive integers such that an + n divides bn + n for every positive integer n. Show that a = b. 27. N7 (RUS) Let P (x) = an xn + an?1 xn?1 + · · · + a0 , where a0 , . . . , an are integers, an > 0, n ≥ 2. Prove that there exists a positive integer m such that P (m!) is a composite number.

2 Solutions

8

2 Solutions

2.1 Solutions to the Shortlisted Problems of IMO 2005

1. Clearly, p(x) has to be of the form p(x) = x2 + ax ± 1 where a is an integer. For a = ±1 and a = 0 polynomial p has the required property: it su?ces to take q = 1 and q = x + 1, respectively. Suppose now that |a| ≥ 2. Then p(x) has two real roots, say x1 , x2 , which are also roots of p(x)q (x) = xn + an?1 xn?1 + · · · + a0 , ai = ±1. Thus 1= a0 1 1 1 an?1 + ··· + n ≤ < + ··· + n xi xi |xi | |xi | |xi | ? 1

which implies |x1 |, |x2 | < 2. This immediately rules out the case |a| ≥ 3 and the polynomials p(x) = x2 ± 2x ? 1. The remaining two polynomials x2 ± 2x + 1 satisfy the condition for q (x) = x ? 1. Summing all, the polynomials p(x) with the desired property are x2 ± x ± 1, x2 ± 1 and x2 ± 2x + 1. 2. Given y > 0, consider the function ?(x) = x + yf (x), x > 0. This function is injective: indeed, if ?(x1 ) = ?(x2 ) then f (x1 )f (y ) = f (?(x1 )) = f (?(x2 )) = f (x2 )f (y ), so f (x1 ) = f (x2 ), so x1 = x2 by the de?nition of ?. Now if x1 > x2 and f (x1 ) < f (x2 ), we have ?(x1 ) = ?(x2 ) for 1 ?x 2 > 0, which is impossible; hence f is non-decreasing. The y = f (xx 2 )?f (x 1 ) functional equation now yields f (x)f (y ) = 2f (x + yf (x)) ≥ 2f (x) and consequently f (y ) ≥ 2 for y > 0. Therefore f (x + yf (x)) = f (xy ) = f (y + xf (y )) ≥ f (2x) holds for arbitrarily small y > 0, implying that f is constant on the interval (x, 2x] for each x > 0. But then f is constant on the union of all intervals (x, 2x] over all x > 0, that is, on all of R+ . Now the functional equation gives us f (x) = 2 for all x, which is clearly a solution. Second Solution. In the same way as above we prove that f is nondecreasing, hence its discontinuity set is at most countable. We can extend f to R ∪ {0} by de?ning f (0) = inf x f (x) = limx→0 f (x) and the new function f is continuous at 0 as well. If x is a point of continuity of f we have f (x)f (0) = limy→0 f (x)f (y ) = limy→0 2f (x + yf (x)) = 2f (x), hence f (0) = 2. Now, if f is continuous at 2y then 2f (y ) = limx→0 f (x)f (y ) = limx→0 2f (x + yf (x)) = 2f (2y ). Thus f (y ) = f (2y ), for all but countably many values of y . Being non-decreasing f is a constant, hence f (x) = 2. 3. Assume w.l.o.g. that p ≥ q ≥ r ≥ s. We have (pq +rs)+(pr +qs)+(ps+qr) = (p + q + r + s)2 ? p2 ? q 2 ? r2 ? s2 = 30. 2

It is easy to see that pq + rs ≥ pr + qs ≥ ps + qr which gives us pq + rs ≥ 10. Now setting p + q = x we obtain x2 + (9 ? x)2 = (p + q )2 + (r + s)2 =

2.1 Copyright c : The Authors and Springer

9

21 + 2(pq + rs) ≥ 41 which is equivalent to (x ? 4)(x ? 5) ≥ 0. Since x = p + q ≥ r + s we conclude that x ≥ 5. Thus 25 ≤ p2 + q 2 + 2pq = 21 ? (r2 + s2 ) + 2pq ≤ 21 + 2(pq ? rs), or pq ? rs ≥ 2, as desired. Remark. The quadruple (p, q, r, s) = (3, 2, 2, 2) shows that the estimate 2 is best possible. 4. Setting y = 0 yields (f (0) + 1)(f (x) ? 1) = 0, and since f (x) = 1 for all x is impossible, we get f (0) = ?1. Now plugging in x = 1 and y = ?1 gives us f (1) = 1 or f (?1) = 0. In the ?rst case setting x = 1 in the functional equation yields f (y + 1) = 2y + 1, i.e. f (x) = 2x ? 1 which is one solution. Suppose now that f (1) = a = 1 and f (?1) = 0. Plugging (x, y ) = (z, 1) and (x, y ) = (?z, ?1) in the functional equation yields f (z + 1) = (1 ? a)f (z ) + 2z + 1 f (?z ? 1) = f (z ) + 2z + 1. (?)

It follows that f (z + 1) = (1 ? a)f (?z ? 1) + a(2z + 1), i.e. f (x) = (1 ? a)f (?x) + a(2x ? 1). Analogously f (?x) = (1 ? a)f (x) + a(?2x ? 1), which together with the previous equation yields (a2 ? 2a)f (x) = ?2a2 x ? (a2 ? 2a).

2ax Now a = 2 is clearly impossible. For a ∈ {0, 2} we get f (x) = ? a?2 ? 1. This function satis?es the requirements only for a = ?2, giving the solution f (x) = ?x ? 1. In the remaining case, when a = 0, we have f (x) = f (?x). Setting y = z and y = ?z in the functional equation and subtracting yields f (2z ) = 4z 2 ? 1, so f (x) = x2 ? 1 which satis?es the equation. Thus the solutions are f (x) = 2x ? 1, f (x) = ?x ? 1 and f (x) = x2 ? 1.

5. The desired inequality is equivalent to x2 + y 2 + z 2 x2 + y 2 + z 2 x2 + y 2 + z 2 + + ≤ 3. x5 + y 2 + z 2 y 5 + z 2 + x2 z 5 + x2 + y 2 (?)

By the Cauchy inequality we have (x5 + y 2 + z 2 )(yz + y 2 + z 2 ) ≥ (x5/2 (yz )1/2 + y 2 + z 2 )2 ≥ (x2 + y 2 + z 2 )2 and therefore x2 + y 2 + z 2 yz + y 2 + z 2 ≤ . x5 + y 2 + z 2 x2 + y 2 + z 2 We get analogous inequalities for the other two summands in (?). Summing these up yields x2 + y 2 + z 2 x2 + y 2 + z 2 xy + yz + zx x2 + y 2 + z 2 + + ≤2+ 2 , 5 2 2 5 2 2 5 2 2 x +y +z y +z +x z +x +y x + y2 + z 2

10

2 Solutions

which together with the well-known inequality x2 + y 2 + z 2 ≥ xy + yz + zx gives us the result. Second solution. Multiplying the both sides with the common denominator and using the notation as in Chapter 2 (Muirhead’s inequality) we get T5,5,5 + 4T7,5,0 + T5,2,2 + T9,0,0 ≥ T5,5,2 + T6,0,0 + 2T5,4,0 + 2T4,2,0 + T2,2,2 . By Schur’s and Muirhead’s inequalities we have that T9,0,0 + T5,2,2 ≥ 2T7,2,0 ≥ 2T7,1,1 . Since xyz ≥ 1 we have that T7,1,1 ≥ T6,0,0 . Therefore T9,0,0 + T5,2,2 ≥ 2T6,0,0 ≥ T6,0,0 + T4,2,0 . (1)

Moreover, Muirhead’s inequality combined with xyz ≥ 1 gives us T7,5,0 ≥ T5,5,2 , 2T7,5,0 ≥ 2T6,5,1 ≥ 2T5,4,0 , T7,5,0 ≥ T6,4,2 ≥ T4,2,0 , and T5,5,5 ≥ T2,2,2 . Adding these four inequalities to (1) yields the desired result. 6. A room will be called economic if some of its lamps are on and some are o?. Two lamps sharing a switch will be called twins. The twin of a lamp l will be denoted ? l. Suppose we have arrived at a state with the minimum possible number of uneconomic rooms, and that this number is strictly positive. Let us choose any uneconomic room, say R0 , and a lamp l0 in it. Let l? 0 be in a room R1 . Switching l0 we make R0 economic; thereby, since the number of uneconomic rooms cannot be decreased, this change must make room R1 uneconomic. Now choose a lamp l1 in R1 having the twin l? 1 in a room R2 . Switching l1 makes R1 economic, and thus must make R2 uneconomic. Continuing in this manner we obtain a sequence l0 , l1 , . . . of lamps with ? li in a room Ri and l i = li+1 in Ri+1 for all i. The lamps l0 , l1 , . . . are switched in this order. This sequence has the property that switching li ? and l i makes room Ri economic and room Ri+1 uneconomic. Let Rm = Rk with m > k be the ?rst repetition in the sequence (Ri ). Let us stop switching the lamps at lm?1 . The room Rk was uneconomic prior to switching lk . Thereafter lamps lk and ? lm?1 have been switched in Rk , but since these two lamps are distinct (indeed, their twins l? k and lm?1 are distinct), the room Rk is now economic as well as all the rooms R0 , R1 , . . . , Rm?1 . This decreases the number of uneconomic rooms, contradicting our assumption. 7. Let v be the number of video winners. One easily ?nds that for v = 1 and v = 2, the number n of customers is at least 2k + 3 and 3k + 5 respectively. We prove by induction on v that if n ≥ k + 1 then n ≥ (k + 2)(v + 1) ? 1. We can assume w.l.o.g. that the total number n of customers is minimum possible for given v > 0. Consider a person P who was convinced by nobody but himself. Then P must have won a video; otherwise P could be removed from the group without decreasing the number of video winners. Let Q and R be the two persons convinced by P . We denote by C the set of persons made by P through Q to buy a sombrero, including Q, and

2.1 Copyright c : The Authors and Springer

11

by D the set of all other customers excluding P . Let x be the number of video winners in C . Then there are v ? x ? 1 video winners in D. We have |C| ≥ (k + 2)(x + 1) ? 1, by induction hypothesis if x > 0 and because P is a winner if x = 0. Similarly, |D| ≥ (k + 2)(v ? x) ? 1. Thus n ≥ 1 + (k + 2)(x + 1) ? 1 + (k + 2)(v ? x) ? 1, i.e. n ≥ (k + 2)(v + 1) ? 1. 8. Suppose that a two-sided m × n board T is considered, where exactly k of the squares are transparent. A transparent square is colored only on one side (then it looks the same from the other side), while a non-transparent one needs to be colored on both sides, not necessarily in the same color. Let C = C (T ) be the set of colorings of the board in which there exist two black paths from the left edge to the right edge, one on top and one underneath, not intersecting at any transparent square. If k = 0 then |C | = N 2 . We prove by induction on k that 2k |C | ≤ N 2 : this will imply the statement of the problem, as |C | = M for k = mn. Let q be a ?xed transparent square. Consider any coloring B in C : If q is converted into a non-transparent square, a new board T ′ with k ? 1 transparent squares is obtained, so by the induction hypothesis 2k?1 |C (T ′ )| ≤ N 2 . Since B contains two black paths at most one of which passes through q , coloring q in either color on the other side will result in a coloring in C ′ ; hence |C (T ′ )| ≥ 2|C (T )|, implying 2k |C (T )| ≤ N 2 and ?nishing the induction. Second solution. By path we shall mean a black path from the left edge to the right edge. Let A denote the set of pairs of m × n boards each of which has a path. Let B denote the set of pairs of boards such that the ?rst board has two non-intersecting paths. Obviously, |A| = N 2 and |B| = 2mn M . To show |A| ≥ |B| we will construct an injection f : B → A. Among paths on a given board we de?ne path x to be lower than y if the set of squares “under” x is a subset of the squares under y . This relation is a relation of incomplete order. However, for each board with at least one path there exists the lowest path (comparing two intersecting paths, we can always take the “lower branch” on each non-intersecting segment). Now, for a given element of B , we “swap” the lowest path and all squares underneath on the ?rst board with the corresponding points on the other board. This swapping operation is the desired injection f . Indeed, since the ?rst board still contains the highest path (which didn’t intersect the lowest one), the new con?guration belongs to A. On the other hand, this con?guration uniquely determines the lowest path on the original element of B ; hence no two di?erent elements of B can go to the same element of A. This completes the proof. 9. Let [XY ] denote the label of segment XY , where X and Y are vertices of the polygon. Consider any segment M N with the maximum label [M N ] = r. By condition (ii), for any Pi = M, N , exactly one of Pi M and Pi N is labelled by r. Thus the set of all vertices of the n-gon splits into two complementary groups: A = {Pi | [Pi M ] = r} and B = {Pi | [Pi N ] = r}.

12

2 Solutions

We claim that a segment XY is labelled by r if and only if it joins two points from di?erent groups. Assume w.l.o.g. that X ∈ A. If Y ∈ A, then [XM ] = [Y M ] = r, so [XY ] < r. If Y ∈ B , then [XM ] = r and [Y M ] < r, so [XY ] = r by (ii), as we claimed. We conclude that a labelling satisfying (ii) is uniquely determined by groups A and B and labellings satisfying (ii) within A and B . (a) We prove by induction on n that the greatest possible value of r is n ? 1. The degenerate cases n = 1, 2 are trivial. If n ≥ 3, the number of di?erent labels of segments joining vertices in A (resp. B ) does not exceed |A| ? 1 (resp. |B| ? 1), while all segments joining a vertex in A and a vertex in B are labelled by r. Therefore r ≤ (|A| ? 1) + (|B| ? 1) + 1 = n ? 1. The equality is achieved if all the mentioned labels are di?erent. (b) Let an be the number of labellings with r = n ? 1. We prove by n?1)! induction that an = n!( 2n?1 . This is trivial for n = 1, so let n ≥ 2. If |A| = k is ?xed, the groups A and B can be chosen in n k ways. The set of labels used within A can be selected among 1, 2, . . . , n ? 2 in n?2 k?1 ways. Now the segments within groups A and B can be labelled so as to satisfy (ii) in ak and an?k ways, respectively. This way every labelling has been counted twice, since choosing A is equivalent to choosing B . It follows that an = 1 2

n?1

k=1

n k

n?2 ak an?k k?1

n?1

n!(n ? 1)! = 2(n ? 1) = n!(n ? 1)! 2(n ? 1)

k=1 n?1

an?k ak · k !(k ? 1)! (n ? k )!(n ? k ? 1)! 1 n!(n ? 1)! 1 · = . 2k?1 2n?k?1 2n?1

k=1

10. Denote by L the leftmost and by R the rightmost marker. To start with, note that the parity of the number of black-side-up markers remains unchanged. Hence, if only two markers remain, these markers must have the same color up. We ’ll show by induction on n that the game can be successfully ?nished if and only if n ≡ 0 or n ≡ 2 (mod 3), and that the upper sides of L and R will be black in the ?rst case and white in the second case. The statement is clear for n = 2, 3. Assume that we ?nished the game for some n, and denote by k the position of the marker X (counting from the left) that was last removed. Having ?nished the game, we have also ?nished the subgames with the k markers from L to X and with the n ? k + 1 markers from X to R (inclusive). Thereby, before X was removed, the upper side of L had been black if k ≡ 0 and white if k ≡ 2 (mod 3), while the upper side of R had been black if n ? k + 1 ≡ 0 and

2.1 Copyright c : The Authors and Springer

13

white if n ? k + 1 ≡ 2 (mod 3). Markers L and R were reversed upon the removal of X . Therefore, in the ?nal position L and R are white if and only if k ≡ n ? k + 1 ≡ 0, which yields n ≡ 2 (mod 3), and black if and only if k ≡ n ? k + 1 ≡ 2, which yields n ≡ 0 (mod 3). On the other hand, a game with n markers can be reduced to a game with n ? 3 markers by removing the second, fourth, and third marker in this order. This ?nishes the induction. Second solution. An invariant can be de?ned as follows. To each white marker with k black markers to its left we assign the number (?1)k . Let S be the sum of the assigned numbers. Then it is easy to verify that the remainder of S modulo 3 remains unchanged throughout the game: For example, when a white marker with two white neighbors and k black markers to its left is removed, S decreases by 3(?1)t . Initially, S = n. In the ?nal position with two markers remained S equals 0 if the two markers are black and 2 if these are white (note that, as before, the two markers must be of the same color). Thus n ≡ 0 or 2 (mod 3). Conversely, a game with n markers is reduced to n ? 3 markers as in the ?rst solution. 11. Assume there were n contestants, ai of whom solved exactly i problems, where a0 + · · · + a5 = n. Let us count the number N of pairs (C, P ), where contestant C solved the pair of problems P . Each of the 15 pairs +1 contestants, implying N ≥ 15 · of problems was solved by at least 2n5 1) 2n+1 = 6 n + 3. On the other hand, a students solved i(i? pairs; hence i 5 2 6n + 3 ≤ N ≤ a2 + 3a3 + 6a4 + 10a5 = 6n + 4a5 ? (3a3 + 5a2 + 6a1 + 6a0 ). Consequently a5 ≥ 1. Assume that a5 = 1. Then we must have N = 6n +4, which is only possible if 14 of the pairs of problems were solved by exactly +1 2n+1 students and the remaining one by 2n5 +1 students, and all students 5 but the winner solved 4 problems. The problem t not solved by the winner will be called tough and the pair +1 + 1 students special. of problems solved by 2n5 Let us count the number Mp of pairs (C, P ) for which P contains a ?xed problem p. Let bp be the number of contestants who solved p. Then Mt = 3bt (each of the bt students solved three pairs of problems containing t), and Mp = 3bp + 1 for p = t (the winner solved four such pairs). On the +1 other hand, each of the ?ve pairs containing p was solved by 2n5 or 2n+1 + 1 students, so M = 2 n + 2 if the special pair contains p , and p 5 Mp = 2n + 1 otherwise. Now since Mt = 3bt = 2n + 1 or 2n + 2, we have 2n + 1 ≡ 0 or 2 (mod 3). But if p = t is a problem not contained in the special pair, we have Mp = 3bp +1 = 2n +1; hence 2n +1 ≡ 1 (mod 3), which is a contradiction. 12. Suppose that there exist desired permutations σ and τ for some sequence a1 , . . . , an . Given a sequence (bi ) with sum divisible by n which di?ers

14

2 Solutions

modulo n from (ai ) only in two positions, say i1 and i2 , we show how to construct desired permutations σ ′ and τ ′ for sequence (bi ). In this way, starting from an arbitrary sequence (ai ) for which σ and τ exist, we can construct desired permutations for any other sequence with sum divisible by n. All congruences below are modulo n. We know that σ (i) + τ (i) ≡ bi for all i = i1 , i2 . We construct the sequence i1 , i2 , i3 , . . . as follows: for each k ≥ 2, ik+1 is the unique index such that σ (ik?1 ) + τ (ik+1 ) ≡ bik . (?) Let ip = iq be the repetition in the sequence with the smallest q . We claim that p = 1 or p = 2. Assume on the contrary that p > 2. Summing up (?) for k = p, p + 1, . . . , q ? 1 and taking the equalities σ (ik ) + τ (ik ) = bik for ik = i1 , i2 into account we obtain σ (ip?1 ) + σ (ip ) + τ (iq?1 ) + τ (iq ) ≡ bp + bq?1 . Since iq = ip , it follows that σ (ip?1 ) + τ (iq?1 ) ≡ bq?1 and therefore ip?1 = iq?1 , a contradiction. Thus p = 1 or p = 2 as claimed. Now we de?ne the following permutations: σ ′ (ik ) = σ (ik?1 ) for k = 2, 3, . . . , q ? 1 and σ ′ (i1 ) = σ (iq?1 ), τ (i2 ) if p = 1, τ ′ (ik ) = τ (ik+1 ) for k = 2, 3, . . . , q ? 1 and τ ′ (i1 ) = τ (i1 ) if p = 2; σ ′ (i) = σ (i) and τ ′ (i) = τ (i) for i ∈ {i1 , . . . , iq?1 }. Permutations σ ′ and τ ′ have the desired property. Indeed, σ ′ (i)+ τ ′ (i) = bi obviously holds for all i = i1 , but then it must also hold for i = i1 . 13. For every green diagonal d, let Cd denote the number of green-red intersection points on d. The task is to ?nd the maximum possible value of the sum d Cd over all green diagonals. Let di and dj be two green diagonals and let the part of polygon M lying between di and dj have m vertices. There are at most n ? m ? 1 red diagonals intersecting both di and dj , while each of the remaining m ? 2 diagonals meets at most one of di , dj . It follows that Cdi + Cdj ≤ 2(n ? m ? 1) + (m ? 2) = 2n ? m ? 4. (?) We now arrange the green diagonals in a sequence d1 , d2 , . . . , dn?3 as follows. It is easily seen that there are two green diagonals d1 and d2 that divide M into two triangles and an (n ? 2)-gon; then there are two green diagonals d3 and d4 that divide the (n ? 2)-gon into two triangles and an (n ? 4)-gon, and so on. We continue this procedure until we end up with a triangle or a quadrilateral. Now the part of M between d2k?1 and d2k has at least n ? 2k vertices for 1 ≤ k ≤ r, where n ? 3 = 2r + e, e ∈ {0, 1}; hence, by (?), Cd2k?1 + Cd2k ≤ n + 2k ? 4. Moreover, Cdn?3 ≤ n ? 3. Summing up yields r Cd1 + Cd2 + · · · + Cdn?3 ≤ (n + 2k ? 4) + e(n ? 3)

k=1

= 3r2 + e(3r + 1) =

3 (n ? 3)2 . 4

2.1 Copyright c : The Authors and Springer

15

This value is attained in the following example. Let A1 A2 . . . An be the n-gon M and let l = n 2 + 1. The diagonals A1 Ai , i = 3, . . . , l and Al Aj , j = l + 2, . . . , n are colored in green, whereas the diagonals A2 Ai , i = l + 1, . . . , n, and Al+1 Aj , j = 3, . . . , l ? 1 are colored in red. 3 (n ? 3)2 ?. Thus the answer is ? 4 14. Let F be the point of tangency of the incircle with AC and let M and N be the respective points of tangency of AB and BC with the corresponding excircles. If I is the incenter and Ia and P respectively the center and the tangency point with ray AC of the excircle corresponding to A, we AIa AIa AI have AI IL = IF = Ia P = Ia N , which implies that △AIL ? △AIa N . Thus L lies on AN , and analogously K lies on CM . Denote x = AF and y = CF . Since BD = BE , AD = BM = x, and CE = BN = y , the condition AB + BC = 3AC gives us DM = y and EN = x. Now the triangles CLN and M KA are congruent since their altitudes KD and LE satisfy DK = EL, DM = CE , and AD = EN . Thus ∠AKM = ∠CLN , implying that ACKL is cyclic. 15. Let P be the fourth vertex of the rhombus C2 A1 A2 P . Since △C2 P C1 is equilateral, we easily conclude that B1 B2 C1 P is also a rhombus. Thus △P B1 A2 is equilateral and ∠(C2 A1 , C1 B2 ) = ∠A2 P B1 = 60? . It easily follows that △AC1 B2 ? = △BA1 C2 and consequently AC1 = BA1 ; similarly BA1 = CB1 . Therefore triangle A1 B1 C1 is equilateral. Now it follows from B1 B2 = B2 C1 that A1 B2 bisects ∠C1 A1 B1 . Similarly, B1 C2 and C1 A2 bisect ∠A1 B1 C1 and ∠B1 C1 A1 ; hence A1 B2 , B1 C2 , C1 A2 meet at the incenter of A1 B1 C1 , i.e. at the center of ABC .

1 16. Since ∠ADL = ∠KBA = 180? ? 1 2 ∠BCD and ∠ALD = 2 ∠AY D = BK AB ∠KAB , triangles ABK and LDA are similar. Thus BK BC = AD = DL = DC DL , which together with ∠LDC = ∠CBK gives us △LDC ? △CBK . Therefore ∠KCL = 360? ? ∠BCD ? (∠LCD + ∠KCB ) = 360? ? ∠BCD ? (∠CKB + ∠KCB ) = 180? ? ∠CBK , which is constant.

17. To start with, we note that points B, E, C are the images of D, F, A respectively under the rotation around point O for the angle ω = ∠DOB , where O is the intersection of the perpendicular bisectors of AC and BD. Then OE = OF and ∠OF E = ∠OAC = 90 ? ω 2 ; hence the points A, F, R, O are on a circle and ∠ORP = 180? ?∠OF A. Analogously, the points B, E, Q, O are on a circle and ∠OQP = 180? ? ∠OEB = ∠OEC = ∠OF A. This shows that ∠ORP = 180? ? ∠OQP , i.e. the point O lies on the circumcircle of △P QR, thus being the desired point. 18. Let O and O1 be the circumcenters of triangles ABC and ADE , respectively. It is enough to show that HM OO1 . Let AA′ be the diameter of the circumcircle of ABC . We note that if B1 is the foot of the altitude from B , then HE bisects ∠CHB1 . Since the triangles COM

16

2 Solutions

and CHB1 are similar (indeed, ∠CHB = ∠COM = ∠A), we have CE 2CO A′ A CH CO EB1 = HB1 = OM = AH = AH .

A Thus, if Q is the intersection point of the bisector of ∠A′ AH with HA′ , B1 ′ Q CE = A we obtain EB QH , which to1 O1 gether with A′ C ⊥ AC and HB1 ⊥ E AC gives us QE ⊥ AC . AnaloO D H gously, QD ⊥ AB . Therefore AQ Q is a diameter of the circumcircle of B C M △ADE and O1 is the midpoint of AQ. It follows that OO1 is a middle A′ line in △A′ AQ which is parallel to HM . Second solution. We again prove that OO1 HM . Since AA′ = 2AO, it su?ces to prove AQ = 2AO1 . Elementary calculations of angles give us ∠ADE = ∠AED = 90? ? α 2. Applying the sine theorem to △DAH and △EAH we now have DE = AH cos γ cos β DH + EH = AH cos α + cos α . Since AH = 2OM = 2R cos α, we obtain

2 2

AO1 =

β ?γ 2R cos α sin α AH (cos β + cos γ ) DE 2 cos( 2 ) = . = 2 sin α 2 sin α cos α sin α cos α 2 2

We now calculate AQ. Let N be the intersection of AQ with the circumγ β ?γ circle. Since ∠N AO = β ? 2 , we have AN = 2R cos( 2 ). Noting that △QAH ? △QN M (and that M N = R ? OM ), we have AQ =

γ γ 2R cos( β ? 2R cos( β ? AN · AH 2 ) · 2 cos α 2 ) cos α = 2AO1 . = = M N + AH 1 + cos α cos2 α 2

19. We denote by D, E, F the points A of tangency of the incircle with BC, CA, AB , respectively, by I the I′ incenter, and by Y ′ the intersection X K E of AX and LY . Since EF is the polar line to the point A with reR spect to the incircle, it meets AL F I at point R such that A, R; K, L are KA conjugated, i.e. KR RL = AL . Then L KR KX KA KX Y Y′ LY ′ = AL = RL = LY and thereC Q D M P fore LY = LY , where Y is the inter- B ′ section of XR and LY . Thus showing that LY = LY (which is the same as showing that P M = M Q, i.e. CP = QC ) is equivalent to showing that XY contains R. Since XKY L is an inscribed trapezoid, it is enough to show that R lies on its axis of symmetry, that is, DI .

2.1 Copyright c : The Authors and Springer

17

ER ′ Hence AB AC = F R . Let I be the point of intersction of the line through FR AC I′ ′ F parallel to IE with the line IR. Then F EI = RE = AB and ∠I F I = ∠BAC (angles with orthogonal rays). Thus the triangles ABC and F II ′ are similar, implying that ∠F II ′ = ∠ABC . Since ∠F ID = 180? ? ∠ABC , it follows that R, I , and D are collinear.

Since AM is the median, the triangles ARB and ARC have equal areas S△ABR (AB ·F R) = ( and since ∠(RF, AB ) = ∠(RE, AC ) we have that 1 = S△ AC ·ER) . ACR

20. We shall show the inequalities p(ABC ) ≥ 2p(DEF ) and p(P QR) ≥ 1 2 p(DEF ). The statement of the problem will immediately follow. Let Db and Dc be the re?ections of D in AB and AC , and let A1 , B1 , C1 be the midpoints of BC, CA, AB , respectively. It is easy to see that Db , F, E, Dc are collinear. Hence p(DEF ) = Db F + F E + EDc = Db Dc ≤ 1 Db C1 + C1 B1 + B1 Dc = 1 2 (AB + BC + CA) = 2 p(ABC ). To prove the second inequality we observe that P , Q, and R are the points of tangency of the excircles with the sides of △DEF . Let F Q = ER = x, DR = F P = y , and DQ = EP = z , and let δ, ε, ? be the angles of △DEF at D, E, F , respectively. Let Q′ and R′ be the projections of Q and R onto EF , respectively. Then QR ≥ Q′ R′ = EF ? F Q′ ? R′ E = EF ? x(cos ? + cos ε). Summing this with the analogous inequalities for F D and DE we obtain p(P QR) ≥ p(DEF ) ? x(cos ? + cos ε) ? y (cos δ + cos ?) ? z (cos δ + cos ε). Assuming w.l.o.g. that x ≤ y ≤ z we also have DE ≤ F D ≤ F E and consequently cos ? + cos ε ≥ cos δ + cos ? ≥ cos δ + cos ε. Now Chebyshev’s inequality gives us p(P QR) ≥ p(DEF )? 2 3 (x+ y + z )(cos ε +cos ?+cos δ ) ≥ 1 p(DEF ) ? (x + y + z ) = 1 2 p(DEF ), where we used x + y + z = 2 p(DEF ) and the fact that the sum of the cosines of the angles in a triangle does not exceed 3 2 . This ?nishes the proof. 21. We will show that 1 is the only such number. It is su?cient to prove that for every prime number p there exists some am such that p | am . For p = 2, 3 we have p | a2 = 48. Assume now that p > 3. Appyling Fermat’s theorem, we have: 6ap?2 = 3 · 2p?1 + 2 · 3p?1 + 6p?1 ? 6 ≡ 3 + 2 + 1 ? 6 = 0 (mod p). Hence p | ap?2 , i.e. gcd(p, ap?2 ) = p > 1. This completes the proof. 22. It immediately follows from the condition of the problem that all the terms of the sequence are distinct. We also note that |ai ? an | ≤ n ? 1 for all integers i, n where i < n, because if d = |ai ? an | ≥ n then {a1 , . . . , ad } contains two elements congruent to each other modulo d, which is a contradiction. It easily follows by induction that for every n ∈ N the set {a1 , . . . , an } consists of consecutive integers. Thus, if we assumed some integer k did not appear in the sequence a1 , a2 , . . . , the same would have

18

2 Solutions

to hold for all integers either larger or smaller than k , which contradicts the condition that in?nitely many positive and negative integers appear in the sequence. Thus, the sequence contains all integers. 23. Let us consider the polynomial P (x) = (x + a)(x + b)(x + c) ? (x ? d)(x ? e)(x ? f ) = Sx2 + Qx + R, where Q = ab + bc + ca ? de ? ef ? f d and R = abc + def . Since S | Q, R, it follows that S | P (x) for every x ∈ Z. Hence, S | P (d) = (d + a)(d + b)(d + c). Since S > d + a, d + b, d + c and thus cannot divide any of them, it follows that S must be composite. 24. We will show that n has the desired property if and only if it is prime. For n = 2 we can take only a = 1. For n > 2 and even, 4 | n!, but an + 1 ≡ 1, 2 (mod 4), which is impossible. Now we assume that n is odd. Obviously (n! ? 1)n + 1 ≡ (?1)n + 1 = 0 (mod n!). If n is composite and d n n n!k ! +1 = k=1 n its prime divisor, then n d ?1 k dk , where each summand n ! + 1. Thus, is divisible by n! because d2 | n!; therefore n! divides n d ?1 all composite numbers are ruled out. It remains to show that if n is an odd prime and n! | an + 1, then n! | a + 1 and therefore a = n! ? 1 is the only relevant value for which n! | an + 1. n +1 Consider any prime number p ≤ n. If p | aa+1 , we have p | (?a)n ?1 and by p?1 Fermat’s theorem p | (?a) ? 1. Therefore p | (?a)(n,p?1) ? 1 = ?a ? 1, n +1 = an?1 ? an?2 + · · · ? a + 1 ≡ n i.e. a ≡ ?1 (mod p). But then aa+1 n +1 is coprime to (n ? 1)! (mod p), implying that p = n. It follows that aa+1 and consequently (n ? 1)! divides a + 1. Moreover, the above consideration shows that n must divide a + 1. Thus n! | a + 1 as claimed. This ?nishes our proof. 25. We will use the abbreviation HD to denote a “highly divisible integer”. Let n = 2α2 (n) 3α3 (n) · · · pαp (n) be the factorization of n into primes. We have d(n) = (α2 (n) + 1) · · · (αp (n) + 1). We start with the following two lemmas. Lemma 1. If n is a HD and p, q primes with pk < q l (k, l ∈ N), then kαq (n) ≤ lαp (n) + (k + 1)(l ? 1). Proof. The inequality is trivial if αq (n) < l. Suppose that αq (n) ≥ l. Then npk /q l is an integer less than q , and d(npk /q l ) < d(n), which is equivalent to (αq (n) + 1)(αp (n) + 1) > (αq (n) ? l + 1)(αp (n) + k + 1) implying the desired inequality. Lemma 2. For each p and k there exist only ?nitely many HD’s n such that αp (n) ≤ k . Proof. It follows from Lemma 1 that if n is a HD with αp (n) ≤ k , then αq (n) is bounded for each prime q and αq (n) = 0 for q > pk+1 . Therefore there are only ?nitely many possibilities for n.

2.1 Copyright c : The Authors and Springer

19

We are now ready to prove both parts of the problem. (a) Suppose that there are in?nitely many pairs (a, b) of consecutive HD’s with a | b. Since d(2a) > d(a), we must have b = 2a. In particular, d(s) ≤ d(a) for all s < 2a. All but ?nitely many HD’s a are divisible by 2 and by 37 . Then d(8a/9) < d(a) and d(3a/2) < d(a) yield (α2 (a)+4)(α3 (a) ? 1) < (α2 (a)+1)(α3 (a)+1) ? 3α3 (a) ? 5 < 2α2 (a), α2 (a)(α3 (a) + 2) ≤ (α2 (a) + 1)(α3 (a) + 1) ? α2 (a) ≤ α3 (a) + 1. We now have 3α3 (a) ? 5 < 2α2 (a) ≤ 2α3 (a) + 2 ? α3 (a) < 7, which is a contradiction. (b) Assume for a given prime p and positive integer k that n is the smallest HD with αp ≥ k . We show that n p is also a HD. Assume the oppon site, i.e. that there exists a HD m < n p such that d(m) ≥ d( p ). By assumption, m must also satisfy αp (m) + 1 ≤ αp (n). Then d(mp) = d(m) αp (n) + 1 αp (m) + 2 ≥ d(n/p) = d(n), αp (m) + 1 αp (n)

contradicting the initial assumption that n is a HD (since mp < n). This proves that n p is a HD. Since this is true for every positive integer k the proof is complete. 26. Assuming b = a, it trivially follows that b > a. Let p > b be a prime number and let n = (a + 1)(p ? 1) + 1. We note that n ≡ 1 (mod p ? 1) and n ≡ ?a (mod p). It follows that rn = r · (rp?1 )a+1 ≡ r (mod p) for every integer r. We now have an + n ≡ a ? a = 0 (mod p). Thus, an + n is divisible by p, and hence by the condition of the problem bn + n is also divisible by p. However, we also have bn + n ≡ b ? a (mod p), i.e. p |b ? a, which contradicts p > b. Hence, it must follow that b = a. We note that b = a trivially ful?lls the conditions of the problem for all a ∈ N. 27. Let p be a prime and k < p an even number. We note that (p ? k )!(k ? 1)! ≡ (?1)k?1 (p ? k )!(p ? k + 1) . . . (p ? 1) = (?1)k?1 (p ? 1)! ≡ 1 (mod p) by Wilson’s theorem. Therefore (k ? 1)!n P ((p ? k )!) = ≡

n i=0 n i=0

ai [(k ? 1)!]n?i [(p ? k )!(k ? 1)!]i ai [(k ? 1)!]n?i = S ((k ? 1)!) (mod p),

where S (x) = an + an?1 x + · · · + a0 xn . Hence p | P ((p ? k )!) if and only if p | S ((k ? 1)!). Note that S ((k ? 1)!) depends only on k . Let k > 2an + 1. Then, s = (k ? 1)!/an is an integer which is divisible by all primes smaller than k . Hence S ((k ? 1)!) = an bk for some bk ≡ 1 (mod s). It follows that bk is divisible only by primes larger than k . For large enough k we have |bk | > 1. Thus for every prime divisor p of bk we have p | P ((p ? k )!). It remains to select a large enough k for which |P ((p ? k )!)| > p. We take k = (q ? 1)!, where q is a large prime. All the numbers k + i for

20

2 Solutions

i = 1, 2, . . . , q ? 1 are composite (by Wilson’s theorem, q | k + 1). Thus p = k + q + r, for some r ≥ 0. We now have |P ((p ? k )!)| = |P ((q + r)!)| > (q + r)! > (q ? 1)! + q + r = p, for large enough q , since n = deg P ≥ 2. This completes the proof. Remark. The above solution actually also works for all linear polynomials P other than P (x) = x + a0 . Nevertheless, these particular cases are easily handled. If |a0 | > 1, then P (m!) is composite for m > |a0 |, whereas P (x) = x + 1 and P (x) = x ? 1 are both composite for, say, x = 5!. Thus the condition n ≥ 2 was redundant.

A Notation and Abbreviations

A.1 Notation

We assume familiarity with standard elementary notation of set theory, algebra, logic, geometry (including vectors), analysis, number theory (including divisibility and congruences), and combinatorics. We use this notation liberally. We assume familiarity with the basic elements of the game of chess (the movement of pieces and the coloring of the board). The following is notation that deserves additional clari?cation. ? B (A, B, C ), A ? B ? C : indicates the relation of betweenness, i.e., that B is between A and C (this automatically means that A, B, C are di?erent collinear points). ? A = l1 ∩ l2 : indicates that A is the intersection point of the lines l1 and l2 . ? AB : line through A and B , segment AB , length of segment AB (depending on context). ? [AB : ray starting in A and containing B . ? (AB : ray starting in A and containing B , but without the point A. ? (AB ): open interval AB , set of points between A and B . ? [AB ]: closed interval AB , segment AB , (AB ) ∪ {A, B }. ? (AB ]: semiopen interval AB , closed at B and open at A, (AB ) ∪ {B }. The same bracket notation is applied to real numbers, e.g., [a, b) = {x | a ≤ x < b} . ? ABC : plane determined by points A, B, C , triangle ABC (△ABC ) (depending on context). ? [AB, C : half-plane consisting of line AB and all points in the plane on the same side of AB as C .

22

A Notation and Abbreviations

? (AB, C : [AB, C without the line AB . ? a, b, c, α, β, γ : the respective sides and angles of triangle ABC (unless otherwise indicated). ? k (O, r): circle k with center O and radius r. ? d(A, p): distance from point A to line p. ? SA1 A2 ...An : area of n-gon A1 A2 . . . An (special case for n = 3, SABC : area of △ABC ). ? N, Z, Q, R, C: the sets of natural, integer, rational, real, complex numbers (respectively). ? Zn : the ring of residues modulo n, n ∈ N. ? Zp : the ?eld of residues modulo p, p being prime. ? Z[x], R[x]: the rings of polynomials in x with integer and real coe?cients respectively. ? R? : the set of nonzero elements of a ring R. ? R[α], R(α), where α is a root of a quadratic polynomial in R[x]: {a + bα | a, b ∈ R}. ? X0 : X ∪ {0} for X such that 0 ∈ / X. ? X + , X ? , aX + b, aX + bY : {x | x ∈ X, x > 0}, {x | x ∈ X, x < 0}, {ax + b | x ∈ X }, {ax + by | x ∈ X, y ∈ Y } (respectively) for X, Y ? R, a, b ∈ R. ? [x], ?x?: the greatest integer smaller than or equal to x. ? ?x?: the smallest integer greater than or equal to x. The following is notation simultaneously used in di?erent concepts (depending on context). ? |AB |, |x|, |S |: the distance between two points AB , the absolute value of the number x, the number of elements of the set S (respectively). ? (x, y ), (m, n), (a, b): (ordered) pair x and y , the greatest common divisor of integers m and n, the open interval between real numbers a and b (respectively).

A.2 Abbreviations

We tried to avoid using nonstandard notation and abbreviations as much as possible. However, one nonstandard abbreviation stood out as particularly convenient: ? w.l.o.g.: without loss of generality.

A.2 Abbreviations

23

Other abbreviations include: ? RHS: right-hand side (of a given equation). ? LHS: left-hand side (of a given equation). ? QM, AM, GM, HM: the quadratic mean, the arithmetic mean, the geometric mean, the harmonic mean (respectively). ? gcd, lcm: greatest common divisor, least common multiple (respectively). ? i.e.: in other words. ? e.g.: for example.

B Codes of the Countries of Origin

ARG ARM AUS AUT BEL BLR BRA BUL CAN CHN COL CUB CYP CZE CZS EST FIN FRA FRG GBR GDR GEO GER

Argentina Armenia Australia Austria Belgium Belarus Brazil Bulgaria Canada China Colombia Cuba Cyprus Czech Republic Czechoslovakia Estonia Finland France Germany, FR United Kingdom Germany, DR Georgia Germany

GRE HKG HUN ICE INA IND IRE IRN ISR ITA JAP KAZ KOR KUW LAT LIT LUX MCD MEX MON MOR NET NOR NZL

Greece Hong Kong Hungary Iceland Indonesia India Ireland Iran Israel Italy Japan Kazakhstan Korea, South Kuwait Latvia Lithuania Luxembourg Macedonia Mexico Mongolia Morocco Netherlands Norway New Zealand

PHI POL POR PRK PUR ROM RUS SAF SIN SLO SMN SPA SWE THA TUN TUR TWN UKR USA USS UZB VIE YUG

Philippines Poland Portugal Korea, North Puerto Rico Romania Russia South Africa Singapore Slovenia Serbia and Montenegro Spain Sweden Thailand Tunisia Turkey Taiwan Ukraine United States Soviet Union Uzbekistan Vietnam Yugoslavia