Mathematical Excalibur, Volume 16, Number 4

Abstract

Mathematical Excalibur Volume 16, Number 4 February 2012 Zsigmondy ’s Theorem Andy Loo (St. Paul’s Co-educational College) Olympiad Corner Below are the problems of the 2011-2012 British Math Olympiad Round 1 held on 2 December 2011. Problem 1. Find all (positive or negative) integers n for which n2+20n+11 is a perfect square. Problem 2. Consider the numbers 1, 2, n. Find, in terms of n, the largest integer t such that these numbers can be arranged in a row so that all consecutive terms differ by at least t. Problem 3. Consider a circle S. The point P lies outside S and a line is drawn through P, cutting S at distinct points X and Y. Circles S1 and S2 are drawn through P which are tangent to S at X and Y respectively. Prove that the difference of the radii of S1 and S2 is independent of the positions of P, X and Y. Problem 4. Initially there are m balls in one bag, and n in the other, where m, n > 0. Two different operations are allowed: a) Remove an equal number of balls from each bag; b) Double the number of balls in one bag. (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 March 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 In recent years, a couple of “hard” number theoretic problems in the IMO turn out to be solvable by simple applications of deep theorems. For instances, IMO 2003 Problem 6 and IMO 2008 Problem 3 are straight forward corollaries of the Chebotarev density theorem and a theorem of Deshouillers and Iwaniec respectively. In this article we look at yet another mighty theorem, which was discovered by the Austro-Hungarian mathematician Karl Zsigmondy in 1882 and which can be used to tackle many Olympiad problems at ease. Zsigmondy’s theorem First part: If a, b and n are positive integers with a>b, gcd(a, b)=1 and n≥2, then an–bn has at least one prime factor that does not divide ak–bk for all positive integers k<n, with the exceptions of: i) 26–16 and ii) n=2 and a+b is a power of 2. Second part: If a, b and n are positive integers with a>b and n≥2, then an+bn has at least one prime factor that does not divide ak+bk for all positive integers k<n, with the exception of 23+13. The proof of this theorem is omitted due to limited space. Interested readers may refer to [2]. To see its power, let us look at how short solutions can be obtained using Zsigmondy’s theorem to problems of various types. Example 1 (Japanese MO 2011). Find all quintuples of positive integers (a,n,p,q,r) such that an–1 = (ap–1)(aq–1)(ar–1). Solution. If a≥3 and n≥3, then by Zsigmondy’s theorem, an–1 has a prime factor that does not divide ap–1, aq–1 and ar–1 (plainly n>p,q,r), so there is no solution. The remaining cases (a < 3 or n < 3) are easy exercises for the readers. Example 2 (IMO Shortlist 2000). Find all triplets of positive integers (a,m,n) such that am+1|(a+1)n. Solution. Note that (a,m,n)=(2,3,n) with n ≥ 2 are solutions. For a > 1, m ≥ 2 and (a,m) ≠ (2,3), by Zsigmondy’s theorem, am+1 has a prime factor that does not divide a+1, and hence does not divide (a+1)n, so there is no solution. The cases (a =1 or m =1) lead to easy solutions. Example 3 (Math Olympiad Summer Program 2001) Find all quadruples of positive integers (x,r,p,n) such that p is a prime, n,r>1 and xr–1 = pn. Solution. If xr–1 has a prime factor that does not divide x–1, then since xr–1 is divisible by x–1, we deduce that xr–1 has at least two distinct prime factors, a contradiction unless (by Zsigmondy’s theorem) we have the exceptional cases x=2, r=6 and r=2, x+1 is a power of 2. The former does not work. For the latter, obviously p=2 since it must be even. Let x+1=2y. Then 2n = x2–1 = (x+1)(x–1) = 2y(2y–2). It follows that y=2 (hence x=3) and n=3. Example 4 (Czech-Slovak Match 1996). Find all positive integral solutions to px–yp=1, where p is a prime. Solution. The equation can be rewritten as px = yp+1. Now y = 1 leads to (p,x) = (2,1) and (y,p) = (2,3) leads to x = 2. For y > 1 and p≠3, by Zsigmondy’s theorem, yp+1 has a prime factor that does not divide y+1. Since yp+1 is divisible by y+1, it follows that yp+1 has at least two prime factors, a contradiction. Remark. Alternatively, the results of Examples 3 and 4 follow from Catalan’s conjecture (proven in 2002), which guarantees that the only positive integral solution to the equation xa–yb=1 with x,y,a,b>1 is x=3, a=2, y=2, b=3. Mathematical Excalibur, Vol. 16, No. 4, Feb. 12 Page 2 Example 5 (Polish MO 2010 Round 1). Let p and q be prime numbers with q>p>2. Prove that 2pq–1 has at least three distinct prime factors. Solution. Note that 2p–1 and 2q–1 divide 2pq–1. By Zsigmondy’s theorem, 2pq–1 has a prime factor p1 that does not divide 2p–1 and 2q–1. Moreover, 2q–1 has a prime factor p2 that does not divide 2p–1. Finally, 2p–1 has a prime factor p3. The next example illustrates a more involved technique of applying Zsigmondy’s theorem to solve a class of Diophantine equations. Example 6 (Balkan MO 2009). Solve the equation 5x – 3y = z2 in positive integers. Solution. By considering (mod 3), we see that x must be even. Let x=2w. Then 3y = 52w–z2 = (5w–z)(5w+z). Note That (5w–z,5w+z) = (5w–z,2z) = (5w–z,z) = (5w,z) = 1, so 5w – z = 1 and 5w + z = 3a for some positive integer a ≥ 2. Adding, 2(5w) = 3a + 1. For a = 2, we have w = 1, corresponding to the solution x = 2, y = 2 and z = 4. For a ≥ 3, by Zsigmondy’s theorem, 3a+1 has a prime factor p that does not divide 32 + 1 = 10, which implies p≠2 or 5, so there is no solution in this case. Example 7. Find all positive integral solutions to pa–1=2n(p–1), where p is a prime. Solution. The case p=2 is trivial. Assume p is odd. If a is not a prime, let a=uv. Then pu–1 has a prime factor that does not divide p–1. Since pu–1 divides pa–1=2n(p–1), this prime factor of pu–1 must be 2. But by Zsigmondy’s theorem, pa–1 has a prime factor that does not divide pu–1 and p–1, a contradiction to the equation. So a is a prime. The case a=2 yields p=2n–1, i.e. the Mersenne primes. If a is an odd number, then by Zsigmondy’s theorem again, pa–1=2n(p–1) has a prime factor that does not divide p–1; this prime factor must be 2. However, 2 divides p–1, a contradiction. (continued on page 4) A Geometry Theorem Kin Y. Li The following is a not so well known, but useful theorem. Solution. Let ∠BAC=∠DAC=θ and G’ be on segment BC such that ∠G’AC =∠EAC=α. We will show G’, F, D are collinear, which implies G’=G. Applying the subtended angle theorem to ABE, ABC and ACD respectively, we get AF AB AE sin(θ +α ) = sinα + sinθ , Subtended Angle Theorem. D is a point inside ∠BAC (<180°). Let α =∠BAD and β =∠CAD. D is on side BC if and only if AG AB AC sin sin( ) sinθ = α + θ −α and (3) AE AD AC sinθ = sinα + sin(θ −α ) . sin( ) sin sin (*). AD AC AB α + β = α + β Proof. Note D is on segment BC if and Doing (1)−(2)+(3), we get only if the area of ΔABC is the sum of the areas of ΔABD and ΔACD. This is sin( ) sin sin AF AD AG θ +α = α + θ AB⋅ ACsinα( +β ) = AB⋅ AD α + AC⋅ AD β By the subtended angle theorem, G’, F, D are collinear. Therefore, G Multiplying by 2/(AB·AC·AD) yields (*). Example 3. Below, we will write PQ∩RS=X to mean lines PQ and RS intersect at point X. Example 1. (Butterfly Theorem) Let A,C,E,B,D,F be points in cyclic order on a circle and CD∩EF=P is the midpoint of AB. Let M = AB∩DE and Let ADBC=K, ABCD=L, N = ABCF. Prove that MP = NP. BD∩KL=F and ACKL=G. Prove that 1/KL = ½(1/KF +1/KG). Solution. Applying the subtended angle theorem to KAL,KDL,KDF and KAG, we get Solution. By the intersecting chord theorem, PC·PD=PE·PF, call this x. Applying the subtended angle theorem To PDE and PCF, we get KB KL KA KC KL KD sinα( +β ) = sinα + sinβ , sinα( +β ) = sinα + sinβ sin( ) sin sin sin( ) sin sin PN PC PF PM PD PE α β α β KB KF KD KC KG KA sinα( +β ) = sinα + sinβ , sinα( +β ) = sinα + sinβ Call these (1), (2), (3), (4) respectively. Doing (1)+(2)−(3)−(4), we get Subtracting these equations, we get KL KF KG sin( ) 1 1 PD PC PF PE PM PN Let Q and R be the midpoints of EF and CD respectively. Since OPAB, we have PF−PE = 2PQ = 2OP cos(90°−α) = 2OP sin α. Then similarly we have PD−PC = 2OP sin β. Hence, the right side of (*) is zero. So the left side of (*) is also zero. Since 0 < α+β < 180°, we get sin (α+β) ≠ 0. Then PM = PN. which implies the desired equation. Example 2. (1999 Chinese National Math Competition) In the convex quadrilateral ABCD, diagonal AC bisects∠BAD. Let E be on side CD such that BE∩AC=F and DBC=G. Prove that ∠GAC =∠EAC. Mathematical Excalibur, Vol. 16, No. 4, Feb. 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 March 28, 2012. Problem 386. Observe that 7+1=23 and 77+1= 23×113×911. Prove that for n = 2, 3, 4,…, in the prime factorization of , the sum of the Problem 387. Determine (with proof) all functions f : [0,+∞) →[0,+∞) such that for every x ≥ 0, we have 4f(x) ≥ 3x and f (4f(x) − 3x) = x. Problem 388. In ΔABC, ∠BAC=30° and ∠ABC=70°. There is a point M lying inside ΔABC such that ∠MAB= ∠MCA=20°. Determine ∠MBA (with proof). Problem 389. There are 80 cities. An airline designed flights so that for each of these cities, there are flights going in both directions between that city and at least 7 other cities. Also, passengers from any city may fly to any other city by a sequence of these flights. Determine the least k such that no matter how the flights are designed subject to the conditions above, passengers from one city can fly to another city by a sequence of at most k flights. Problem 390. Determine (with proof) all ordered triples (x, y, z) of positive integers satisfying the equation x2y2 = z2(z2 − x2 − y2). Solutions 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. Solution. AN-anduud Problem Solving Group (Ulaanbaatar, Mongolia), CHAN Chun Wai and LEE Chi Man (Statistics and Actuarial Science Society SS HKUSU), Andrew KIRK (Mearns Castle High School, Glasgow, Scotland), Kevin LAU Chun Ting (St. Paul’s Co-educational College, S.3), LO Shing Fung (F3E, Carmel Alison Lam Foundation Secondary School) and Andy LOO (St. Paul’s Co-educational College). We induct on k. For k=1, we can merge the 2 balls in at most 1 transfer. Suppose the case k=n is true. For k=n+1, since 2k is even, considering (odd-even) parity of the number of balls in each pile, we see the number of piles with odd numbers of balls is even. Pair up these piles. In each pair, after 1 transfer, both piles will result in even number of balls. So we need to consider only the situation when all piles have even number of balls. Then in each pile, pair up the balls. This gives altogether 2n pairs. Applying the case k=n with the paired balls, we solve the case k=n+1. 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. Solution. Alumni 2011 (Carmel Alison Lam Foundation Secondary School) and AN-anduud Problem Solving Group (Ulaanbaatar, Mongolia) and Mihai STOENESCU (Bischwiller, France). For n = 1,2,3,…, vn+2 = 8(8vn−vn−1) −vn = 63vn− 8vn−1. Then vn+2 ≡ vn−1 (mod 3) and vn+2 ≡ −vn−1 (mod 7). Since v0= 0, v1=1, v2 = 8, so v3k+1, v3k+2 ≢ 0 (mod 3) and (mod 7) and v3k ≡ 0 (mod 3) and (mod 7). Other commended solvers: CHAN Chun Wai and LEE Chi Man (Statistics and Actuarial Science Society SS HKUSU), CHAN Long Tin (Diocesan Boys’ School), CHAN Yin Hong (St. Paul’s Co-educational College), Andrew KIRK (Mearns Castle High School, Glasgow, Scotland), Kevin LAU Chun Ting (St. Paul’s Co-educational College, S.3), LKL Excalibur (Madam Lau Kam Lung Secondary School of MFBM), Andy LOO (St. Paul’s Co-educational College), NGUYEN van Thien (Luong The Vinh High School, Dong Nai, Vietnam), O Kin Chit Alex (G.T.(Ellen Yeung) College), Ángel PLAZA (Universidad de Las Palmas de Gran Canaria, Spain), Yan Yin WANG (City University of Hong Kong, Computing Math, Year 2), ZOLBAYAR Shagdar (Orchlon School, Ulaanbaatar, Mongolia),Titu ZVONARU (Comanesti, Romania) and Neculai STANCIU (“George Emil Palade’’ Secondary School, Buzău, Romania). 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. Solution 1. Kevin LAU Chun Ting (St. Paul’s Co-educational College, S.3). exponents is at least 2 From BC = (AB+AC)/2 = BD+CE, we see there exists a point F be on side BC such that BF=BD and CF=CE. Since BI bisects ∠FBD, by SAS, IBD IBF. Then ∠BDI=∠BFI. Similarly, ∠CEI = ∠CFI. Then ∠ADI +∠AEI = (180°−∠BDI ) + (180°−∠CEI ) = 360° −∠BFI −∠CFI = 180°. So A,D,I,E are concyclic. Since OD AD and OE AE, so A,D,O,E are also conyclic. Then A,D,I,O are concyclic. So ∠OIA =∠ODA=90°. Solution 2. AN-anduud Problem Solving Group (Ulaanbaatar, Mongolia), Ercole SUPPA (Teramo, Italy), Titu ZVONARU (Comanesti, Romania) and Neculai STANCIU (“George Emil Palade’’ Secondary School, Buzau, Romania). Let a=BC, b=CA, c=AB and let R, r, s be the circumradius, the inradius and the semiperimeter of BC respectively. By the famous formulas OI2 = R2−2Rr, s−a = AI cos(A/2), Rr = abc/(4s) and cos2(A/2) = s(s−a)/(bc), we get (cos ( / 2) If a = (b+c)/2, then we get 2s = 3a and bc(s−a)/s = abc/(2s). So AI2+OI2 = R2 = OA2. By the converse of Pythagoras’ Theorem, we get OIAI. Comment: In the last paragraph, all steps may be reversed so that OIAI if and only if a = (b+c)/2. Mathematical Excalibur, Vol. 16, No. 4, Feb. 12 Page 4 Other commended solvers: Alumni 2011 (Carmel Alison Lam Foundation Secondary School), CHAN Chun Wai and LEE Chi Man (Statistics and Actuarial Science Society SS HKUSU), Andrew KIRK (Mearns Castle High School, Glasgow, Scotland), Andy LOO (St. Paul’s Co-educational College), MANOLOUDIS Apostolos (4° Lyk. Korydallos, Piraeus, Greece), NGUYEN van Thien (Luong The Vinh High School, Dong Nai, Vietnam), Mihai STOENESCU (Bischwiller, France) and ZOLBAYAR Shagdar (Orchlon School, Ulaanbaatar, Mongolia)

Problem 384. For all positive real numbers a,b,c satisfying a + b + c = 3, prove that Solution William PENG. Let a b c D = + + Then A+3B is the left side of the desired inequality. Now since a + b + c = 3, we have C = 4D −3. By the Cauchy-Schwarz inequality, we have (a+b+c)D 32, AC D2 and BC D2. The first of these gives us D so that (D−3)(D−1)0, which implies D 2 4D−3. The second and third imply A B D Other commended solvers: Alumni 2011 (Carmel Alison Lam Foundation Secondary School), AN-anduud Problem Solving Group (Ulaanbaatar, Mongolia), Andrew KIRK (Mearns Castle High School, Glasgow, Scotland), LKL Excalibur (Madam Lau Kam Lung Secondary School of MFBM), Andy LOO (St. Paul’s Co-educational College), NGUYEN van Thien (Luong The Vinh High School, Dong Nai, Vietnam) and Paolo PERFETTI (Math Dept, Universita degli studi di Tor Vergata Roma, via della ricerca scientifica, Roma, Italy). 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. Solution. AN-anduud Problem Solving Group (Ulaanbaatar, Mongolia), CHAN Chun Wai and LEE Chi Man (Statistics and Actuarial Science Society SS HKUSU), Andrew KIRK (Mearns Castle High School, Glasgow, Scotland), Andy LOO (St. Paul’s Co-educational College) and Yan Yin WANG (City University of Hong Kong, Computing Math, Year 2) Let Si be the total number of problems Jack solved from the first day to the end of the i-th day. Since he solves at least one problem everyday, we have 0 S1 S2 S3 S77. Since he can solve at most 12 problems every week, we have S77 12×11=132. Consider the two strictly increasing sequences S1, S2, S77 and S1+21, S2+21, S77+21. Now these 154 integers are at least 1 and at most 132+21=153. By the pigeonhole principle, since the two sequences are strictly increasing, there must be m < k such that Sk=Sm+21. Therefore, Jack solved a total of 21 problems from the (m+1)-st day to the end of the k-th day. Olympiad Corner (continued from page 1) Problem 4 (cont). Is it possible to empty both bags after a finite sequence of operations? Operation b) is now replaced with b') Triple the number of balls in one bag. Is it now possible to empty both bags after a finite sequence of operations? Problem 5. Prove that the product of four consecutive positive integers cannot be equal to the product of two consecutive positive integers. Problem 6. Let ABC be an acute-angled triangle. The feet of all the altitudes from A, B and C are D, E and F respectively. Prove that DE+DF BC and determine the triangles for which equality holds. Zsigmondy’s Theorem (continued from page 2) Example 8. Find all positive integral solutions to (a+1)(a2+a+1)(an+an–1+⋯+1) = am+am-1+⋯+1. Solution. Note that n = m = 1 is a trivial solution. Other than that, we must have m>n. Write the equation as then rearranging we get By Zsigmondy’s theorem, we must have a = 2 and m + 1 = 6, i.e. m = 5 (otherwise, am–1 has a prime factor that does not divide a2–1, a3–1, …, an+1–1, a contradiction), which however does not yield a solution for n. The above examples show that Zsigmondy’s theorem can instantly reduce many number theoretic problems to a handful of small cases. We should bear in mind the exceptions stated in Zsigmondy’s theorem in order not to miss out any solutions. Below are some exercises for the readers. Exercise 1 (1994 Romanian Team Selection Test). Prove that the sequence an=3n–2n contains no three terms in geometric progression. Exercise 2. Fermat’s last theorem asserts that for a positive integer n 3, the equation xn+yn=zn has no integral solution with xyz≠0. Prove this statement when z is a prime. Exercise 3 (1996 British Math Olympiad Round 2). Determine all sets of non-negative integers x, y and z which satisfy the equation 2x+3y=z2. Reference PISOLVE, The Zsigmondy Theorem, http://www.artofproblemsolving.com/ Forum/viewtopic.php?f=721&t=42233 [2] Lola Thompson, Zsigmondy’s Theorem, http://www.math.dartmouth.edu/~tho mpson/Zsigmondy's%20Theorem.pdf Solution to Olympiad Corner, vol. 16, no. 4 The following are solutions by Dalton Fung (Shatin College), who was one of the nine contestants, achieved perfect scores on the 2012 BMO Round 1 paper. Problem 1. Let n2+20n+ll=k2 for some nE, kENu. Completing square, we get 89=(n+l0)2-k2 =(n+ 1 O+k)(n+ 1 O-k). Note that kE N implies n+ 1 O+Ien+ 1 O-k. Since 89 is a prime, we have (n+ 1 O+k = 89 and n+ 1 O-k = 1) or (n+ 1 O+k = -1 and n+ 1 O-k = -89). In each system, we add the equations and solve for n. The first system yields n=35 and k=44. The second system yields n=-55 and k=44. All steps are reversible. Therefore, the only solutions are n = 35 or -55. Problem 2. We denote the required t by tmax. We consider two cases. Case 1 Cn is even). First we show tmax :s nl2. (We note that iftmax n/2, then an arrangement that works for tmax also works for (n/2)+ 1. However, no arrangement can work for (n/2)+ 1 because such arrangement would contain n/2 and a neighbor x of n/2 such that (n/2)-x2:(n/2)+ 1 or x-(nl2)2:(n/2)+ 1, which leads to -12:x or x2:n+ 1, contradiction.) Next we will construct a sequence that works for n/2. We partition {l,2, ... ,n} into {l,1+(nl2)}, {2, 2+(n/2)}, ... ,{n/2, n} Then 1, 1+(nl2), 2, 2+(n/2), ... ,n/2, n is such a sequence for n/2. So tmax= n/2. Case 2 Cn is odd). First we show tmax :s (n-l )/2. (We note that if tmax > (n-l )/2, then an arrangement that works for tmax also works for (n+ 1 )/2. However, no arrangement can work for (n+ 1)12 because such arrangement would contain (n+ 1)/2 and a neighbor x of (n+ 1)/2 such that (n+ l)l2-x2:(n+ 1)/2 or x-(n+ 1)/22:(n+ 1)/2, which leads to 02:x or x2:n+ 1, contradiction.) Next we will construct a sequence that works for (n-l)/2. We partition {1,2, ... ,n} into {n}, {(n-1)/2, n-l}, {(n-3)12, n-2}, ... ,{2, 2+(n-l)/2}, {I, 1+(n-1)/2}. Then n, (n-1)/2, n-l, (n-3)/2, n-2,2, 2+(n-l)/2, 1, 1+(n-l)/2 is such a sequence for (n-1 )/2. So tmax= (n-l )/2. To conclude, tmax = Lnl2J for both n even and odd. (Figure for Problem 3) Problem 3. Let 0, 0], O2 be the centers of S, S], S2 respectively. Let 1', r], r2 be the radii of S, S], S2 respectively. Since S] and S2 are tangent to S at X and Y respectively, we see O],X,O are coilinear and also 02,O,Y are collinear. Now we have LO]PX=LO]XP=LOXY=LOYX=L02YP=L02PY, call this 8. By considering 6. PXO], we get r] = (Y2PX)/(cos 8). Similarly, r2 = (YzPY)/(cos 8) and r = (YzXY)/(cos 8). Now Ir]-r21 == I(YzPX)/(cos 8)- (YzPY)/(cos 8)1 = 1 (YzXY)/(cos 8)1 = r, which is independent of the positions ofP, X and Y. Problem 4. For the first part of the problem, we assume, without loss of generality, that m2:n. We set a=m-n. Note that aE N U {O}. We consider two cases. Case 1 Cn> [ml2] ). Then n-a =2n-m2:0. Now we remove n-a balls from each bag by operation (a). Then we have m-(n-a)=2a balls in the first bag and n-(n-a)= a balls in .the second bag. We use operation (b) to double the balls in the second 'bag. Now we have 2a balls in each bag. By operation (a), we can empty both bags. Case 2 (n[m/2]). In this case, we can use operation (b) finitely many times to get the number of balls, n', in the second bag satisfies m2:n2:fm/21. (This is always possible because assuming for some tEN, t f m/21 and 2t m, we get t f m/21 = 2t < 2 f m/21 :s m+ 1 (so 2t :s m), which contradicts 2t > m). Then the case reduces to case 1. Hence, the first part of the problem has an affirmative answer. Next we will show the second part of the problem has a negative answer. This follows from the Lemma. The total number of balls in both bags modulo 2 is an invariant. Proof. For operation (a), we have to remove an even number of balls in total. For operation (b), if a bag has an odd (resp. even) number of balls before operation (b), then it still has an odd (resp. even) number of balls after operation (b). By the lemma, if m+n is odd in the beginning, then it is not possible to empty both bags after a finite sequence of operations. Problem 5. Suppose (n-1)n(n+ 1)(n+2)=i(i+ 1) for some nE{2,3,4, ... } and iEN. Then (n2+n-2)(n2+n) = (n-1)(n+2)n(n+ 1) = i(i+ 1). Note that n2+n-3 > O. Case 1 (i>n2+n). Then i(i+1) > (n2+n)(n2+n+1) > (n2+n)(n2+n-2). Case 2 0=n2+n). Then i(i+ 1) = (n2+n)(n2+n+ 1) > (n2+n)(n2+n-2). Case 3 0=n2+n-1). Then i(i+ 1) = (n2+n-1)(n2+n) > (n2+n-2)(n2+n). Case 4 0=n2+n-2). Then i(i+ 1) = (n2+n-2)(n2+n-1) < (n2+n-2)(n2+n). Case 5 (i=n2+n-3). Then i(i+ 1) =(n2+n-3)(n2+n-2) < (n2+n)(n2+n-2). Case 6 0<n2+n-3). Then i(i+ 1) < (n2+n-3)(n2+n-2) < (n2+n)(n2+n-2). B Therefore there are no solutions. A D (Figure for Problem 6) Problem 6. Let L.A, L.B, L.C denote L.BAC, L.ABC, L.BCA respectively. Without loss of generality, we assume L.B 2:L.C. Lemma 1. L.B 2:L.C AF 2: AE. Proof. L.B 2:L.C AC 2: AB by sine rule. Now AF/AC = cosL.A= AE/AB. So AC 2: AB AF 2: AE. Lemma 2. DExDF=DCxBD. Proof. By the property of orthocenter, we get D, H, E, Care concyclic; F, C H, D, Bare concyclic; E, H, F, A are concyclic; A, F, D, Care concyclic; C, E, F, Bare concyclic; B, D, E, A are concyclic. Now applying sine rule to 6.ADE and the fact D, H, E, Care concyclic, we have DE = AE(sin L.DAE/sin L.ADE)=AE(sin L.DAC/sin L.ACF)=AE[(DC/AC)/(AF/AC)] = DCCAE/AF Similarly, DF= BD(AF/AE)BD ..... (2). Then DExDF=DC(AE/AF)xBD(AF/AE) = DCxBD. Now DE+DF BC=BD+DC DE2+2DExDF+DF2 BD2+2BCxDC+DC2 DE2+DF2 BD2+DC2 (by Lemma 2) BD2+DC22: DC2(AE2/AF2)+BD2(AF2/AE2) (by (1) and (2)) DC2(1-AE2/AF2) 2: BD2(1-AF2/AE2) DC2/AF2 2: BD2/AE2 DC/BD 2: AF/AE (AD/tanL.C)/(AD/tanL.B) 2: sin L.AEF/sin L.AFE = sinL.B/sinL.C cosL.CI cosL.B 2: 1 cos L.C 2: cos L.B, which is true since n12 > L.B 2:L.C > O. For the equality case, DE+DF=BC coSL.C = cosL.B L.C = L.B AC=AB.