Mathematical Excalibur, Volume 11, Number 4

Abstract

Mathematical Excalibur Volume 11, Number 4 November 2006 – December 2006 Pole and Polar Kin Y. Li Olympiad Corner The 9th China Hong Kong Math Olympiad was held on Dec. 2, 2006. The following were the problems. Problem 1. Let M be a subset of {1, 2, …, 2006} with the following property: For any three elements x, y and z (x < y < z) of M, x + y does not divide z. Determine the largest possible size of M. Justify your claim. Problem 2. For a positive integer k, let f1(k) be the square of the sum of the digits of k. (For example f1(123) = (1+2+3)2 = 36.) Let fn+1(k) = f1(fn(k)). Determine the value of f2007(22006). Justify your claim. Problem 3. A convex quadrilateral ABCD with AC ≠ BD is inscribed in a circle with center O. Let E be the intersection of diagonals AC and BD. If P is a point inside ABCD such that , 90o = ∠ + ∠ = ∠ + ∠ PDC PBC PCB PAB prove that O, P and E are collinear. Problem 4. Let a1, a2, a3,… be a sequence of positive numbers. If there exists a positive number M such that for every n = 1, 2, 3, …, 2 2 2 2 1 2 1 ... , n n a a a Ma+ + + + < then prove that there exists a positive number M’ such that for every n = 1, 2, 3, …, 1 2 1 ... ' . n n a a a M a+ + + + < 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 January 25, 2007. For individual subscription for the next five issues for the 05-06 academic year, send us five stamped self-addressed envelopes. Send all correspondence to: Dr. Kin-Yin LI Department of Mathematics The Hong Kong University of Science and Technology Clear Water Bay, Kowloon, Hong Kong Fax: (852) 2358 1643 Email: makyli@ust.hk Let C be a circle with center O and radius r. Recall the inversion with respect to C (see Mathematical Excalibur, vol. 9, no. 2, p.1) sends every point P≠O in the same plane as C to the image point P’ on the ray OP such that OP·OP’=r2. The polar of P is the line p perpendicular to the line OP at P’. Conversely, for any line p not passing through O, the pole of p is the point P whose polar is p. The function sending P to p is called the pole-polar transformation (or reciprocation) with respect to O and r (or with respect to C). Following are some useful facts: (1) If P is outside C, then recall P’ is found by drawing tangents from P to C, say tangent at X and Y. Then P’ = OP ∩XY, where ∩ denotes intersection. By Symmetry, OP⊥XY. So the polar p of P is the line XY. Conversely, for distinct points X, Y on C, the pole of the line XY is the intersection of the tangents at X and Y. Also, it is the point P on the perpendicular bisector of XY such that O, X, P, Y are concyclic since ∠ OXP = 90°= ∠ OYP. (2) (La Hire’s Theorem) Let x and y be the polars of X and Y, respectively. Then X is on line y  Y is on line x. Proof. Let X’, Y’ be the images of X, Y for the inversion with respect to C. Then OX·OX’ = r2 = OY·OY’ implies X, X’, Y, Y’ are concyclic. Now X is on y ∠ XY’Y = 90° ∠ XX’Y = 90°  Y is on x. (3) Let x,y,z be the polars of distinct points X,Y,Z respectively. Then Z = x∩y  z = XY. Proof. By La Hire’s theorem, Z on x∩y  X on z and Y on z  z = XY. (4) Let W, X, Y, Z be on C. The polar p of P = XY∩WZ is the line through Q = WX∩ZY and R = XZ∩YW. Proof. Let S, T be the poles of s = XY, t = WZ respectively. Then P = s∩t. By fact (3), S = x∩y, T = w∩z and p = ST. For hexagon WXXZYY, we have Q=WX∩ZY, S=XX∩YY, R=XZ∩YW, where XX denotes the tangent line at X. By Pascal’s theorem (see Mathematical Excalibur, vol. 10, no. 3, p.1), Q,S,R are collinear. Similarly, considering the hexagon XWWYZZ, we see Q,T,R are collinear. Therefore, p = ST = QR. Next we will present some examples using the pole-polar transformation. Example 1. Let UV be a diameter of a semicircle. P,Q are two points on the semicircle with UP<UQ. The tangents to the semicircle at P and Q meet at R. If S=UP∩VQ, then prove that RS⊥UV. Solution (due to CHENG Kei Tsi). Let K=PQ∩UV. With respect to the circle, by fact (4), the polar of K passes through UP∩VQ=S. Since the tangents to the semicircle at P and Q meet at R, by fact (1), the polar of R is PQ. Since K is on line PQ, which is the polar of R, by La Hire’s theorem, R is on the polar of K. So the polar of K is the line RS. As K is on the diameter UV extended, by the definition of polar, we get RS⊥UV. Mathematical Excalibur, Vol. 11, No. 4, Nov. 06 – Dec. 06 Page 2 Example 2. Quadrilateral ABCD has an inscribed circle Γ with sides AB, BC, CD, DA tangent to Γ at G, H, K, L respectively. Let AB∩CD =E, AD∩BC = F and GK∩HL = P. If O is the center of Γ, then prove that OP⊥EF. Solution. Consider the pole-polar transformation with respect to the inscribed circle. By fact (1), the polars of E, F are lines GK, HL respectively. Since GK∩HL = P, by fact (3), the polar of P is line EF. By the definition of polar, we get OP⊥EF. Example 3. (1997 Chinese Math Olympiad) Let ABCD be a cyclic quadrilateral. Let AB∩CD = P and AD∩BC = Q. Let the tangents from Q meet the circumcircle of ABCD at E and F. Prove that P, E, F are collinear. Solution. Consider the pole-polar transformation with respect to the circumcircle of ABCD. Since P = AB∩CD, by fact (4), the polar of P passes through AD∩BC = Q. By La Hire’s theorem, P is on the polar of Q, which by fact (1), is the line EF. Example 4. (1998 Austrian-Polish Math Olympiad) Distinct points A, B, C, D, E, F lie on a circle in that order. The tangents to the circle at the points A and D, the lines BF and CE are concurrent. Prove that the lines AD, BC, EF are either parallel or concurrent. Solution Let O be the center of the circle and X = AA∩DD∩BF∩CE. If BC||EF, then by symmetry, lines BC and EF are perpendicular to line OX. Since AD⊥OX, we get BC||EF||AD. If lines BC, EF intersect, then by fact (4), the polar of X = CE∩BF passes through BC∩EF. Since the tangents at A and D intersect at X, by fact (1), the polar of X is line AD. Therefore, AD, BC and EF are concurrent in this case. Example 5. (2006 China Western Math Olympiad) As in the figure below, AB is a diameter of a circle with center O. C is a point on AB extended. A line through C cuts the circle with center O at D, E. OF is a diameter of the circumcircle of .BOD with center O1. Line CF intersect the circumcircle again at G. Prove that O,A,E,G are concyclic.

Solution (due to WONG Chiu Wai). Let AE∩BD=P. By fact (4), the polar of P with respect to the circle having center O is the line through BA∩DE = C and AD∩EB = H. Then OP⊥CH. Let Q = We claim Q = G. Once this shown, we will have P = BD ∩ OG. Then PE·PA = PD·PB = PG·PO, which implies O, A, E, G are concyclic. To show Q = G, note that ∠ PQH, ∠ PDH and ∠ PEH are 90°, which implies P, E, Q, H, D are concyclic. Then ∠ PQD = ∠ PED = ∠ DBO, which implies Q, D, B, O are concyclic. Therefore, Q = G since they are both the point of intersection (other than O) of the circumcircle of .BOD and the circle with diameter OC. Example 6. (2006 China Hong Kong Math Olympiad) A convex quadrilateral ABCD with AC ≠ BD is inscribed in a circle with center O. Let E be the intersection of diagonals AC and BD. If P is a point inside ABCD such that 90o = ∠ + ∠ = ∠ + ∠ PDC PBC PCB PAB prove that O, P and E are collinear. Solution (due to WONG Chiu Wai). Let Γ, Γ1, Γ2 be the circumcircles of quadrilateral ABCD, .PAC, .PBD with centers O, O1, O2 respectively. We first show that the polar of O1 with respect to Γ is line AC. Since OO1 is the perpendicular bisector of AC, by fact (1), all we need to show is that ∠ AOC + ∠ AO1C = 180°. For this, note ∠ APC = 360°. ( ∠ PAB +∠ PCB+ ∠ ABC) = 270°. ∠ ABC = 90° +∠ ADC and so ∠ AO1C =2(180°. ∠ APC) =2(90°. ∠ ADC) =180°.2 ∠ ADC =180°. ∠ AOC. Similarly, the polar of O2 with respect to Γ is line BD. By fact (3), since E = AC∩BD, the polar of E with respect to Γ is line O1O2. So OE⊥O1O2. (Next we will consider radical axis and radical center, see Mathematical Excalibur, vol. 4, no. 3, p. 2.) Among Γ, Γ1, Γ2, two of the pairwise radical axes are lines AC and BD. This implies E is the radical center. Since Γ1, Γ2 intersect at P, so PE is the radical axis of Γ1, Γ2, which implies PE⊥O1O2. Combining with OE⊥O1O2 proved above, we see O, P and E are collinear. (continued on page 4) Mathematical Excalibur, Vol. 11, No. 4, Nov. 06 – Dec. 06 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 submitting solutions is January 25, 2007. Problem 261. Prove that among any 13 consecutive positive integers, one of them has sum of its digits (in base 10) divisible by 7. Problem 262. Let O be the center of the circumcircle of .ABC and let AD be a diameter. Let the tangent at D to the circumcircle intersect line BC at P. Let line PO intersect lines AC, AB at M, N respectively. Prove that OM = ON. Problem 263. For positive integers m, n, consider a (2m+1)×(2n+1) table, where in each cell, there is exactly one ant. At a certain moment, every ant moves to a horizontal or vertical neighboring cell. Prove that after that moment, there exists a cell with no ant. Problem 264. For a prime number p > 3 and arbitrary integers a, b, prove that p p ba ab . is divisible by 6p. Problem 265. Determine (with proof) the maximum of where x1, x2, …, xn are nonnegative real numbers whose sum is 1.

Solutions

Problem 256. Show that there is a rational number q such that 0 90 sin 89 sin 2 sin 1 sin q = o o o o L Solution 1. Jeff CHEN (Virginia, USA), Koyrtis G. CHRYSSOSTOMOS (Larissa, Greece, teacher), G.R.A. 20 Math Problem Group (Roma, Italy) and D. Kipp JOHNSON (Valley Catholic School, Teacher, Beaverton, Oregon, USA). Let . 180 / 2 i e π ω= Then we have 1 sin Therefore, . 10 3 sin 89 ko Solution 2. Jeff CHEN (Virginia, USA), Koyrtis G. CHRYSSOSTOMOS (Larissa, Greece, teacher). Let S be the left-handed side. Note sin cos 2 cos sin 3 sin + = 60 sin( ) 60 sin( sin 4 Using this, we have Problem 257. Let n > 1 be an integer. Prove that there is a unique positive integer A < n2 such that [n2/A] + 1 is divisible by n, where [x] denotes the greatest integer less than or equal to x. (Source: 1993 Jiangsu Math Contest) Solution. Jeff CHEN (Virginia, USA), G.R.A. 20 Math Problem Group (Roma, Italy) and Fai YUNG. We claim the unique number is A =n+1. If n = 2, then 1 ≤ A < n2 = 4 and only A = 3 works. If n > 2, then [n2/A]+1 divisible by n implies This leads to The case A = n + 1 works because The case A = n does not work because [n2/n] + 1 = n + 1 is not divisible by n when n >1. For 0 < A < n, assume [n2/A]+1=kn for some positive integer k. This leads to which implies n < kA ≤ (n2+A)/n < n+1. This is a contradiction as kA is an integer and cannot be strictly between n and n + 1. Problem 258. (Due to Mihaiela Vizental and Alfred Eckstein, Arad, Romaina) Show that if A, B, C are in the interval (0, π/2), then f (A,B,C)+f (B,C,A)+f (C,A,B) ≡ 3, where Solution. Samuel Liló Abdalla (Brazil), Koyrtis G. CHRYSSOSTOMOS (Larissa, Greece, teacher) and Fai YUNG. Note sin 4 sin 3 sin 2 sin 6 sin 6 sin 6 1 ) , , ( z y x z y x z y x f For a, b, c > 0, by the AM-HM inequality, we have Multiplying by 3 2 on both sides, we get Let r = sin A, s = sin B, t = sin C, a = 1/(2r + 3s + 4t), b = 1/(2s + 3t + 4r) and Mathematical Excalibur, Vol. 11, No. 4, Nov. 06 – Dec. 06 Page 4 Using (*), we get

The result follows. Problem 259. Let AD, BE, CF be the altitudes of acute triangle ABC. Through D, draw a line parallel to line EF intersecting line AB at R and line AC at Q. Let P be the intersection of lines EF and CB. Prove that the circumcircle of .PQR passes through the midpoint M of side BC. (Source: 1994 Hubei Math Contest) Solution. Jeff CHEN (Virginia, USA). Observe that (1) ∠ BFC = 90° = ∠ BEC implies B, F, E, C concyclic; (2) ∠ AEB = 90° = ∠ ADB implies A,B,D,E concyclic. By (1), we have ∠ ACB = ∠ AFE. From EF||QR, we get ∠ AFE = ∠ ARQ. So ∠ ACB = ∠ ARQ. Then B, Q, R, C are concyclic. By the intersecting chord theorem, RD·QD=BD·CD (*) Since ∠ BEC = 90° and M is the midpoint of BC, we get MB = ME and ∠EBM = ∠ BEM. Now ∠EBM = ∠EPM + ∠ BEP ∠ BEM = ∠ DEM + ∠ BED. By (1) and (2), ∠BEP = ∠ BCF = 90° . ∠ ABC = ∠ BAD = ∠ BED. So ∠ EPM = ∠ DEM. Then right triangles EPM and DEM are similar. We have ME/MP = MD/ME and so MB2=ME2=MD·MP=MD(MD+PD) =MD2+MD·PD. Then MD·PD = MB2. MD2 = (MB.MD)(MB+MD) = BD(MC+MD) = BD·CD. Using (*), we get RD·QD=MD·PD. By the converse of the intersecting chord theorem, P, Q, R, M are concyclic. Commended solvers: Koyrtis G. CHRYSSOSTOMOS (Larissa, Greece, teacher). Problem 260. In a class of 30 students, number the students 1, 2, …, 30 from best to worst ability (no two with the same ability). Every student has the same number of friends in the class, where friendships are mutual. Call a student good if his ability is better than more than half of his friends. Determine the maximum possible number of good students in this class. (Source: 1998 Hubei Math Contest) Solution. Jeff CHEN (Virginia, USA) and Fai YUNG. Suppose each student has m friends and n is the maximum number of good students. There are 15m pairs of friendship. For m odd, m = 2k . 1 for some positive integer k. For j = 1, 2, …, k, student j has at least (2k.j) ≥ k > m/2 worse friends, hence student j is good. For the other n . k good students, every one of them has at least k worse friends. Then Solving for n, we get

For m even, m = 2k for some positive integer k. For j = 1, 2, …, k, student j has at least (2k + 1 . j) > k = m/2 worse friends, hence student j is good. For the other n . k good students, every one of them has at least k + 1 worse friends. Then Solving for n, we get Therefore, n ≤ 25. For an example of n = 25, in the odd case, we need to take k = 5 (so m = 9). Consider the 6×5 matrix M with Mij= 5(i . 1) + j. For M1j, let his friends be M6j, M1k and M2k for all k ≠ j. For Mij with 1 < i < 6, let his friends be M6j, M(i.1)k and M(i+1)k for all k ≠ j. For M6j, let his friends be Mij and M5k for all i < 6 and k ≠ j. It is easy to check 1 to 25 are good. Pole and Polar (continued from page 2) Example 7. (1998 IMO) Let I be the incenter of triangle ABC. Let the incircle of ABC touch the sides BC, CA and AB at K, L and M respectively. The line through B parallel to MK meets the lines LM and LK at R and S respectively. Prove that angle RIS is acute.

Solution. Consider the pole-polar transformation with respect to the incircle. Due to tangency, the polars of B, K, L, M are lines MK, BC, CA, AB respectively. Observe that B is sent to B’ = IB∩MK under the inversion with respect to the incircle. Since B’ is on line MK, which is the polar of B, by La Hire’s theorem, B is on the polar of B’. Since MK||RS, so the polar of B’ is line RS. Since R,B,S are collinear, their polars concur at B’. Next, since the polars of K, L intersect at C and since L, K, S are collinear, their polars concur at C. Then the polar of S is B’C. By the definition of polar, we get IS⊥B’C. By a similar reasoning, we also get IR⊥B’A. Then ∠ RIS = 180° . ∠ AB’C. To finish, we will show B’ is inside the circle with diameter AC, which implies ∠ AB’C > 90° and hence ∠ RIS < 90°. Let T be the midpoint of AC. Then A B C B T B ' ' ' 2 + = ) ' ( ) ' ( MA M B KC K B + + + = . MA KC + = Since KC and MA are nonparallel, AC AL CL MA KC T B = Therefore, B’ is inside the circle with diameter AC.

Solutions to Olympiad Corner, vol.11 No.4

1. Clearly M = (1003,1004, ..., 2006) satisfies the requirement. Denote by IMI the size of M, then max(M~22006-1003tl=1004. On the other hand, let a, be the smallest element of M, we can find unique positive integers q and r, 0 5 r < a,, such that 2006 = qa, + r. Partition elements in {1,2, ..., 2006) larger than 4 according to modulus a, : . 4 +1,2a, +1,...,(q-l)a1 +l,qa, +1; 4 +2,24 + 2 4 q - i ) a , +2,q4+2; I . . a, + r, 2a, + r ,..., (q - l)a, + r, qa, t r; a, +r+1,2a, +r+l,...,(q-l)a,+r+l; ' ... ' . I +a,- 1,24+a,-1, ...,(q- i)a, + q - ~ 2q, 34, 4q, ..* ,qq. i Noticing a, is the smallest element of M, hence at most one element may be selected from any two consecutive elements of each row. Hence in the first r rows we can take at most - ';'I : elements from each row. And in the last 4 - r rows at most elements may be selected from each row. Hence q + l 4 I1 + -. r t -(a, - r ) 2 2 r t q a , 2006 = 1 +- = 1 +- = 1004. 2 2 Together we see that the largest possible size of M is 1004. 2. We have 2m < 8'' hence f,(2'O06) < (9x700)' < 5x10'. Furthermore f2(22006)<(4+9X7)2<4900 and f,(22w6)S(3+9x3)2 =302. Now 26=1(mod9) and hence 2m ~2'=4(mod9)4. Thus f,(2'OO6)~4' -7(mod9) and f2(2m)=772 =4(mod9). This leads to f3(2*Oo6)=n' with nI30 and n=f2(2'OO6)=4(mod9). Hence f3(22w6)=16, 169 or 484 which gives f4(2m) = 49 or 256, fs(22wb) =169, f6(22006) = 256, etc. Finally f, (2'OO6) = 169. 3.(Solution 1) Let r be the circumcircle of ABCD, r, be the circumcircle of AAPC and let rz be the circumcircle of ABPD. The radical axis of r and r, is line BD. Since P is on both rI and r,, P is on the radical axis of ,rl and r,. Since AC and BD intersect at [ radical axis of r and I?, is line AC. The E, E ,is the radical center of r, r, and T,.The line PE is the radical axis of r, and rZ. To show 0, P and E are collinear, it suffices to show the power of 0 with respect to r, and r,are the same, that is 0 is also on the radical axis PE of r, and r. Now draw BP. By the exterior angle theorem, LAPC = LPAB + LABC t LPCB = 90' +-LAOC. Next, LACO=-(18o'-LAOC)=180'-(90'+-LA'OC)=180-LAPC. This implies OC is tangent to at C. Similarly, OE is tangent to r2 at B. Since OC = OB, the power of 0 with respect to I?, and rz are the same. (Solution 2) Extend AP, BP, CP, DP to meet the circumcircle r of ABCD again at . A', B',.C', D' respectively. Now 90' =LPAB+LPCB =-LA'OB+--LC'OB=-~'OC'. So A'C' is a diameter of r. Similarly B'D' is also a diameter of r. So A'C'nB'D'=O.'Let B'A and C'D. C , intersect at Q. Applying Pascal's theorem to, B, B I, A, C, C ', D on r. we see BB'nCC'=P,B'AnC'D=Q and ACnBD=E are collinear. Next, applying Pascal's theorem to A,A',C', D, D', B' on r, we see AA'n DD' = P , A' C ' n D'B; 3'0 and C'D n B' A = Q are collinear. Therefore 0, P, Q and E are collinear. 4. Call a sequence of positive numbers CI, CZ, c3, ..: m d if there exists a positive number N such that for every n = 1,2,3, 2 3 Suppose a sequence of positive numbers CI, cz, cg, . . . is good. Then we have (1) there exists such that for all integer n > 1, Cn+l > rc,, and (2) there exists a positive integer j such that for all integer n > 1, cn+l > 2cn. For (l), by (*), we can take r = 1/N. For (2), we choose integer j > 2N+1 and note that Nc NC Nc Adding these and using (*), we have Conversely, a sequence of positive numbers CI, c2, c3, ... satisfying (1) and (2) is good. To see this, for n > 1, break the sum of CI to Cn-1 into j sums so the term ck is in the i-th sum for k = i (modj?. Then Therefore, a sequence is good if and only if conditions (1) and (2) hold. For ,the problem, note the sequence a, a2 , (Ij y . . . is good with r, j satisfying (l), (2) implies the sequence al, uz, a3. . . . is good with &, 2j satisfying (l), (2). December 2006 4 張百康 高子眉 梁達榮 李健賢 吳鏡波 楊秀英