Mathematical Excalibur, Volume 15, Number 5

Abstract

Mathematical Excalibur Volume 15, Number 5 February-April 2011 Harmonic Series (I) Leung Tat-Wing Olympiad Corner Below are the problems of the 2011 Canadian Math Olympiad, which was held on March 23, 2011. Problem 1. Consider 70-digit numbers n, with the property that each of the digits 1, 2, 3, …, 7 appears in the decimal expansion of n ten times (and 8, 9 and 0 do not appear). Show that no number of this form can divide another number of this form. Problem 2. Let ABCD be a cyclic quadrilateral whose opposite sides are not parallel, X the intersection of AB and CD, and Y the intersection of AD and BC. Let the angle bisector of ∠AXD intersect AD, BC at E, F respectively and let the angle bisector of ∠AYB intersect AB, CD at G, H respectively. Prove that EGFH is a parallelogram. Problem 3. Amy has divided a square up into finitely many white and red rectangles, each with sides parallel to the sides of the square. Within each white rectangle, she writes down its width divided by its height. Within each red rectangle, she writes down its height divided by its width. Finally, she calculates x, the sum of these numbers. (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 May 29, 2011. 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 A series of the form m m d m d where m, d are numbers such that the denominators are never zero, is called a harmonic series. For example, the series is a harmonic series, or more generally is also a harmonic series. Below we always assume 1 ≤ m < n. There are many interesting properties concerning this kind of series. Example 1: H(1,n) is unbounded, i.e. for any positive number A, we can find n big enough, so that H(1,n) ≥ A. Solution For any positive integer r, note

which can be proved by induction. Hence we can take enough pieces of these fractions to make H(1,n) as large as possible. Example 2: H(m,n) is never an integer. Solution (i) For the special case m = 1, let s be such that 2s ≤ n < 2s+1. We then multiply H(1,n) by 2s–1Q, where Q is the product of all odd integers in [1, n]. All terms in H(1,n) will become an integer except the term 2s will become an integer divided by 2 (a half integer). This implies H(1,n) is not an integer. (ii) Alternatively, for the case m =1, let p be the greatest prime number not exceeding n. By Bertrand’s postulate there is a prime q with p < q < 2p. Therefore we have n < 2p. If H(1,n) is an integer, then

is an integer divisible by p. However the term n!/p (an addend) is not divisible by p but all other addends are. (iii) We deal with the case m > 1. Suppose 2α | k but 2α+1 does not divide k (write this as 2α || k), then we call α the “parity order” of k. Now observe 2α, 3·2α, 5·2α, ⋯ all have the same parity order. Between these numbers, there are 2·2α, 4·2α, 6·2α, ⋯, all have greater parity orders. Hence, between any two numbers of the same parity order, there is one with greater parity order. This implies among m, m+1, …, n, there is a unique integer with the greatest parity order, say q of parity order μ. Now multiply by 2μL, where L is the product of all odd integers in [m, n]. Then 2μL·H(m,n) is an odd number. Hence where p is even and q is odd and so is not an integer. Example 3 (APMO 1997): Given that where the denominators contains partial sum of the sequence of reciprocals of triangular numbers. Prove that S > 1001. Solution Let Tn be the nth triangular number. Then Tn=n(n+1)/2 and hence Since 1993006=1996·1997/2, we get 1996 1997 1024 1996 1 1

Hence, S > (1996+6)/2=1001 using example 1 that H(r+1,2r) ≥ 1/2 for r = 2, 4, 8, 16, 32, 64, 128, 256, 512. Mathematical Excalibur, Vol. 15, No. 5, Feb.-Apr. 11 Page 2 Congruence relations of harmonic series are of some interest. First, let us look at an example. Example 4 (IMO 1979): Let p, q be natural numbers such that 2 3 4 1318 1319 Prove that p is divisible by 1979. Solution We will prove the famous Catalan identity (due to N. Botez (1872) and later used by Catalan): It is proved as follows: 2n n 2n Thus 660 661 1318 1319 2 660 1319 661 1318 1319 660 1( 1979 1979 ... 1979 ) 2 660 1319 661 1318 1319 660 1979 , p q A B where B is the product of some positive integers less than 1319. However, 1979 is prime, hence 1979| p. For another proof using congruence relations, observe that if (k,1979) =1, then by Fermat’s little theorem, k1978 ≡ 1 (mod 1979). Hence, we can consider 1/k ≡ k1977 (mod 1979). Then Σ Σ 1319 1 1977 1319 k 659 1977 1319 1977 2 (2 ) 1977 2 21977 659 1977 1319 1977 989 660 1977 1977 1319 660 1977 ( (1979 ) ) 989 660 ( 1977 ( )1977 ) 0 (mod 1979). Note that 1/k (mod p) (as well as many fraction mod p) makes sense if k ≢ 0 (mod p). Also, as a generalization, we have Example 5: If H(m,n) = q/p and m+n is an odd prime number, then m+n | q. Solution Note that H(m,n) has an even number of terms and it equals ( 1) / 2 n m 1 1 j m j n j 0 r m n s m j n j n m m n

where gcd(s,r) = 1. Since m+n is prime, gcd(r,m+n) = 1. Then q/p = (m+n)s/r and m+n | q. The Catalan identity is also used in the following example. Example 6 (Rom Math Magazine, July 1998): Let 1 2 3 4 2011 2012 A= and 1007 2012 1008 2011 2012 1007 B= Evaluate A/B. Solution 1006 1006 2012 1008 2012 1007 3019 1008 2011 3019 1007 2012 3019 = 3019B Hence . 2 = 3019 B A Example 7: Given any proper fraction m/n, where m, n are positive integers satisfying 0 < m < n, then prove it is the sum of fractions of the form where x1, x2, …, xk are distinct positive integers. Solution We use the “greedy method”. Let x1 be the positive integer such that i.e. x1 is the least integer greater than or equal to n/m. If 1/x1 = m/n, then the problem is done. Otherwise x nx nx where m1=mx1−n < m (due to m/n < 1/(x1 −1) ) and obviously nx1> n. Let x2 be another positive integer such that The procedure can be repeated until m m1 > m2 > ⋯ > mk > 0 and 1 2 1 1 ... 1 , n x x x = + + + where 1 ≤ k ≤ m. (Note: writing 1 1 1, n n 1 n(n 1) we observe actually there are infinitely many ways of writing any proper fractions as sum of fractions of this kind. These fractions are called unit fractions or Egyptian fractions.) Example 8: Remove those terms in such that its denominator in decimal expansion contains the digit “9”, then prove that the sequence is bounded. Solution The integers without the digit 9 in the interval [10m−1, 10m−1] are m-digit numbers. The first digit from the left cannot be the digits “0” and “9”, (8 choices), the other digits cannot contain “9”, hence nine choices 0, 1, 2, 3, 4, 5, 6, 7 and 8. Altogether there are 8·9m−1 such integers. The sum of their reciprocals is less than

(continued on page 4) Mathematical Excalibur, Vol. 15, No. 5, Feb.-Apr. 11 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 May 29, 2011. Problem 366. Let n be a positive integer in base 10. For i =1,2,…,9, let a(i) be the number of digits of n that equal i. Prove that 2a(1)3a(2)L9a(8)10a(9) ≤ n +1 and determine all equality cases. Problem 367. For n = 1,2,3,…, let xn and yn be positive real numbers such that 2 +2 +1 = + n n n x x x and +2 + = + n n n y y y If x1, x2, y1, y2 are all greater than 1, then prove that there exists a positive integer N such that for all n > N, we have xn > yn. Problem 368. Let C be a circle, A1, A2, …, An be distinct points inside C and B1, B2, …, Bn be distinct points on C such that no two of the segments A1B1, A2B2,…, AnBn intersect. A grasshopper can jump from Ar to As if the line segment ArAs does not intersect any line segment AtBt (t≠r,s). Prove that after a certain number of jumps, the grasshopper can jump from any Au to any Av. Problem 369. ABC is a triangle with BC > CA > AB. D is a point on side BC and E is a point on ray BA beyond A so that BD=BE=CA. Let P be a point on side AC such that E, B, D, P are concyclic. Let Q be the intersection point of ray BP and the circumcircle of ΔABC different from B. Prove that AQ+CQ=BP. Problem 370. On the coordinate plane, at every lattice point (x,y) (these are points where x, y are integers), there is a light. At time t = 0, exactly one light is turned on. For n = 1, 2, 3, …, at time t = n, every light at a lattice point is turned on if it is at a distance 2005 from a light that was turned on at time t = n − 1. Prove that every light at a lattice point will eventually be turned on at some time.

Solutions

Problem 361. Among all real numbers a and b satisfying the property that the equation x4+ax3+bx2+ax+1=0 has a real root, determine the minimum possible value of a2+b2 with proof. Solution. U. BATZORIG (National University of Mongolia) and Evangelos MOUROUKOS (Agrinio, Greece). Consider all a,b such that the equation has x as a real root. The equation implies x ≠ 0. Using the Cauchy-Schwarz inequality (or looking at the equation as the line (x3 + x)a + x2b + (x4 + 1) = 0 in the (a,b)-plane and computing its distance from the origin), as

(a 2b a ) x x x (ax3 + bx2 + ax)2 = (x4 +1)2 , we get 6 4 2 with equality if and only if x = ±1 (at which both sides are 4/5). For x = 1, (a,b) = (−4/5, −2/5). For x = −1, (a,b) = (−2/5,4/5). Finally, by calculus or rewriting it as 5(x4 + 1)2 − 4(2x6 + x4 + 2x2) = (x2 − 1)2(5x4 + 2x2 + 5) ≥ 0. So the minimum of a2 + b2 is 4/5. Other commended solvers: CHAN Long Tin (Diocesan Boys’ School), Hong Kong Joint School Math Society, LI Pak Hin (PLK Vicwood K. T. Chong Sixth Form College), LKL Excalibur (Madam Lau Kam Lung Secondary School of MFBM), Raymond LO (King’s College), Paolo PERFETTI (Math Dept, Università degli studi di Tor Vergata Roma, via della ricerca scientifica, Roma, Italy), Anna PUN Ying (HKU Math), The 7B Math Group (Carmel Alison Lam Foundation Secondary School) and Alice WONG Sze Nga (Diocesan Girls’ School). Problem 362. Determine all positive rational numbers x,y,z such that are integers. Solution. CHAN Long Tin (Diocesan Boys’ School), Hong Kong Joint School Math Society, Raymond LO (King’s College), Anna PUN Ying (HKU Math) and The 7B Math Group (Carmel Alison Lam Foundation Secondary School). Let A = x + y + z, B = xyz and C = 1/x + 1/y +1/z, then A, B, C are integers. Since xy + yz + zx = BC, so x,y,z are the roots of the equation t3−At2 + BCt −B = 0. Since the coefficients are integers and the coefficient of t3 is 1, by Gauss lemma or the rational root theorem, the roots x, y, z are integers. Since they are positive, without loss of generality, we may assume z ≥ y ≥ x ≥ 1. Now 1 ≤ 1/x +1/y +1/z ≤ 3/x lead to x=1, 2 or 3. For x = 1, 1/y + 1/z = 1 or 2, which yields (y,z) = (1,1) or (2,2). For x = 2, 1/y + 1/z = 1/2, which yields (y,z) = (3,6) or (4,4). For x = 3, 1/y + 1/z = 2/3, which yields (y,z) = (3,3). So the solutions are (x,y,z) = (1,1,1), (1,2,2), (2,3,6), (2,4,4), (3,3,3) and permutations of coordinates. Other commended solvers: LI Pak Hin (PLK Vicwood K. T. Chong Sixth Form College) and Alice WONG Sze Nga (Diocesan Girls’ School). Problem 363. Extend side CB of triangle ABC beyond B to a point D such that DB=AB. Let M be the midpoint of side AC. Let the bisector of ∠ABC intersect line DM at P. Prove that ∠BAP =∠ACB. Solution. Raymond LO (King’s College). A D B C M P F E Construct line BF || line CA with F on line AD. Let DM intersect BF at E. Since BD=AB, we get ∠BDF =∠BAF = ½∠ABC =∠ABP =∠CBP. Then line FD || line PB. Hence, ΔDFE is similar to ΔPBE. Since BF||CA and M is the midpoint of Mathematical Excalibur, Vol. 15, No. 5, Feb.-Apr. 11 Page 4 AC, so E is the midpoint of FB, i.e. FE=BE. Then ΔDFE is congruent to ΔPBE. Hence, FD=PB. This along with DB = BA and ∠BDF =∠ABP imply ΔBDF is congruent to Δ ABP. Therefore, ∠BAP =∠DBF =∠ACB. Other commended solvers: U. BATZORIG (National University of Mongolia), CHAN Long Tin (Diocesan Boys’ School), Hong Kong Joint School Math Society, Abby LEE Shing Chi (SKH Lam Woo Memorial Secondary School), LI Pak Hin (PLK Vicwood K. T. Chong Sixth Form College), LKL Excalibur (Madam Lau Kam Lung Secondary School of MFBM), Anna PUN Ying (HKU Math), The 7B Math Group (Carmel Alison Lam Foundation Secondary School), Ercole SUPPA (Liceo Scientifico Statale E.Einstein, Teramo, Italy) and Alice WONG Sze Nga (Diocesan Girls’ School). Problem 364. Eleven robbers own a treasure box. What is the least number of locks they can put on the box so that there is a way to distribute the keys of the locks to the eleven robbers with no five of them can open all the locks, but every six of them can open all the locks? The robbers agree to make enough duplicate keys of the locks for this plan to work. Solution. CHAN Long Tin (Diocesan Boys’ School), Hong Kong Joint School Math Society, LI Pak Hin (PLK Vicwood K. T. Chong Sixth Form College), LKL Excalibur (Madam Lau Kam Lung Secondary School of MFBM), Raymond LO (King’s College), Emanuele NATALE (Università di Roma “Tor Vergata”, Roma, Italy), Anna PUN Ying (HKU Math), The 7B Math Group (Carmel Alison Lam Foundation Secondary School) and Alice WONG Sze Nga (Diocesan Girls’ School). Let n be the least number of locks required. If for every group of 5 robbers, we put a new lock on the box and give a key to each of 6 other robbers only, then the plan works. Thus 462. Conversely, in the case when there are n locks, for every group G of 5 robbers, there exists a lock L(G), which they do not have the key, but the other 6 robbers all have keys to L(G). Assume there exist G ≠G’ such that L(G)=L(G’). Then there is a robber in G and not in G’. Since G is one of the 6 robbers not in G’, he has a key to L(G’), which is L(G), contradiction. So G ≠ G’ implies L(G) ≠ L(G). Then the number of locks is at least as many groups of 5 robbers. So 462. Therefore, n = 462. Problem 365. For nonnegative real numbers a,b,c satisfying ab+bc+ca = 1, prove that

Solution. CHAN Long Tin (Diocesan Boys’ School) and Alice WONG Sze Nga (Diocesan Girls’ School). Since a, b, c ≥ 0 and ab+bc+ca = 1, none of the denominators can be zero. Multiplying both sides by a+b+c, we need to show 2 2(a b c).

This follows from using the Cauchy- Schwarz inequality and expanding (c+a+b−2)2 ≥ 0 as shown below a b (a b)c (b c)a (c a)b c (c + a + b)2 4(a + b + c) − 4. Other commended solvers: Andrea FANCHINI (Cantu, Italy), D. Kipp JOHNSON (Valley Catholic School, Teacher, Beaverton, Oregon, USA), LI Pak Hin (PLK Vicwood K. T. Chong Sixth Form College), Paolo PERFETTI (Math Dept, Università degli studi di Tor Vergata Roma, via della ricerca scientifica, Roma, Italy), Anna PUN Ying (HKU Math) and The 7B Math Group (Carmel Alison Lam Foundation Secondary School). Olympiad Corner (continued from page 1) Problem 3. (Cont.) If the total area of the white rectangles equals the total area of the red rectangles, what is the smallest possible value of x? Problem 4. Show that there exists a positive integer N such that for all integers a > N, there exists a contiguous substring of the decimal expansion of a which is divisible by 2011. (For instance, if a = 153204, then 15, 532, and 0 are all contiguous substrings of a. Note that 0 is divisible by 2011.) Problem 5. Let d be a positive integer. Show that for every integer S there exists an integer n > 0 and a sequence ε1, ε2, …, εn, where for any k, εk = 1 or εk = −1, such that S = ε1(1+d)2 + ε2(1+2d)2 + ε3(1+3d)2 + ⋯ + εn(1+nd)2. Harmonic Series (I) (continued from page 2) The sum of reciprocals of all such numbers is therefore less than

Example 9: Let m > 1 be a positive integer. Show that 1/m is the sum of consecutive terms in the sequence

Solution Since the problem is reduced to finding integers a and b such that m a b One obvious solution is a = m−1 and b = m(m−1). To find other solutions of (*), we note that 1/a > 1/m, so m > a. Let a = m−c, then b = (m2/c)−m. For each c satisfying c | m2 and 1 ≤ c ≤ m, there exists one and only one pair of a and b satisfying (*), and because a < b, the representation is unique. Let d(n) count the number of factors of n. Now consider all factors of m2 except m, there are d(m2)−1 of them. If c is one of them, then exactly one of c or m2/c will be less than m. Hence the number of solutions of (*) is [d(m2)−1]/2. Solutions to Olympiad Corner, vol 15, no.5 (1) Consider 70-digit numbers n, with the property that each of the digits 1,2,3, ... ,7 appears in the decimal expansion of n ten times (and 8, 9, and 0 do not appear). Show that no number of this form can divide another number of this form. Solution. Assume the contrary: there exist a and b .of the prescribed form, such that b 2: a and a divides b. Then a divides b - a. Claim: a is not divisible by 3 but b - a is divisible by 9. Indeed, the sum of the digits is 10(1 + ... + 7) = 280, for both a and b. [Here one needs to know or prove that an integer n is equivalent of the sum of its digits modulo 3 and modulo 9.] We conclude that b - a is divisible by 9a. But this is impossible, since 9a has 71 digits and b has only 70 digits, so 9a > b > b -:- a. 0 (2) Let ABCD be a cyclic quadrilateral whose opposite sides are not parallel, X the intersection of AB and CD, and Y the intersection of AD and BC. Let the angle bisector of LAX D intersect AD, B C at E, I: respectively and let the angle bisector of LAY B intersect AB, CD at G, H respectively. Prove that EGF H is a parallelogram. Solution. Since ABCD is cyclic, 6.XAC rv 6..XDB and 6.Y AC rv 6..YBD. Therefore, XA XC' AC YA YC XD = XB = DB = YB = YD~ Let s be this ratio. Therefore, by the angle bisector theorem, AE XA XC CF ED = XD = XB = FB = s, and AG YA YC CH GB = YB = YD = HD = s: H ence, GA'GE = FOEF an d EADE = DHHO ' Therefore, EH II ACII GF and EG II DB II H F. EG F H is a parallelogram. Hence, (3) Amy has divided a square up into finitely many white .and red rectangles, each with sides parallel to the sides of the square. Within each white rectangle, she writes down its width divided by its height. Within each red rectangle, she writes down its height divided by its width. Finally, she calculates x, the sum of these numbers. If the total area of the white rectangles equals the total area of the red rectangles, what is the smallest possible value of x? Solution. Let ai and bi denote the width and height of each white rectangle, and let Ci and di denote the width and height of each red rectangle. Also, let L denote the side length of the original square. Lemma: Either L: ai 2: L or I: di 2: L. Proof of lemma: Suppose there exists a horizontal line across the square that is covered entirely with white rectangles. Then, the total width of these rectangles is at least L, and the claim is proven. Otherwise, there is a red rectangle intersecting every horizontal line, and hence the total height of these rectangles is at least L. 0 Now, let us assume without loss of generality that I: ai 2:: L. By the Cauchy-Schwarz inequality, (Lair L2. But we know I: aibi = 2, so it follows that I2:: 2. Furthermore, each Ci ~ L, so Therefore, x is at least 2.5. Conversely, x = 2.5 can be achieved by making the top half of the square one colour, and the bottom half the other colour. 0 (4) Show that there exists a positive integer N such that for all integers a > N, there exists a contiguous substring of the decimal expansion of a that is divisible by 2011. (For instance, if a = 153204, then 15, 532, and 0 are all contiguous substrings of a. Note that o is divisible by 2011.) Solution. We claim that if the decimal expansion of a has at least 2012 digits, then a contains the required substring. Let the decimal expansion of a be akak-l ... ao. For i = 0, ... ,2011, Let bi be the number with decimal expansion aiai-l ... ao. Then, by pidgenhole principle, bi == bj mod 2011 for some i < j 2011. It follows that 2011 divides bj - bi = C· Wi. Here C is the substring aj .... _ai+l., Since 2011 and 10 are relatively prime, it follows that 2011 divides c. 0 (5) Let d be a positive integer. Show that for every integer S, there exists an integer n > 0 and a sequence El, E2, .. '.' En, where for any k, Ek = 1 or Ek = -1, such that S = El(l + d)2 + E2(1 + 2d)2:+ E3(1 + 3d)2 + ... + En(;l + ndf Solution. Let Uk = (1 + kd)2. We calculate Uk+3 - Uk+2 - Uk+l + Uk' This turns out to be 4d2, a constant. Changing signs, we obtain the sum -4d2. Thus if we have found an expression for a certain number So as a sum of the desired type, we can obtain an expression of the desired type for So + (4d2 )q, for any integer q. It remains to show that for any S, there exists an integer S' such that S' == S (mod 4d2) and S' can be expressed in the desired form. Look at the sum (1 + d)2 + (1 + 2d)2 + ... + (1 + N d)2, where N is 'large.' We can at will choose N so that the sum is odd, or so that the sum is even. By changing the sign in front of (1 + kd)2 to a minus sign, we decrease the sum by 2(1 + kd)2. In particular, if k == 0 (mod 2d), we decrease the sum by 2 (modulo 4d2). So If N is large enough, there are many k < N such that k is a multiple of 2d, By switching the sign in front of r of these, we change ('downward') the congruence class modulo 4d2 by 2r. By choosing N so that the original sum is odd, and choosing suitable r < 2d2, we can obtain numbers congruent to all odd numbers modulo 4d2. By choosing N so that the original sum is even, we can obtain numbers congruent to all even numbers modulo 4d2 . This completes the proof.