v15_n2

Volume 15, Number 2 July - September, 2010 Lagrange Interpolation Formula Kin Y. Li Olympiad Corner Below are the problems used in the selection of the Indian team for IMO-2010. Problem 1. Is there a positive integer n, which is a multiple of 103, such that 22n+1≡2 (mod n)? Problem 2. Let a, b, c be integers such that b is even. Suppose the equation x3+ax2+bx+c=0 has roots α, β, γ such that α2 = β+γ. Prove that α is an integer and β≠γ. Problem 3. Let ABC be a triangle in which BC < AC. Let M be the midpoint of AB; AP be the altitude from A on to BC; and BQ be the altitude from B on to AC. Suppose QP produced meet AB (extended) in T. If H is the orthocenter of ABC, prove that TH is perpendicular to CM. Problem 4. Let ABCD be a cyclic quadrilateral and let E be the point of intersection of its diagonals AC and BD. Suppose AD and BC meet in F. Let the midpoints of AB and CD be G and H respectively. If Γ is the circumcircle of triangle EGH, prove that FE is tangent to Γ. (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 October 20, 2010. For individual subscription for the next five issues for the 10-11 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 Let n be a positive integer. If we are given two collections of n+1 real (or complex) numbers w0, w1, …, wn and c0, c1, …, cn with the wk’s distinct, then there exists a unique polynomial P(x) of degree at most n satisfying P(wk) = ck for k = 0,1,…,n. The uniqueness is clear since if Q(x) is also such a polynomial, then P(x)−Q(x) would be a polynomial of degree at most n and have roots at the n+1 numbers w0, w1, …, wn, which leads to P(x)−Q(x) be the zero polynomial. Now, to exhibit such a polynomial, we define f0(x)=(x−w1)(x−w2)⋯(x−wn) and similarly for i from 1 to n, define fi(x)=(x−w0)⋯(x−wi−1)(x−wi+1)⋯(x−wn). Observe that fi(wk) = 0 if and only if i≠k. Using this, we see ∑ = = n i ii i i wf xfcxP 0 )( )()( satisfies P(wk) = ck for k = 0,1,…,n. This is the famous Lagrange interpolation formula. Below we will present some examples of using this formula to solve math problems. Example 1. (Romanian Proposal to 1981 IMO) Let P be a polynomial of degree n satisfying for k = 0,1,…,n, . 1 )( 1− ⎟⎟⎠ ⎞ ⎜⎜⎝ ⎛ += k n kP Determine P(n+1). Solution. For k = 0,1,…,n, let wk=k and . )!1( )!1(!1 1 + −+=⎟⎟⎠ ⎞ ⎜⎜⎝ ⎛ += − n knk k n ck Define f0, f1, … , fn as above. We get fk(k) = (−1)n−kk!(n−k)! and . )1( )!1()1( kn nnfk −+ +=+ By the Lagrange interpolation formula, ,)1( )( )1()1( 0 0 ∑ ∑ = = −−=+=+ n k n k kn k k k kf nfcnP which is 0 if n is odd and 1 if n is even. Example 2. (Vietnamese Proposal to 1977 IMO) Suppose x0, x1, …, xn are integers and x0 > x1> ⋯ > xn. Prove that one of the numbers |P(x0)|, |P(x1)|, … , |P(xn)| is at least n!/2n, where P(x) = xn + a1xn–1 + ⋯ + an is a polynomial with real coefficients. Solution. Define f0, f1, … , fn using x0, x1, …, xn. By the Lagrange interpolation formula, we have , )( )()()( 0 ∑ = = n i ii i i xf xfxPxP since both sides are polynomials of degrees at most n and are equal at x0, x1, …, xn. Comparing coefficients of xn, we get ∑ = = n i ii i xf xP 0 . )( )(1 Since x0, x1, …, xn are strictly decreasing integers, we have ∏∏ += − = −−= n ij ij i j ijii xxxxxf 1 1 0 |||||)(| . ! 1)!(! ⎟⎟⎠ ⎞ ⎜⎜⎝ ⎛=−≥ i n n ini Let the maximum of |P(x0)|, |P(x1)|, … , |P(xn)| be |P(xk)|. By the triangle inequality, we have . ! )(2 ! )( )(| )( 1 00 n xP i n n xP xf xP k nn i k n i ii i =⎟⎟⎠ ⎞ ⎜⎜⎝ ⎛≤≤ ∑∑ == Then |P(xk)| ≥ n!/2n. Example 3. Let P be a point on the plane of ∆ABC. Prove that .3≥++ AB PC CA PB BC PA Mathematical Excalibur, Vol. 15, No. 2, Jul. - Sep. 2010 Page 2 Solution. We may take the plane of ∆ABC to be the complex plane and let P, A, B, C be corresponded to the complex numbers w, w1, w2, w3 respectively. Then PA=|w–w1|, BC=|w2–w3|, etc. Now the only polynomial P(x) of degree at most 2 that equals 1 at w1, w2, w3 is the constant polynomial P(x) ≡ 1. So, expressing P(x) by the Lagrange interpolation formula, we have ))(( ))(( ))(( ))(( 3121 32 2313 21 wwww wxwx wwww wxwx −− −−+−− −− .1 ))(( ))(( 1232 13 ≡−− −−+ wwww wxwx Next, setting x = w and applying the triangle inequality, we get .1≥++ BC PA AB PC AB PC CA PB CA PB BC PA (*) The inequality (r+s+t)2 ≥ 3(rs+st+tw), after subtracting the two sides, reduces to [(r–s)2+(s–t)2+(t–r)2]/2 ≥ 0, which is true. Setting r= PA/BC, s=PB/CA and t=PC/AB, we get .3 2 ⎟⎠ ⎞⎜⎝ ⎛ ++≥⎟⎠ ⎞⎜⎝ ⎛ ++ BC PA AB PC AB PC CA PB CA PB BC PA AB PC CA PB BC PA Taking square roots of both sides and applying (*), we get the desired inequality. Example 4. (2002 USAMO) Prove that any monic polynomial (a polynomial with leading coefficient 1) of degree n with real coefficients is the average of two monic polynomials of degree n with n real roots. Solution. Suppose F(x) is a monic real polynomial. Choose real y1, y2, … ,yn such that for odd i, yi < min{0,2F(i)} and for even i, yi > max{0,2F(i)}. By the Lagrange interpolation formula, there is a polynomial of degree less than n such that P(i) = yi for i=1,2,…,n. Let G(x) = P(x)+(x−1)(x−2)⋯(x−n) and H(x) = 2F(x)−G(x). Then G(x) and H(x) are monic real polynomials of degree n and their average is F(x). As y1, y3, y5, … < 0 and y2, y4, y6, ⋯ > 0, G(i)=yi and G(i+1)=yi+1 have opposite signs (hence G(x) has a root in [i,i+1]) for i=1,2,…,n−1. So G(x) has at least n−1 real roots. The other root must also be real since non-real roots come in conjugate pair. Therefore, all roots of G(x) are real. Similarly, for odd i, G(i) = yi < 2F(i) implies H(i)=2F(i)−G(i) > 0 and for even i, G(i) = yi > 2F(i) implies H(i) = 2F(i)−G(i) < 0. These imply H(x) has n real roots by reasoning similar to G(x). Example 5. Let a1, a2, a3, a4, b1, b2, b3, b4 be real numbers such that bi–aj≠0 for i,j=1,2,3,4. Suppose there is a unique set of numbers X1, X2, X3, X4 such that ,1 41 4 31 3 21 2 11 1 =−+−+−+− ab X ab X ab X ab X ,1 42 4 32 3 22 2 12 1 =−+−+−+− ab X ab X ab X ab X ,1 43 4 33 3 23 2 13 1 =−+−+−+− ab X ab X ab X ab X .1 44 4 34 3 24 2 14 1 =−+−+−+− ab X ab X ab X ab X Determine X1+X2+X3+X4 in terms of the ai’s and bi’s. Solution. Let .)()()( 4 1 4 1 ∏ ∏ = = −−−= i i ii bxaxxP Then the coefficient of x3 in P(x) is . 4 1 4 1 ∑ ∑ = = − i i ii ab Define f1, f2, f3, f4 using a1, a2, a3, a4 as above to get the Lagrange interpolation formula . )( )()()( 4∑ = = ii ii i i af xfaPxP Since the coefficient of x3 in fi(x) is 1, the coefficient of x3 in P(x) is also . )( )(4 1 ∑ =i ii i af aP Next, observe that P(bj)/fi(bj) = bj – ai, which are the denominators of the four given equations! For j = 1,2,3,4, setting x = bj in the interpolation formula and dividing both sides by P(bj), we get .)(/)( )( )( )( )(1 4 4 1 ∑ ∑ = = −== ii i ij iii ii ji j i ab afaP af bf bP aP Comparing with the given equations, by uniqueness, we get Xi=P(ai)/fi(ai) for i = 1,2,3,4. So . )( )( 4 1 44 1 4 1 ∑ ∑∑∑ = === −== i i ii i ii i i i abaf aPX Comment: This example is inspired by problem 15 of the 1984 American Invitational Mathematics Examination. Example 6. (Italian Proposal to 1997 IMO) Let p be a prime number and let P(x) be a polynomial of degree d with integer coefficients such that: (i) P(0) = 0, P(1) = 1; (ii) for every positive integer n, the remainder of the division of P(n) by p is either 0 or 1. Prove that d ≥ p − 1. Solution. By (i) and (ii), we see P(0)+P(1)+⋯+P(p − 1)≡k (mod p) (#) for some k∈{1,2,…, p − 1}. Assume d ≤ p − 2. Then P(x) will be uniquely determined by the values P(0), P(1), …, P(p − 2). Define f0, f1, …, fp−2 using 0, 1, …, p − 2 as above to get the Lagrange interpolation formula . )( )()()( 2 0 ∑− = = p k k k kf xfkPxP As in example (1), we have fk(k) = (−1)p−2−kk!(p−2−k)!, kp ppfk −− −=− 1 )!1()1( and so . 1 )1)(()1( 2 0 ∑− = − ⎟⎟⎠ ⎞ ⎜⎜⎝ ⎛ −−=− p k kp k p kPpP Next, we claim that .20)(mod)1( 1 −≤≤−≡⎟⎟⎠ ⎞ ⎜⎜⎝ ⎛ − pkforp k p k This is true for k = 0. Now for 0 < i < p, )(mod0 )!(! ! p ipi p i p ≡−=⎟⎟⎠ ⎞ ⎜⎜⎝ ⎛ because p divides p!, but not i!(p−i)!. If the claim is true for k, then )(mod)1( 1 11 1 1 p k p k p k p k+−≡⎟⎟⎠ ⎞ ⎜⎜⎝ ⎛ −−⎟⎟⎠ ⎞ ⎜⎜⎝ ⎛ +=⎟⎟⎠ ⎞ ⎜⎜⎝ ⎛ + − and the induction step follows. Finally the claim yields ∑− = −≡− 2 0 ).(mod)()1()1( p k p pkPpP So P(0)+P(1)+⋯+P(p − 1)≡ 0 (mod p), a contradiction to (#) above. Mathematical Excalibur, Vol. 15, No. 2, Jul. - Sep. 2010 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 October 20, 2010. Problem 351. Let S be a unit sphere with center O. Can there be three arcs on S such that each is a 300° arc on some circle with O as center and no two of the arcs intersect? Problem 352. (Proposed by Pedro Henrique O. PANTOJA, University of Lisbon, Portugal) Let a, b, c be real numbers that are at least 1. Prove that . 2 3 111 222 ≥+++++ ab abc ca cab bc bca Problem 353. Determine all pairs (x, y) of integers such that x5−y2=4. Problem 354. For 20 boxers, find the least number n such that there exists a schedule of n matches between pairs of them so that for every three boxers, two of them will face each other in one of the matches. Problem 355. In a plane, there are two similar convex quadrilaterals ABCD and AB1C1D1 such that C, D are inside AB1C1D1 and B is outside AB1C1D1 Prove that if lines BB1, CC1 and DD1 concur, then ABCD is cyclic. Is the converse also true? ***************** Solutions **************** Problem 346. Let k be a positive integer. Divide 3k pebbles into five piles (with possibly unequal number of pebbles). Operate on the five piles by selecting three of them and removing one pebble from each of the three piles. If it is possible to remove all pebbles after k operations, then we say it is a harmonious ending. Determine a necessary and sufficient condition for a harmonious ending to exist in terms of the number k and the distribution of pebbles in the five piles. (Source: 2008 Zhejiang Province High School Math Competition) Solution. CHOW Tseung Man (True Light Girl’s College), CHUNG Ping Ngai (MIT Year 1), HUNG Ka Kin Kenneth (CalTech Year 1). The necessary and sufficient condition is every pile has at most k pebbles in the beginning. The necessity is clear. If there is a pile with more than k pebbles in the beginning, then in each of the k operations, we can only remove at most 1 pebble from that pile, hence we cannot empty the pile after k operations. For the sufficiency, we will prove by induction. In the case k=1, three pebbles are distributed with each pebble to a different pile. So we can finish in one operation. Suppose the cases less than k are true. For case k, since 3k pebbles are distributed. So at most 3 piles have k pebbles. In the first operation, we remove one pebble from each of the three piles with the maximum numbers of pebbles. This will take us to a case less than k. We are done by the inductive assumption. Problem 347. P(x) is a polynomial of degree n such that for all w∈{1, 2, 22, …, 2n}, we have P(w) = 1/w. Determine P(0) with proof. Solution 1. Carlo PAGANO (Università di Roma “Tor Vergata”, Roma, Italy). William CHAN Wai-lam (Carmel Alison Lam Foundation Secondary School) and Thien Nguyen (Nguyen Van Thien Luong High School, Dong Nai Province, Vietnam). Let Q(x) = xP(x)−1 = a(x−1)(x−2)⋯(x−2n). For x≠1, 2, 22, …, 2n, . 2 1 2 1 1 1 )( )(' nxxxxQ xQ −++−+−= L Since Q(0)= −1 and Q’(x)=P(x)+xP’(x), ∑ = −==−== n k nkQ QQP 0 . 2 12 2 1 )0( )0(')0(')0( Solution 2. CHUNG Ping Ngai (MIT Year 1), HUNG Ka Kin Kenneth (CalTech Year 1), Abby LEE (SKH Lam Woo Memorial Secondary School, Form 5) and WONG Kam Wing (HKUST, Physics, Year 2). Let Q(x) = xP(x)−1 = a(x−1)(x−2)⋯(x−2n). Now Q(0) = −1 = a(−1)n+12s, where s = 1+2+⋯+n. So a = (−1)n 2−s. Then P(0) is the coefficient of x in Q(x), which is ∑ = −− −==+++− n k nk nsssna 0 1 . 2 12 2 1)222()1( L Other commended solvers: Samuel Lilό ABDALLA (ITA-UNESP, São Paulo, Brazil), Problem 348. In ∆ABC, we have ∠BAC = 90° and AB < AC. Let D be the foot of the perpendicular from A to side BC. Let I1 and I2 be the incenters of ∆ABD and ∆ACD respectively. The circumcircle of ∆AI1I2 (with center O) intersects sides AB and AC at E and F respectively. Let M be the intersection of lines EF and BC. Prove that I1 or I2 is the incenter of the ∆ODM, while the other one is an excenter of ∆ODM. (Source: 2008 Jiangxi Province Math Competition) Solution. CHOW Tseung Man (True Light Girl’s College). A B CD I1 I2 O F E M We claim EF intersects AD at O. Since ∠EAF=90°, EF is a diameter through O. Next we will show O is on AD. Since AI1, AI2 bisect ∠BAD, ∠CAD respectively, we get ∠I1AI2=45°. Then ∠I1OI2=90°. Since OI1=OI2, ∠OI1I2=45°. Also, DI1, DI2 bisect ∠BDA, ∠CDA respectively implies ∠I1DI2=90°. Then D, I1, O, I2 are concyclic. So .45 2212 ADIIOIODI ∠==∠=∠ o Then O is on AD and the claim is true. Since ∠EOI1 = 2∠EAI1 = 2∠DAI1 = ∠DOI1 and I1 is on the angle bisector of ∠ODM, we see I1 is the incenter of ∆ODM. Similarly, replacing E by F and I1 by I2 in the last sentence, we see I2 is an excenter of ∆ODM. Other commended solvers: CHUNG Ping Ngai (MIT Year 1), HUNG Ka Kin Kenneth (CalTech Year 1) and Abby LEE (SKH Lam Woo Memorial Secondary School, Form 5). Problem 349. Let a1, a2, …, an be rational numbers such that for every positive integer m, m n mm aaa +++ L21 is an integer. Prove that a1, a2, …, an are integers. Mathematical Excalibur, Vol. 15, No. 2, Jul. - Sep. 2010 Page 4 Solution. CHUNG Ping Ngai (MIT Year 1) and HUNG Ka Kin Kenneth (CalTech Year 1). We may first remove all the integers among a1, a2, …, an since their m-th powers are integers, so the rest of a1, a2, …, an will still have the same property. Hence, without loss of generality, we may assume all a1, a2, …, an are rational numbers and not integers. First write every ai in simplest term. Let Q be their least common denominator and for all 1≤i≤n, let ai=ki/Q. Take a prime factor p of Q. Then p is not a prime factor of one of the ki’s. So one of the remainders ri when ki is divided by p is nonzero! Since ki≡ri(mod p), so for every positive integer m, ).(mod0 111 mm n i m i n i m i n i m i pQakr ≡⎟⎠ ⎞⎜⎝ ⎛=≡ ∑∑∑ === This implies . 1 ∑ = ≤ n i m i m rp Since ri < p, ,0lim1lim1 11 =⎟⎟⎠ ⎞ ⎜⎜⎝ ⎛=≤ ∑∑ =∞→=∞→ n i m i m n i m imm p rr p which is a contradiction. Comments: In the above solution, it does not need all positive integers m, just an infinite sequence of positive integers m with the given property will be sufficient. Problem 350. Prove that there exists a positive constant c such that for all positive integer n and all real numbers a1, a2, …, an, if P(x) = (x − a1)(x − a2) ⋯ (x − an), then .)(max)(max ]1,0[]2,0[ xPcxP x n x ∈∈ ≤ (Ed.-Both solutions below show the conclusion holds for any polynomial!) Solution 1. LEE Kai Seng. Let S be the maximum of |P(x)| for all x∈[0,1]. For i=0,1,2,…,n, let bi=i/n and ).())(()()( 110 niii bxbxbxbxxf −−−−= +− LL By the Lagrange interpolation formula, for all real x, . )( )()()( 0 ∑ = = n i ii i i bf xfbPxP For every w∈[0,2], |w−bk| ≤ |2−bk| for all k = 0,1,2,…,n. So ∏ = ⎟⎠ ⎞⎜⎝ ⎛ −=≤ n i ii n ifwf 0 2)2()( nn nnnn )1()22)(12(2 +−−= L . ! )!2( nnn n= Also, |P(bi)| ≤ S and .)!(!)( nii n inibf −= By the triangle inequality, . 22 )( )( )()( 00 ∑∑ == ⎟⎟⎠ ⎞ ⎜⎜⎝ ⎛ − ⎟⎟⎠ ⎞ ⎜⎜⎝ ⎛≤≤ n iii i n i i n in i n S bf wf bPwP Finally, .2 2 2 2222 0 42 0 ∑ ∑ = = ≤⎟⎟⎠ ⎞ ⎜⎜⎝ ⎛=⎟⎟⎠ ⎞ ⎜⎜⎝ ⎛ ⎟⎟⎠ ⎞ ⎜⎜⎝ ⎛≤⎟⎟⎠ ⎞ ⎜⎜⎝ ⎛ − ⎟⎟⎠ ⎞ ⎜⎜⎝ ⎛n i nn n i n n n n i n n in i n Then .)(max162)(max ]1,0[ 4 ]2,0[ xPSwP x nn w ∈∈ =≤ Solution 2. G.R.A.20 Problem Solving Group (Roma, Italy). For a bounded closed interval I and polynomial f(x), let ||f||I denote the maximum of |f(x)| for all x in I. The Chebyschev polynomial of order n is defined by T0(x) = 1, T1(x) = x and Tn(x) = 2xTn−1(x)−Tn−2(x) for n ≥ 2. (Ed.-By induction, we can obtain Tn(x) = 2nxn+cn−1xn−1 + ⋯ + c0 and Tn(cos θ)=cos nθ. So Tn(cos(πk/n))= (−1)k, which implies all n roots of Tn(x) are in (−1,1) as it changes sign n times.) It is known that for any polynomial Q(x) with degree at most n>0 and all t∉[−1,1], |Q(t)| ≤ ||Q||[−1,1] |Tn(t)|. (!) To see this, we may assume ||Q||[−1,1] = 1 by dividing Q(x) by such maximum. Assume x0∉[−1,1] and |Q(x0)| > |Tn(x0)|. Let a = T(x0)/Q(x0) and R(x) = aQ(x)−Tn(x). For k = 0, 1, 2, ⋯, n, since Tn(cos(πk/n)) = (−1)k and |a|<1, we see R(cos(πk/n)) is positive or negative depending on whether k is odd or even. (In particular, R(x)≢0.) By continuity, R(x) has n+1 distinct roots on [−1,1]∪{x0}, which contradicts the degree of R(x) is at most n. Next, for the problem, we claim that for every t∈[1,2], we have |P(t)| ≤ 6n ||P||[0,1]. (Ed.-Observe that the change of variable t = (s+1)/2 is a bijection between s∈[−1,1] and t∈[0,1]. It is also a bijection between s∈[1,3] and t∈[1,2].) By letting Q(s) = P((s+1)/2), the claim is equivalent to proving that for every s∈[1,3], we have |Q(s)|≤ 6n||Q||[−1,1]. By (!) above, it suffices to show that |Tn(s)| ≤ 6n for every s∈[1,3]. Clearly, |T0(s)|=1=60. For n=1 and s∈[1,3], |T1(s)|=s≤3<6. Next, since the largest root of Tn is less than 1, we see all Tn(s) > 0 for all s∈[1,3]. Suppose cases n−2 and n−1 are true. Then for all s∈[1,3], we have 2sTn−1(s), Tn−2(s) > 0 and so |Tn(s)| = |2sTn−1(s)−Tn−2(s)| ≤ max(2sTn−1(s), Tn−2(s)) ≤ max(6·6n−1, 6n−2) = 6n. This finishes everything. Olympiad Corner (continued from page 1) Problem 5. Let A=(ajk) be a 10×10 array of p