Baixe Useful substituitions: problems from the book of advanced maths - 2008 e outras Notas de estudo em PDF para Matemática, somente na Docsity! Contents TWO USEFUL SUBSTITUTIONS 2 ALWAYS CAUCHY-SCHWARZ 11 EQUATIONS AND BEYOND 25 LOOK AT THE EXPONENT! 38 PRIMES AND SQUARES 53 T2’S LEMMA 65 ONLY GRAPHS, NO SUBGRAPHS! 81 COMPLEX COMBINATORICS 90 FORMAL SERIES REVISITED 101 NUMBERS AND LINEAR ALGEBRA 117 ARITHMETIC PROPERTIES OF POLYNOMIALS 130 LAGRANGE INTERPOLATION 144 HIGHER ALGEBRA IN COMBINATORICS 166 GEOMETRY AND NUMBERS 184 THE SMALLER, THE BETTER 195 DENSITY AND REGULAR DISTRIBUTION 204 THE SUM OF DIGITS OF A POSITIVE INTEGER 218 ANALYSIS AGAINST NUMBER THEORY? 233 QUADRATIC RECIPROCITY 249 SOLVING ELEMENTARY INEQUALITIES WITH INTEGRALS 264 1 TWO USEFUL SUBSTITUTIONS We know that in most inequalities with a constraint such as abc = 1 the substitution a = x y , b = y z , c = z x simplifies the solution (don’t kid yourself, not all problems of this type become easier!). But have you ever thought about other similar substitutions? For example, what if we had the conditions x, y, z > 0 and xyz = x + y + z + 2? Or x, y, z > 0 and xy + yz + zx + 2xyz = 1? There are numerous problems that reduce to these conditions and to their corresponding substitutions. You will be probably surprised when finding out that the first set of conditions implies the existence of positive real numbers a, b, c such that x = b + c a , y = c + a b , z = a + b c . Let us explain why. The condition xyz = x+y+z+2 can be written in the following equivalent way: 1 1 + x + 1 1 + y + 1 1 + z = 1. Proving this is just a matter of simple computations. Take now a = 1 1 + x , b = 1 1 + y , c = 1 1 + z . Then a + b + c = 1 and x = 1− a a = b + c a . Of course, in the same way we find y = c + a b , z = a + b c . The converse (that is, b + c a , c + a b , a + b c satisfy xyz = x+ y + z = 2) is much easier and is settled again by basic computations. Now, what about the second set of conditions? If you look carefully, you will see that it is closely related to the first one. Indeed, x, y, z > 0 satisfy xy + yz + zx + 2xyz = 1 if and only if 1 x , 1 y , 1 z verify 1 xyz = 1 x + 1 y + 1 z + 2, so the substitution here is x = a b + c , y = b c + a , z = c a + b . 2 Example 4. Prove that if x, y, z > 0 and xyz = x + y + z + 2, then 2( √ xy + √ yz + √ zx) ≤ x + y + z + 6. Mathlinks site Solution. This is tricky, even with the substitution. There are two main ideas: using some identities that transform the inequality into an easier one and then using the substitution. Let us see. What does 2( √ xy + √ yz + √ zx) suggest? Clearly, it is related to ( √ x + √ y + √ z)2 − (x + y + z). Consequently, our inequality can be written as √ x + √ y + √ z ≤ √ 2(x + y + z + 3). The first idea that comes to mind (that is using the Cauchy- Schwarz inequality in the form √ x + √ y + √ z ≤ √ 3(x + y + z) ≤√ 2(x + y + z + 3)) does not lead to a solution. Indeed, the last inequal- ity is not true: setting x+y+z = s, we have 3s ≤ 2(s+3). This is because from the AM-GM inequality it follows that xyz ≤ s 3 27 , so s3 27 ≥ s + 2, which is equivalent to (s− 6)(s + 3)2 ≥ 0, implying s ≥ 6. Let us see how the substitution helps. The inequality becomes√ b + c a + √ c + a b + √ a + b c ≤ √ 2 ( b + c a + c + a b + a + b c + 3 ) The last step is probably the most important. We have to change the expression b + c a + c + a b + a + b c + 3 a little bit. We see that if we add 1 to each fraction, then a + b + c will appear as common factor, so in fact b + c a + c + a b + a + b c + 3 = (a + b + c) ( 1 a + 1 b + 1 c ) . 5 And now we have finally solved the problem, amusingly, by employ- ing again the Cauchy-Schwarz inequality:√ b + c a + √ c + a b + √ a + b c ≤ √ (b + c + c + a + a + b) ( 1 a + 1 b + 1 c ) . We continue with a 2003 USAMO problem. There are many proofs for this inequality, none of them easy. The following solution is again not easy, but it is natural for someone familiar with this kind of substitution. Example 5. Prove that for any positive real numbers a, b, c the following inequality holds (2a + b + c)2 2a2 + (b + c)2 + (2b + c + a)2 2b2 + (c + a)2 + (2c + a + b)2 2c2 + (a + b)2 ≤ 8. Titu Andreescu, Zuming Feng, USAMO 2003 Solution. The desired inequality is equivalent to( 1 + b + c a )2 2 + ( b + c a )2 + ( 2 + c + a b )2 2 + ( c + a b )2 + ( 1 + a + b c )2 2 + ( a + b c )2 ≤ 8. Taking our substitution into account, it suffices to prove that if xyz = x + y + z + 2, then (2 + x)2 2 + x2 + (2 + y)2 2 + y2 + (2 + z)2 2 + z2 ≤ 8. This is in fact the same as 2x + 1 x2 + 2 + 2y + 1 y2 + 2 + 2z + 1 z2 + 2 ≤ 5 2 . Now, we transform this inequality into (x− 1)2 x2 + 2 + (y − 1)2 y2 + 2 + (z − 1)2 z2 + 2 ≥ 1 2 . This last form suggests using the Cauchy-Schwarz inequality to prove that (x− 1)2 x2 + 2 + (y − 1)2 y2 + 2 + (z − 1)2 z2 + 2 ≥ (x + y + z − 3) 2 x2 + y2 + z2 + 6 . 6 So, we are left with proving that 2(x+y + z−3)2 ≥ x2 +y2 + z2 +6. But this is not difficult. Indeed, this inequality is equivalent to 2(x + y + z − 3)2 ≥ (x + y + z)2 − 2(xy + yz + zx) + 6. Now, from xyz ≥ 8 (recall who x, y, z are and use the AM-GM inequality three times), we find that xy+yz +zx ≥ 12 and x+y+z ≥ 6 (by the same AM-GM inequality). This shows that it suffices to prove that 2(s−3)2 ≥ s2−18 for all s ≥ 6, which is equivalent to (s−3)(s−6) ≥ 0, clearly true. And this difficult problem is solved! The following problem is also hard. We have seen a difficult solution in the chapter ”Equations and beyond”. Yet, there is an easy solution using the substitutions described in this unit. Example 6. Prove that if x, y, z ≥ 0 satisfy xy + yz + zx + xyz = 4 then x + y + z ≥ xy + yz + zx. India, 1998 Solution. Let us write the given condition as x 2 · y 2 + y 2 · z 2 + z 2 · x 2 + 2 x 2 · y 2 · z 2 = 1. Hence there are positive real numbers a, b, c such that x = 2a b + c , y = 2b c + a , z = 2c a + b . But now the solution is almost over, since the inequality x + y + z ≥ xy + yz + zx is equivalent to a b + c + b c + a + c a + b ≥ 2ab (c + a)(c + b) + 2bc (a + b)(a + c) + 2ca (b + a)(b + c) . After clearing denominators, the inequality becomes a(a + b)(a + c) + b(b + a)(b + c) + c(c + a)(c + b) ≥ 7 5. Prove that in any triangle ABC the following inequality holds cos A + cos B + cos C ≥ 1 4 (3 + cos(A−B) + cos(B − C) + cos(C −A)). Titu Andreescu 6. Prove that in every acute-angled triangle ABC, (cos A + cos B)2 + (cos B + cos C)2 + (cos C + cos A)2 ≤ 3. 7. Prove that if a, b, c > 0 and x = a+ 1 b , y = b+ 1 c , z = c+ 1 a , then xy + yz + zx ≥ 2(x + y + z). Vasile Cartoaje 8. Prove that for any a, b, c > 0, (b + c− a)2 (b + c)2 + a2 + (c + a− b)2 (c + a)2 + b2 + (a + b− c)2 (a + b)2 + c2 ≥ 3 5 . Japan, 1997 10 ALWAYS CAUCHY-SCHWARZ In recent years the Cauchy-Schwarz inequality has become one of the most used results in elementary mathematics, an indispensable tool of any serious problem solver. There are countless problems that reduce readily to this inequality and even more problems in which the Cauchy- Schwarz inequality is the key idea of the solution. In this unit we will not focus on the theoretical results, since they are too well-known. Yet, seeing the Cauchy-Schwarz inequality at work is not so well spread out. This is the reason why we will see this inequality in action in several simple examples first, employing then gradually the Cauchy-Schwarz inequality in some of the most difficult problems. Let us begin with a very simple problem, a direct application of the inequality. Yet, it underlines something less emphasized: the analysis of the equality case. Example 1. Prove that the finite sequence a0, a1, . . . , an of positive real numbers is a geometrical progression if and only if (a20 +a 2 1 + · · ·+a2n−1)(a21 +a22 + · · ·+a2n) = (a0a1 +a1a2 + · · ·+an−1an)2. Solution. We see that the relation given in the problem is in fact the equality case in the Cauchy-Schwarz inequality. This is equivalent to the proportionality of the n-tuples (a0, a1, . . . , an−1) and (a1, a2, . . . , an), that is a0 a1 + a1 a2 = · · · = an−1 an . But this is just actually the definition of a geometrical progression. Hence the problem is solved. Note that Lagrange’s identity allowed us to work with equivalences. Another easy application of the Cauchy-Schwarz inequality is the following problem. This time the inequality is hidden in a closed form, 11 which suggests using calculus. There exists a solution by using deriva- tives, but it is not as elegant as the featured one: Example 2. Let p be a polynomial with positive real coefficients. Prove that p(x2)p(y2) ≥ p2(xy) for any positive real numbers x, y. Russian Mathematical Olympiad Solution. If we work only with the closed expression p(x2)p(y2) ≥ p2(xy), the chances of seeing a way to proceed are small. So, let us write p(x) = a0 + a1x + · · ·+ anxn. The desired inequality becomes (a0 + a1x2 + · · ·+ anx2n)(a0 + a1y2 + · · ·+ any2n) ≥ (a0 + a1xy + · · ·+ anxnyn)2. And now the Cauchy-Schwarz inequality comes into the picture: (a0 + a1xy + · · ·+ anxnyn)2 = ( √ a0 · √ a0 + √ a1x2 · √ a2y2 + · · ·+ √ anxn · √ anyn)2 ≤ (a0 + a1x2 + · · ·+ anx2n)(a0 + a1y2 + · · ·+ any2n). And the problem is solved. Moreover, we see that the conditions x, y > 0 are useless, since we have of course p2(xy) ≤ p2(|xy|). Addi- tionally, note an interesting consequence of the problem: the function f : (0,∞) → (0,∞), f(x) = ln p(ex) is convex, that is why we said in the introduction to this problem that it has a solution based on calculus. The idea of that solution is to prove that the second derivative of is non- negative. We will not prove this here, but we note a simple consequence: the more general inequality p(xk1)p(x k 2) . . . p(x k k) ≥ pk(x1x2 . . . xk), which follows the Jensen’s inequality for the convex function f(x) = ln p(ex). 12 Example 5. Let a1, a2, . . . , an, b1, b2, . . . , bn be real numbers such that (a21+a 2 2+· · ·+a2n−1)(b21+b22+· · ·+b2n−1) > (a1b1+a2b2+· · ·+anbn−1)2. Prove that a21 + a 2 2 + · · ·+ a2n > 1 and b21 + b22 + · · ·+ b2n > 1. Titu Andreescu, Dorin Andrica, TST 2004, USA Solution. At first glance, the problem does not seem to be related to Aczel’s inequality. Let us take a more careful look. First of all, it is not difficult to observe that an indirect approach is more efficient. Moreover, we may even assume that both numbers a21 +a 2 2 + · · ·+a2n−1 and b21 + b 2 2 + · · · + b2n − 1 are negative, since they have the same sign (this follows immediately from the hypothesis of the problem). Now, we want to prove that (a21 + a 2 2 + · · ·+ a2n − 1)(b21 + b22 + · · ·+ b2n − 1) ≤ (a1b1 + a2b2 + · · ·+ anbn − 1)2 (1) in order to obtain the desired contradiction. And all of a sudden we arrived at the result in the previous problem. Indeed, we have now the conditions 1 > a21 + a 2 2 + · · · + a2n and 1 > b21 + b22 + · · · + b2n, while the conclusion is (1). But this is exactly Aczel’s inequality, with A = 1 and B = 1. The conclusion follows. Of a different kind, the following example shows that an apparently very difficult inequality can become quite easy if we do not complicate things more than necessary. It is also a refinement of the Cauchy-Schwarz inequality, as we can see from the solution. Example 6. For given n > k > 1 find in closed form the best con- stant T (n, k) such that for any real numbers x1, x2, . . . , xn the following 15 inequality holds:∑ 1≤i<j≤n (xi − xj)2 ≥ T (n, k) ∑ 1≤i<j≤k (xi − xj)2. Gabriel Dospinescu Solution. In this form, we cannot make any reasonable conjecture about T (n, k), so we need an efficient transformation. We observe that∑ 1≤i<j≤n (xi − xj)2 is nothing else than n n∑ i=1 x2i − ( n∑ i=1 xi )2 and also ∑ 1≤i<j≤k (xi − xj)2 = k k∑ i=1 x2i − ( k∑ i=1 xi )2 , according to Lagrange’s identity. Consequently, the inequality can be written in the equivalent form n n∑ i=1 x2i − ( n∑ i=1 xi )2 ≥ T (n, k) k k∑ i=1 x2i − ( k∑ i=1 xi )2 . And now we see that it is indeed a refinement of the Cauchy-Schwarz inequality, only if in the end it turns out that T (n, k) > 0. We also observe that in the left-hand side there are n − k variables that do not appear in the right-hand side and that the left-hand side is minimal when these variables are equal. So, let us take them all to be zero. The result is n k∑ i=1 x2i − ( k∑ i=1 xi )2 ≥ T (n, k) k k∑ i=1 x2i − ( k∑ i=1 xi )2 , which is equivalent to (T (n, k)− 1) ( k∑ i=1 xi )2 ≥ (kT (n, k)− n) k∑ i=1 x2i (1) 16 Now, if kT (n, k)−n > 0, we can take a k-tuple (x1, x2, . . . , xk) such that k∑ i=1 xi = 0 and k∑ i=1 x2i 6= 0 and we contradict the inequality (1). Hence we must have kT (n, k) − n ≤ 0 that is T (n, k) ≤ n k . Now, let us proceed with the converse, that is showing that n n∑ i=1 x2i − ( n∑ i=1 xi )2 ≥ n k k k∑ i=1 x2i − ( k∑ i=1 xi )2 (2) for any real numbers x1, x2, . . . , xn. If we manage to prove this inequality, then it will follow that T (n, k) = n k . But (2) is of course equivalent to n n∑ i=k+1 x2i ≥ ( n∑ i=1 xi )2 − n k ( k∑ i=1 xi )2 . Now, we have to apply the Cauchy-Schwarz inequality, because we need n∑ i=k+1 xi. We find that n n∑ i=k+1 x2i ≥ n n− k ( n∑ i=k+1 xi )2 and so it suffices to prove that n n− k A2 ≥ (A + B)2 − n k B2, (3) where we have taken A = n∑ i=k+1 xi and B = k∑ i=1 xi. But (3) is straight- forward, since it is equivalent to (kA− (n− k)B)2 + k(n− k)B2 ≥ 0, which is clear. Finally, the conclusion is settled: T (n, k) = n k is the best constant. We continue the series of difficult inequalities with a very nice prob- lem of Murray Klamkin. This time, one part of the problem is obvious 17 Thus, it remains to prove the inequality n∑ i=1 ai 2 (1− ai)2 ≤ n∑ i=1 a2i (1− ai)2 + n(n− 1) (2n− 1)2 . The latter can be written of course in the following form: n∑ i=1 ai(1− 2ai) (1− ai)2 ≤ 2n(n− 1) (2n− 1)2 . This encourages us to study the function f : [ 0, 1 2 ] → R, f(x) = x(1− 2x) (1− x)2 and to see if it is concave. This is not difficult, for a short computa- tion shows that f ′′(x) = −6x (1− x)4 ≤ 0. Hence we can apply Jensen’s inequality to complete the solution. We end this discussion with a remarkable solution, found by the member of the Romanian Mathematical Olympiad Committee, Claudiu Raicu, to the difficult problem given in 2004 in one of the Romanian Team Selection Tests. Example 9. Let a1, a2, . . . , an be real numbers and let S be a non- empty subset of {1, 2, . . . , n}. Prove that(∑ i∈S ai )2 ≤ ∑ 1≤i≤j≤n (ai + · · ·+ aj)2. Gabriel Dospinescu, TST 2004, Romania Solution. Let us define si = a1 + a2 + · · ·+ ai for i ≥ 1 and s0 = 0. Now, partition S into groups of consecutive numbers. Then ∑ i∈S ai is of the form sj1−si1+sj2−si2+· · ·+sjk−sik , with 0 ≤ i1 < i2 < · · · < ik ≤ n, j1 < j2 < · · · < jk and also i1 < j1, . . . , ik < jk. Now, let us observe that 20 the left-hand side is nothing else than n∑ i=1 s2i + ∑ 1≤i<j≤n (sj − si)2 = ∑ 1≤i<j≤n+1 (sj − si)2. Hence we need to show that (sj1 − si1 + sj2 − si2 + · · ·+ sjk − sik) 2 ≤ ∑ 0≤i<j≤n+1 (sj − si)2. Let us take a1 = si1 , a2 = sj1 , . . . , a2k−1 = sik , a2k = sjk and observe the obvious (but important) inequality∑ 0≤i<j≤n+1 (sj − si)2 ≥ ∑ 1≤i<j≤2k (ai − aj)2. And this is how we arrived at the inequality (a1 − a2 + a3 − · · ·+ a2k−1 − a2k)2 ≤ ∑ 1≤i<j≤2k (ai − aj)2 (1) The latter inequality can be proved by using the Cauchy-Schwarz inequality k-times: (a1 − a2 + a3 − · · ·+ a2k−1 − a2k)2 ≤ k((a1 − a2)2 + (a3 − a4)2 + · · ·+ (a2k−1 − a2k)2) (a1 − a2 + a3 − · · ·+ a2k−1 − a2k)2 ≤ k((a1 − a4)2 + (a3 − a6)2 + · · ·+ (a2k−1 − a2)2) . . . (a1 − a2 + a3 − · · ·+ a2k−1 − a2k)2 ≤ k((a1 − a2k)2 + (a3 − a2)2 + · · ·+ (a2k−1 − a2k−2)2) and by summing up all these inequalities. In the right-hand side we obtain an even smaller quantity than ∑ 1≤i<j≤2k (ai − aj)2, which proves that (1) is correct. The solution ends here. 21 Problems for training 1. Let a, b, c be nonnegative real numbers. Prove that (ax2 + bx + c)(cx2 + bx + a) ≥ (a + b + c)2x2 for all nonnegative real numbers x. Titu Andreescu, Gazeta Matematica 2. Let p be a polynomial with positive real coefficients. Prove that if p ( 1 x ) ≥ 1 p(x) is true for x = 1, then it is true for all x > 0. Titu Andreescu, Revista Matematica Timisoara 3. Prove that for any real numbers a, b, c ≥ 1 the following inequality holds: √ a− 1 + √ b− 1 + √ c− 1 ≤ √ a(bc + 1). 4. For any positive integer n find the number of ordered n-tuples of integers (a1, a2, . . . , an) such that a1 + a2 + · · ·+ an ≥ n2 and a21 + a22 + · · ·+ a2n ≤ n3 + 1. China, 2002 5. Prove that for any positive real numbers a, b, c, 1 a + b + 1 b + c + 1 c + a + 1 2 3 √ abc ≥ (a + b + c + 3 √ abc)2 (a + b)(b + c)(c + a) . Titu Andreescu, MOSP 1999 6. Let a1, a2, . . . , an, b1, b2, . . . , bn be real numbers such that∑ 1≤i<j≤n aiaj > 0. Prove the inequality ∑ 1≤i6=j≤n aibj 2 ≥  ∑ 1≤i6=j≤n aiaj  ∑ 1≤i6=j≤n bibj  Alexandru Lupas, AMM 22 EQUATIONS AND BEYOND Real equations with multiple unknowns have in general infinitely many solutions if they are solvable. In this case, an important task char- acterizing the set of solutions by using parameters. We are going to discuss two real equations and two parameterizations, but we will go beyond, showing how a simple idea can generate lots of nice problems, some of them really difficult. We begin this discussion with a problem. It may seem unusual, but this problem is in fact the introduction that leads to the other themes in this discussion. Example 1. Consider three real numbers a, b, c such that abc = 1 and write x = a + 1 a , y = b + 1 b , z = c + 1 c (1) Find an algebraic relation between x, y, z, independent of a, b, c. Of course, without any ideas, one would solve the equations from (1) with respect to a, b, c and then substitute the results in the relation abc = 1. But this is a mathematical crime! Here is a nice idea. To generate a relation involving x, y, z, we compute the product xyz = ( a + 1 a )( b + 1 b )( c + 1 c ) = ( a2 + 1 a2 ) + ( b2 + 1 b2 ) + ( c2 + 1 c2 ) + 2 = (x2 − 2) + (y2 − 2) + (z2 − 2) + 2. Thus, x2 + y2 + z2 − xyz = 4 (2) and this is the answer to the problem. Now, another question appears: is the converse true? Obviously not (take for example the numbers (x, y, z) = (1, 1,−1)). But looking again 25 at (1), we see that we must have min{|x|, |y|, |z|} ≥ 2. We will prove the following result. Example 2. Let x, y, z be real numbers with max{|x|, |y|, |z|} > 2. Prove that there exist real numbers a, b, c with abc = 1 satisfying (1). Whenever we have a condition of the form max{|x|, |y|, |z|} > 2, it is better to make a choice. Here, let us take |x| > 2. This shows that there exists a nonzero real number u such that x = u + 1 u , (we have used here the condition |x| > 2). Now, let us regard (2) as a second degree equation with respect to z. Since this equation has real roots, the discriminant must be nonnegative, which means that (x2 − 4)(y2 − 4) ≥ 0. But since |x| > 2, we find that y2 ≥ 4 and so there exist a non-zero real number v for which y = v + 1 v . How do we find the corresponding z? Simply by solving the second degree equation. We find two solutions: z1 = uv + 1 uv , z2 = u v + v u and now we are almost done. If z = uv+ 1 uv we take (a, b, c) = ( u, v, 1 uv ) and if z = u v + v u , then we take (a, b, c) = ( 1 u , v, u v ) . All the conditions are satisfied and the problem is solved. A direct consequence of the previous problem is the following: If x, y, z > 0 are real numbers that verify (2), then there exist α, β, χ ∈ R such that x = 2ch(α), y = 2ch(β), z = 2ch(χ), where ch : R → (0,∞), ch(x) = e x + e−x 2 . Indeed, we write (1), in which this time it is clear that a, b, c > 0 and we take α = ln a, β = ln b, χ = ln c. Inspired by the previous equation, let us consider another one x2 + y2 + z2 + xyz = 4, (3) 26 where x, y, z > 0. We will prove that the set of solutions of this equation is the set of triples (2 cos A, 2 cos B, 2 cos C) where A,B, C are the angles of an acute triangle. First, let us prove that all these triples are solutions. This reduces to the identity cos2 A + cos2 B + cos2 C + 2 cos A cos B cos C = 1. This identity can be proved readily by using the sum-to-product formulas, but here is a nice proof employing geometry and linear algebra. We know that in any triangle we have the relations a = c cos B + b cos C b = a cos C + c cos A c = b cos A + a cos B which are simple consequences of the Law of Cosines. Now, let us con- sider the system  x− y cos C − z cos B = 0 −x cos C + y − z cos A = 0 −x cos B + y cos A− z = 0 From the above observation, it follows that this system has a non- trivial solution, that is (a, b, c) and so we must have∣∣∣∣∣∣∣∣ 1 − cos C − cos B − cos C 1 − cos A − cos B − cos A 1 ∣∣∣∣∣∣∣∣ = 0, which expanded gives cos2 A + cos2 B + cos2 C + 2 cos A cos B cos C = 1. For the converse, we see first that 0 < x, y, z < 2, hence there are numbers A,B ∈ ( 0, π 2 ) such that x = 2 cos A, y = 2 cos B. Solving the equation with respect to z and taking into account that z ∈ (0, 2) we 27 not rational, that is, there aren’t polynomials p, q such that √ x2 − 4 = p(x) q(x) . But this is easy because if such polynomials existed, than each zero of x2− 4 should have even multiplicity, which is not the case. Con- sequently, for each y with |y| > 2 we have h(x, y) = k(x, y) = 0 for all x. But this means that h(x, y) = k(x, y) = 0 for all x, y, that is our polynomial is divisible with x2 + y2 + z2 − xyz − 4. O a different kind, the following problem and the featured solution prove that sometimes an efficient substitution can help more than ten complicated ideas. Example 6. Let a, b, c > 0. Find all triples (x, y, z) of positive real numbers such that{ x + y + z = a + b + c a2x + b2y + c2z + abc = 4xyz Titu Andreescu, IMO Shortlist, 1995 Solution. We try to use the information given by the second equa- tion. This equation can be written as a2 yz + b2 zx + c2 xy + abc xyz = 4 and we already recognize the relation u2 + v2 + w2 + uvw = 4 where u = a √ yz , v = b√ zx , w = c √ xy . According to example 3, we can find an acute-angled triangle ABC such that u = 2 cos A, v = 2 cos B, w = 2 cos C. We have made use of the second condition, so we use the first one to deduce that x + y + z = 2 √ xy cos C + 2 √ yz cos A + 2 √ zx cos B. 30 Trying to solve this as a second degree equation in √ x, we find the discriminant −4(√y sinC − √ z sinB)2. Because this discriminant is nonnegative, we infer that √ y sinC = √ z sinB and √ x = √ y cos C + √ z cos B. Combining the last two relations, we find that √ x sinA = √ y sinB = √ z sinC Now we square these relations and we use the fact that cos A = a 2 √ yz , cos B = b 2 √ zx , cos C = c 2 √ xy . The conclusion is: x = b + c 2 , y = c + a 2 , z = a + b 2 and it is immediate to see that this triple satisfies both conditions. Hence there is a unique triple that is solution to the given system. Notice that the condition x + y + z = 2 √ xy cos C + 2 √ yz cos A + 2 √ zx cos B is the equality case in the lemma stated in the solution of the following problem. This could be another possible solution of the problem. We have discussed the following very difficult problem in the chapter ”An useful substitution”. We will see that example 3 helps us find a nice geometric solution to this inequality. Example 7. Prove that if the positive real numbers x, y, z satisfy xy + yz + zx + xyz = 4, then x + y + z ≥ xy + yz + zx. India, 1998 31 Solution. It is not difficult to observe that at first glance, the con- dition xy + yz + zx + xyz = 4 it’s not the same as the equation (3). Let us write the condition xy + yz + zx + xyz = 4 in the form √ xy2 + √ yz2 + √ zx 2 + √ xy · √yz · √ zx = 4. Now, we can use the result from example 3 and we deduce the exis- tence of an acute-angled triangle ABC such that √ yz = 2 cos A √ zx = 2 cos B √ xy = 2 cos C We solve the system and we find the triplet (x, y, z) = ( 2 cos B cos C cos A , 2 cos A cos C cos B , 2 cos A cos B cos C ) Hence we need to prove that 2 cos B cos C cos A + 2 cos A cos C cos B + 2 cos A cos B cos C ≥ 2(cos2 A+cos2 B+cos2 C). This one is a hard inequality and it follows from a more general result. Lemma. If ABC is a triangle and x, y, z are arbitrary real numbers, then x2 + y2 + z2 ≥ 2yz cos A + 2zx cos B + 2xy cos C. Proof of the lemma. Let us consider points P,Q,R on the lines AB, BC, CA, respectively, such that AP = BQ = CR = 1 and P,Q,R and do not lie on the sides of the triangle. Then we see that the inequality is equivalent to (x · −→ AP + y · −−→ BQ + z · −→ CR)2 ≥ 0, which is obviously true. 32 from where we find that √ x0 + 1 √ x0 = 7. Similarly, we obtain that 4 √ x0 + 1 4 √ x0 = 3. Solving the equation, we obtain 4 √ x0 = ( 1 + √ 5 2 )2 = λ2 that is x0 = λ8. And so we have found the general formula an = λ8Fn + λ−8Fn . And now the problem becomes easy, since an + 2 = (λ4Fn + λ−4Fn)2 and 2 + √ 2 + an = (λ2Fn + λ−2Fn)2. All we are left to prove is that λ2k + 1 λ2k ∈ R for all k ∈ R. But this isn’t difficult, since λ2 + 1 λ2 ∈ R, λ4 + 1 λ4 ∈ R and λ2(k+1) + 1 λ2(k+1) = ( λ2 + 1 λ2 )( λ2k + 1 λ2k ) − ( λ2(k−1) + 1 λ2(k−1) ) . Problems for training 1. Find all triples x, y, z of positive real numbers, solutions to the system: { x2 + y2 + z2 = xyz + 4 xy + yz + zx = 2(x + y + z) 2. Let x, y, z > 0 such that x2 + y2 + z2 + xyz = 4. Prove that√ (2− a)(2− b) (2 + a)(2 + b) + √ (2− b)(2− c) (2 + b)(2 + c) + √ (2− c)(2− a) (2 + c)(2 + a) = 1. Cristinel Mortici, Romanian Inter-county Contest 35 3. Prove that if a, b, c ≥ 0 satisfy the condition |a2+b2+c2−4| = abc, then (a− 2)(b− 2) + (b− 2)(c− 2) + (c− 2)(a− 2) ≥ 0. Titu Andreescu, Gazeta Matematica 4. Find all triples (a, b, c) of positive real numbers, solutions to the system { a2 + b2 + c2 + abc = 4 a + b + c = 3 Cristinel Mortici, Romanian Inter-county Contest 5. Prove that in any triangle the following inequality holds( sin A 2 + sin B 2 + sin C 2 )2 ≤ cos2 A 2 + cos2 B 2 + cos2 C 2 . 6. Let x, y, z > 0 such that xy + yz + zx + xyz = 4. Prove that 3 ( 1√ x + 1 √ y + 1√ z )2 ≥ (x + 2)(y + 2)(z + 2). Gabriel Dospinescu 7. Prove that in any acute-angled triangle the following inequality holds( cos A cos B )2 + ( cos B cos C )2 + ( cos C cos A )2 + 8 cos A cos B cos C ≥ 4. Titu Andreescu, MOSP 2000 8. Solve in positive integers the equation (x + 2)(y + 2)(z + 2) = (x + y + z + 2)2. Titu Andreescu 9. Let n > 4 be a given positive integer. Find all pairs of positive integers (x, y) such that xy − (x + y) 2 n = n− 4. 36 Titu Andreescu 10. Let the sequence (an)n≥0, where a0 = a1 = 97 and an+1 = an−1an + √ (a2n − 1)(a2n−1 − 1) for all n ≥ 1. Prove that 2 + √ 2 + 2an is a perfect square for all n ≥ 0. Titu Andreescu 11. Find all triplets of positive integers (k, l,m) with sum 2002 and for which the system  x y + y x = k y z + z y = l z x + x y = m has real solutions. Titu Andreescu, proposed for IMO 2002 12. Find all functions f : (0,∞) → (0,∞) with the following prop- erties: a) f(x)+f(y)+f(z)+f(xyz) = f( √ xy)f( √ yz)f( √ zx) for all x, y, z; b) if 1 ≤ x < y then f(x) < f(y). Hojoo Lee, IMO Shortlist 2004 13. Prove that if a, b, c ≥ 2 satisfy the condition a2+b2+c2 = abc+4, then a + b + c + ac + bc ≥ 2 √ (a + b + c + 3)(a2 + b2 + c2 − 3). Marian Tetiva 14. Prove that if a, b, c ≥ 0 satisfy a2 + b2 + c2 + abc = 4 then 0 ≤ ab + bc + ca− abc ≤ 2. Titu Andreescu, USAMO 2001 37 Of course, it is enough to prove that for each k ≥ 1 the term cor- responding to k in the first sum is greater than or equal to the term corresponding to k in the second sum. With the substitution x = a pk , y = b pk , we have to prove that for any nonnegative real numbers x, y we have [3x + 3y] + [2x] + [3y] + [2y] ≥ [2x + 3y] + [x + 2y] + [x + y] + [x] + 2[y]. This isn’t easy, but with another useful idea the inequality will be- come easy. The idea is that [3x + 3y] = 3[x] + 3[y] + [3{x}+ 3{y}] and similar relations for the other terms of the inequality. After this operation, we see that it suffices to prove the inequality only for 0 ≤ x, y < 1. Why is the new inequality easy? Because we can easily compute all terms, after splitting in some cases, so that to see when [2{x}], [3{y}], [2{y}] are 0, 1 or 2. We won’t continue studying these cases, since another beautiful problem is waiting. Example 2. Let a, b be positive integers such that a|b2, b3|a4, a5|b6, b7|a8, . . . . Prove that a = b. Solution. Let us take a prime p and try to prove that vp(a) = vp(b). We see that the hypothesis a|b2, b3|a4, a5|b6, b7|a8, . . . is the same as a4n+1|b4n+2 and b4n+3|a4n+4 for all natural number n. But the relation a4n+1|b4n+2 can be interpreted as (4n + 1)vp(a) ≤ (4n + 2)vp(b) for all n, that is vp(a) ≤ lim n→∞ 4n + 2 4n + 1 vp(b) = vp(b). Similarly, the condition b4n+3|a4n+4 implies vp(a) ≥ vp(b) and so vp(a) = vp(b). The conclusion follows: a = b. 40 We have mentioned in the beginning of the discussion a nice and easy problem, so probably it’s time to solve it, although for sure the reader has already done this. Example 3. Prove that lcm(a, b, c)2|lcm(a, b) · lcm(b, c) · lcm(c, a) for any positive integers a, b, c. Solution. Let p an arbitrary prime number. We have vp(lcm(a, b, c)2) = 2 max{x, y, z} and vp(lcm(a, b) · lcm(b, c) · lcm(c, a)) = max{x, y}+max{y, z}+max{z, x}, where x = vp(a), y = vp(b), z = vp(c). So, we need to prove that max{x, y}+ max{y, z}+ max{z, x} ≥ 2 max{x, y, z} for any nonnegative integers x, y, z. But this is easy, since we may assume that x ≥ y ≥ z (the symmetry allows us this supposition) and the inequality becomes 2x + y ≥ 2x, obviously true. It is time for some difficult problems, which are all based on the observations from the beginning of the discussion. Example 4. Prove that there exists a constant c such that for any positive integers a, b, n that verify a! · b!|n! we have a + b < n + c lnn. Paul Erdos Solution. This time the other formula for vp(n!) is useful. Of course, there is no reasonable estimation of this constant, so we should better see what happens if a! · b!|n!. Then v2(a!) + v2(b!) ≤ v2(n!), which can be translated as a − s2(a) + b − s2(b) ≤ n − s2(n) < n. So, we have found almost exactly what we needed: a + b < n + s2(a) + s2(b). Now, we need another observation: the sum of digits of a number A when written in binary is at most the number of digits of A in base 2, which is 1 + [log2 A] (this follows from the fact that 2k−1 ≤ A < 2k, where 41 k is the number of digits of A in base 2). So, we have the estimations a + b < n + s2(a) + s2(b) ≤ n + 2 + log2 ab ≤ n + 2 + 2 log2 n (since we have of course a, b ≤ n). And now the conclusion is immediate. The following problem appeared in Kvant as a hard problem. It took quite a long time before an olympic found an extraordinary solution. We shall not present his solution; but another one, even easier. Example 5. Is there an infinite set of positive integers such that no matter how we choose some elements of this set, their sum is not an integer power of exponent at least 2? Kvant Solution. Let us take A = {2n · 3n+1|n ≥ 1} If we consider some different numbers from this set, their sum will be of the form 2x ·3x+1 ·y, where (y, 6) = 1. This is surely not a power of exponent at least 2, since otherwise the exponent should divide both x and x + 1. Thus this set is actually a good choice. The following problem shows the beauty of elementary number- theory. It combines diverse ideas and techniques and the result is at least beautiful. This one is also a classic problem, that appeared in lots of mathematics competitions. Example 6. Prove that for any natural number n, n! is a divisor of n−1∏ k=0 (2n − 2k). Solution. So, let us take a prime number p. Of course, for the ar- gument to be non-trivial, we take p ≤ n (otherwise doesn’t divide n!). First, let us see what happens with p = 2. We have v2(n!) = n− s2(n) ≤ n− 1 42 find that nk = 5, nk−1 = and a quick research of all possibilities shows that there are no solutions. Thus, the given equation has no solution in natural numbers. A tricky APMO problem asked once upon a time to prove there is a number 2 < n < 2000 such that n|2n + 2. We will let to the reader the job to verify that 2 · 11 · 43 is a solution (and especially the job to find how we arrived at this number) and also the exercise to prove that there are actually infinitely many such numbers. Yet... small verifications show that all such numbers are even. Proving this turns out to be a difficult problem and this was proved for the first time by Sierpinski. Note. After the quadratic reciprocity law topic, it will be proved that 2 11 43 is a solution of the problem. Example 8. Prove that for any n > 1 we cannot have n|2n−1 + 1. Solution. Although very short, the proof is tricky. Let n = s∏ i=1 pkii where p1 < · · · < ps are prime numbers. The idea is to look at v2(pi−1). Choose that pi which minimizes this quantity and write pi = 1 + 2rimi with mi odd. Then of course we have n ≡ 1 (mod 2mi). Hence we can write n − 1 = 2mt. We have 22mt ≡ −1 (mod pi) thus we surely have −1 ≡ 22mtmi ≡ 2(pi−1)t ≡ 1 (mod pi) (the last congruence being derived from Fermat’s theorem). Thus pi = 2, which is clearly impossible. We continue with a very nice and hard problem, in which the idea of looking at the exponents really saves us. This problem seemed to appear for the first time in AMM , proposed by Armond E. Spencer. In the last years, it appeared in various contests. Example 9. Prove that for any integers a1, a2, . . . , an the number∏ 1≤i<j≤n ai − aj i− j is an integer. Armond Spencer, AMM E 2637 45 Solution. This time, we consider a prime number p and we prove that for each k ≥ 1, there are more numbers divisible by pk in the se- quence of differences (ai−aj)1≤i<j≤n than in the sequence (i−j)1≤i<j≤n. Since vp  ∏ 1≤i<j≤n (ai − aj)  =∑ k≥1 Npk  ∏ 1≤i<j≤n (ai − aj)  (here Nx ∏ y∈A y  is the number of terms from the sequence A that are multiples of x) and vp  ∏ 1≤i<j≤n (i− j)  =∑ k≥1 Npk  ∏ 1≤i<j≤n (i− j)  , the problem will be solved if we prove our claim. Now, let us fix k ≥ 1 and let us suppose that there are exactly bi indices j ∈ {1, 2, . . . , n} such that aj ≡ i (mod pk), for each i ∈ {0, 1, . . . , pk − 1}. Then we have Npk  ∏ 1≤i<j≤n (ai − aj)  = pk−1∑ i=0 ( bi 2 ) . We see that if ai = i, then bi = [ n + i pk ] (there are [ n + i pk ] numbers congruent with i (mod p) between 1 and n; any of them is of the form i + jp, with 0 ≤ j ≤ n− i p , of course, if i = 0 we have 1 ≤ j ≤ n p ). So, Npk  ∏ 1≤i<j≤n (i− j)  = pk−1∑ i=0  [nipk ] 2  and it suffices to prove that pk−1∑ i=0 ( bi 2 ) ≥ pk−1∑ i=0  [nipk ] 2  . 46 Now, observe that we are practically asked to find the minimal value of pk−1∑ i=0 ( xi 2 ) , when pk−1∑ i=0 xi = n (it is clear that pk−1∑ i=0 bi = n = pk−1∑ i=0 [ ni pk ] from the definition of bi). For this, let us suppose that x1 ≤ x2 ≤ · · · ≤ xpk−1 is the n-tuple which attains the minimal value (such a n-tuple exists since the equation pk−1∑ i=0 xi = n has a finite number of solutions). If xpk−1 > x0 + 1, then we consider the n-tuple (x0 + 1, x1, . . . , xpk−2, xpk−1 − 1) which has the sum of the components n, but for which( x0 + 1 2 ) + ( x1 2 ) + · · ·+ ( xpk−2 2 ) + ( xpk−1 − 1 2 ) < ( x0 2 ) + ( x1 2 ) + · · ·+ ( xpk−2 2 ) + ( xpk−1 2 ) . The last inequality is true, since it is equivalent with xpk−1 > x0+1, so it is true. But this contradicts the minimality of (x0, x1, . . . , x2, . . . , xpk−1). So, we must have xpk−1 ≤ x0 + 1 and from here it follows that xi ∈ {x0, x0 + 1} for all i ∈ {0, 1, 2, . . . , pk − 1}. Thus, there is j ∈ {0, 1, 2, . . . , pk − 1} such that x0 = x1 = · · · = xj and xj+1 = xj+2 = · · · = xpk−1 = x0 + 1. This easily implies that the minimal n-tuple is in fact ([ n + i pk ]) i=0,pk−1 and the problem is solved. Finally, it is time for a challenge. Example 10. Let a, b two different positive rational numbers such that for infinitely many numbers n, an − bn is integer. Then prove that a, b are also integers. Gabriel Dospinescu, Mathlinks Contest Solution. Let us start by writing a = x z , b = y z , where x, y, z are different natural numbers relatively prime. We know thus that zn|xn−yn 47 After all, we have shown that in this case we must have m ≤ vp(Am −Bm) ≤ vp(Aj −Bj) + i. Using again the fact that A ≡ B (mod p), we infer that Aj−1 + Aj−2B + · · ·+ Bj−1 ≡ jAp−1 ≡ j (mod p), which shows that vp(Aj −Bj) = vp(A−B). Thus, for infinitely many numbers m we have m ≤ vp(A−B) + [log2 m], which is clearly impossible. Thus, we must have p|x and p|y, contradiction with the fact that x, y, z are relatively prime. This shows that z = 1 and a, b are integers. Problems for training 1. Prove the identity lcm(a, b, c)2 lcm(a, b) · lcm(b, c) · lcm(c, a) = gcd(a, b, c)2 gcd(a, b) · gcd(b, c) · gcd(c, a) for any positive integers a, b, c. USAMO, 1972 2. Let a, b, c, d be positive integers such that ab = cd. Prove that gcd(a, c) · gcd(a, d) = a · gcd(a, b, c, d). Polish Mathematical Olympiad 3. Let a1, a2, . . . , ak, b1, b2, . . . , bk be positive integers such that gcd(ai, bi) = 1 for all i ∈ {1, 2, . . . , k}. Let m− lcm[b1, b2, . . . , bk]. Prove that gcd ( a1m1 b1 , a2m2 b2 , . . . , akmk bk ) = gcd(a1, a2, . . . , ak). IMO Shortlist 1974 50 4. Let n such that 2n−2005|n!. Prove that this number has at most 2005 non-zero digits when written in base 2. 5. Prove that for any natural number n we have (n2)!( n n )( n + 1 n ) . . . ( 2n− 1 n ) n!n ∈ R. R.M Grassl, T. Porter, AMM E 3123 6. Prove the identity (n + 1)lcmk=0,n ( n k ) = lcm(1, 2, . . . , n + 1) for any positive integer n. Peter L Montgomery, AMM E 2686 7. Let 0 < a1 < · · · < an be integers. Find the maximal value of the number m for which we can find the integers 0 < b1 < · · · < bm such that n∑ k=1 2ak = m∑ k−1 bk and n∏ k=1 (2ak)! = m∏ k=1 bk!. Gabriel Dospinescu 8. Prove that the least common multiple of the numbers 1, 2, . . . , n equals the least common multiple of the numbers ( n 1 ) , ( n 2 ) , . . . , ( n n ) if and only if n + 1 is a prime. Laurentiu Panaitopol, TST 1990 Romania 9. Prove that for any n ∈ N we have n!(n + 1)!(n + 2)!|(3n)!. Komal 10. Prove that the product of the numbers between 21917 + 1 and 21991 − 1 is not a perfect square. Tournament of the Towns, 1991 11. Show that if n is a positive integer and a and b are integers, then n! divides a(a + b)(a + 2b) . . . (a + (n− 1)b)bn− 1. 51 IMO Shortlist, 1985 12. Prove that k!k 2+k+1 divides (k3)!. Poland Olympiad 13. Let x, y be relatively prime different natural numbers. Prove that for infinitely many primes p the exponent of p in xp−1 − yp−1 is odd. AMM 14. Let a1, . . . , an > 0 such that whenever k is a prime number of a power of a prime number, we have{a1 k } + · · ·+ {an k } < 1. Prove that there is a unique index i ∈ {1, 2, . . . , n} such that a1 + · · ·+ an < 1 + [ai]. 16. Find the exponent of 2 in the decomposition of the number( 2n+1 2n ) − ( 2n 2n−1 ) . AMM 17. Prove that (xn)n≥1 the exponent of 2 in the decomposition of the numerator of 2 1 + 22 2 + · · · + 2 n n , goes to infinity as n → ∞. Even more, prove that x2n ≥ 2n − n + 1 (hint: try to prove first the identity 2 1 + 22 2 + · · ·+ 2 n n = 2n n n−1∑ k=0 1( n− 1 k )). Adapted after a Kvant problem 18. Prove that the product of at most 25 consecutive integers is not a square. Narumi’s theorem 52 Proving that B is infinite is almost identical with the proof that there exist infinitely many primes. Indeed, suppose that p1, p2, . . . , pn are all the elements of B greater than 3 and consider the odd number N = 4p1p2 . . . pn + 3. Because N ≡ 3 (mod 4), N must have a prime factor that belongs to B. But since pi is not a divisor of N for any i = 1, n the contradiction is reached and thus B is infinite. In the same manner we can prove that A is infinite, but this time we must use the second question. Indeed, we consider this time the number M = (q1q2 . . . qm)2+ 1, where q1, q2, . . . , qm are all the elements of A and then simply apply the result from the second question. The conclusion is plain. It is not difficult to characterize the elements of the set C. A number is a sum of two squares if and only if any prime factor of it that also belongs to B appears at an even exponent in the decomposition of that number. The proof is just a consequence of the first examples and we will not insist. Having presented some basic results that we will use in this unit, it is time to see how many applications these two examples have. An easy consequence of the previous observations is the following. As a simple application of the first example, we consider the following problem, which is surely easy for someone who knows Fermat’s theorem regarding the elements of A and very difficult otherwise. Example 3. Find the number of integers x ∈ {−1997, . . . , 1997} for which 1997|x2 + (x + 1)2. India, 1998 Solution. We know that any congruence of the second degree re- duces to the congruence x2 ≡ a (mod p). So, let us proceed and reduce the given congruence to this special form. This is not difficult, since x2 +(x+1)2 ≡ 0 (mod 1997) is of course equivalent to 2x2 +2x+1 ≡ 0 (mod 1997), which in turn becomes (2x + 1)2 + 1 ≡ 0 (mod 1997). Since 1997 ∈ A, the congruence n2 ≡ −1 (mod 1997) surely has at 55 least a solution. More precisely, there are exactly two solutions that belong to {1, 2, . . . , 1996} because if n0 is a solution, so is 1997 − n0 and it is clear that it has at most two non-congruent solutions mod 1997. Because (2, 1997) = 1, the function x → 2x + 1 is a permutation of R1997 and so the initial congruence has exactly two solutions with x ∈ {1, 2, . . . , 1996}. In a similar way, we find that there are exactly two solutions with x ∈ {−1997,−1996, . . . ,−1}. Therefore there are exactly four numbers x ∈ {−1997, . . . , 1997} such that 1997|x2 + (x + 1)2. From a previous observation, we know that the condition that a number is a sum of two squares is quite restrictive. This suggests that the set X is quite RARA. This conclusion can be translated in the following nice problem. Example 4. Prove that C doesn’t have bounded gaps, that is there are arbitrarily long sequences of integers, no term of which can be written as the sum of two perfect squares. AMM Solution. The statement of the problem suggests using the Chinese Remainder Theorem, but here the main idea is to use the complete characterization of the set C, that we have just discussed: C = {n ∈ R| if p|n and p ∈ B, then vp(n) ∈ 2R}. Hence we know what we have to do. We will take long sequences of consecutive integers, each of them having a prime factor that belongs to B and has exponent 1. More precisely, we take different elements of B, let them p1, p2, . . . , pn (we can take as many as we need, since B is infinite) and then we look for a 56 solution of the system of congruences x ≡ p1 − 1 (mod p21) x ≡ p2 − 2 (mod p22) . . . x ≡ pn − n (mod p2n) The existence of such a solution follows from the Chinese Remainder Theorem. Thus, the numbers x+1, x+2, . . . , x+n cannot be written as the sum of two perfect squares, since pi|xi, but p2i does not divide x + i. Since n is as large as we want, the conclusion follows. The Diophantine equation x(x + 1)(x + 2) . . . (x + n) = yk has been extensively studied by many mathematicians and great results have been obtained. But these results are very difficult to prove and we prefer to present a related problem, with a nice flavor of elementary mathematics. Example 5. Prove that a set of p− 1 consecutive positive integers, where p ∈ B, cannot be partitioned into two subsets, each having the same product of the elements. Solution. Let us suppose that the positive integers x + 1, x + 2, . . . , x + p − 1 have been partitioned into two classes X, Y , each of them having the same product of the elements. If at least one of them is a multiple of p, then there must be another one divisible by p (since in this case both the products of elements from X and Y must be multi- ples of p), which is clearly impossible. Thus, none of these numbers is a multiple of p, which means that the set of remainders of these numbers when divided by p is exactly 1, 2, . . . , p− 1. Also, from the hypothesis it follows that there exists a positive integer n such that (x + 1)(x + 2) . . . (x + p− 1) = n2. Hence n2 ≡ 1 · 2(p − 1) ≡ −1 (mod p), the last congruence being true by Wilson’s theorem. But from the second example we know that 57 b) 2f(x2 + y2)− f(x)− f(y) ∈ {0, 1, . . . , n} for all integers x and y. For this n, find all the functions with the above properties. Solution. We will use all results proved in the beginning of the note. First, we will prove that for n = 1 there are functions which verify a) and b). We remind that A and B are the sets of all primes of the form 4k + 1 and 4k + 3, respectively. For any p ∈ B we define: fp : Z → Z, fp(x) = { 0, if p|x 1, otherwise Using properties of sets A and B, one can easily verify that fp verifies the restrictions of the problem. Hence fp is a solution of the problem for any p ∈ B. We will prove now that if f is non-constant and verifies the conditions of the problem, then n > 0. Suppose not. Then 2f(x2+y2) = f(x)+f(y) and hence 2f2(x) = 2f(x2 + 02) = f(x) + f(0). It is clear that we have f2(0) = f(0). Since f is non-constant, we must have f(0) = 0. Consequently, we must have 2f2(x) = f(x) for every integer x. But if there exists x such that f(x) = 1 2 , then f2(x2) 6= 2f(x2), contradiction. Thus, f(x) = 0 for any integer x and f is constant, contradiction. So, n = 1 is the smallest number for which there are non-constant functions which verify a) and b). We will prove now that any non-constant function f which verifies a) and b) must be of the form fp. We have already seen that f(0) = 0. Since f2(1) = f(1) and f is non-constant, we must have f(1) = 1. Also, 2f2(x)− f(x) = 2f(x2 + 02)− f(x)− f(0) ∈ {0, 1} for every integer x. Thus, f(x) ∈ {0, 1}. Since f2(−1) = f(1) = 1 and f(−1) ∈ [0,∞), we must have f(−1) = 1 and f(−x) = f(−1)f(x) = f(x) for any integer x. Then, since f(xy) = f(x)f(y), it is enough to find f(p) for any prime p. We prove that there is 60 exactly one prime number p for which f(p) = 0. Since f is non-constant, there exists a prime number p for which f(p) = 0. Suppose there is another prime q for which f(q) = 0. Then 2f(p2 + q2) ∈ {0, 1}, which means f(p2 + q2) = 0. Then for any integers a and b we must have: 0 = 2f(a2+b2)f(p2+q2) = 2f((ap+bq)2+(aq−bp)2). Since 0 ≤ f(x)+f(y) ≤ 2f(x2 + y2) for any x and y, we must have f(ap + bq) = f(aq− bp) = 0. Since p and q are relatively prime, there are integers a and b such that aq− bp = 1. Then we have 1 = f(1) = f(aq− bp) = 0, contradiction. So ,there is exactly one prime number p for which f(p) = 0. Let us suppose that p = 2. Then f(x) = 0 for any even x and 2f(x2+y2) = 0 for any odd numbers x and y. This implies that f(x) = f(y) = 0 for any odd numbers x and y and thus f is constant, contradiction. Therefore p ∈ A ∪ B. Suppose p ∈ A. According to proposition 2, there are positive integers a and b such that p = a2 + b2. Then we must have f(a) = f(b) = 0. But max{a, b} > 1 and there is a prime number q such that q|max{a, b} and f(q) = 0 (otherwise, we would have f(max{a, b} = 1). But it is clear that q < p and thus we have found two distinct primes p and q such that f(p) = f(q) = 0, which, as we have already seen, is impossible. Consequently, p ∈ B and we have f(x) = 0 for any x divisible by p and f(x) = 1 for any x which is not divisible by p. Hence, f must be fp and the conclusion follows. Problems for training 1. Prove that if p ∈ A, then it can be represented in exactly one way as the sum of the squares of two integers, except for the order of the terms. 2. Prove that a positive integer can be written as the sum of two perfect squares if and only if it can be written as the sum of the squares of two rational numbers. 61 Euler 3. Find all positive integers n with the property that the equation n = x2 + y2, where 0 ≤ x ≤ y and (x, y) = 1 has exactly one solution. 4. Here is another proof of the theorem from example 1. Suppose that p = 4k + 1 ∈ A and let x, y ∈ Z such that max{|x|, |y|} < p 2 and 2xε ( 2k k ) (mod p), y ≡ (2k)!x (mod p). Prove that p = x2 + y2. Gauss 5. Find all pairs of positive integers (m,n) such that m2 − 1|3m + (n!− 1)m. Gabriel Dospinescu 6. The positive integers a, b have the property that the numbers 15a + 16b and 16a − 15b are both perfect squares. What is the least possible value that can be taken on by the smallest of the two squares? IMO CE AN? 7. Prove that the number 4mn−m− n cannot be a perfect square if m,n are positive integers. IMO 1984 Shortlist 8. Find all n-tuples of positive integers (a1, a2, . . . , an) such that (a1!− 1)(a2!− 1) . . . (an!− 1)− 16 is a perfect square. Gabriel Dospinescu 9. Find all pairs of positive integers (x, y) such that the number x2 + y2 x− y is a divisor of 1995. Bulgaria, 1995 62 T2’S LEMMA T2’s lemma is clearly a direct application of the Cauchy-Schwarz in- equality. Some will say that it is actually the Cauchy-Schwarz inequality and they are not wrong. Anyway, this particular lemma has become very popular among the American students who attended the training of the USA IMO team. This happened after a lecture delivered by the first author at the Mathematical Olympiad Summer Program (MOSP) held at Georgetown University in June, 2001. But what exactly does this lemma say? It says that for any real numbers a1, a2, . . . , an and any positive real numbers x1, x2, . . . , xn the inequality a21 x1 + a22 x2 + · · ·+ a 2 n xn ≥ (a1 + a2 + · · ·+ an) 2 x1 + x2 + · · ·+ xn (1) holds. And now we see why calling it also the Cauchy-Schwarz inequality is natural, since it is practically an equivalent form of this inequality:( a21 x1 + a22 x2 + · · ·+ a 2 n xn ) (x1 + x2 + · · ·+ xn) ≥ √a21 x1 · √ x1 + √ a22 x2 · √ x2 + · · ·+ √ a2n xn · √ xn 2 . But there is another nice proof of (1), by induction. The inductive step is reduced practically to the case n = 2, which is immediate. Indeed, it boils down to (a1x2 − a2x1)2 ≥ 0 and the equality occurs if and only if a1 x1 = a2 x2 . Applying this result twice it follows that a21 x1 + a22 x2 + a23 x3 ≥ (a1 + a2) 2 x1 + x2 + a23 x3 ≥ (a1 + a2 + a3) 2 x1 + x2 + x3 and we see that a simple inductive argument finishes the proof. With this brief introduction, let us discuss some problems. And there are plenty 65 of them given in mathematical contests or proposed in mathematical magazines! First, an old problem, that became classical. We will see that with T2’s lemma it becomes straightforward and even more, we will obtain a refinement of the inequality. Example 1. Prove that for any positive real numbers a, b, c a3 a2 + ab + b2 + b3 b2 + bc + c2 + c3 c2 + ca + a2 ≥ a + b + c 3 . Tournament of the Towns, 1998 Solution. We will change the left-hand side of the inequality so that we could apply T2’s lemma. This is not difficult: we just have to write it in the form a4 a(a2 + ab + b2) + b4 b(b2 + bc + c2) + c4 c(c2 + ca + a2) . It follows that the left-hand side is greater than or equal to (a2 + b2 + c2)2 a3 + b3 + c3 + ab(a + b) + bc(b + c) + ca(c + a) But we can easily observe that a3 + b3 + c3 + ab(a + b) + bc(b + c) + ca(c + a) = (a + b + c)(a2 + b2 + c2), so we have proved an even stronger inequality, that is a3 a2 + ab + b2 + b3 b2 + bc + c2 + c3 c2 + ca + a2 ≥ a 2 + b2 + c2 a + b + c . The second example also became representative for a whole class of problems. There are countless examples of this type in numerous contests and mathematical magazines, so we find it necessary to discuss it at this point. 66 Example 2. For arbitrary positive real numbers a, b, c, d prove the inequality a b + 2c + 3d + b c + 2d + 3a + c d + 2a + 3b + d a + 2b + 3c ≥ 2 3 . Titu Andreescu, IMO 1993 Shortlist Solution. If we write the left-hand side in the form a2 a(b + 2c + 3d) + b2 b(c + 2d + 3a) + c2 c(d + 2a + 3b) + d2 d(a + 2b + 3c) , then the way to continue is clear, since from the lemma we obtain a b + 2c + 3d + b c + 2d + 3a + c d + 2a + 3b + d a + 2b + 3c ≥ (a + b + c + d) 2 4(ab + bc + cd + da + ac + bd) . Hence it suffices to prove the inequality 3(a + b + c + d)2 ≥ 8(ab + bc + cd + da + ac + bd). But it is not difficult to see that (a + b + c + d)2 = a2 + b2 + c2 + d2 + 2(ab + bc + cd + da + ac + bd), implies 8(ab + bc + cd + da + ac + bd) = 4(a + b + c + d)2 − 4(a2 + b2 + c2 + d2). Consequently, we are left with the inequality 4(a2 + b2 + c2 + d2) ≥ (a + b + c + d)2, which is just the Cauchy-Schwarz inequality for four variables. The problem below, given at the IMO 1995, was discussed exten- sively in many publications. It could be also solved by using the above lemma. 67 this lemma), but it is false for all even numbers n ≥ 14 as well as for sufficiently large odd numbers n. Let us examine the case n = 5, a problem proposed for MOSP 2001. Example 5. Prove that for any positive real numbers a1, a2, a3, a4, a5, a1 a2 + a3 + a2 a3 + a4 + a3 a4 + a5 + a4 a5 + a1 + a5 a1 + a2 ≥ 5 2 . Solution. Again, we apply the lemma and we conclude that it suf- fices to prove the inequality (a1 + a2 + a3 + a4 + a5)2 ≥ 5 2 [a1(a2 + a3) + a2(a3 + a4) + a3(a4 + a5) + a4(a5 + a1) + a5(a1 + a2)] Let us denote a1 + a2 + a3 + a4 + a5 = S. Then we observe that a1(a2 + a3) + a2(a3 + a4) + a3(a4 + a5) + a4(a + 5 + a1) + a5(a1 + a2) = a1(S − a1) + a2(S − a2) + a3(S − a3) + a4(S − a4) + a5(S − a5) 2 = S2 − a21 − a22 − a23 − a24 − a25 2 . With this identity, we infer that the intermediate inequality is in fact (a1 + a2 + a3 + a4 + a5)2 ≥ 5 4 (S2 − a21 − a22 − a23 − a24 − a25), equivalent to 5(a21 + a 2 2 + a 2 3 + a 2 4 + a 2 5) ≥ S2, which is nothing else then the Cauchy-Schwarz inequality. Another question arises: is there a positive real number such that for any positive real numbers a1, a2, . . . , an and any n ≥ 3 the following inequality holds: a1 a2 + a3 + a2 a3 + a4 + · · ·+ an a1 + a2 ≥ cn. This time, the answer is positive, but finding the best such constant is an extremely difficult task. It was first solved by Drinfield (who, by the way, is a Fields’ medalist). The answer is quite complicated and we 70 will not discuss it here (for a detailed presentation of Drinfield’s method the interested reader can consult the written examination given at ENS in 1997). The following problem, given at the Moldavian TST in 2005, shows that c = √ 2− 1 is such a constant (not optimal). For any a1, a2, . . . , an and any n ≥ 3 the following inequality holds: a1 a2 + a3 + a2 a3 + a4 + · · ·+ an a1 + a2 ≥ ( √ 2− 1)n. The proof is completely elementary, yet very difficult to find. An in- genious argument using the arithmetic-geometric means inequality does the job: let us write the inequality in the form a1 + a2 + a3 a2 + a3 + a2 + a3 + a4 a3 + a4 + · · ·+ an + a1 + a2 a1 + a2 ≥ √ 2 · n. Now, using the AM-GM inequality, we see that it suffices to prove the stronger inequality: a1 + a2 + a3 a2 + a3 · a2 + a3 + a4 a3 + a4 . . . an + a1 + a2 a1 + a2 ≥ ( √ 2)n. Observe that (ai + ai+1 + ai+2)2 = ( ai + ai+1 2 + ai+1 2 + ai+2 )2 ≥ 4 ( ai + ai+1 2 )(ai+1 2 + ai+2 ) (the last inequality being again a consequence of the AM-GM inequal- ity). Thus, n∏ i=1 (ai + ai+1 + ai+2)2 ≥ n∏ i=1 (2ai + ai+1) n∏ i=1 (2ai+2 + ai+1). Now, the real trick is to rewrite appropriately the last products. Let us observe that n∏ i=1 (2ai+2 + ai+1) = n∏ i=1 (2ai+1 + ai), 71 so n∏ i=1 (2ai + ai+1) n∏ i=1 (2ai+2 + ai+1) = n∏ i=1 [(2ai + ai+1)(ai + 2ai+1)] ≥ n∏ i=1 (2(ai + ai+1)2) = 2n ( n∏ i=1 (ai + ai+1) )2 . The conclusion now follows. This lemma came handy even at the IMO 2005 (problem 3). In order to prove that for any positive real numbers x, y, z such that xyz ≥ 1 the following inequality holds∑ x2 + y2 + z2 x5 + y2 + z2 ≤ 3, a few students successfully used the above mentioned lemma. For exam- ple, a student from Ireland applied this result and called it ”SQ Lemma”. During the coordination, the Irish deputy leader explained what ”SQ” stood for: ”...escu”. A typical solution using this lemma is as follows: x5 + y2 + z2 = x4 1 x + y4 y2 + z4 z2 ≥ (x 2 + y2 + z2)2 1 x + y2 + z2 , hence ∑ x2 + y2 + z2 x5 + y2 + z2 ≤ ∑ 1 x + y2 + z2 x2 + y2 + z2 = 2 + xy + yz + zx xyz(x2 + y2 + z2) ≤ 3. It is now time for the champions. We begin with a difficult geometric inequality for which we have found a direct solution using T2’s lemma. Here it is. Example 6. Prove that in any triangle ABC the following inequality holds rarb mamb + rbrc mbmc + rcra mcma ≥ 3. Ji Chen, Crux Mathematicorum 72 we have to prove that for any positive real numbers x, y, z satisfying xyz = x + y + z + 2, the inequality (x− 1)2 x2 + 1 + (y − 1)2 y2 + 1 + (z − 1)2 z2 + 1 ≥ 3 5 holds. It is now time to use T2’s lemma in the form (x− 1)2 x2 + 1 + (y − 1)2 y2 + 1 + (z − 1)2 z2 + 1 ≥ (x + y + z − 3) 2 x2 + y2 + z2 + 3 . Hence it is enough to prove the inequality (x + y + z − 3)2 x2 + y2 + z2 + 3 ≥ 3 5 . But this is equivalent to (x + y + z)2 − 15(x + y + z) + 3(xy + yz + zx) + 18 ≥ 0. This is not an easy inequality. We will use the proposed problem 3 from the unit ”Two useful substitutions” to reduce the above inequality to the form (x + y + z)2 − 9(x + y + z) + 18 ≥ 0, which follows from the inequality x + y + z ≥ 6. And the problem is solved. But here is another original solution. Alternative solution. Let us apply T2’s lemma in the following form: (b + c− a)2 a2 + (b + c)2 + (c + a− b)2 b2 + (c + a)2 + (a + b− c)2 c2 + (a + b)2 = ((b + c)2 − a(b + c))2 a2(b + c)2 + (b + c)4 + ((c + a)2 − b(c + a))2 b2(c + a)2 + (c + a)4 + ((a + b)2 − c(a + b))2 c2(a + b)2 + (a + b)4 ≥ 4(a 2 + b2 + c2)2 a2(b + c)2 + b2(c + a)2 + c2(a + b)2 + (a + b)4 + (b + c)4 + (c + a)4 . 75 Consequently, it suffices to prove that the last quantity is greater than or equal to 3 5 . This can be done by expanding everything, but here is an elegant proof using the observation that a2(b + c)2 + b2(c + a)2 + c2(a + b)2 + (a + b)4 + (b + c)4 + (c + a)4 = [(a + b)2 + (b + c)2 + (c + a)2](a2 + b2 + c2) +2ab(a + b)2 + 2bc(b + c)2 + 2ca(c + a)2. Because (a + b)2 + (b + c)2 + (c + a)2 ≤ 4(a2 + b2 + c2), we observe that the desired inequality reduces to 2ab(a + b)2 + 2bc(b + c)2 + 2ca(c + a)2 ≤ 8 3 (a2 + b2 + c2)2. But this inequality is not so difficult. Indeed, first we observe that 2ab(a + b)2 + 2bc(b + c)2 + 2ca(c + a)2 ≤ 4ab(a2 + b2) + 4bc(b2 + c2) + 4ca(c2 + a2). Then, we also find that 4ab(a2 + b2) ≤ a4 + b4 + 6a2b2, since (a− b)4 ≥ 0. Hence 4ab(a2 + b2) + 4bc(b2 + c2) + 4ca(c2 + a2) ≤ 2(a2 + b2 + c2)2 +2(a2b2 + b2c2 + c2a2) ≤ 8 3 (a2 + b2 + c2)2 and so the problem is solved. With minor changes, we can readily see that this solution works without the assumption that a, b, c are positive. We end this discussion (which remains probably permanently open) with a difficult problem, based on two hidden applications of T2’s lemma. 76 Example 8. Let a1, a2, . . . , an > 0 such that a1 + a2 + · · ·+ an = 1. Prove that: (a1a2+a2a3+· · ·+ana1) ( a1 a22 + a2 + a2 a23 + a3 + · · ·+ an a21 + a1 ) ≥ n n + 1 . Gabriel Dospinescu Solution. How can we get to a1a2 + a2a3 + · · · + ana1? Probably from a21 a1a2 + a22 a2a3 + · · · + a 2 n ana1 after we use the lemma. So, let us try this the following estimation: a1 a2 + a2 a3 +· · ·+an a1 = a21 a1a2 + a22 a2a3 +· · ·+ a 2 n ana1 ≥ 1 a1a2 + a2a3 + · · ·+ ana1 . The new problem, proving that a1 a22 + a2 + a2 a23 + a3 + · · ·+ an a21 + a1 ≥ n n + 1 ( a1 a2 + a2 a3 + · · ·+ an a1 ) seems even more difficult, but we will see that we have to make one more step in order to solve it. Again , we look at the right-hand side and we write a1 a2 + a2 a3 + · · ·+ an a1 as ( a1 a2 + a2 a3 + · · ·+ an a1 )2 a1 a2 + a2 a3 + · · ·+ an a1 . After applying T2’s lemma, we find that a1 a22 + a2 + a2 a23 + a3 + · · ·+ an a21 + a1 = ( a1 a2 )2 a1 + a1 a2 + ( a2 a3 )2 a2 + a2 a3 + · · ·+ ( an a1 )2 an + an a1 ≥ ( a1 a2 + a2 a3 + · · ·+ an a1 )2 1 + a1 a2 + a2 a3 + · · ·+ an a1 . 77 12. Let n ≥ 4 an integer and let a1, a2, . . . , an be positive real num- bers such that a21 + a 2 2 + · · ·+ a2n = 1. Prove that a1 a22 + 1 + a2 a23 + 1 + · · ·+ an a21 + 1 ≥ 4 5 (a1 √ a1 + a2 √ a2 + · · ·+ an √ an)2. Mircea Becheanu, Bogdan Enescu, TST 2002, Romania 13. Find the best constant k(n) such that for any positive real numbers a1, a2, . . . , an satisfying a1a2 . . . an = 1 the following inequality holds a1a2 (a21 + a2)(a 2 2 + a1) + a2a3 (a22 + a3)(a 2 3 + a2) + · · ·+ ana1 (a2n + a1)(a21 + a2) ≤ kn. Gabriel Dospinescu, Mircea Lascu 14. Prove that for any positive real numbers a, b, c, (2a + b + c)2 2a2 + (b + c)2 + (2b + c + a)2 2b2 + (c + a)2 + (2c + a + b)2 2c2 + (a + b)2 ≤ 8. Titu Andreescu, Zuming Feng, USAMO 2003 80 ONLY GRAPHS, NO SUBGRAPHS! There were so many strategies and useful ideas till now, that the reader might say: enough with this game of tricks! When shall we go to serious facts? Not only that we will ”dissapoint” him again, but we will try also to convince him that these are more than simple tools and tricks. They help to create a good base, which is absolutely indispensable for someone who enjoys mathematics and moreover, they are the first step to some really beautiful and difficult theorems or problems. And the reader must admit that the last problems discussed in the previous units are quite serious facts. It is worth mentioning that they are not panacea. This assertion is proved by the fact that each year problems that are based on well-known ”tricks” prove to be very difficult in contests. We will focus in this unit on a very familiar theme: graphs without complete subgraphs. Why do we say familiar? Because there are hun- dreds of problems proposed to different contests around the world and in mathematical magazines that deal with this subject and each one seems to add something. Before passing to the first problem, we will assume that the basic knowledge about graphs is known and we will denote by d(A) and C(A) the number, respectively the set of vertices adjacent to A. Also, we will say that a graph does not have a complete k subgraph if there aren’t k vertices any two of them connected. For simplicity, we will say that G is k-free. First, we will discuss probably the first classical result about triangles-free graphs, the famous Turan’ theorem. But be- fore that, an useful lemma, which is also known as Zarankiewicz lemma and which is the main idea in Turan’ theorem’ proof. Example 1. If G is a k-free graph, then there exists a vertex having degree at most [ k − 2 k − 1 n ] . Zarankiewicz 81 Solution. Suppose not and take an arbitrary vertex A1. Then |C(A1)| > [ k − 2 k − 1 n ] , so there exists A2 ∈ C(A1). Moreover, |C(A1) ∩ C(A2)| = d(A1) + d(A2)− |C(A1 ∪A2)| ≥ 2 ( 1 + [ k − 2 k − 1 n ]) − n > 0. Pick a vertex A3 ∈ C(A1) ∩ C(A2). A similar argument shows that |C(A1) ∩ C(A2) ∩ C(A3)| ≥ 3 ( 1 + [ k − 2 k − 1 n ]) − 2n. Repeating this argument, we find A4 ∈ C(A1) ∩ C(A2) ∩ C(A3), . . . , Ak−1 ∈ k−2⋂ i=1 C(Ai). Also, we have∣∣∣∣∣ j⋂ i=1 C(Ai) ∣∣∣∣∣ ≥ j ( 1 + [ k − 2 k − 1 n ]) − (j − 1)n. This can be proved easily by induction. Thus,∣∣∣∣∣ k−1⋂ i=1 C(Ai) ∣∣∣∣∣ ≥ (k − 1) ( 1 + [ k − 2 k − 1 n ]) − (k − 2)n > 0 and consequently we can choose Ak ∈ k−1⋂ i=1 C(Ai). But it is clear that A1, A2, . . . , Ak form a complete k graph, which contradicts the assumption that G is k-free. We are now ready to prove Turan’ theorem. Example 2. The maximal number of edges of a k-free graph with vertices is k − 2 2 · n 2 − r2 k − 1 + ( r 2 ) , 82 maximizes the number of edges in a k-free graph. Yet, the reversed form of a reversed form is the natural one. In the aim of this principle, let us look at the ”reversed” graph, the complementary one. We must show that it has at most ( 21 2 ) −100 = 110 edges. But this is immediate, since it is clear that this new graph does not have triangles and so, by Turan’ theorem it has at most 212 − 1 4 = 110 edges. And the problem is solved. At first glance, the following problem seem to have no relation with the previously examples, but, as we will see, it is a simple consequence of Zarankiewicz’ lemma. This problem is an adaptation of a USAMO 1978 problem. Anyway, this is trickier than the contest problem. Example 5. There are n delegates at a conference, each of them knowing at most k languages. Anyway, among any three delegates, at least two speak a common language. Find the smallest number n (in terms of k) such that it is always possible to find a language spoken by at least three delegates. Solution. We will prove that n = 2k + 3. First, we prove that if there are 2k + 3 delegates,then the conclusion of the problem holds. The condition ”among any three of them there are at least two who can communicate” suggests us to take the 3-free graph with vertices in the persons and whose edges join persons that cannot communicate. From Zarankiewicz’ lemma, there exists a vertex whose degree is at most[n 2 ] = k +1. Thus, it is not connected with at least k +1 other vertices. Therefore, there exists a person A and k + 1 persons A1, A2, . . . , Ak+1 that can communicate with A. Since A knows at most k languages, there are two persons among A1, A2, . . . , Ap that know a language also known by A. But that language is known by at least three delegates and we are done. It remains to prove now that we can create a situation in which there are 2k + 2 delegates, but no language is known by more than two delegates. We use again Turan’ graph, by creating two groups of k + 1 85 delegates. In each group a person will have a common language with each other person from the group and will not have common languages with the members of the other group. Of course, any language is spoken by at most two delegates and there are no triangles. The following problem turned out to be a surprise at one of the Team Selection Tests for 2004 IMO, being solved by 4 contestants. The idea is even easier than in the previous problems, but this time we need a little observation, that is not so obvious. Example 6. Let A1, A2, . . . , A101 be different subsets of the set {1, 2, . . . , n}. Suppose that the union of any 50 subsets has more than 50 51 n elements. Prove that there are three subsets among them, any two of them having common elements. Gabriel Dospinescu, TST 2004 Romania Solution. Of course, as the conclusion suggests, we should take a graph with vertices in the subsets, connecting two subsets if they have common elements. Let us assume that this graph is 3-free. The main idea is not to use Zarankiewicz’ lemma, but to find much more vertices with small degrees. In fact, we will prove that there are at least 51 vertices whose degree are smaller than or equal to 50. Suppose this is not the case, thus there are at least 51 vertices whose degrees are greater than 51. Let us pick such a vertex A. It is connected with at least 51 vertices, thus it must be adjacent to a vertex B, whose degree is at least 51. Since A and B are each connected with at least 51 vertices, there is a vertex adjacent to both, so we have a triangle, contradicting our assumption. Therefore, we can find Ai1 , . . . , Ai51 , all of them having degrees at most 50. Consequently, Ai1 is disjoint from at least 50 subsets. Since the union of these subsets has more than 50 51 n elements, we infer that |Ai1 | < n− 50 51 n = n 51 . In a similar way, we obtain that |Aij | ≤ n 51 86 for all j ∈ {1, 2, . . . , 51} and so |Ai1 ∪Ai2 ∪ · · · ∪Ai50 | ≤ |Ai1 |+ · · ·+ |Ai50 | < 50 51 n, which contradicts the hypothesis. And the solution ends here. We end the discussion with an adaptation of a very nice and quite challenging problem from the American Mathematical Monthly. Example 7. Prove that the complementary of any 3-free graph with n vertices and m edges has at least n(n− 1)(n− 5) 24 + 2 n ( m− n 2 − n 4 )2 triangles. A.W Goodman, AMM Solution. Believe it or not, the number of triangles from the com- plementary graph can be expressed only in terms of the degrees of the vertices of the graph. More precisely, if G is the graph, then the number of triangles from the complementary graph is( n 3 ) − 1 2 ∑ x∈X d(x)(n− 1− d(x)), where X is the set of vertices of G. Indeed, consider all triples (x, y, z) of vertices of G. We will count the triples that do not form a triangle in the complementary graph G. Indeed, consider the sum ∑ x∈X d(x)(n−1−d(x)). It counts twice every triple (x, y, z) in which are connected, while z is not adjacent to any of x, y: once for x and once for y. But it also counts twice every triple (x, y, z) in which y is connected with both x, z: once for x and once for z. Therefore, 1 2 ∑ x∈X d(x)(n− 1− d(x)) is exactly the number of triples (x, y, z) that do not form a triangle in the complementary graph (here we have used the fact that G is 3-free). Now, it is enough to prove 87 COMPLEX COMBINATORICS When reading the title, one will surely expect a hard unit, which will show what a complex field is combinatorics. Unfortunately, this was not our intention. We ”just” want to discuss some combinatorial problems that can be solved elegantly using complex numbers. In this moment, the reader will probably say we are crazy, but we will continue our idea and say that complex numbers can play a very important role in counting problems and also in problems related to tilings. There are also numerous applications in combinatorial number theory, so our purpose is to present a little bit from each of these situations. After that, the reader will surely have the pleasure of solving the proposed problems using this technique. For fear of useless repetition, we will present in the beginning of the discussion a useful result Lemma. If p is a prime number and a0, a1, . . . , ap−1 ∈ Q satisfy the relation a0 + a1ε + a2ε2 + · · ·+ ap−1εp−1 = 0, where ε = cos 2π p + i sin 2π p , then a0 = a1 = · · · = ap−1. We will say just a few words about the proof, which is not difficult. It is enough to observe that the polynomials a0+a1x+a2x2+· · ·+ap−1xp−1 and 1+x+x2 + · · ·+xp−1 cannot be relatively prime-because they share a common root-and since 1 + x + x2 + · · ·+ xp−1 is irreducible over Q, 1 + x + x2 + · · · + xp−1 must divide a0 + a1x + a2x2 + · · · + ap−1xp−1, which can only happen if a0 = a1 = · · · = ap−1. Therefore, the lemma is proved and it is time to solve some nice problems. Not before saying that in the following examples m(A) will denote the sum of the elements of the set A. By convention m(∅) = 0. 90 The first example is an adaptation from a problem given in the Inter- County Contest ”Traian Lalescu”. Of course, there is a solution using recurrent sequences, but it is by far less elegant than the following one. Example 1. How many numbers with n digits, all equal to 1, 3, 4, 6, 7, 9 are divisible by 7? Solution. Let a(k)n be the number of n-digits numbers, formed using only the digits 1, 3, 4, 6, 7, 9 and which are congruent to k modulo 7. It is clear that 6∑ k=0 a(k)n ε k = ∑ x1,x2,...,xn∈{1,3,4,6,7,9} εx1+x2+···+xn = (ε + ε3 + ε4 + ε6 + ε7 + ε9)n, where ε = cos 2π 7 + i sin 2π 7 . The remark that 1 + ε + ε2 + · · ·+ ε6 = 0 helps us to bring (ε+ε3 +ε4 +ε6 +ε7 +ε9)n to the simpler form (−ε5)n. Let us assume that n is divisible by 7, for example (the other cases can be discussed similarly). Then 6∑ k=0 a(k)n ε k = (−1)n and from the lemma we infer that a(0)n − (−1)n = a(1)n = · · · = a(6)n . Let k be the common value. Then 7k = 6∑ k=0 a(k)n − (−1)n = 6n− (−1)n - this is because exactly 6n numbers have n digits, all equal to 1, 3, 4, 6, 7, 9. Thus, in this case we have a(0)n = (−1)n + 6n − (−1)n 7 . We leave to the reader the study of the other cases: n ≡ 12, 3, 4, 5, 6 (mod 7). The same simple, but tricky idea can offer probably the most beau- tiful solution for the difficult IMO 1995 problem 6. It worth saying that Nikolai Nikolov won a special prize for the following magnificent solu- tion. 91 Example 2. Let p > 2 be a prime number and A = {1, 2, . . . , 2p}. Find the number of subsets of A, each having p elements and the sum of the elements divisible by p. Marcin Kuczma, IMO 1995 Solution. Consider ε = cos 2π p + i sin 2π p and let xj the number of subsets x ⊂ A such that |X| = p and m(X) ≡ j (mod p). Then it is clear that p−1∑ j=0 xjε j = ∑ B⊂A,|B|=p εm(B) = ∑ 1≤c1<c2<···<cp≤2p εc1+c2+···+cp . But ∑ 1≤c1<c2<···<cp≤2p εc1+c2+···+cp is exactly the coefficient of xp in the expansion (X + ε)(X + ε2) . . . (X + ε2p). Since Xp − 1 = (X − 1)(X − ε) . . . (X − εp−1), we easily find that (X + ε)(X + ε2) . . . (X + ε2p) = (Xp + 1)2. Thus, p−1∑ j=0 xjε j = 2 and lemma implies the equality x0−2 = x1 = · · · = xp−1. Since there are ( 2p p ) subsets with p elements, we have x0 + x1 + · · ·+ xp−1 = ( 2p p ) . Therefore, x0 = 2 + 1 p (( 2p p ) − 2 ) . With a somewhat different, but closely related idea we can solve the following nice problem. Example 3. Let a1, a2, . . . , am be natural numbers and let f(k) the number of m-tuples (c1, c2, . . . , cm) such that 1 ≤ ci ≤ ai, i = 1,m and c1 + c2 + · · ·+ cm ≡ k (mod n), where n > 1 is a natural number. Prove that f(0) = f(1) = · · · = f(n − 1) if and only if there exists an index i ∈ {1, 2, . . . ,m} such that n|ai. Reid Burton, Rookie Contest ,1999 92 From the lemma, it follows that x0 − rc0 = x1 − rc1 = · · · = xp−1 − rcp−1 = k. Because clearly c0, c1, . . . , cp−1 ∈ R, it remains to prove that r|k. Since pk = x0 + x1 + · · ·+ xp−1 − r(c0 + c1 + · · ·+ cp−1) = (1 + 2 + · · ·+ n)m − r(b0 + b1 + · · ·+ bm(p−2)) = ( n(n + 1) 2 )m − r ( p(p− 1) 2 )m , it is clear that r|k. Here we have used the hypothesis. The problem is solved. It is time now to leave this kind of problems and to speak a little bit about some nice applications of complex numbers in tilings. The idea is to put a complex number in each square of a table and then to translate the hypothesis and the conclusion in terms of complex numbers. But we will better see how this technique works by solving a few problems. First, some easy problems. Example 5. Consider a rectangle which can be tiled with a finite combination of 1×m or n×1 rectangles, where m,n are natural numbers. Prove that it is possible to tile this rectangle using only rectangles 1×m or only with rectangles n× 1. Gabriel Carrol ,BMC Contest,2000 Solution. It is obvious that the rectangle has natural dimensions, let them be a, b. Now, let us partition the rectangle into 1 × 1 squares and denote this squares (1, 1), (1, 2), . . . , (a, 1), . . . , (a, 1), (a, 2), . . . , (a, b). Next, put the number εi1ε j 2 in the square whose label is (i, j), where ε1 = cos 2π n + i sin 2π n , ε2 = cos 2π m + i sin 2π m . 95 The main observation is that the sum of the numbers in any 1×m or n × 1 rectangle is 0. This is immediate, but the consequence of this simple observation is really surprising. Indeed, it follows that the sum of the numbers from all the squares is 0 and so 0 = ∑ 1≤i≤a 1≤j≤b εi1ε j 2 = a∑ i=1 εi1 b∑ j=1 εj2. Thus, at least one of the numbers a∑ i=1 εi1 and b∑ j−1 εj2 is 0. But this means that n|a or m|b. In any of these cases, it is clear that we can tile the rectangle using only horizontal or vertical rectangles. The idea in the previous problem is quite useful, many tilings prob- lems having straightforward solutions by using it. An example is the following problem, given in Baltic Contest in 1998. Example 6. Can we tile a 13 × 13 table using only 1 × 4, 4 × 1 rectangles, such that only the center of the table does not belong to any rectangle? Baltic Contest,1998 Solution. Suppose such a tiling is possible and label the squares of the table as in the previous problem. Next, associate to square (k, j) the number ik+2j . Obviously, the sum of the numbers from each 1× 4, 4× 1 rectangle is 0. Therefore, the sum of all numbers from the squares of the table is equal to the number in the square situated at the center of the table. Thus, i21 = (i + i2 + · · ·+ i13)(i2 + i4 + · · ·+ i26) = i · i 13 − 1 i− 1 · i2 · i 26 − 1 i2 − 1 = i3, which clearly cannot hold. Thus, the assumption was wrong and such a tiling does not exist. 96 The following example we are going to discuss is based on the same idea, but here complex numbers are more involved. Example 7. On a 8 × 9 table we put rectangles 3 × 1 and figures formed by rectangles 1 × 3 by cutting the median 1 × 1 square. The rectangles and the figures do not intersect and cannot be rotated. Prove that there exists a set S of 18 squares of the table such that if there are exactly two uncovered squares, then they belong to S. Gabriel Dospinescu Solution. Again, we label the squares of the table (1, 1), (1, 2), . . . , (8, 9) by starting from the up-left corner. In the square labeled (k, j) we will put the number ij ·εk, where i2 = −1 and ε2 +ε+1 = 0. The sum of the numbers from any figure or rectangle is 0. The sum of the numbers from the table is ( 8∑ k=1 εk ) 9∑ j=1 ij  = −i. Let us suppose that the squares (a1, b1), (a2, b2) are the only un- covered squares. Then we have of course ib1εa1 + ib2εa2 = −i. Let z1 = ib1−1εa1 , z2 = ib2−1εa2 . We have |z1| = |z2| = 1 and z1 + z2 = −1. It follows that 1 z1 + 1 z2 = −1 and so z31 = z32 = 1. This in turn im- plies the equalities i3(b1−1) = i3(b2−1) = 1, from where we conclude that b1 ≡ b2 ≡ 1 (mod 4). Therefore, the relation z1 + z2 = −1 becomes εa1 + εa2 = −1, which is possible if and only if the remainders of the numbers a1, a2 when divided by 3 are 1 and 2. Thus, we can take S the set of squares that lie at the intersection of the lines 1, 2, 4, 5, 7, 8 with the columns 1, 5, 9. From the above argument, if two squares remain uncovered, then surely they belong to S. The conclusion is immediate. 97