Mathematical Excalibur, Volume 16, Number 3

Abstract

Mathematical Excalibur Volume 16, Number 3 November 2011 -January 2012 Remarks on IMO 2011 Leung Tat-Wing Olympiad Corner Below are the problems of the 2011 International Math Olympiad. Problem 1. Given any set A={a1, a2, a3, a4} of four distinct positive integers, we denote the sum a1+a2+a3+a4 by sA. Let nA denote the number of pairs (i,j) with 1≤i<j≤4 for which ai+aj divides sA. Find the sets A of four distinct positive integers which achieve the largest possible value of nA. Problem 2. Let S be a finite set of at least two points in the plane. Assume that no three points of S are collinear. A windmill is a process that starts with a line going through a single point P S. The line rotates clockwise about the pivot P until the first time that the line meets some other point belonging to S. This point, Q, takes over as the new pivot, and the line now rotates clockwise about Q, until it next meets a point of S. This process continues indefinitely. Show that we can choose a point P in S and a line ℓ going through P such that the resulting windmill uses each point of S as a pivot infinitely many times. (continued on page 4) Editors: 張 百 康 (CHEUNG Pak-Hong), Munsang College, HK 高 子 眉 (KO Tsz-Mei) 梁 達 榮 (LEUNG Tat-Wing) 李 健 賢 (LI Kin-Yin), Dept. of Math., HKUST 吳 鏡 波 (NG Keng-Po Roger), ITC, HKPU Artist: 楊 秀 英 (YEUNG Sau-Ying Camille), MFA, CU Acknowledgment: Thanks to Elina Chiu, Math. Dept. HKUST for general assistance. On-line: http://www.math.ust.hk/mathematical_excalibur/ The editors welcome contributions from all teachers and students. With your submission, please include your name, address, school, email, telephone and fax numbers (if available). Electronic submissions, especially in MS Word, are encouraged. The deadline for receiving material for the next issue is February 28, 2012. For individual subscription for the next five issues for the 09-10 academic year, send us five stamped self-addressed envelopes. Send all correspondence to: Dr. Kin-Yin LI, Math Dept., Hong Kong Univ. of Science and Technology, Clear Water Bay, Kowloon, Hong Kong Fax: (852) 2358 1643 Email: makyli@ust.hk Department of Mathematics, The Hong Kong University of Science and Technology The 52nd IMO was held in Amsterdam, Netherlands, on 12-24, July, 2011. Contestants took two 4½ hour exams during the mornings of July 18 and 19. Each exam was consisted of 3 problems of varying degree of difficulty. The problems were first shortlisted by the host country, selected from problems submitted earlier by various countries. Leaders from 101 countries then picked the 2011 IMO problems (see Olympiad Corner). Traditionally an easy pair was selected (Problems 1 and 4), then a hard pair (Problems 3 and 6), with Problem 6 usually selected as the “anchor problem”, and finally the intermediate pair (Problems 2 and 5). I would like to discuss first the problems selected, aim to provide something extra besides those which were provided by the solutions. However I would discuss the problems by slightly different grouping. Problems 1 and 4 First the easy pair, problems 1 and 4. The problem selection committee thought that both problems were quite easy. It was nice to select one as a problem of the contest. But if both problems were selected, then the paper would be too easy (or even disastrous). Indeed eventually both problems were selected. But it was not enough for anyone to get a bronze medal even if he could solve both problems (earning 14 points) as the cut-off for bronze was 16. In my opinion problem 1 is the easier of the pair. Indeed we may without loss of generality assume a1 < a2 < a3 < a4. So if the sum of one pair of the as divides sA, then it will also divide the sum of the other pair. But clearly a bigger pair cannot divide a smaller pair, so it is impossible that a3 + a4 dividing a1 + a2, nor is it possible that a2 + a4 dividing a1 + a3. Therefore the maximum possible value of nA can only be 4. To achieve this, it suffices to consider divisibility conditions among the other pairs. Now as we need a1 + a4 dividing a2 + a3 and also a2 + a3 dividing a1 + a4, we must have a1 + a4 = a2 + a3. Putting a4= a2+a3−a1 into the equations a3 + a4 = m(a1 + a2) and a2 + a4 = n(a1 + a3) with m > n > 1, we eventually get (m,n) = (3,2) or (4,2). Finally we get (a1, a2, a3, a4) = (k, 5k, 7k, 11k) or (k, 11k, 19k, 29k), where k is a positive integer. As the derivation of the answers is rather straight-forward, it does not pose any serious difficulty. For problem 4, it is really quite easy if one notes the proper recurrence relation. Indeed the weights 20, 21, 22,2n−1 form a “super-increasing sequence”, any weight is heavier than the sum of all lighter weights. Denote by f(n) the number of ways of placing the weights. We consider first how to place the lightest weight (weight 1). Indeed if it is placed in the first move, then it has to be in the left pan. However if it is placed in the second to the last move, then it really doesn’t matter where it goes, using the “super-increasing property”. Hence altogether there are 2n−1 possibilities of placing the weight of weight 1. Now placing the weights 21, 22, …, 2n−1 clearly is the same as placing the weights 20, 21, …, 2n−2. There are f(n−1) ways of doing this. Thus we establish the recurrence relation f(n) = (2n−1)f(n−1). Using f(1) = 1, by induction, we get f(n) = (2n −1)(2n −3)(2n −5)⋯1. The problem becomes a mere exercise of recurrence relation if one notices how to place the lightest weight (minimum principle). It is slightly harder if we consider how to place the heaviest weight. Indeed if the heaviest weight is to be placed in the ith move, then it has to be placed in the left pan There are 1 ways of Mathematical Excalibur, Vol. 16, No. 3, Nov.11 -Jan. 12 Page 2 choosing the previous i−1 weights and there are f(i−1) ways of placing them. After the heaviest weight is placed, it doesn’t matter how to place the other weights, and there are (n−i)!×2n−i ways of placing the remaining weights. Thus Replacing n by n −1 and by comparing the two expressions we again get f(n) = (2n−1)f(n−1). We have no serious difficulty with this problem. Problems 3 and 5 In my opinion both problems 3 and 5 were of similar flavor. Both were “functional equation” type of problems. Problem 3 was slightly more involved and problem 5 more number theoretic. One can of course put in many values and obtain some equalities or inequalities. But the important thing is to substitute some suitable values so that one can derive important relevant properties that can solve the problem. In problem 5, indeed the condition f(m−n) | (f(m) − f(n)) (*) poses very serious restrictions on the image of f(x). Putting n=0, one gets f(m) | (f(m) − f(0)), thus f(m) | f(0). Since f(0) can only have finitely many factors, the image of f(x) must be finite. Putting m=0, one gets f(−n) | f(n), and by interchanging n and −n, one gets f(n) = f(−n). Now f(n) | (f(2n) − f(n)), hence f(n) | f(2n), and by induction f(n) | f(mn). Put n = 1 into the relation. One gets f(1) | f(m). The image of f(x) is therefore a finite sequence f(1) = a1< a2< ⋯ < ak = f(0). One needs to show ai | ai+1. To complete the proof, one needs to analyze the sequence more carefully, say one may proceed by induction on k. But personally I like the following argument. Let f(x) = ai and f(y) = ai+1. We have f(x−y) | (f(y) − f(x)) < f(y) and f(y) − f(x) is positive, hence f (x − y) is in the image of f(x) and therefore f(x−y) ≤ ai= f(x). Now if f(x−y) < f(x), then f(x) − f(x −y) > 0. Thus f(y) = f(x−(x−y)) | (f(x) − f(x −y)). In this case the right-hand side is positive. We have f(y) ≤ f(x) − f(x −y)) < f(x) < f(y), a contradiction. So we have f(x−y) = f(x). Thus f(x) | f(y) as needed. It seems that Problem 3 is more involved. However, by making useful and clever substitutions, it is possible to solve the problem in a relatively easy way. The following solution comes from one of our team members. Put y = z−x into the original equation f(x+y) ≤ yf(x) + f(f(x)), one gets f(z) ≤ z f(x) − xf (x) + f( f(x)). By letting z = f(k) in the derived inequality one gets f(f(k)) ≤ f(k) f(x) − xf (x) + f( f(x)). Interchanging k and x one then gets f(f(x)) ≤ f(k) f(x) − kf (k) + f( f(k)). Hence f(x+y) ≤ y f(x) + f( f(x)) ≤ f(x)f(k) −kf(k) + f(f(k)). Letting y =f(k) − x in the inequality, we get f(f(k)) ≤ f(k) f(x) − xf (x) + f(k) f(x) − kf (k) + f( f(k)) or 0 ≤ 2 f(k) f(x) − xf(x) −k f(k). Finally letting k = 2 f(x) and simplifying, we arrive at the important and essential (hidden) inequality 0 ≤ −xf(x). This means for x > 0, f(x) ≤ 0, and for x < 0, f(x) ≥ 0. But if there is an x0 < 0 such that f(x0) > 0, then putting x = x0 and y = 0 into the original equation, we gets 0<f(x0) ≤ f(f(x0)). However if f(x0) > 0, then f(f(x0)) ≤ 0, hence a contradiction. This means for all x < 0, f(x) = 0. Finally one has to prove f(0) = 0. We suppose first f(0) > 0. Put x = 0 and y < 0 sufficiently small into the original equation, one gets f(y) < 0, a contradiction. Suppose f(0) < 0. Take x, y < 0. We get 0 = f(x+y) ≤ y f(x) + f( f(x)) = y f(x) + f(0) = f(0) < 0, again contradiction! This implies f(0) = 0. Problem 2 To me, problem 2 was one of a kind. The problem was considered as “intermediate” and should not be too hard. However at the end only 21 out of 564 contestants scored full marks. It was essentially a problem of computational geometry. We know that if there is a line that goes through two or more of the points and such that all other points are on the line or only on one side of the points, then by repeatedly turning angles as indicated in the problem, the convex hull of the point set will be constructed (so-called Jarvis’ march). Therefore some points may be missed. So in order to solve the problem, we cannot start from the “boundary”. Thus it is natural that we start from the “center”, or a line going through a point that separates the other points into equal halves (or differ by one). Indeed this idea is correct. The hard part is how to substantiate the argument. Many contestants found it hard. Induction argument does not work because adding or deleting one point may change the entire route. The proposer gives the following “continuity argument”. We consider only the case that there are an odd number of points on the plane. Let l be a line that goes through one of the points and that separates the other points into two equal halves. Note that such line clearly exists. Color one half-plane determined by the line orange (for Netherlands) and the other half-plane blue. The color of the plane changes accordingly while the line is turning. Note also that when the line moves to another pivot, the number of points on the two sides remain the same, except when two points are on the line during the change of pivots. So consider what happen when the line turns 180°, (turning while changing pivots). The line will go through the same original starting point. Only the colors of the two sides of the line interchange! This means all the points have been visited at least once! A slightly modified argument works for the case there are an even number of points on the plane. Problem 6 This was the most difficult problem of the contest (the anchor problem), only 6 out of more than 564 contestants solved the problem. Curiously these solvers were not necessarily from the strongest teams. The problem is hard and beautiful, and I feel that it may be a known problem because it is so nice. However, I am not able to find any further detail. It is not convenient to reproduce the full solution here. But I still want to discuss the main idea used in the first official solution briefly. From ΔABC and the tangent line L at T, we produce the reflecting lines La, Lb, and Lc. The reflecting lines meet at A”, B” and C” respectively. Now from A, we draw a circle of radius AT, meeting the circumcircle γ of ABC at A’. Likewise we have BT=BB’ and CT=CC’ (see the figure). (continued on page 4) Mathematical Excalibur, Vol. 16, No. 3, Nov.11 -Jan. 12 Page 3 Problem Corner We welcome readers to submit their solutions to the problems posed below for publication consideration. The solutions should be preceded by the solver’s name, home (or email) address and school affiliation. Please send submissions to Dr. Kin Y. Li, Department of Mathematics, The Hong Kong University of Science & Technology, Clear Water Bay, Kowloon, Hong Kong. The deadline for sending solutions is February 28, 2012. Problem 381. Let k be a positive integer. There are 2k balls divided into a number of piles. For every two piles A and B with p and q balls respectively, if p ≥ q, then we may transfer q balls from pile A to pile B. Prove that it is always possible to make finitely many such transfers so as to have all the balls end up in one pile. Problem 382. Let v0 = 0, v1 = 1 and vn+1 = 8vn−vn−1 for n = 1,2,3,…. Prove that vn is divisible by 3 if and only if vn is divisible by 7. Problem 383. Let O and I be the circumcenter and incenter of ΔABC respectively. If AB≠AC, points D, E are midpoints of AB, AC respectively and BC=(AB+AC)/2, then prove that the line OI and the bisector of ∠CAB are perpendicular. Problem 384. For all positive real numbers a,b,c satisfying a + b + c = 3, prove that Problem 385. To prepare for the IMO, in everyday of the next 11 weeks, Jack will solve at least one problem. If every week he can solve at most 12 problems, then prove that for some positive integer n, there are n consecutive days in which he can solve a total of 21 problems. Solutions Problem 376. A polynomial is monic if the coefficient of its greatest degree term is 1. Prove that there exists a monic polynomial f(x) with integer coefficients such that for every prime p, f(x) ≡ 0 (mod p) has solutions in integers, but f(x) = 0 has no solution in integers. Solution. Alumni 2011 (Carmel Alison Lam Foundation Secondary School), Maxim BOGDAN (“Mihai Eminescu” National College, Botosani, Romania), Koopa KOO and Andy LOO (St. Paul’s Co-educational College). Let f(x)=(x2−2)(x2−3)(x2−6). Then f(x) = 0 has no solution in integers. For p = 2 or 3, f(6) ≡ 0 (mod p). For a prime p > 3, if there exists x such that x2 ≡ 2 or 3 (mod p), then f(x) ≡ 0 (mod p) has solutions in integers. Otherwise, from Euler’s criterion, it follows that there will be x such that x2 ≡ 6 (mod p) and again f(x) ≡ 0 (mod p) has solutions in integers. Comments: For readers not familiar with Euler’s criterion, we will give a bit more details. For c relatively prime to a prime p, by Fermat’s little theorem, we have (c(p−1)/2−1)(c(p−1)/2+1) = cp−1−1≡ 0 (mod p), which implies c(p−1)/2 ≡ 1 or −1 (mod p). If there exists x such that x2 ≡ c (mod p), then c(p−1)/2 ≡ xp−1 ≡ 1 (mod p). Conversely, if c(p−1)/2 ≡ 1 (mod p), then there is x such that x2 ≡ c (mod p). [This is because there is a primitive root g (mod p) (see vol. 15, no. 1, p. 1 of Math Excalibur), so we get c ≡ gi (mod p) for some positive integer i, then gi(p−1)/2 ≡ 1 (mod p). Since g is a primitive root (mod p), so i(p−1)/2 is a multiple of p−1, then i must be even, hence c ≡ (gi/2)2 (mod p).] In above, if 2 and 3 are not squares (mod p), then 6(p−1)/2=2(p−1)/23(p−1)/2 ≡ (−1)2 =1 (mod p), hence 6 is a square (mod p). Problem 377. Let n be a positive integer. For i=1,2,…,n, let zi and wi be complex numbers such that for all 2n choices of ε1, ε2, …, εn equal to ±1, we have Prove that Solution. William PENG and Jeff PENG (Dallas, Texas, USA). The case n = 1 is clear. Next, recall the parallelogram law |a+b|2+|a−b|2=2|a|2+2|b|2, which follows from adding the + and − cases of the identity (a ±b)(a ±b) = aa ± ab ±ba +bb. For n = 2, we have |z1+z2|≤|w1+w2| and |z1−z2|≤|w1−w2|. Squaring both sides of these inequalities, adding them and applying the parallelogram law, we get the desired inequality. Next assume the case n=k holds. Then for the n=k+1 case, we use the 2k choices with ε1 = ε2 to get from the n=k case that Similarly, using the other 2k choices with 1 = 2, we get Adding the last two inequalities and applying the parallelogram law, we get the n=k+1 case. Other commended solvers: Alumni 2011 (Carmel Alison Lam Foundation Secondary School),Maxim BOGDAN (“Mihai Eminescu” National College, Botosani, Romania), O Kin Chit, Alex (G.T.(Ellen Yeung) College) and Mohammad Reza SATOURI (Bushehr, Iran). Problem 378. Prove that for all positive integers m and n, there exists a positive integer k such that 2k −m has at least n distinct positive prime divisors. Solution. William PENG and Jeff PENG(Dallas,Texas, USA). For the case m is odd, we will prove the result by inducting on n. If n=1, then just choose k large so that the odd number 2k −m is greater than 1. Next assume there exists a positive integer k such that j = 2k −m has at least n distinct positive prime divisors. Let s= k+φ(j2), where φ(j2) is the number of positive integers at most j2 that are relatively prime to j2. Since j is odd, by Euler’s theorem, 2s − m ≡ 2k ×1−m = j (mod j 2 ). Then 2s − m is of the form j+tj2 for some positive integer t. Hence it is divisible by j and (2s − m)/j is relatively prime to j. Therefore, 2s − m has at least n+1 distinct prime divisors. For the case m is even, write m=2ir, where i is a nonnegative integer and r is odd. Then as proved above there is k such that 2k − r has at least n distinct prime divisors and so is 2i+k − m. Mathematical Excalibur, Vol. 16, No. 3, Nov.11 -Jan. 12 Page 4 Other commended solvers: Maxim BOGDAN (“Mihai Eminescu” National College, Botosani, Romania) Problem 379. Let ℓ be a line on the plane of ΔABC such that ℓ does not intersect the triangle and none of the lines AB, BC, CA is perpendicular to ℓ. Let A’, B’, C’ be the feet of the perpendiculars from A, B, C to ℓ respectively. Let A’’, B”, C” be the feet of the perpendiculars from A’, B’, C’ to lines BC, CA, AB respectively. Prove that lines A’A”, B’B”, C’C” are concurrent. Solution. William PENG and Jeff PENG (Dallas, Texas, USA) and ZOLBAYAR Shagdar (9th Grade, Orchlon Cambridge International School, Mongolia). Let lines B’B” and C’C” intersect at D. To show line A’A” also contains D, since ∠CA”A’ = 90°, it suffices to show ∠CA”D = 90°. Let lines BC and B’B” intersect at O. We claim that ΔDOA” is similar to Δ COB”. (Since ∠ OB”C = 90°, the claim will imply ∠OA”D = 90°, which is the same as ∠CA”D = 90°.) For the claim, first note ∠AC”D = 90° = ∠AB”D, which implies A,C”,B”,D are concyclic. So ∠C”AB”=∠B”DC”. Next, ∠BC”D = 90° =∠DA”B implies B,C”,A”,D are concyclic. So ∠C”BA” =∠A”DC”. Then ∠ODA”=180°−(∠A”DC”+∠B”DC”) =180°− (∠C”BA”+∠C”AB”) =∠ACB =∠OCB”. This along with ∠DOA”=∠COB” yield the claim and we are done. Other commended solvers: Alumni 2011 (Carmel Alison Lam Foundation Secondary School) and Maxim BOGDAN (“Mihai Eminescu” National College, Botosani, Romania). Problem 380. Let S = {1,2,…,2000}. If A and B are subsets of S, then let |A| and |B| denote the number of elements in A and in B respectively. Suppose the product of |A| and |B| is at least 3999. Then prove that sets A−A and B−B contain at least one common element, where X−X denotes {s−t : s, t ∈ X and s ≠ t}. (Source: 2000 Hungarian-Israeli Math Competition) Solution. Maxim BOGDAN (“Mihai Eminescu” National College, Botosani, Romania) and William PENG and Jeff PENG (Dallas,Texas, USA). Note that the set T={(a,b): aεA and bεB} has |A|×|B| ≥ 3999 elements. Also, the set W={a+b: aεA and bεB} is a subset of {2,3,…4000}. If W = {2,3,…,4000}, then 2 and 4000 in W imply sets A and B both contain 1 and 2000. This leads to A−A and B−B both contain 1999. If W≠{2,3,…4000}, then W has less than 3999 elements. By the pigeonhole principle, there would exist (a,b) ≠ (a’,b’) in T such that a+b=a’+b’. This leads to a−a’=b’−b in both A−A and B−B. Olympiad Corner (continued from page 1) Problem 3. Let f : be a real-valued function defined on the set of real numbers that satisfies f(x+y) ≤ y f(x) + f( f(x)) for all real numbers x and y. Prove that f(x) = 0 for all x Problem 4. Let n > 0 be an integer. We are given a balance and n weights of weigh 20, 21, …, 2n−1. We are to place each of the n weights on the balance, one after another, in such a way that the right pan is never heavier than the left pan. At each step we choose one of the weights that has not yet been placed on the balance, and place it on either the left pan or the right pan, until all the weights have been placed. Determine the number of ways in which this can be done. Problem 5. Let f be a function from the set of integers to the set of positive integers. Suppose that, for any two integers m and n, the difference f(m)−f(n) is divisible by f(m−n). Prove that, for all integers m and n with f(m)≤f(n), the number f(n) is divisible by f(m). Problem 6. Let ABC be an acute triangle with circumcircle. Let L be a tangent line to γ, and let La, Lb and Lc be the line obtained by reflecting L in the lines BC, CA and AB, respectively. Show that the circumcircle of the triangle determined by the lines La, Lb and Lc is tangent to the circle γ. Remarks on IMO 2011 (continued from page 2) The essential point is to observe that A”B”C” is in fact homothetic to A’B’C’, with the homothetic center at H, a point on i.e. A”B”C” is an expansion of A’B’C’ at H by a constant centre. This implies the circumcircle of A”B”C” is tangent to γ at H. A lot of discussions were conducted concerning changing the format of the Jury system during the IMO. At present the leaders assemble to choose six problems from the short-listed problems. There are issues concerning security and also financial matter (to house the leaders in an obscure place far away from the contestants can be costly). Many contestants need good results to obtain scholarships and enter good universities and the leaders have incentive for their own good to obtain good results for their teams. For me I am inclined to let the Jury system remains as such. The main reason is simply the law of large numbers, a better paper may be produced if more people are involved. Indeed both the Problem Selection Group and the leaders may make mistakes. But we get a better chance to produce a better paper after detailed discussion. In my opinion we generally produce a more balanced paper. The discussion is still going on. Perhaps some changes are unavoidable, for better or for worse. Here are some remarks concerning the performance of the teams. We keep our standard or perhaps slightly better than the last few years. I am glad that some of our team members are able to solve the harder problems. Although the Chinese team is still ranked first (unofficially), they are not far better than the other strong teams (USA, Russia, etc). In particular, the third rank performance of the Singaporean team this time is really amazing. 4. Solutions to Olympiad Corner, Vol 16, no. 3 Problem 1, maximum value, loss of generality pair of indices Inequality candidate solutions Problem 2 Give the rotating line an orientation and distinguish its side as the oranje side and the blue side . Notice that whenever the pivot changes from some point T to another point U after the change T is on the same side as U was before. Therefore, the number of elements of # on the oranje side and the number of those on the blue side remain the same throughout the whole process (except for those moments when the line contains two points First consider the case that S is odd we claim that through any point T S there is a line that has n points on each side. To see this, choose an oriented line through T containing no other point o S and suppose that it has n + r points on its oranje side if r then we have established the claim so we may assume that as the line rotates through 180 around T the number of points of S on its oranje side changes by 1 whenever the line passes through a point after 180 the number of points on the oranje side is n – r therefore there is an intermediate stage at which the oranje side, and thus also the blue side contains n points. Point P arbitrarily line initial state of the windmill. During a rotation windmill pivot the unique Parallel translation disturb the balance odd case oriented line blue side Problems 3 substituting Real numbers Inequalities yields Substitute contradicts here Inequalities yields A zero of Problems 4 assume first move left pan heavier than scale Weight answer left side right side inserting Left pan valid sequences positive integers Problem 5 two integers taking m the given condistion f Hence the difference satisfies Deduce Problem 6 avoid a large case distinction notion of oriented angles Namely for two lines m and n we denote angle rotate anticlockwise Line parallel All oriented angles are considered modulo 180 Denote the point of tangency similar way Midpoints triangles homothetic translates of each other homothely belongs circumcircles respect tangent intersection consider the case symmetry angle bisectors of the lines analogrously Bisectors of the lines the incenter or one of the angle bisectors of the lines one of the excenters of triangle Analogously concyclic Now we can complete the proof. Let K be the second intersection point Applying PASCAL’s theorem to hexagon collinear with the intersection point the center of the homothety mapping