Mathematical Excalibur, Volume 12, Number 5

Abstract

Mathematical Excalibur Volume 12, Number 5 January 2008 Square It! Pham Van Thuan (Hanoi University of Science, 334 Nguyen Trai, Thanh Xuan, Hanoi) Olympiad Corner Below were the problems of the 2007 Estonian IMO Team Selection Contest. First Day Problem 1. On the control board of a nuclear station, there are n electric switches (n > 0), all in one row. Each switch has two possible positions: up and down. The switches are connected to each other in such a way that, whenever a switch moves down from its upper position, its right neighbor (if it exists) automatically changes position. At the beginning, all switches are down. The operator of the board first changes the position of the leftmost switch once, then the position of the second leftmost switch twice etc., until eventually he changes the position of the rightmost switch n times. How many switches are up after all these operations? Problem 2. Let D be the foot of the altitude of triangle ABC drawn from vertex A. Let E and F be points symmetric to D with respect to lines AB and AC, respectively. Let R1 and R2 be (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 25, 2008. 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 Inequalities involving square roots of the form A + B + C + D can be solved using the Cauchy- Schwarz inequality. However, solving inequalities of the following form A + B + C + D ≥ k is far from straightforward. In this article, we will look at such problems. We will solve them by squaring and making more delicate use of the Cauchy-Schwarz inequality. Example 1. Three nonnegative real numbers x, y and z satisfy x2+y2+z2=1. Prove that Solution. Squaring both sides of the inequality and simplifying, we get the equivalent inequality cyclic where cyclic Notice that By the Cauchy-Schwarz inequality, Similarly, we obtain two other such inequalities. Multiplying each of them by 2, adding them together, simplifying and finally using x2 + y2 + z2 = 1, we get the equivalent inequality in the beginning of this solution. Example 2. For a, b, c > 0, prove that Solution. Multiplying both sides by (a + b)(b + c)(c + a), we have to show cyclic a(c a)(a b) ≥ 2 (a + b + c)(ab + bc + ca). Squaring both sides, we get the equivalent inequality cyclic cyclic a3 2 (a b) ab(a c)(b c) 3 ab(a b) 9abc. (*) By the Cauchy-Schwarz inequality and the AM-GM inequality, we have (a + b) ab(a + c)(b + c) ≥ (a + b) ab( ab + c)2 = (a + b)( ab + c) ab = ab(a + b) + (a + b)c ab ≥ ab(a + b) + 2abc. Using this, we have cyclic cyclic a3 2 (a b) ab(c a)(c b) cyclic cyclic a3 2 ab(a b) 12abc. Comparing with (*), we need to show cyclic cyclic a3 ab(a b) 3abc 0. This is just Schur’s inequality cyclic a(a b)(a c) 0. (See Math. Excalibur, vol.10, no.5, p.2) Mathematical Excalibur, Vol. 12, No. 5, Jan. 08 Page 2 From the last example, we saw that other than the Cauchy-Schwarz inequality, we might need to recall Schur’s inequality cyclic Here we will also point out a common variant of Schur’s inequality, namely cyclic This variant can be proved in the same way as Schur’s inequality (again see Math. Excalibur, vol.10, no.5, p.2). Both inequalities become equality if and only if either the variables are all equal or one of them is zero, while the other two are equal. In the next two examples, we will use these. Example 3. Let a, b, c be nonnegative real numbers such that a + b + c = 1. Prove that a+(b−c)2 + b+(c−a)2 + c+(a−b)2 ≥ 3. When does equality occur? Solution. Squaring both sides of the inequality and using a2+b2+c2 = (a+b+c)2 −2(ab+bc+ca) = 1 − 2(ab+bc+ca), we get the equivalent inequality cyclic a (b c)2 b (c a)2 3(ab bc ca). By the Cauchy-Schwarz inequality, a + (b − c)2 b + (c − a)2 = (b − c)2 + (a + b + c)a (c − a)2 + (a + b + c)b ≥| (b − c)(c − a) | +(a + b + c) ab. Similarly, we can obtain two other such inequalities. Adding them together, the right side is

cyclic cyclic b c c a a b c ab By the triangle inequality and the case r = 0 of Schur’s inequality, we get a2 b2 c2 ab bc ca cyclic cyclic cyclic Thus, to finish, it will be enough to show a2 + b2 + c2 + (a + b + c)( ab + bc + ca) ≥ 4(ab + bc + ca). Now we make the substitutions x = a, y = b and z = c. In terms of x, y, z, the last inequality becomes cyclic Since the terms are of degree 4, we consider the case r = 2 of Schur’s inequality, which is cyclic This is not quite equal to . So next (due to degree 4 consideration again), we will look at the case r = 1 of the variant cyclic Readily we see is just the sum of Schur’s inequality with twice its variant. Finally, tracing back, we see equality occurs if and only if a = b = c= 1/3 or one of them is 0, while the other two are equal to 1/2. Example 4. Three nonnegative real numbers a, b, c satisfy a + b + c = 2. Prove that

Solution. Squaring both sides of the inequality and using a + b + c = 2, we get the equivalent inequality cyclic Note that

Applying twice the Cauchy-Schwarz inequality, we have

Mathematical Excalibur, Vol. 12, No. 5, Jan. 08 Page 4 which implies XY⊥PH. Similarly, ZY⊥PH. So, X, Y, Z are on a line perpendicular to line PH. Solution 2. Anna Ying PUN (HKU, Math Year 2) and Stephen KIM (Toronto, Canada). Set the origin of the coordinate plane at H. For a point J, let (xJ, yJ) denote its coordinates. Since the slope of line PA is (yP −yA)/(xP−xA), the equation of line HL is (xP −xA)x + (yP −yA)y = 0. (1) Since the slope of line HA is yA/xA, the equation of line BC is xAx + yAy = xAxB + yAyB. (2) Let t = xAxB + yAyB. Since point C is on line BC, we get xAxC + yAyC = xAxB + yAyB=t. Similarly, xBxC + yByC=t. Since X is the intersection of lines BC and HL, so the coordinates of X satisfy the sum of equations (1) and (2), that is xPx + yPy = t. (Since the slope of line PH is yP/xP, this is the equation of a line that is perpendicular to line PH.) Similarly, the coordinates of Y and Z satisfy xPx + yPy = t. Therefore, X, Y, Z lie on a line perpendicular to line PH. Commended solvers: Salem MALIKIĆ (Sarajevo College, 4th Grade, Sarajevo, Bosnia and Herzegovina). Problem 289. Let a and b be positive numbers such that a + b < 1. Prove that min Solution. Samuel Liló ABDALLA (ITA, São Paulo, Brazil), Jeff CHEN (Virginia, USA), CHEUNG Wang Chi (Magdalene College, University of Cambridge, England), Anna Ying PUN (HKU, Math Year 2), Salem MALIKIĆ (Sarajevo College, 4th Grade, Sarajevo, Bosnia and Herzegovina), Simon YAU Chi Keung (City University of Hong Kong) and Fai YUNG. Since 0 < a, b < a + b < 1, we have (b−1)2 + a(2b−a) = b2+2(a−1)b−a2+1 = (b+a−1)2+2a(1−a) > 0. In case a ≥ b > 0, we have min , a(a−1)2+ab(2a−b) b(b−1)2+ab(2b−a) (a−b)[(a+b−1)2+2ab] ≥ 0, which is true. In case b > a > 0, we have min , ( 1) (2 ) ( 1) (2 ) ⇔ b(a−1)2+b2(2a−b) ≥ a(b−1)2+a2(2b−a) (b−a)(1 −a2 −b2) ≥ 0, which is also true as a2 +b2 < a+b < 1. Problem 290. Prove that for every integer a greater than 2, there exist infinitely many positive integers n such that a n − 1 is divisible by n. Solution 1. Jeff CHEN (Virginia, USA), CHEUNG Wang Chi (Magdalene College, University of Cambridge, England), GRA20 Problem Solving Group (Roma, Italy) and HO Kin Fai (HKUST, Math Year 3). We will show by math induction that n = (a − 1)k for k = 1, 2, 3, … satisfy the requirement. For k = 1, since a − 1 > 1 and a ≡ 1 (mod a − 1), so aa−1 −1 ≡ 1a−1 − 1 = 0 (mod a − 1). Next, suppose case k is true. Then a(a−1)k −1 is divisible by (a − 1)k. For the case k + 1, all we need to show is Note b = a( −1) ≡ 1(moda −1). a k The left side of the above displayed congruence is 1 1 0(mod 1). This completes the induction. Solution 2. Anna Ying PUN (HKU, Math Year 2) and Salem MALIKIĆ (Sarajevo College, 4th Grade, Sarajevo, Bosnia and Herzegovina). Note n = 1 works. We will show if n works, then an − 1( > 2n − 1 ≥ n) also works. If n works, then an − 1 = nk for some positive integer k. Then aa ank an anj n which shows an − 1 works. Comments: Cheung Wang Chi pointed out that interestingly n = 1 is the only positive integer such that 2n−1 is divisible by n (denote this by n | 2n−1). [This fact appeared in the 1972 Putnam Exam.-Ed.] To see this, he considered a minimal n > 1 such that n | 2n−1. He showed if a, b, q ∈ ℤ+ and a = bq + r with 0 ≤ r < b, then 2a − 1 = ((2b)q − 1)2r + (2r − 1) = (2b − 1)N + (2r − 1) for some N ∈ ℤ+. Hence, gcd(2a−1,2b−1) = gcd(2b−1,2r−1) = ⋯ = 2gcd(a,b)−1 by the Euclidean algorithm. Since n|2n−1 and n|2φ(n)−1 by Euler’s theorem, so n|2d −1, where d = gcd(n, φ(n)) ≤ φ(n) < n. Then n | 2d − 1 implies d > 1 and d|2d − 1, contradicting minimality of n. Commended solvers: Samuel Liló ABDALLA (ITA, São Paulo, Brazil) and Fai YUNG. Olympiad Corner (continued from page 1) Problem 2. (Cont.) the circumradii of triangles BDE and CDF, respectively, and r1 and r2 be the inradii of the same triangles. Prove that |SABD- SACD| ≥ |R1r1-R2r2|, where SK is the area of figure K. Problem 3. Let n be a natural number, n ≥ 2. Prove that if (bn-1)/(b-1) is a prime power for some positive integer b, then n is prime. Second Day Problem 4. In square ABCD, points E and F are chosen in the interior of sides BC and CD, respectively. The line drawn from F perpendicular to AE passes through the intersection point G of AE and diagonal BD. A point K is chosen on FG such that AK = EF. Find ∠EKF. Problem 5. Find all continuous functions such that for all reals x and y, f (x + f (y)) = y + f (x + 1). Problem 6. Consider a 10×10 grid. On every move, we color 4 unit squares that lie in the intersection of some two rows and two columns. A move is allowed if at least one of the 4 squares is previously uncolored. What is the largest possible number of moves that can be taken to color the whole grid?

Answer: 1 Solution 1. Enumerate the switches with numbers 1 to n from left right We prove first that the result of two consecutive changes does not depend m the order of the changes. Let x and y be the numbers of the switches changed If there exists a number z such that x 5 z < y and switch number z is down then Changing the position of x can influence only switches fr5om x to z changing the position of switch y can influence only this switch and switches right form y. thus the results of the changes are independent of each other If no such z exists then changing switch number x causes a change of switch number y after that switches x to y 1 are all down while all switches in the right from them are in the same position as if switch number y were changed. Thus after moving both x and y m either order, switches from x to y - 1 are down and the switches with large number are m the position as when switch y were moved Twice We' prove now that, after all operations, precisely the leftmost switch is UP. This claim holds trivially for n = 1. Assume the claim holding for n switches and consider a board with n + 1 switches. According to what was proven above, the moves can be performed in arbitrary order. Therefore first change switch number 2 ante, the switch number 3 twice etc, until the last switch . By the induction hypo-, switch number 2 is up and all the others are down. Each switch has to be moved are more; if we do it from right to left then switches n + 1, to 3 go up, then moving switch 2 down brings all them down and finally switch 1 is moved up. Thus 1 is the only switch remaining up. Solution 2 Let q be then & of times the ith switch changes its position during the whole process According to the condition of the .Glen, each switch m e s either when it is moved directly by the operator or its left neighbour moves down. As all switches are down at the beginning, the ith switch moves down times thus, i.e., the claim holds for assuming that its holds for we obtain Altogether, this shows that al is odd and 4 is even for all i 2 2 Hem, after the process, Solution 3. Interpret the position of switches on the board as binary numbers so that the ith ith switch from the left corresponds to the ith lowest binary digit: being down d e s 0 and being up encodes 1. Changing .the ith switch then works like addition of 2'-' Modulo2 the initial position encodes number 0 the final position encodesl-2~+ 2-21+...+n-2'-1~modulo2!'. We prove that 1 - (mod2'). If n = lthen this holds. Assume that the claim holds for n = k. Multiplying this by 2 gives 1-2l+2-2?+...+k.$=2 ( m o d e ) i.e., the claim holds for n = k + 1. Solution 3, one could prove by induction a stronger cl- 1 2' + 2 - 2' + ...+p-2'-' = (n.-1)-T+1. 2. Solution 1. Consider first the case where D lies between points B and C (see Fig. 14). An 1 1 SABD= - . IA BanDS m = z.lAD[ - CDl, we have . 2 Let G be the incentre of triangle BDE and let G1 be the projection of G to line BD. Then ' IGG'l = rl. By symmetry, LBEA = LBDA = 90°, hence quadrangle BEAD is cyclic and line segment AB is its circum* Thus lABl = 2R1. As triangles ADB and GGIB am similar, we have implying = IADI - [GBI. Let H be the IADI - IGG'I' incentre of triangle CDF; then analogously 2R2r2 = 1 AD1 Hence Triangle ADG is isosceles because LADG = 90 Thus 2 Subtracting equality IAD + 1cDl2 = IAC h mI ADI2 + I B D IAB(' gives IBD(' - lCDl2 = lABl – which is equivalent to ((IBDI - ICDI) - (IBDI + ICD() = (IABI - IACI) - (IABI + IACI). Consequently. As lBCl < lABl+ IACI, we must have IlBDl- lCDll 1 IlGBl- IHC] 1, which gives the desired inequality. Figure 14 Figure 15 If D does not lie between B and C (see Fig. 15) then assume w1o.g. that it is on ray BC. Reflect line segment AC wzt. line AD; points C and H transform to some points C' and HI, respectively. Now apply the solution above for triangle ABC'. The desired claim Follows then by using = lCDl and lHIC'l = IHCI. Solution 2. Denote LBAD = /3 and LCAD = 7. Then ' As in Solution 1, show that quadrangle BEAD is cyclic Let K be the point of intersection of its diagonals. As i = 2l AB,l we get R1 = -2lcAoDsl B' furthermore, = Analogously we obtain SACD= 2 IAD From these equalities, we can et hat - DSAC D+ d Rlrl- RZQh. ave the same sign since and belong to the first quarter where tan is beg assume that both are non-negative be (otherwise B and C). Then B 2 7 and the desired inequality is equivalent to SABO 2 SACD. Now B tan- B tan whence By 27 and tan being increasing, the inequality follows. the production Now consider the presentation Each factor is greater: than 1 and a power of p. As is a positive integral power of the numerator is divisible by p, (mod p). By &mats little theorem, bP = b (mod p). Thus b = 1 (mod p) and b - 1 is divisible by p. But then the numeator V - 1 must be divisible by $, ie, bp m 1 (mod ). If m 2 2 then the above contains factor- bf-1 = I+V+ ...+bP(rl). On one hand this is congruent to p modulo p2 as all addends are congruent to 1. On the other hand, this factor is a power of p while being greater than p, hence it is a multiple of p2. This contraction shows that m=l,qed. Remark.1. Fermat's little theorem can easily be avoided in the solution Cutting this Out from the solution above, it still shows that if ienbP-1 is not divisible by Continuing from this, we see that -bp-1 is divisible by p but not by p2. Hence & factor must be p. Now gives a contradiction Answer 135 Solution Since AGFD is a cyclic quadrilateral (see Fig: 16), LGAF = LGDF = 6' and LGFA = LGDA = 45', SO triangle AGF is isosceles and lGAl = IGF(. Now, right triangle AGK and FGE are congruent, and lGKl= IGEI, so triangle G&E is also isosceles. finally, LGKE = 4S0 and Figure 16 LEU = 180' - LGKE = 135'. : f ( x ) = l + x a n d f ( x ) Solution. Taking y = - f (x + I), we see that there is a value a such that f (a) = 0. We Consider two cases. Let first a # 1. Taking y = x+l, we get f(x+f(x+l)) = x+1+ f(x+l). Let g(x) = x +I(% + I), then f (g(x)) = 1 + g(x) for all x. Since f is continuous, so is g. Taking y = a ih the initial relation, we get f (x) = a + f (x + I), and so g(x - 1) - g(x) = a - 1 for all x. Since a # 1, g is unbounded and by continuity, takes all real values, so f(z) = l+zf or al lz. Let now a = 1, ie, f (1) = 0. Then x = 0 yields f (fQ) = y for an reds y. Taking now y = f (1 - x) m the initial relation, we get f or0 = f(1-x)+f(x+l). Fm+y,tahgy'= x+f(x+l),so f(x+f(l-x)) = 1-x- f(1-x). Leth(x) = x+ f(1-x),then f (h(x)) = 1 - h(x) holds for all x. Replacing x with -x and taking y = 1 m the initial relation, we get f (-x) = 1 + f (1 - x), so h(x + 1) - h(x) = 2 Again, k is continuous and must take all real values, so f(z) =l-z for al lz. It is straightforward to verify that both solutions indeed satisfy the initial relation. Solution . By always choosing the first line, the first column and a square of the remaining 9 x 9 grid as the lower right square, the whole grid can be coloured in 81 moves. We now prove that it is not possible to make more than 81 moves. Consider a sequence of moves- Select for each move one square that is chosen for the first time during this move and colour the remaining squares already before starting the sequence. Then, take all squares that were not selected and colour them m advance, i.e, already before starting the sequence of moves. Since all selected squares must be different, every move m the sequence now colours exactly one square. Next, consider a bipartite graph with the 10 rows and 10 columns as vertices. Every time a square Is coloured, draw an edge between the row and the column corresponding to this square We claim that the graph is connected we start the sequence of moves. Indeed, suppose that during some move, we pick rows (a, b) and columns (c,d), such that only square (b,d) is coloured for the first time, i.e, we add the edge (b,d). But then b is already connected with d through b - c - a - d, so the number of connected components does not decrease. Since the graph of a fully coloured grid is connected, it must also be connected m the beginning. But a connected graph with 20 vertices must have at least 19 edges, so we can add only 100 - 19 = 81 new edges, and hence any sequence can have at most 81 moves.