Tuyển tập đề thi IMO thế giới 1969-1997

Chia sẻ: Trần Bá Trung4 | Ngày: | Loại File: PDF | Số trang:182

Thêm vào BST

Báo xấu

251
lượt xem 52
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

Tuyển tập đề thi IMO thế giới 1969-1997 giúp các em học sinh có tài liệu tham khảo , luyện tập. Tài liệu bao gồm các bài tập tự luận, tài liệu rất hay để các bạn tham khảo. Chúc các bạn thi tốt.

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Tuyển tập đề thi IMO thế giới 1969-1997

Preface This book is a continuation Mathematical Olympiads 1995-1996: Olympiad Problems from Around the World, published by the American Mathemat- ics Competitions. It contains solutions to the problems from 25 national and regional contests featured in the earlier pamphlet, together with se- lected problems (without solutions) from national and regional contests given during 1997. This collection is intended as practice for the serious student who wishes to improve his or her performance on the USAMO. Some of the problems are comparable to the USAMO in that they came from na- tional contests. Others are harder, as some countries ﬁrst have a national olympiad, and later one or more exams to select a team for the IMO. And some problems come from regional international contests (“mini-IMOs”). Diﬀerent nations have diﬀerent mathematical cultures, so you will ﬁnd some of these problems extremely hard and some rather easy. We have tried to present a wide variety of problems, especially from those countries that have often done well at the IMO. Each contest has its own time limit. We have not furnished this in- formation, because we have not always included complete contests. As a rule of thumb, most contests allow a time limit ranging between one-half to one full hour per problem. Thanks to Walter Mientka for his continuing support of this project, and to the students of the 1997 Mathematical Olympiad Summer Program for their help in preparing solutions. The problems in this publication are copyrighted. Requests for repro- duction permissions should be directed to: Dr. Walter Mientka Secretary, IMO Advisory Broad 1740 Vine Street Lincoln, NE 68588-0658, USA.
Contents 1 1996 National Contests: Problems and Solutions 3 1.1 Bulgaria . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3 1.2 Canada . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9 1.3 China . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12 1.4 Czech and Slovak Republics . . . . . . . . . . . . . . . . . . 17 1.5 France . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22 1.6 Germany . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25 1.7 Greece . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27 1.8 Iran . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29 1.9 Ireland . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34 1.10 Italy . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38 1.11 Japan . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41 1.12 Poland . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 44 1.13 Romania . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 47 1.14 Russia . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 57 1.15 Spain . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 76 1.16 Turkey . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 81 1.17 United Kingdom . . . . . . . . . . . . . . . . . . . . . . . . 84 1.18 United States of America . . . . . . . . . . . . . . . . . . . 89 1.19 Vietnam . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 96 2 1996 Regional Contests: Problems and Solutions 100 2.1 Asian Paciﬁc Mathematics Olympiad . . . . . . . . . . . . . 100 2.2 Austrian-Polish Mathematics Competition . . . . . . . . . . 103 2.3 Balkan Mathematical Olympiad . . . . . . . . . . . . . . . . 108 2.4 Czech-Slovak Match . . . . . . . . . . . . . . . . . . . . . . 110 2.5 Iberoamerican Olympiad . . . . . . . . . . . . . . . . . . . . 114 2.6 St. Petersburg City Mathematical Olympiad . . . . . . . . 118 3 1997 National Contests: Problems 131 3.1 Austria . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 131 3.2 Bulgaria . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 132 3.3 Canada . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 136 3.4 China . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 137 1
3.5 Colombia . . . . . . . . . . . . . . . . . . . . . . . . . . . . 139 3.6 Czech and Slovak Republics . . . . . . . . . . . . . . . . . . 140 3.7 France . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 141 3.8 Germany . . . . . . . . . . . . . . . . . . . . . . . . . . . . 142 3.9 Greece . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 144 3.10 Hungary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 145 3.11 Iran . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 146 3.12 Ireland . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 147 3.13 Italy . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 148 3.14 Japan . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 149 3.15 Korea . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 150 3.16 Poland . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 152 3.17 Romania . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 153 3.18 Russia . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 155 3.19 South Africa . . . . . . . . . . . . . . . . . . . . . . . . . . 161 3.20 Spain . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 162 3.21 Taiwan . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 163 3.22 Turkey . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 165 3.23 Ukraine . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 166 3.24 United Kingdom . . . . . . . . . . . . . . . . . . . . . . . . 167 3.25 United States of America . . . . . . . . . . . . . . . . . . . 168 3.26 Vietnam . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 169 4 1997 Regional Contests: Problems 170 4.1 Asian Paciﬁc Mathematics Olympiad . . . . . . . . . . . . . 170 4.2 Austrian-Polish Mathematical Competition . . . . . . . . . 171 4.3 Czech-Slovak Match . . . . . . . . . . . . . . . . . . . . . . 173 4.4 Hungary-Israel Mathematics Competition . . . . . . . . . . 174 4.5 Iberoamerican Mathematical Olympiad . . . . . . . . . . . 175 4.6 Nordic Mathematical Contest . . . . . . . . . . . . . . . . . 177 4.7 Rio Plata Mathematical Olympiad . . . . . . . . . . . . . . 178 4.8 St. Petersburg City Mathematical Olympiad (Russia) . . . 179 2
1 1996 National Contests: Problems and Solutions 1.1 Bulgaria 1. Prove that for all natural numbers n ≥ 3 there exist odd natural numbers xn , yn such that 7x2 + yn = 2n . n 2 Solution: For n = 3 we have x3 = y3 = 1. Now suppose that for a given natural number n we have odd natural numbers xn , yn such that 7x2 + yn = 2n ; we shall exhibit a pair (X, Y ) such that n 2 2 2 n+1 7X + Y = 2 . In fact, 2 2 xn ± yn 7xn yn 7 + = 2(7x2 + yn ) = 2n+1 . n 2 2 2 One of (xn + yn )/2 and |xn − yn |/2 is odd (as their sum is the larger of xn and yn , which is odd), giving the desired pair. 2. The circles k1 and k2 with respective centers O1 and O2 are exter- nally tangent at the point C, while the circle k with center O is externally tangent to k1 and k2 . Let be the common tangent of k1 and k2 at the point C and let AB be the diameter of k perpendicular to . Assume that O and A lie on the same side of . Show that the lines AO2 , BO1 , have a common point. Solution: Let r, r1 , r2 be the respective radii of k, k1 , k2 . Also let M and N be the intersections of AC and BC with k. Since AM B is a right triangle, the triangle AM O is isosceles and ∠AM O = ∠OAM = ∠O1 CM = ∠CM O1 . Therefore O, M, O1 are collinear and AM/M C = OM/M O1 = r/r1 . Similarly O, N, O2 are collinear and BN/N C = ON/N O2 = r/r2 . Let P be the intersection of with AB; the lines AN, BM, CP con- cur at the orthocenter of ABC, so by Ceva’s theorem, AP/P B = (AM/M C)(CN/N B) = r2 /r1 . Now let D1 and D2 be the intersec- tions of with BO1 and AO2 . Then CD1 /D1 P = O1 C/P B = r1 /P B, and similarly CD2 /D2 P = r2 /P A. Thus CD1 /D1 P = CD2 /D2 P and D1 = D2 , and so AO2 , BO1 , have a common point. 3
3. Let a, b, c be real numbers and let M be the maximum of the function y = |4x3 + ax2 + bx + c| in the interval [−1, 1]. Show that M ≥ 1 and ﬁnd all cases where equality occurs. Solution: For a = 0, b = −3, c = 0, we have M = 1, with the maximum achieved at −1, −1/2, 1/2, 1. On the other hand, if M < 1 for some choice of a, b, c, then (4x3 + ax2 + bx + c) − (4x3 + 3x) must be positive at −1, negative at −1/2, positive at 1/2, and negative at 1, which is impossible for a quadratic function. Thus M ≥ 1, and the same argument shows that equality only occurs for (a, b, c) = (0, −3, 0). (Note: this is a particular case of the minimum deviation property of Chebyshev polynomials.) 4. The real numbers a1 , a2 , . . . , an (n ≥ 3) form an arithmetic progres- sion. There exists a permutation ai1 , ai2 , . . . , ain of a1 , a2 , . . . , an which is a geometric progression. Find the numbers a1 , a2 , . . . , an if they are all diﬀerent and the largest of them is equal to 1996. Solution: Let a1 < a2 < · · · < an = 1996 and let q be the ratio of the geometric progression ai1 , . . . ain ; clearly q = 0, ±1. By reversing the geometric progression if needed, we may assume |q| > 1, and so |ai1 | < |ai2 | < · · · < |ain |. Note that either all of the terms are positive, or they alternate in sign; in the latter case, the terms of either sign form a geometric progression by themselves. There cannot be three positive terms, or else we would have a three- term geometric progression a, b, c which is also an arithmetic pro- gression, violating the AM-GM inequality. Similarly, there cannot be three negative terms, so there are at most two terms of each sign and n ≤ 4. If n = 4, we have a1 < a2 < 0 < a3 < a4 and 2a2 = a1 + a3 , 2a3 = a2 + a4 . In this case, q < −1 and the geometric progression is either a3 , a2 , a4 , a1 or a2 , a3 , a1 , a4 . Suppose the former occurs (the argument is similar in the latter case); then 2a3 q = a3 q 3 + a3 and 2a3 + a3 q + a3 q 2 , giving q = 1, a contradiction. We deduce n = 3 and consider two possibilities. If a1 < a2 < 0 < a3 = 1996, then 2a2 = a2 q 2 + a2 q, so q 2 + q − 2 = 0 and 4
q = −2, yielding (a1 , a2 , a3 ) = (−3992, −998, 1996). If a1 < 0 < a2 < a3 = 1996, then 2a2 = a2 q + a2 q 2 , so again q = −2, yielding (a1 , a2 , a3 ) = (−998, 499, 1996). 5. A convex quadrilateral ABC is given for which ∠ABC + ∠BCD < 180◦ . The common point of the lines AB and CD is E. Prove that ∠ABC = ∠ADC if and only if AC 2 = CD · CE − AB · AE. Solution: Let C1 be the circumcircle of ADE, and let F be its second intersection with CA. In terms of directed lengths, we have AC 2 = CD · CE + AB · AE if and only if AB · AE = AC 2 − CD · CE = CA2 − CA · AF = AC · AF, that is, if and only if B, C, E, F are concyclic. But this happens if and only if ∠EBC = ∠EF C, and ∠EF C = ∠EF A = π − ∠ADE = ∠CDA (in directed angles modulo π), so B, C, E, F are concyclic if and only if ∠ABC = ∠ADC (as undirected angles), as desired. 6. Find all prime numbers p, q for which pq divides (5p − 2p )(5q − 2q ). Solution: If p|5p − 2p , then p|5 − 2 by Fermat’s theorem, so p = 3. Suppose p, q = 3; then p|5q − 2q and q|5p − 2p . Without loss of generality, assume p > q, so that (p, q − 1) = 1. Then if a is an integer such that 2a ≡ 5 (mod q), then the order of a mod q divides p as well as q − 1, a contradiction. Hence one of p, q is equal to 3. If q = 3, then q|53 − 23 = 9 · 13, so q = 13, and similarly p ∈ {3, 13}. Thus the solutions are (p, q) = (3, 3), (3, 13), (13, 3). 7. Find the side length of the smallest equilateral triangle in which three discs of radii 2, 3, 4 can be placed without overlap. Solution: A short computation shows that discs of radii 3 √ 4 and can be ﬁt into two corners of an equilateral triangle of side 11 3 so 5
as to just touch, and that a disc of radius 2 easily ﬁts into the third corner without overlap. On the other hand, if the discs of radii 3 and 4 ﬁt into an equilateral triangle without overlap, there exists a line separating them (e.g. a tangent to one perpendicular to their line of centers) dividing the triangle into a triangle and a (possibly degenerate) convex quadrilateral. Within each piece, the disc can be moved into one of the corners of the original triangle. Thus the two discs ﬁt into the corners without overlap, so the side length of the √ triangle must be at least 11 3. 8. The quadratic polynomials f and g with real coeﬃcients are such that if g(x) is an integer for some x > 0, then so is f (x). Prove that there exist integers m, n such that f (x) = mg(x) + n for all x. Solution: Let f (x) = ax2 + bx + c and g(x) = px2 + qx + r; assume without loss of generality p > 0 and q = 0 (by the change of variable x → x − q/(2p)). Let k be an integer such that k > s and t = (k − s)/p > q/(2p). Since g(t) = k is an integer, so is f (t) = a(k − s)/p + bt + c, as is k+1−s k−s b 1 a f −f =√ √ √ + . p p p k+1−s− k−s p This tends to a/p as k increases, so a/p must be an integer; moreover, b must equal 0, or else the above expression will equal a/p plus a small quantity for large k, which cannot be an integer. Now put m = a/p and n = c − ms; then f (x) = mg(x) + n. 9. The sequence {an }∞ is deﬁned by n=1 an n a1 = 1, an+1 = + , n ≥ 1. n an Prove that for n ≥ 4, a2 = n. n √ √ Solution: We will show by induction that n ≤ an ≤ n/ n − 1 for n ≥ 1, which will imply the claim. These inequalities clearly hold for n = 1, 2, 3. Now assume the inequality for some n. Let fn (x) = x/n + n/x. We ﬁrst have for n ≥ 3, n n √ an+1 = fn (an ) ≥ fn √ =√ > n + 1. n−1 n−1 6
√ On the other hand, using that an > (n − 1)/ n − 2 (which we just proved), we get for n ≥ 4, n−1 (n − 1)2 + n2 (n − 2) √ an+1 = fn (an ) < fn √ = √ < n + 2. n−2 (n − 1)n n − 2 10. The quadrilateral ABCD is inscribed in a circle. The lines AB and CD meet at E, while the diagonals AC and BD meet at F . The circumcircles of the triangles AF D and BF C meet again at H. Prove that ∠EHF = 90◦ . Solution: (We use directed angles modulo π.) Let O be the circumcenter of ABCD; then ∠AHB = ∠AHF +∠F HB = ∠ADF +∠F CB = 2∠ADB = ∠AOB, so O lies on the circumcircle of AHB, and similarly on the circum- circle of CHD. The radical axes of the circumcircles of AHB, CHD and ABCD concur; these lines are AB, CD and HO, so E, H, O are collinear. Now note that π ∠OHF = ∠OHC+∠CHF = ∠ODC+∠CBF = −∠CAD+∠CBD, 2 so ∠EHF = ∠OHF = π/2 as desired. (Compare IMO 1985/5.) 11. A 7 × 7 chessboard is given with its four corners deleted. (a) What is the smallest number of squares which can be colored black so that an uncolored 5-square (Greek) cross cannot be found? (b) Prove that an integer can be written in each square such that the sum of the integers in each 5-square cross is negative while the sum of the numbers in all squares of the board is positive. Solution: (a) The 7 squares (2, 5), (3, 2), (3, 3), (4, 6), (5, 4), (6, 2), (6, 5) 7
suﬃce, so we need only show that 6 or fewer will not suﬃce. The crosses centered at (2, 2), (2, 6), (3, 4), (5, 2), (5, 6), (6, 4) are disjoint, so one square must be colored in each, hence 5 or fewer squares do not suﬃce. Suppose exactly 6 squares are colored. Then none of the squares (1, 3), (1, 4), (7, 2) can be col- ored; by a series of similar arguments, no square on the perime- ter can be colored. Similarly, (4, 3) and (4, 5) are not covered, and by a similar argument, neither is (3, 4) or (5, 4). Thus the center square (4, 4) must be covered. Now the crosses centered at (2, 6), (3, 3), (5, 2), (5, 6), (6, 4) are disjoint and none contains the center square, so each con- tains one colored square. In particular, (2, 2) and (2, 4) are not colored. Replacing (3, 3) with (2, 3) in the list shows that (3, 2) and (3, 4) are not colored. Similar symmetric arguments now show that no squares besides the center square can be covered, a contradiction. Thus 7 squares are needed. (b) Write −5 in the 7 squares listed above and 1 in the remaining squares. Then clearly each cross has negative sum, but the total of all of the numbers is 5(−7) + (45 − 7) = 3. 8
1.2 Canada 1. If α, β, γ are the roots of x3 − x − 1 = 0, compute 1−α 1−β 1−γ + + . 1+α 1+β 1+γ Solution: The given quantity equals 1 1 1 2 + + − 3. α+1 β+1 γ+1 Since P (x) = x3 − x − 1 has roots α, β, γ, the polynomial P (x − 1) = x3 − 3x2 + 2x − 1 has roots α + 1, β + 1, γ + 1. By a standard formula, the sum of the reciprocals of the roots of x3 + c2 x2 + c1 x + c0 is −c1 /c0 , so the given expression equals 2(2) − 3 = 1. 2. Find all real solutions to the following system of equations: 4x2 = y 1 + 4x2 4y 2 = z 1 + 4y 2 4z 2 = x. 1 + 4z 2 Solution: Deﬁne f (x) = 4x2 /(1 + 4x2 ); the range of f is [0, 1), so x, y, z must lie in that interval. If one of x, y, z is zero, then all three are, so assume they are nonzero. Then f (x)/x = 4x/(1 + 4x2 ) is at least 1 by the AM-GM inequality, with equality for x = 1/2. Therefore x ≤ y ≤ z ≤ x, and so equality holds everywhere, implying x = y = z = 1/2. Thus the solutions are (x, y, z) = (0, 0, 0), (1/2, 1/2, 1/2). 3. Let f (n) be the number of permutations a1 , . . . , an of the integers 1, . . . , n such that (i) a1 = 1; (ii) |ai − ai+1 | ≤ 2, i = 1, . . . , n − 1. 9
Determine whether f (1996) is divisible by 3. Solution: Let g(n) be the number of permutations of the desired form with an = n. Then either an−1 = n − 1 or an−1 = n − 2; in the latter case we must have an−2 = n − 1 and an−3 = n − 3. Hence g(n) = g(n − 1) + g(n − 3) for n ≥ 4. In particular, the values of g(n) modulo 3 are g(1) = 1, 1, 1, 2, 0, 1, 0, 0, . . . repeating with period 8. Now let h(n) = f (n) − g(n); h(n) counts permutations of the desired form where n occurs in the middle, sandwiched between n−1 and n− 2. Removing n leaves an acceptable permutation, and any acceptable permutation on n−1 symbols can be so produced except those ending in n−4, n−2, n−3, n−1. Hence h(n) = h(n−1)+g(n−1)−g(n−4) = h(n−1)+g(n−2); one checks that h(n) modulo 3 repeats with period 24. Since 1996 ≡ 4 (mod 24), we have f (1996) ≡ f (4) = 4 (mod 3), so f (1996) is not divisible by 3. 4. Let ABC be an isosceles triangle with AB = AC. Suppose that the angle bisector of ∠B meets AC at D and that BC = BD + AD. Determine ∠A. Solution: Let α = ∠A, β = (π − α)/4 and assume AB = 1. Then by the Law of Sines, sin α sin α sin β BC = , BD = , AD = . sin 2β sin 3β sin 3β Thus we are seeking a solution to the equation sin(π − 4β) sin 3β = (sin(π − 4β) + sin β) sin 2β. Using the sum-to-product formula, we rewrite this as cos β − cos 7β = cos 2β − cos 6β + cos β − cos 3β. Cancelling cos β, we have cos 3β − cos 7β = cos 2β − cos 6β, which implies sin 2β sin 5β = sin 2β sin 4β. Now sin 5β = sin 4β, so 9β = π and β = π/9. 10
5. Let r1 , r2 , . . . , rm be a given set of positive rational numbers whose m sum is 1. Deﬁne the function f by f (n) = n − k=1 rk n for each positive integer n. Determine the minimum and maximum values of f (n). Solution: Of course rk n ≤ rk n, so f (n) ≥ 0, with equality for n = 0, so 0 is the minimum value. On the other hand, we have rk n − rk n < 1, so f (n) ≤ m − 1. Here equality holds for n = t − 1 if t is the least common denominator of the rk . 11
1.3 China 1. Let H be the orthocenter of acute triangle ABC. The tangents from A to the circle with diameter BC touch the circle at P and Q. Prove that P, Q, H are collinear. Solution: The line P Q is the polar of A with respect to the circle, so it suﬃces to show that A lies on the pole of H. Let D and E be the feet of the altitudes from A and B, respectively; these also lie on the circle, and H = AD ∩ BE. The polar of the line AD is the intersection of the tangents AA and DD, and the polar of the line BE is the intersection of the tangents BB and EE. The collinearity of these two intersections with C = AE∩BD follows from applying Pascal’s theorem to the cyclic hexagons AABDDE and ABBDEE. (An elementary solution with vectors is also possible and not diﬃcult.) 2. Find the smallest positive integer K such that every K-element sub- set of {1, 2, . . . , 50} contains two distinct elements a, b such that a+b divides ab. Solution: The minimal value is k = 39. Suppose a, b ∈ S are such that a + b divides ab. Let c = gcd(a, b), and put a = ca1 , b = cb1 , so that a1 and b1 are relatively prime. Then c(a1 + b1 ) divides c2 a1 b1 , so a1 + b1 divides ca1 b1 . Since a1 and b1 have no common factor, neither do a1 and a1 + b1 , or b1 and a1 + b1 . In short, a1 + b1 divides c. Since S ⊆ {1, . . . , 50}, we have a + b ≤ 99, so c(a1 + b1 ) ≤ 99, which implies a1 + b1 ≤ 9; on the other hand, of course a1 + b1 ≥ 3. An exhaustive search produces 23 pairs a, b satisfying the condition: a1 + b1 = 3 (6, 3), (12, 6), (18, 9), (24, 12), (30, 15), (36, 18), (42, 21), (48, 24) a1 + b1 =4 (12, 4), (24, 8), (36, 12), (48, 16) a1 + b1 =5 (20, 5), (40, 10), (15, 10), (30, 20), (45, 30) a1 + b1 =6 (30, 6) a1 + b1 =7 (42, 7), (35, 14), (28, 21) a1 + b1 =8 (40, 24) a1 + b1 =9 (45, 36) 12
Let M = {6, 12, 15, 18, 20, 21, 24, 35, 40, 42, 45, 48} and T = {1, . . . , 50}− M . Since each pair listed above contains an element of M , T does not have the desired property. Hence we must take k ≥ |T | + 1 = 39. On the other hand, from the 23 pairs mentioned above we can select 12 pairs which are mutually disjoint: (6, 3), (12, 4), (20, 5), (42, 7), (24, 8), (18, 9), (40, 10), (35, 14), (30, 15), (48, 16), (28, 21), (45, 36). Any 39-element subset must contain both elements of one of these pairs. We conclude the desired minimal number is k = 39. 3. Let f : R → R be a function such that for all x, y ∈ R, f (x3 + y 3 ) = (x + y)(f (x)2 − f (x)f (y) + f (y)2 ). (1) Prove that for all x ∈ R, f (1996x) = 1996f (x). Solution: Setting x = y = 0 in the given equation, we have f (0) = 0. Setting y = 0, we ﬁnd f (x3 ) = xf (x)2 , or equivalently, f (x) = x1/3 f (x1/3 )2 . (2) In particular, x and f (x) always have the same sign, that is, f (x) ≥ 0 for x ≥ 0 and f (x) ≤ 0 for x ≤ 0. Let S be the set S = {a > 0 : f (ax) = af (x)∀x ∈ R}. Clearly 1 ∈ S; we will show a1/3 ∈ S whenever a ∈ S. In fact, axf (x)2 = af (x3 ) = f (ax3 ) = f ((a1/3 x)3 ) = a1/3 f (a1/3 x)2 and so [a1/3 f (x)]2 = f (a1/3 x)2 . Since x and f (x) have the same sign, we conclude f (a1/3 x) = a1/3 f (x). Now we show that a, b ∈ S implies a + b ∈ S: f ((a + b)x) = f ((a1/3 x1/3 )3 + (b1/3 x1/3 )3 ) = (a1/3 + b1/3 )[f (a1/3 x1/3 )2 − f (a1/3 x1/3 )f (b1/3 x1/3 ) + f (b1/3 x1/3 )2 ] = (a1/3 + b1/3 )(a2/3 − a1/3 b1/3 + b2/3 )x1/3 f (x1/3 )2 = (a + b)f (x). 13
By induction, we have n ∈ S for each positive integer n, so in par- ticular, f (1996x) = 1996f (x) for all x ∈ R. 4. Eight singers participate in an art festival where m songs are per- formed. Each song is performed by 4 singers, and each pair of singers performs together in the same number of songs. Find the smallest m for which this is possible. Solution: Let r be the number of songs each pair of singers per- forms together, so that 4 8 m =r 2 2 and so m = 14r/3; in particular, m ≥ 14. However, m = 14 is indeed possible, using the arrangement {1, 2, 3, 4} {5, 6, 7, 8} {1, 2, 5, 6} {3, 4, 7, 8} {3, 4, 5, 6} {1, 3, 5, 7} {2, 4, 6, 8} {1, 3, 6, 8} {2, 4, 5, 7} {1, 4, 5, 8} {2, 3, 6, 7} {1, 4, 6, 7} {1, 2, 7, 8} {2, 3, 5, 8}. n 5. Suppose n ∈ N, x0 = 0, xi > 0 for i = 1, 2, . . . , n, and i=1 xi = 1. Prove that n xi π 1≤ √ √ < . i=1 1 + x0 + · · · + xi−1 · xi + · · · + xn 2 Solution: The left inequality follows from the fact that √ 1 1 + x0 + x1 + · · · + xi−1 x1 + · · · + xn ≤ (1+x0 +· · ·+xn ) = 1, 2 so that the middle quantity is at least xi = 1. For the right inequality, let θi = arcsin(x0 + · · · + xi ) (i = 0, . . . , n) so that √ 1 + x0 + x1 + · · · + xi−1 xi + · · · + xn = cos θi−1 14
and the desired inequality is n sin θi − sin θi−1 π < . i=1 cos θi−1 2 Now note that θi + θi−1 θi − θi−1 sin θi − sin θi−1 = 2 cos sin < cosθi−1 (θi − θi−1 ), 2 2 using the facts that θi−1 < θi and that sin x < x for x > 0, so that n n sin θi − sin θi−1 π < θi − θi−1 = θn − θ0 < , i=1 cos θi−1 i=1 2 as claimed. 6. In triangle ABC, ∠C = 90◦ , ∠A = 30◦ and BC = 1. Find the minimum of the length of the longest side of a triangle inscribed in ABC (that is, one such that each side of ABC contains a diﬀerent vertex of the triangle). Solution: We ﬁrst ﬁnd the minimum side length of an equilateral triangle inscribed in ABC. Let D be a point on BC and put x = BD. Then take points E, F on CA, AB, respectively, such that √ CE = 3x/2 and BF = 1 − x/2. A calculation using the Law of Cosines shows that 2 7 2 7 4 3 DF 2 = DE 2 = EF 2 = x − 2x + 1 = x− + . 4 4 7 7 Hence the triangle DEF is equilateral, and its minimum possible side length is 3/7. We now argue that the minimum possible longest side must occur for some equilateral triangle. Starting with an arbitrary triangle, ﬁrst suppose it is not isosceles. Then we can slide one of the endpoints of the longest side so as to decrease its length; we do so until there are two longest sides, say DE and EF . We now ﬁx D, move E so as to decrease DE and move F at the same time so as to decrease EF ; we do so until all three sides become equal in length. (It is ﬁne 15
if the vertices move onto the extensions of the sides, since the bound above applies in that case as well.) Hence the mininum is indeed 3/7, as desired. 16
1.4 Czech and Slovak Republics 1. Prove that if a sequence {G(n)}∞ of integers satisﬁes n=0 G(0) = 0, G(n) = n − G(G(n)) (n = 1, 2, 3, . . .), then (a) G(k) ≥ G(k − 1) for any positive integer k; (b) no integer k exists such that G(k − 1) = G(k) = G(k + 1). Solution: (a) We show by induction that G(n) − G(n − 1) ∈ {0, 1} for all n. If this holds up to n, then G(n + 1) − G(n) = 1 + G(G(n − 1)) − G(G(n)). If G(n − 1) = G(n), then G(n + 1) − G(n) = 1; otherwise, G(n − 1) and G(n) are consecutive integers not greater than n, so G(G(n)) − G(G(n − 1)) ∈ {0, 1}, again completing the induction. (b) Suppose that G(k − 1) = G(k) = G(k + 1) + A for some k, A. Then A = G(k + 1) = k + 1 − G(G(k)) = k + 1 − G(A) and similarly A = k − G(A) (replacing k + 1 with k above), a contradiction. √ Note: It can be shown that G(n) = nw for w = ( 5 − 1)/2. 2. Let ABC be an acute triangle with altitudes AP, BQ, CR. Show that for any point P in the interior of the triangle P QR, there exists a tetrahedron ABCD such that P is the point of the face ABC at the greatest distance (measured along the surface of the tetrahedron) from D. 17
Solution: We ﬁrst note that if S is the circumcircle of an acute triangle KLM , then for any point X = S inside the triangle, we have min{XK, XL, XM } < SK = SL = SM, since the discs centered at K, L, M whose bounding circles pass through S cover the entire triangle. Fix a point V in the interior of the triangle P QR; we ﬁrst assume the desired tetrahedron exists and determine some of its properties. Rotate the faces ABD, BCD, CAD around their common edges with face ABC into the plane ABC, so that the images D1 , D2 , D3 of D lie outside of triangle ABC. We shall choose D so that triangle D1 D2 D3 is acute, contains triangle ABC and has circumcenter V ; this suﬃces by the above observation. In other words, we need a point D such that AV is the perpendicu- lar bisector of D1 D3 , BV that of D1 D2 , and CV that of D2 D3 . We thus need ∠D1 D2 D3 = π − ∠BV C and so on. Since V lies inside P QR, the angle BV C is acute, and so ∠D1 D2 D3 is ﬁxed and acute. We may then construct an arbitrary triangle D1 D2 D3 similar to the unknown triangle D1 D2 D3 , let V be its circumcenter, and con- struct points A , B , C on the rays from V through the midpoints of D3 D1 , D1 D2 , D2 D3 , respectively, so that triangles A B C and ABC are similar. We can also ensure that the entire triangle A B C lies inside D1 D2 D3 . Then folding up the hexagon A D1 B D2 C D3 along the edges of triangle A B C produces a tetrahedron similar to the required tetrahedron. 3. Given six three-element subsets of a ﬁnite set X, show that it is possible to color the elements of X in two colors such that none of the given subsets is all in one color. Solution: Let A1 , . . . , A6 be the subsets; we induct on the number n of elements of X, and there is no loss of generality in assuming n ≥ 6. If n = 6, since 6 = 20 > 2 · 6, we can ﬁnd a three-element 3 subset Y of X not equal to any of A1 , . . . , A6 or their complements; coloring the elements of Y in one color and the other elements in the other color meets the desired condition. 18
Now suppose n > 6. There must be two elements u, v of X such that {u, v} is not a subset of any Ai , since there are at least 7 = 21 2 pairs, and at most 6 × 3 = 18 lie in an Ai . Replace all occurrences of u and v by a new element w, and color the resulting elements using the induction hypothesis. Now color the original set by giving u and v the same color given to w. 4. An acute angle XCY and points A and B on the rays CX and CY , respectively, are given such that |CX| < |CA| = |CB| < |CY |. Show how to construct a line meeting the ray CX and the segments AB, BC at the points K, L, M , respectively, such that KA · Y B = XA · M B = LA · LB = 0. Solution: Suppose K, L, M have already been constructed. The triangles ALK and BY L are similar because ∠LAK = ∠Y BL and KA/LA = LB/Y B. Hence ∠ALK = ∠BY L. Similarly, from the similar triangles ALX and BM L we get ∠AXL = ∠M LB. We also have ∠M LB = ∠ALK since M, L, K are collinear; we conclude ∠LY B = ∠AXL. Now ∠XLY = ∠XLB+∠BLY = ∠XAL+∠AXL+∠ABM −∠LY B = 2∠ABC. We now construct the desired line as follows: draw the arc of points L such that ∠XLY = 2∠ABC, and let L be its intersection with AB. Then construct M on BC such that ∠BLM = ∠AXL, and let K be the intersection of LM with CA. 5. For which integers k does there exist a function f : N → Z such that (a) f (1995) = 1996, and (b) f (xy) = f (x) + f (y) + kf (gcd(x, y)) for all x, y ∈ N? Solution: Such f exists for k = 0 and k = −1. First take x = y in (b) to get f (x2 ) = (k + 2)f (x). Applying this twice, we get f (x4 ) = (k + 2)f (x2 ) = (k + 2)2 f (x). 19