# IMO 2005 ShortList Problems and Solutions

Algebra

1

Algebra
A1. Find all monic integer polynomials p(x) of degree two for which there exists an integer polynomial q(x) such that p(x)q(x) is a polynomial having all coe?cients ±1. First solution. We show that the only polynomials p(x) with the required property are x2 ± x ± 1, x2 ± 1 and x2 ± 2x + 1. Let f (x) be any polynomial of degree n having all coe?cients ±1. Suppose that z is a root of f (x) with |z| > 1. Then |z|n = | ± z n?1 ± z n?2 ± · · · ± 1| ≤ |z|n?1 + |z|n?2 + · · · + 1 = |z|n ? 1 . |z| ? 1

This leads to |z|n (|z| ? 2) ≤ ?1; hence |z| < 2. Thus, all the roots of f (x) = 0 have absolute value less than 2. Clearly, a polynomial p(x) with the required properties must be of the form p(x) = x2 + ax ± 1 for some integer a. Let x1 and x2 be its roots (not necessarily distinct). As x1 x2 = ±1, we may assume that |x1 | ≥ 1 and |x2 | ≤ 1. Since x1 , x2 are also roots of p(x)q(x), a polynomial with coe?cients ±1, we have |x 1 | < 2, and so |a| = |x1 + x2 | ≤ |x1 | + |x2 | < 2 + 1. Thus, a ∈ {±2, ±1, 0}. If a = ±1, then q(x) = 1 leads to a solution. If a = 0, then q(x) = x + 1 leads to a solution. If a = ±2, both polynomials x2 ± 2x ? 1 have one root of absolute value greater than 2, so they cannot satisfy the requirement. Finally, the polynomials p(x) = x2 ± 2x + 1 do have the required property with q(x) = x 1, respectively. Comment. By a “root” we may mean a “complex root,” and then nothing requires clari?cation. But complex numbers need not be mentioned at all, because p(x) = x2 + ax ± 1 has real roots if |a| ≥ 2; and the cases of |a| ≤ 1 must be handled separately anyway. The proposer remarks that even if p(x)q(x) is allowed to have zero coe?cients, the conclusion |z| < 2 about its roots holds true. However, extra solutions appear: x2 and x2 ± x.

2

Algebra

Second solution. Suppose that the polynomials p(x) = a 0 + a1 x + x2 and q(x) = b0 + b1 x + · · · + bn xn are such that p(x)q(x) = c0 + c1 x + · · · + cn+2 xn+2 with all ck = ±1. Then |a0 | = |b0 | = |bn | = 1 and a0 b1 = c 1 ? a 1 b0 , whence |b1 | ≥ |a1 | ? 1, |bk | ≥ |a1 bk?1 | ? |bk?2 | ? 1 for k = 2, . . . , n. a0 bk = ck ? a1 bk?1 ? bk?2 for k = 2, . . . , n,

Assume |a1 | ≥ 3. Then clearly q(x) cannot be a constant, so n ≥ 1, and we get |b1 | ≥ 2, |bk | ≥ 3|bk?1 | ? |bk?2 | ? 1 for k = 2, . . . , n.

Recasting the last inequality into |bk | ? |bk?1 | ≥ 2|bk?1 | ? |bk?2 | ? 1 ≥ 2 |bk?1 | ? |bk?2 | ? 1 we see that the sequence dk = |bk | ? |bk?1 | (k = 1, . . . , n) obeys the recursive estimate dk ≥ 2dk?1 ? 1 for k ≥ 2. As d1 = |b1 | ? 1 ≥ 1, this implies by obvious induction dk ≥ 1 for k = 1, . . . , n. Equivalently, |b k | ≥ |bk?1 | + 1 for k = 2, . . . , n, and hence |bn | ≥ |b0 | + n, in contradiction to |b0 | = |bn | = 1, n ≥ 1. It follows that p(x) must be of the form a 0 + a1 x + x2 with |a0 | = 1, |a1 | ≤ 2. If |a1 | ≤ 1 or |a1 | = 2 and a0 = 1, then the corresponding q(x) exists; see the eight examples in the ?rst solution. We are left with the case |a1 | = 2, a0 = ?1. Assume q(x) exists. There is no loss of generality in assuming that b 0 = 1 and a1 = 2 (if b0 = ?1, replace q(x) by ?q(x); and if a1 = ?2, replace q(x) by q(?x)). With b0 = 1, a0 = ?1, a1 = 2 the initial recursion formulas become b1 = 2 ? c 1 , bk = 2bk?1 + bk?2 ? ck for k = 2, . . . , n.

Therefore b1 ≥ 1, b2 ≥ 2b1 + 1 ? c2 ≥ 2, and induction shows that bk ≥ 2 for k = 2, . . . , n, again in contradiction with |b n | = 1. So there are no “good” trinomials p(x) except the eight mentioned above.

Algebra

3

A2. Let R+ denote the set of positive real numbers. Determine all functions f : R+ → R+ such that f (x)f (y) = 2f x + yf (x) for all positive real numbers x and y. Solution. The answer is the constant function f (x) = 2 which clearly satis?es the equation. First, we show that a function f satisfying the equation is nondecreasing. Indeed, suppose that f (x) < f (z) for some positive real numbers x > z. Set y = (x ? z)(f (z) ? f (x)) > 0, so that x + yf (x) = z + yf (z). The equation now implies f (x)f (y) = 2f (x + yf (x)) = 2f (z + yf (z)) = f (z)f (y), therefore f (x) = f (z), a contradiction. Thus, f is nondecreasing. Assume now that f is not strictly increasing, that is, f (x) = f (z) holds for some positive real numbers x > z. If y belongs to the interval (0, (x ? z)/f (x)] then z < z + yf (z) ≤ x. Since f is nondecreasing, we obtain f (z) ≤ f (z + yf (z)) ≤ f (x) = f (z), leading to f (z +yf (z)) = f (x). Thus, f (z)f (y) = 2f (z +yf (z)) = 2f (x) = 2f (z). Hence, f (y) = 2 for all y in the above interval. But if f (y0 ) = 2 for some y0 then 2 · 2 = f (y0 )f (y0 ) = 2f (y0 + y0 f (y0 )) = 2f (3y0 ); therefore f (3y0 ) = 2. By obvious induction, we get that f (3 k y0 ) = 2 for all positive integers k, and so f (x) = 2 for all x ∈ R+ . Assume now that f is a strictly increasing function. We then conclude that the inequality f (x)f (y) = 2f (x + yf (x)) > 2f (x) holds for all positive real numbers x, y. Thus, f (y) > 2 for all y > 0. The equation implies 2f (x + 1 · f (x)) = f (x)f (1) = f (1)f (x) = 2f (1 + xf (1)) for x > 0,

and since f is injective, we get x + 1 · f (x) = 1 + x · f (1) leading to the conclusion that f (x) = x(f (1) ? 1) + 1 for all x ∈ R+ . Taking a small x (close to zero), we get f (x) < 2, which is a contradiction. (Alternatively, one can verify directly that f (x) = cx + 1 is not a solution of the given functional equation.)

4

Algebra

A3. Four real numbers p, q, r, s satisfy p+q+r+s = 9 and p2 + q 2 + r 2 + s2 = 21.

Prove that ab ? cd ≥ 2 holds for some permutation (a, b, c, d) of (p, q, r, s). First solution. Up to a permutation, we may assume that p ≥ q ≥ r ≥ s. We ?rst consider the case where p + q ≥ 5. Then p2 + q 2 + 2pq ≥ 25 = 4 + (p2 + q 2 + r 2 + s2 ) ≥ 4 + p2 + q 2 + 2rs, which is equivalent to pq ? rs ≥ 2. Assume now that p + q < 5; then 4 < r + s ≤ p + q < 5. Observe that (pq + rs) + (pr + qs) + (ps + qr) = Moreover, pq + rs ≥ pr + qs ≥ ps + qr, because (p ? s)(q ? r) ≥ 0 and (p ? q)(r ? s) ≥ 0. We conclude that pq + rs ≥ 10. From (1), we get 0 ≤ (p + q) ? (r + s) < 1, therefore (p + q)2 ? 2(p + q)(r + s) + (r + s)2 < 1. Adding this to (p + q)2 + 2(p + q)(r + s) + (r + s)2 = 92 gives (p + q)2 + (r + s)2 < 41. Therefore 41 = 21 + 2 · 10 ≤ (p2 + q 2 + r 2 + s2 ) + 2(pq + rs) = (p + q)2 + (r + s)2 < 41, which is a contradiction. (p + q + r + s)2 ? (p2 + q 2 + r 2 + s2 ) = 30. 2 (1)

Algebra

5

Second solution. We ?rst note that pq + pr + ps + qr + qs + rs = 30, as in the ?rst solution. Thus, if (a, b, c, d) is any permutation of (p, q, r, s), then bc + cd + db = 30 ? a(b + c + d) = 30 ? a(9 ? a) = 30 ? 9a + a 2 , while Hence 30 ? 9a + a2 ≤ 21 ? a2 , leading to a ∈ [3/2, 3]. Thus the numbers p, q, r and s are in the interval [3/2, 3]. Assume now that p ≥ q ≥ r ≥ s. Note that q ≥ 2 because otherwise p = 9 ? (q + r + s) ≥ 9 ? 3q > 9 ? 6 = 3, which is impossible. Write x = r ? s, y = q ? r and z = p ? q. On the one hand, (p ? q)2 + (p ? r)2 + (p ? s)2 + (q ? r)2 + (q ? s)2 + (r ? s)2 On the other hand, this expression equals z 2 + (z + y)2 +(z + y + x)2 + y 2 + (y + x)2 + x2 = 3x2 + 4y 2 + 3z 2 + 4xy + 4yz + 2zx. Hence, 3x2 + 4y 2 + 3z 2 + 4xy + 4yz + 2zx = 3. Furthermore, pq ? rs = q(p ? s) + (q ? r)s = q(x + y + z) + ys. If x + y + z ≥ 1 then, in view of q ≥ 2, we immediately get pq ? rs ≥ 2. If x + y + z < 1 then (2) implies 3x2 + 4y 2 + 3z 2 + 4xy + 4yz + 2zx > 3(x + y + z)2 . It follows that y 2 > 2xy + 2yz + 4zx ≥ 2y(x + z), so that y > 2(x + z) and hence 3y > 2(x + y + z). The value of the left-hand side of (2) obviously does not ex√ √ ceed 4(x + y + z)2 , so that 2(x + y + z) ≥ 3. Eventually, 3y > 3 and recalling that s ≥ 3/2, we obtain √ √ √ 3 3 3 3 3 + · = > 2. pq ? rs = q(x + y + z) + ys ≥ 2 · 2 3 2 2 (2) = 3(p2 + q 2 + r 2 + s2 ) ? 2(pq + pr + ps + qr + qs + rs) = 3. bc + cd + db ≤ b2 + c2 + d2 = 21 ? a2 .

6

Algebra

A4. Find all functions f : R → R satisfying the equation for all real numbers x and y.

f (x + y) + f (x)f (y) = f (xy) + 2xy + 1

Solution. The solutions are f (x) = 2x ? 1, f (x) = ?x ? 1 and f (x) = x 2 ? 1. It is easy to check that these functions indeed satisfy the given equation. We begin by setting y = 1 which gives f (x + 1) = af (x) + 2x + 1, (1) where a = 1 ? f (1). Then we change y to y + 1 in the equation and use (1) to expand f (x + y + 1) and f (y + 1). The result is a (f (x + y) + f (x)f (y)) + (2y + 1)(1 + f (x)) = f (x(y + 1)) + 2xy + 1, or, using the initial equation again, a (f (xy) + 2xy + 1) + (2y + 1)(1 + f (x)) = f (x(y + 1)) + 2xy + 1. Let us now set x = 2t and y = ?1/2 to obtain a (f (?t) ? 2t + 1) = f (t) ? 2t + 1.

Replacing t by ?t yields one more relation involving f (t) and f (?t): a (f (t) + 2t + 1) = f (?t) + 2t + 1. We now eliminate f (?t) from the last two equations, leading to

(2)

Note that a = ?1 (or else 8t = 0 for all t, which is false). If additionally a = 1 then 1 ? a2 = 0, therefore f (t) = 2 1?a 1+a t ? 1.

(1 ? a2 )f (t) = 2(1 ? a)2 t + a2 ? 1.

Setting t = 1 and recalling that f (1) = 1 ? a, we get a = 0 or a = 3, which gives the ?rst two solutions. The case a = 1 remains, where (2) yields f (t) = f (?t) Now set y = x and y = ?x in the original equation. In view of (3), we obtain, respectively, f (2x) + f (x)2 = f (x2 ) + 2x2 + 1, Subtracting gives f (2x) = 4x2 + f (0). Set x = 0 in (1). Since f (1) = 1 ? a = 0, this yields f (0) = ?1. Hence f (2x) = 4x 2 ? 1, i. e. f (x) = x2 ? 1 for all x ∈ R. This completes the solution. f (0) + f (x)2 = f (x2 ) ? 2x2 + 1. for all t ∈ R. (3)

Algebra

7

A5. Let x, y and z be positive real numbers such that xyz ≥ 1. Prove the inequality y5 ? y2 z5 ? z2 x5 ? x 2 + 5 + 5 ≥ 0. x5 + y 2 + z 2 y + z 2 + x 2 z + x 2 + y 2 First solution. Standard recasting shows that the given inequality is equivalent to x2 + y 2 + z 2 x2 + y 2 + z 2 z 2 + x 2 + y 2 + + ≤ 3. x5 + y 2 + z 2 y 5 + z 2 + x 2 z 5 + x 2 + y 2 In view of the Cauchy-Schwarz inequality and the condition xyz ≥ 1, we have (x5 + y 2 + z 2 )(yz + y 2 + z 2 ) ≥ x5/2 (yz)1/2 + y 2 + z 2 or x2 + y 2 + z 2 yz + y 2 + z 2 ≤ 2 . x5 + y 2 + z 2 x + y2 + z 2 x2 + y 2 + z 2 x2 + y 2 + z 2 x2 + y 2 + z 2 yz + zx + xy + 5 + 5 ≤2+ 2 ≤ 3, 5 + y2 + z 2 2 + x2 2 + y2 x y +z z +x x + y2 + z 2
2

≥ (x2 + y 2 + z 2 )2 ,

Taking the cyclic sum and using the fact that x 2 + y 2 + z 2 ≥ yz + zx + xy gives

which is exactly what we wished to show. Comment. The way the Cauchy-Schwarz inequality is used is the crucial point in the solution; it is not at all obvious! The condition xyz ≥ 1 (which might as well have been xyz = 1) allows to transform the expression to a homogeneous form. The smart use of Cauchy-Schwarz inequality has the e?ect that the common numerators of the three fractions become common denominators in the transformed expression. Second solution. We shall prove something more, namely that y5 z5 x5 + 5 + 5 ≥ 1, x5 + y 2 + z 2 y + z 2 + x 2 z + x 2 + y 2 and 1≥ y2 z2 x2 + 5 + 5 . x5 + y 2 + z 2 y + z 2 + x 2 z + x 2 + y 2 (1)

(2)

We ?rst prove (1). We have yz(y 2 + z 2 ) = y 3 z + yz 3 ≤ y 4 + z 4 ; the latter inequality holds because y 4 ? y 3 z ? yz 3 + z 4 = (y 3 ? z 3 )(y ? z) ≥ 0. Therefore x(y 4 + z 4 ) ≥ xyz(y 2 + z 2 ) ≥ y 2 + z 2 , or x5 x4 x5 ≥ 5 = 4 . x5 + y 2 + z 2 x + xy 4 + xz 4 x + y4 + z 4

8

Algebra

Taking the cyclic sum, we get the desired inequality. The proof of (2) is based on exactly the same ideas as in the ?rst solution. From the Cauchy-Schwarz inequality and the fact that xyz ≥ 1, we have (x5 + y 2 + z 2 )(yz + y 2 + z 2 ) ≥ (x2 + y 2 + z 2 )2 , implying x2 (yz + y 2 + z 2 ) x2 ≤ . x5 + y 2 + z 2 (x2 + y 2 + z 2 )2

Taking the cyclic sum, we have x2 y2 z2 + 5 + 5 x5 + y 2 + z 2 y + z 2 + x 2 z + x 2 + y 2 2(x2 y 2 + y 2 z 2 + z 2 x2 ) + x2 yz + y 2 zx + z 2 xy (x2 + y 2 + z 2 )2 2 + y 2 + z 2 )2 ? (x4 + y 4 + z 4 ) + (x2 yz + y 2 zx + z 2 xy) (x . (x2 + y 2 + z 2 )2

≤ =

Thus we need to show that x4 + y 4 + z 4 ≥ x2 yz + y 2 zx + z 2 xy; and this last inequality holds because x4 + y 4 + z 4 = x4 + y 4 y 4 + z 4 z 4 + x 4 + + ≥ x 2 y 2 + y 2 z 2 + z 2 x2 2 2 2 x2 y 2 + y 2 z 2 y 2 z 2 + z 2 x2 z 2 x2 + x 2 y 2 + + = 2 2 2 ≥ y 2 zx + z 2 xy + x2 yz.

Combinatorics

9

Combinatorics
C1. A house has an even number of lamps distributed among its rooms in such a way that there are at least three lamps in every room. Each lamp shares a switch with exactly one other lamp, not necessarily from the same room. Each change in the switch shared by two lamps changes their states simultaneously. Prove that for every initial state of the lamps there exists a sequence of changes in some of the switches at the end of which each room contains lamps which are on as well as lamps which are o?. Solution. Two lamps sharing a switch will be called twins. A room will be called normal if some of its lamps are on and some are o?. We devise an algorithm that increases the number of normal rooms in the house. After several runs of the algorithm we arrive at the state with all rooms normal. Choose any room R0 which is not normal, assuming without loss of generality that all lamps in R0 are o?. If there is a pair of twins in R 0 , we switch them on and stop. Saying stop means that we have achieved what we wanted: there are more normal rooms than before the algorithm started. So suppose there are no twins in R0 . Choose any lamp a0 ∈ R0 and let b0 ∈ R1 be its twin. Change their states. After this move room R 0 becomes normal. If R1 also becomes (or remains) normal, then stop. Otherwise all lamps in R 1 are in equal state; as before we can assume that there are no twins in R 1 . Choose any lamp a1 ∈ R1 other than b0 and let b1 ∈ R2 be its twin. Change the states of these two twin lamps. If R2 becomes (or stays) normal, stop. Proceed in this fashion until a repetition occurs in the sequence R 0 , R1 , R2 , . . . . Thus assume that the rooms R0 , R1 , . . . , Rm are all distinct, each Ri connected to Ri+1 through a twin pair ai ∈ Ri , bi ∈ Ri+1 (i = 0, . . . , m?1), and there is a lamp am ∈ Rm (am = bm?1 ) which has its twin bm in some room Rk visited earlier (0 ≤ k ≤ m?1). If the algorithm did not stop after we entered room R m , we change the states of the lamps am and bm ; room Rm becomes normal. If k ≥ 1, then there are two lamps in Rk touched previously, bk?1 and ak . They are the twins of ak?1 and bk , so neither of them can be bm (twin to am ). Recall that the moment we entered room R k the ?rst time, by pressing the bk?1 switch, this room became “abnormal” only until we touched lamp a k . Thus bk?1 and ak are in di?erent states now. Whatever the new state of lamp b m , room Rk remains normal. Stop.

10

Combinatorics

Finally, if k = 0, then bm ∈ R0 and bm = a0 because the twin of a0 is b0 . Each room has at least three lamps, so there is a lamp c ∈ R 0 , c = a0 , c = bm . In the ?rst move lamp a0 was put on while c stayed o?. Whatever the new state of b m , room R0 stays normal. Stop. So, indeed, after a single run of this algorithm, the number of normal rooms increases at least by 1. This completes the proof. Comment. The problem was submitted in the following formulation: A school has an even number of students, each of whom attends exactly one of its (?nitely many) classes. Each class has at least three students, and each student has exactly one “best friend” in the same school such that, whenever B is A’s “best friend”, then A is B’s “best friend”. Furthermore, each student prefers either apple juice over orange juice or orange juice over apple juice, but students change their preferences from time to time. “Best friends”, however, will change their preferences (which may or may not be the same) always together, at the same moment. Whatever preference each student may initially have, prove that there is always a sequence of changes of preferences which will lead to a situation in which no class will have students all of whom have the same preference.

Combinatorics

11

C2. Let k be a ?xed positive integer. A company has a special method to sell sombreros. Each customer can convince two persons to buy a sombrero after he/she buys one; convincing someone already convinced does not count. Each of these new customers can convince two others and so on. If each one of the two customers convinced by someone makes at least k persons buy sombreros (directly or indirectly), then that someone wins a free instructional video. Prove that if n persons bought sombreros, then at most n/(k + 2) of them got videos. First solution. Consider the problem in reverse: If w persons won free videos, what is the least number n of persons who bought sombreros? One can easily compute this minimum for small values of w: for w = 1 it is 2k + 3, and for w = 2 it is 3k + 5. These can be rewritten as n ≥ 1 · (k + 2) + (k + 1) and n ≥ 2(k + 2) + (k + 1), leading to the conjecture that n ≥ w(k + 2) + (k + 1). (1)

Let us say that a person P in?uenced a person Q if P made Q buy a sombrero directly or indirectly, or if Q = P . A component is the set of persons in?uenced by someone who was in?uenced by no one else but himself. No person from a component in?uenced another one from a di?erent component. So it su?ces to prove (1) for each component. Indeed, if (1) holds for r components of size n i with wi winners, i = 1, . . . , r, then n= ni ≥ (wi (k + 2) + (k + 1)) = wi (k + 2) + r(k + 1),

implying (1) for n = ni , w = wi . Thus one may assume that the whole group is a single component, i. e. all customers were in?uenced by one person A (directly or indirectly). Moreover, it su?ces to prove (1) for a group G with w winners and of minimum size n. Notice that then A is a video winner. If not, imagine him removed from the group. A video winner from the original group is also a winner in the new one. So we have decreased n without changing w, a contradiction. Under these assumptions, we proceed to prove (1) by induction on w ≥ 1. For w = 1, the group of customers contains a single video winner A, the two persons B and C he/she convinced directly to buy sombreros, and two nonintersecting groups of k persons, the ones persuaded by B and C (directly or indirectly). This makes at least 2k + 3 persons, as needed. Assume the claim holds for groups with less than w winners, and consider a group with n winners where everyone was in?uenced by some person A. Recall that A is a winner. Let B and C be the persons convinced directly by A to buy

12

Combinatorics

sombreros. Let nB be the number of people in?uenced by B, and w B the number of video winners among them. De?ne n C and wC analogously. We have nB ≥ wB (k + 2) + (k + 1), by the induction hypothesis if w B > 0 and because A is a winner if wB = 0. Analogously nC ≥ wC (k + 2) + (k + 1). Adding the two inequalities gives us n ≥ w(k + 2) + (k + 1), since n = n B + nC + 1 and w = wB + wC + 1. This concludes the proof. Second solution. As in the ?rst solution, we say that a person P in?uenced a person Q if P made Q buy a sombrero directly or indirectly, or if Q = P . Likewise, we keep the de?nition of a component. For brevity, let us write winners instead of video winners. The components form a partition of the set of people who bought sombreros. It is enough to prove that in each component the fraction of winners is at most 1/(k + 2). We will minimise the number of people buying sombreros while keeping the number of winners ?xed. First, we can assume that no winners were convinced (directly) by a nonwinner. Indeed, if a nonwinner P convinced a winner Q, remove all people in?uenced by P but not by Q and let whoever convinced P (if anyone did) now convince Q. Observe that no winner was removed, hence the new con?guration has fewer people, but the same winners. Thus, indeed, there is no loss of generality in assuming that: The set of all buyers makes up a single component. Every winner could have been convinced only by another winner. (2) (3)

Now remove all the winners and consider the new components. We claim that Each new component has at least k + 1 persons. (4)

Indeed, let C be a new component. In view of (2), there is a member C of C who had been convinced by some removed winner W . Then C must have in?uenced at least k + 1 people (including himself), but all the people in?uenced by C are in C. Therefore |C| ≥ k + 1. Now return the winners one by one in such a way that when a winner returns, the people he convinced (directly) are already present. This is possible because of (3). In that way the number of components decreases by one with each winner, thus the number of components with all winners removed is equal to w + 1, where w is the number of winners. It follows from (4) that the number of nonwinners satis?es the estimate n ? w ≥ (w + 1)(k + 1). This implies the desired bound.

Combinatorics

13

C3. In an m × n rectangular board of mn unit squares, adjacent squares are ones with a common edge, and a path is a sequence of squares in which any two consecutive squares are adjacent. Each square of the board can be coloured black or white. Let N denote the number of colourings of the board such that there exists at least one black path from the left edge of the board to its right edge, and let M denote the number of colourings in which there exist at least two non-intersecting black paths from the left edge to the right edge. Prove that N 2 ≥ M · 2mn . Solution. We generalise the claim to the following. Suppose that a twosided m × n board is considered, where some of the squares are transparent and some others are not. Each square must be coloured black or white. However, a transparent square needs to be coloured only on one side; then it looks the same from above and from below. In contrast, a non-transparent square must be coloured on both sides (in the same colour or not). Let A (respectively B) be the set of colourings of the board with at least one black path from the left edge to the right edge if one looks from above (respectively from below). Let C be the set of colourings of the board in which there exist two black paths from the left edge to the right edge of the board, one on top and one underneath, not intersecting at any transparent square. Let D be the set of all colourings of the board. We claim that |A| · |B| ≥ |C| · |D|. (1) Note that this implies the original claim in the case where all squares are transparent: one then has |A| = |B| = N , |C| = M , |D| = 2 mn . We prove (1) by induction on the number k of transparent squares. If k = 0 then |A| = |B| = N · 2mn , |C| = N 2 and |D| = (2mn )2 , so equality holds in (1). Suppose the claim is true for some k and consider a board with k + 1 transparent squares. Let A, B, C and D be the sets of colourings of this board as de?ned above. Choose one transparent square ?. Now, convert ? into a non-transparent square, and let A , B , C and D be the respective sets of colourings of the new board. By the induction hypothesis, we have: |A | · |B | ≥ |C | · |D |. (2)

Upon the change made, the number of all colourings doubles. So |D | = 2|D|. To any given colouring in A, there correspond two colourings in A , obtained by colouring ? black and white from below. This is a bijective correspondence,

14

Combinatorics

so |A | = 2|A|. Likewise, |B | = 2|B|. In view of (2), it su?ces to prove that |C | ≥ 2|C|. (3)

Make ? transparent again and take any colouring in C. It contains two black paths (one seen from above and one from below) that do not intersect at transparent squares. Being transparent, ? can therefore lie on at most one of them, say on the path above. So when we make ? non-transparent, let us keep its colour on the side above but colour the side below in the two possible ways. The two colourings obtained will be in C . It is easy to see that when doing so, di?erent colourings in C give rise to di?erent pairs of colourings in C . Hence (3) follows, implying (2). As already mentioned, this completes the solution. Comment. A more direct approach to the problem may go as follows. Consider two m × n boards instead of one. Let A denote the set of all colourings of the two boards such that there are at least two non-intersecting black paths from the left edge of the ?rst board to its right edge. Clearly, |A| = M · 2 mn : we can colour the ?rst board in M ways and the second board in an arbitrary fashion. Let B denote the set of all colourings of the two boards such that there is at least one black path from the left edge of the ?rst board to its right edge, and at least one black path from the left edge of the second board to its right edge. Clearly, |B| = N 2 . It su?ces to ?nd an injective function f : A → B. Such an injection can indeed be constructed. However, working it out in all details seems to be a delicate task.

Combinatorics

15

C4. Let n ≥ 3 be a given positive integer. We wish to label each side and each diagonal of a regular n-gon P1 , . . . , Pn with a positive integer less than or equal to r so that: (i) every integer between 1 and r occurs as a label; (ii) in each triangle Pi Pj Pk two of the labels are equal and greater than the third. Given these conditions: (a) Determine the largest positive integer r for which this can be done. (b) For that value of r, how many such labellings are there? Solution. A labelling which satis?es condition (ii) will be called good. A labelling which satis?es both given conditions (i) and (ii) will be called very good. Let us try to understand the structure of good labellings. Sides and diagonals of the polygon will be called just edges. Let AB be an edge with the maximum label m. Let X be any vertex di?erent from A and B. Condition (ii), applied to triangle ABX, implies that one of the segments AX, BX has label m, and the other one has a label smaller than m. Thus we can split all vertices into two disjoint groups 1 and 2; group 1 contains vertices X such that AX has label m (including vertex B) and group 2 contains vertices X such that BX has label m (including vertex A). We claim that the edges labelled m are exactly those which join a vertex of group 1 with a vertex of group 2. First consider any vertex X = B in group 1 and any vertex Y = A in group 2. In triangle AXY , we already know that the label of AX (which is m) is larger than the label of AY (which is not m). Therefore the label of XY also has to be equal to m, as we wanted to show. Now consider any two vertices X, Y in group 1. In triangle AXY , the edges AX and AY have the same label m. So the third edge must have a label smaller than m, as desired. Similarly, any edge joining two vertices in group 2 has a label smaller than m. We conclude that a good labelling of an n-gon consists of: ? a collection of edges with the maximum label m; they are the ones that go from a vertex of group 1 to a vertex of group 2, ? a good labelling of the polygon determined by the vertices of group 1, and ? a good labelling of the polygon determined by the vertices of group 2.

16

Combinatorics

(a) The greatest possible value of r is n?1. We prove this by induction starting with the degenerate cases n = 1 and n = 2, where the claim is immediate. Assusme it true for values less than n, where n ≥ 3, and consider any good labelling of an n-gon P . Its edges are split into two groups 1 and 2; suppose they have k and n?k vertices, respectively. The k-gon P 1 formed by the vertices in group 1 inherits a good labelling. By the induction hypothesis, this good labelling uses at most k?1 di?erent labels. Similarly, the (n?k)-gon P 2 formed by the vertices in group 2 inherits a good labelling which uses at most n?k?1 di?erent labels. The remaining segments, which join a vertex of group 1 with a vertex of group 2, all have the same (maximum) label. Therefore, the total number of di?erent labels in our good labelling is at most (k?1) + (n?k?1) + 1 = n?1. This number can be easily achieved, as long as we use di?erent labels in P 1 and P2 . (b) Let f (n) be the number of very good labellings of an n-gon P with labels 1, . . . , n?1. We will show by induction that This holds for n = 1 and n = 2. Fix n ≥ 3 and assume that f (k) = k!(k ? 1)!/2 k?1 for k < n. Divide the n vertices into two non-empty groups 1 and 2 in any way. If group 1 is of size k, there are n ways of doing that. We must label every edge joining k a vertex of group 1 and a vertex of group 2 with the label n?1. Now we need to choose which k?1 of the remaining labels 1, 2, . . . , n?2 will be used to label the k-gon P1 ; there are n?2 possible choices. The remaining n?k?1 labels will k?1 be used to label the (n?k)-gon P2 . Finally, there are f (k) very good labellings of P1 and f (n?k) very good labellings of P 2 . Now we sum the resulting expression over all possible values of k, noticing that we have counted each very good labelling twice, since choosing a set to be group 1 is equivalent to choosing its complement. We have: 1 2
n?1 k=1

f (n) = n!(n ? 1)!/2n?1 .

f (n) =

n k

n?2 f (k)f (n ? k) k?1
n?1

=

n!(n ? 1)! 2(n ? 1)

=

n!(n ? 1)! 2(n ? 1)

k=1 n?1 k=1

f (k) f (n ? k) · k!(k ? 1)! (n ? k)!(n ? k ? 1)! 1 1 n!(n ? 1)! · = , 2k?1 2n?k?1 2n?1

which is what we wanted to show.

Combinatorics

17

C5. There are n markers, each with one side white and the other side black, aligned in a row so that their white sides are up. In each step, if possible, we choose a marker with the white side up (but not one of the outermost markers), remove it and reverse the closest marker to the left and the closest marker to the right of it. Prove that one can achieve the state with only two markers remaining if and only if n ? 1 is not divisible by 3. First solution. Given a particular chain of markers, we call white (resp. black) markers the ones with the white (resp. black) side up. Note that the parity of the number of black markers remains unchanged during the game. Hence, if only two markers remain, these markers must have the same colour. Next, we de?ne an invariant. To a white marker with t black markers to its left we assign the number (?1)t . Only white markers have numbers assigned to them. Let S be the residue class modulo 3 of the sum of all numbers assigned to the white markers. It is easy to check that S is an invariant under the allowed operations. Suppose, for instance, that a white marker W is removed, with t black markers to the left of it, and that the closest neighbours of W are black. Then S increases by ?(?1)t + (?1)t?1 + (?1)t?1 = 3(?1)t?1 . The other three cases are analogous. If the game ends with two black markers, the number S is zero; if it ends with two white markers, then S is 2. Since we start with n white markers and in this case S ≡ n (mod 3), a necessary condition for the game to end is n ≡ 0, 2 (mod 3). If we start with n ≥ 5 white markers, taking the leftmost allowed white markers in three consecutive moves, we obtain a row of n ? 3 white markers without black markers. Since the goal can be reached for n = 2, 3, we conclude that the game can end with two markers for every positive integer n satisfying n ≡ 0, 2 (mod 3). Second solution. Denote by L the leftmost and by R the rightmost marker, respectively. To start with, note again that the parity of the number of blackside-up markers remains unchanged. Hence, if only two markers remain, these markers must have the same colour up. We will show by induction on n that the game can be succesfully ?nished if and only if n ≡ 0, 2 (mod 3) and that the upper sides of L and R will be black in the ?rst case and white in the second case. The statement is clear for n = 2 and 3. Assume that we ?nished the game for some n, and denote by k the position of the marker X (counting from the left) that was last removed. Having ?nished the game, we have also ?nished the subgames with the k markers from L to X and with the n ? k + 1 markers

18

Combinatorics

from X to R (inclusive). Thereby, by the induction hypothesis, before X was removed, the upper side of L had been black if k ≡ 0 (mod 3), and white if k ≡ 2 (mod 3), while the upper side of R had been black if n ? k + 1 ≡ 0 (mod 3), and white if n ? k + 1 ≡ 2 (mod 3). Markers R and L were reversed upon the removal of X. Therefore, in the ?nal position, R and L are white if and only if k ≡ n ? k + 1 ≡ 0 (mod 3), which yields n ≡ 2 (mod 3), and black if and only if k ≡ n ? k + 1 ≡ 2 (mod 3), which yields n ≡ 0 (mod 3). On the other hand, a game with n markers can be reduced to a game with n ? 3 markers by removing the second, fourth and third marker in this order. This ?nishes the induction.

Combinatorics

19

C6. In a mathematical competition in which 6 problems were posed to the participants, every two of these problems were solved by more than 2/5 of the contestants. Moreover, no contestant solved all the 6 problems. Show that there are at least 2 contestants who solved exactly 5 problems each. First solution. Assume there were n contestants. Let us count the number N of ordered pairs (C, P ), where P is a pair of problems solved by contestant C. On the one hand, for every one of the 15 pairs of problems, there are at least (2n + 1)/5 contestants who solved both problems in the pair. Therefore N ≥ 15 · 2n + 1 = 6n + 3. 5 (1)

On the other hand, assume k contestants solved 5 problems. Each of them solved 10 pairs of problems, whereas each of the n ? k remaining contestants solved at most 6 pairs of problems. Thus N ≤ 10k + 6(n ? k) = 6n + 4k. (2)

From these two estimates we immediately get k ≥ 1. If (2n + 1)/5 were not an integer, there would be, for every pair of problems, at least (2n + 1)/5 contestants who solved both problems in the pair (rather than (2n + 1)/5). Then (1) would improve to N ≥ 6n + 6 and this would yield k ≥ 2. Alternatively, had some student solved less than 4 problems, he would have solved at most 3 pairs of problems (rather than 6), and our second estimate would improve to N ≤ 6n + 4k ? 3, which together with N ≥ 6n + 3 also gives k ≥ 2. So we are left with the case where 5 divides 2n + 1 and every contestant has solved 4 or 5 problems. Let us assume k = 1 and let us call the contestant who solved 5 problems the ‘winner’. We must then have N = 6n + 4 (the winner solved 10 pairs of problems, and the rest of the contestants solved exactly 6 pairs of problems each). Let us call a pair of problems ‘special’ if more than (2n + 1)/5 contestants solved both problems of the pair. If there were more than one special pair of problems, our ?rst estimate would be improved to N ≥ 13 · 2n + 1 +2 5 2n + 1 +1 5 = 6n + 5,

which is impossible. Similarly, if a special pair of problems exists, no more than (2n + 1)/5 + 1 contestants could have solved both problems in the pair, because otherwise 2n + 1 2n + 1 + + 2 = 6n + 5. N ≥ 14 · 5 5

20

Combinatorics

Let us now count the number M of pairs (C, P ) where the ‘tough’ problem (the one not solved by the winner) is one of the problems in P . For each of the 5 pairs of problems containing the tough problem, there are either (2n + 1)/5 or (2n + 1)/5 + 1 contestants who solved both problems of the pair. We then get M = 2n + 1 or M = 2n + 2; the latter is possible only if there is a special pair of problems and this special pair contains the tough problem. On the other hand, assume m contestants solved the tough problem. Each of them solved 3 other problems and therefore solved 3 pairs of problems containing the tough one. We can then write M = 3m. Hence 2n + 1 ≡ 0 or 2 (mod 3). Finally, let us chose one of the problems other than the tough one, say p, and count the number L of pairs (C, P ) for which p ∈ P . We can certainly chose p such that the special pair of problems, if it exists, does not contain p. Then we have L = 2n + 1 (each of the 5 pairs of problems containing p have exactly (2n+1)/5 contestants who solved both problems of the pair). On the other hand, if l is the number of contestants, other than the winner, who solved problem p, we have L = 3l + 4 (the winner solved problem p and other 4 problems, so she solved 4 pairs of problems containg p, and each of the l students who solved p, solved other 3 problems, hence each of them solved 3 pairs of problems containing p). Therefore 2n + 1 ≡ 1 (mod 3), which is a contradiction. Second solution. This is basically the same proof as above, written in symbols rather than words. Suppose there were n contestants. Let p ij be the number of contestants who solved both problem i and problem j (1 ≤ i < j ≤ 6) and let n r be the number of contestants who solved exactly r problems (0 ≤ r ≤ 6). Clearly, nr = n. By hypothesis, pij ≥ (2n + 1)/5 for all i < j, and so S=
i<j

pij ≥ 15 ·

2n + 1 = 6n + 3. 5
r 2

A contestant who solved exactly r problems contributes a ‘1’ to r in this sum (where as usual 2 = 0 for r < 2). Therefore
6

summands

S=
r=0

r nr . 2

Combining this with the previous estimate we obtain
6

3 ≤ S ? 6n =

r=0

r ? 6 nr , 2

(3)

Combinatorics

21

which rewrites as 4n5 + 9n6 ≥ 3 + 6n0 + 6n1 + 5n2 + 3n3 . If no contestant solved all problems, then n 6 = 0, and we see from the above that n5 must be positive. To show that n5 ≥ 2, assume the contrary, i. e., n5 = 1. Then all of n0 , n1 , n2 , n3 must be zero, so that n4 = n ? 1. The right equality of (3) reduces to S = 6n + 4. Each one of the 15 summands in S = pij is at least (2n + 1)/5 = λ. Because S = 6n + 4, they cannot be all equal (6n + 4 is not divisible by 15); therefore 14 of them are equal to λ and one is λ + 1. Let (i0 , j0 ) be this speci?c pair with pi0 j0 = λ + 1. The contestant who solved 5 problems will be again called the winner. Assume, without loss of generality, that it was problem 6 at which the winner failed, and that problem 1 is not in the pair (i0 , j0 ); that is, 2 ≤ i0 < j0 ≤ 6. Consider the sums S = p16 + p26 + p36 + p46 + p56 and S = p12 + p13 + p14 + p15 + p16 .

Suppose that problem 6 has been solved by x contestants (each of them contributes a ‘3’ to S ) and problem 1 has been solved by y contestants other than the winner (each of them contributes a ‘3’ to S , and the winner contributes a ‘4’). Thus S = 3x and S = 3y + 4. The pair (i0 , j0 ) does not appear in the sum S , which is therefore equal to 5λ = 2n + 1. The sum S is either 5λ or 5λ + 1. Hence 3x ∈ {2n + 1, 2n + 2} and 3y + 4 = 2n + 1, which is impossible, as examination of remainders (mod 3) shows. Contradiction ends the proof. Comment. The problem submitted by the proposer consisted of two parts which were found to be two independent problems by the PSC. Part (a) asked for a proof that if every problem has been solved by more than 2/5 of the contestants then there exists a set of 3 problems solved by more than 1/5 of the contestants and a set of 4 problems solved by more than 1/15 of the contestants. The arguments needed for a proof of (a) seem rather standard, giving advantage to students who practised those techniques at training courses. This is much less the case with part (b), which was therefore chosen to be Problem C6 on the shortlist. The proposer remarks that there exist examples showing the bound 2 can be attained for the number of contestants solving 5 problems, and that the problem would become harder if it asked to ?nd one such example.

22

Combinatorics

C7. Let n > 1 be a given integer, and let a 1 , . . . , an be a sequence of integers such that n divides the sum a1 + · · · + an . Show that there exist permutations σ and τ of 1, 2, . . . , n such that σ(i) + τ (i) ≡ a i (mod n) for all i = 1, . . . , n. Solution. Suppose that there exist suitable permutations σ and τ for a certain integer sequence a1 , . . . , an of sum zero modulo n. Let b1 , . . . , bn be another integer sequence with sum divisible by n, and let b 1 , . . . , bn di?er modulo n from a1 , . . . , an only in two places, i1 and i2 . Based on the fact that σ(i) + τ (i) ≡ bi (mod n) for each i = i1 , i2 , one can transform σ and τ into suitable permutations for b1 , . . . , bn . All congruences below are assumed modulo n. First we construct a three-column rectangular array σ(i1 ) σ(i2 ) σ(i3 ) . . . σ(ip?1 ) σ(ip ) σ(ip+1 ) . . . σ(iq?1 ) σ(iq ) ?bi1 τ (i1 ) τ (i2 ) τ (i3 ) . . . τ (ip?1 ) τ (ip ) τ (ip+1 ) . . . τ (iq?1 ) τ (iq )

?bi2

?bi3 . . .

?bip?1 ?bip ?bip+1 . . . ?biq?1 ?biq

whose rows are some of the ordered triples T i = σ(i), ?bi , τ (i) , i = 1, . . . , n. In the ?rst two rows, write the triples T i1 and Ti2 , respectively. Since σ and τ are permutations of 1, . . . , n, there is a unique index i 3 such that σ(i1 ) + τ (i3 ) ≡ bi2 . Write the triple Ti3 in row 3. There is a unique i4 such that σ(i2 ) + τ (i4 ) ≡ bi3 ; write the triple Ti4 in row 4, and so on. Stop the ?rst moment a number from column 1 occurs in this column twice, as i p in row p and iq in row q, where p < q. We claim that p = 1 or p = 2. Assume on the contrary that p > 2 and consider the subarray containing rows p through q. Each of these rows has sum 0 modulo n, because σ(i) + τ (i) ≡ bi for i = i1 , i2 , as already mentioned. On the other hand, by construction the sum in each downward right diagonal of the original array is also 0 modulo n. It follows that the six boxed entries add up to 0 modulo n, i. e. ?bip + τ (ip ) + τ (ip+1 ) + σ(iq?1 ) + σ(iq ) ? biq ≡ 0.

Combinatorics

23

Now, ip = iq gives biq ≡ σ(iq ) + τ (ip ), so that the displayed formula becomes ?bip + τ (ip+1 ) + σ(iq?1 ) ≡ 0. And since σ(ip?1 ) ? bip + τ (ip+1 ) ≡ 0 by the remark about diagonals, we obtain σ(i p?1 ) = σ(iq?1 ). This implies ip?1 = iq?1 , in contradiction with the de?nition of p and q. Thus p = 1 or p = 2 indeed. Now delete the repeating qth row of the array. Then shift cyclically column 1 and column 3 by moving each of their entries one position down and one position up, respectively. The sum in each row of the new array is 0 modulo n, except possibly in the ?rst and the last row (“most” of the new rows used to be diagonals of the initial array). For p = 1, the last row sum is also 0 modulo n, in view of ip = iq = i1 and σ(iq?2 ) ? biq?1 + τ (iq ) ≡ 0 (see the array on the left below). A single change is needed to accomodate the case p = 2: in column 3, interchange the top entry τ (i2 ) and the bottom entry τ (i1 ) (see the array on the right). The last row sum becomes 0 modulo n since i p = iq = i2 . σ(iq?1 ) σ(i1 ) σ(i2 ) . . . σ(iq?3 ) σ(iq?2 ) ?bi1 τ (i2 ) τ (i3 ) τ (i4 ) . . . τ (iq?1 ) τ (i1 ) σ(iq?1 ) σ(i1 ) σ(i2 ) . . . σ(iq?3 ) σ(iq?2 ) ?bi1 τ (i1 ) τ (i3 ) τ (i4 ) . . . τ (iq?1 ) τ (i2 )

?bi2

?bi3 . . .

?bi2

?bi3 . . .

?biq?2

?biq?1

?biq?2

?biq?1

(p = 1)

(p = 2)

For both p = 1 and p = 2, column 1 and column 3 are permutations the numbers of σ(i1 ), . . . , σ(iq?1 ) and τ (i1 ), . . . , τ (iq?1 ), respectively. So, adding the triples Ti not involved in the construction above, we obtain permutations σ and τ of 1, . . . , n in column 1 and column 3 such that σ (i) + τ (i) ≡ bi for all i = i1 . Finally, the relation σ (i1 ) + τ (i1 ) ≡ bi1 follows from the fact that Σ σ (i) + τ (i) ≡ 0 ≡ Σbi . We proved that the statement remains true if we change elements of the original sequence a1 , . . . , an two at a time. However, one can obtain from any given a1 , . . . , an any other zero-sum sequence by changing two elements at a time. (The condition that the sequence has sum zero modulo n is used here again.) And because the claim is true for any constant sequence, the conclusion follows.

24

Combinatorics

C8. Let M be a convex n-gon, n ≥ 4. Some n?3 of its diagonals are coloured green and some other n?3 diagonals are coloured red, so that no two diagonals of the same colour meet inside M . Find the maximum possible number of intersection points of green and red diagonals inside M . Solution. We start with some preliminary observations. It is well-known that n?3 is the maximum number of nonintersecting diagonals in a convex n-gon and that any such n?3 diagonals partition the n-gon into n?2 triangles. It is also known (and not hard to show by induction) that at least two nonadjacent vertices are then left free; that is, there are at least two diagonals cutting o? triangles from the n-gon. Passing to the conditions of the problem, for any diagonal d, denote by f (d) the number of green/red inresections lying on d. Take any pair of green diagonals d, d and suppose there are k vertices, including the endpoints of d and d , of the part of M between d and d . The remaining n?k vertices span a convex polygon A. . .BC. . .D; here A and B are the vertices of M , adjacent to the endpoints of d, outside the “part of M ” just mentioned, and C and D are the vertices adjacent to the endpoints of d , also outside that part. (A, B can coincide, as well as C, D.) Let m be the number of red segments in the polygon A. . .BC. . .D. Since this (n?k)-gon has at most n?k?3 nonintersecting diagonals, we get m ≤ (n?k?3) + 2; the last ‘2’ comes from the segments AD and BC, which also can be red. Each one of these m red segments intersects both d and d . Each one of the remaining n?3?m red segments can meet at most one of d, d . Hence follows the estimate f (d) + f (d ) ≤ 2m + (n?3?m) = n ? 3 + m ≤ n ? 3 + (n?k?1) = 2n ? k ? 4. Now we pair the green diagonals in the following way: we choose any two green diagonals that cut o? two triangles from M ; they constitute the ?rst pair d1 , d2 . Then we choose two green diagonals that cut o? two triangles from the residual (n?2)-gon, to make up the second pair d 3 , d4 , and so on; d2r?1 , d2r are the two diagonals in the r-th pairing. If n?3 is odd, the last green diagonal remains unpaired. The polygon obtained after the r-th pairing has n?2r vertices. Two sides of that polygon are the two diagonals from that pairing; its remaining sides are either sides of M or some of the green diagonals d 1 , . . . , d2r . There are at most 2r vertices of M outside the part of M between d 2r?1 and d2r . Thus, denoting by kr the number of vertices of that part, we have k r ≥ n ? 2r.

Combinatorics

25

In view of the previous estimates, the number of intersection points on those two diagonals satis?es the inequality f (d2r?1 ) + f (d2r ) ≤ 2n ? kr ? 4 ≤ n + 2r ? 4. If n?3 is even, then d1 , d2 , . . . , dn?3 are all the green diagonals; and if n?3 is odd, the last unpaired green diagonal can meet at most n?3 (i.e., all) red ones. Thus, writing n ? 3 = 2 + ε, ε ∈ {0, 1}, we conclude that the total number of intersection points does not exceed the sum (n + 2r ? 4) + ε · (n ? 3) = (2 + ε ? 1) + ( + 1) + ε(2 + ε) =3
2

r=1

+ ε(3 + 1) =

3 n?3 4

2

,

0 where t is the least integer not less than t. (For n = 4 the void sum r=1 evaluates to 0.) The following example shows that this value can be attained, for both n even and n odd. Let P Q and RS be two sides of M chosen so that the diagonals QR and SP do not meet and, moreover, so that: if U is the part of the boundary of M between Q and R, and V is the part of the boundary of M between S and P (S, P ∈ U , Q, R ∈ V ), then the numbers of vertices of M on U and on V di?er / / by at most 1. Colour in green: the diagonal P R, all diagonals connecting P to vertices on U and all diagonals connecting R to vertices on V . Colour in red: the diagonal QS, all diagonals connecting Q to vertices on V and all diagonals connecting S to vertices on U . 2 3 is the Then equality holds in the estimate above. In conclusion, 4 n ? 3 greatest number of intersection points available.

Comment. It seems that the easiest way to verify that these examples indeed yield equality in the estimates obtained is to draw a diagram and visualise the process of detaching the corner triangles in appropriate pairings; all inequalities that appear in the arguments above turn into equalities. This is also the way (by inspecting the detaching procedure) in which it is expected that the solver can construct these examples.

26

Geometry

Geometry
G1. In a triangle ABC satisfying AB + BC = 3AC the incircle has centre I and touches the sides AB and BC at D and E, respectively. Let K and L be the symmetric points of D and E with respect to I. Prove that the quadrilateral ACKL is cyclic. Solution. Let P be the other point of intersection of BI with the circumcircle of triangle ABC, let M be the midpoint of AC and N the projection of P to IK. Since AB + BC = 3AC, we get BD = BE = AC, so BD = 2CM . Furthermore, ∠ABP = ∠ACP , therefore the triangles DBI and M CP are similar in ratio 2.
B

D I L A M P N K C E

It is a known fact that P A = P I = P C. Moreover, ∠N P I = ∠DBI, so that the triangles P N I and CM P are congruent. Hence ID = 2P M = 2IN ; i. e. N is the midpoint of IK. This shows that P N is the perpendicular bisector of IK, which gives P C = P K = P I. Analogously, P A = P L = P I. So P is the centre of the circle through A, K, I, L and C. Comment. Variations are possible here. One might for instance de?ne N to be the midpoint of IK and apply Ptolemy’s theorem to the quadrilateral BAP C and deduce that the triangles N P I and DBI are similar in ratio 2 to conclude that P N ⊥ IK.

Geometry

27

G2. Six points are chosen on the sides of an equilateral triangle ABC: A 1 , A2 on BC, B1 , B2 on CA, and C1 , C2 on AB, so that they are the vertices of a convex hexagon A1 A2 B1 B2 C1 C2 with equal side lengths. Prove that the lines A1 B2 , B1 C2 and C1 A2 are concurrent. First solution. Let P be the point inside triangle ABC such that the triangle A1 A2 P is equilateral. Note that A1 P C1 C2 and A1 P = C1 C2 , therefore A1 P C1 C2 is a rhombus. Similarly, A2 P B2 B1 is also a rhombus. Hence, the triangle C1 B2 P is equilateral. Let α = ∠B2 B1 A2 , β = ∠B1 A2 A1 and γ = ∠C1 C2 A1 . Then α and β are external angles of the triangle CB 1 A2 with ∠C = 60? , and hence α + β = 240? . Note also that ∠B2 P A2 = α and ∠C1 P A1 = γ. So, α + γ = 360? ? (∠C1 P B2 + ∠A1 P A2 ) = 240? . Hence, β = γ. Similarly, ∠C1 B2 B1 = β. Therefore the triangles A1 A2 B1 , B1 B2 C1 and C1 C2 A1 are congruent, which implies that the triangle A 1 B1 C1 is equilateral. This shows that B1 C2 , A1 B2 and C1 A2 are the perpendicular bisectors of A1 C1 , C1 B1 and B1 A1 ; hence the result.
A

C1 B2 C2 γ P α β B A1 A2 C B1

Second solution. Let α = ∠AC2 B2 , β = ∠AB1 C1 and K be the intersection of B1 C1 with B2 C2 . The triangles B1 B2 C1 and B2 C1 C2 are isosceles, so ∠B1 C1 B2 = β and ∠C2 B2 C1 = α. Denoting further ∠B1 C2 B2 = ? and ∠C1 B1 C2 = ψ we get (from the triangle AB1 C2 ) α + β + ? + ψ = 120? ; and (from the triangles KB1 C2 , KC1 B2 ) α + β = ? + ψ. Then α + β = 60? , ∠C1 KB2 = 120? , and so the quadrilateral

28

Geometry

AB2 KC1 is cyclic. Hence ∠KAC1 = α and ∠B2 AK = β. From KC2 = KA = KB1 and ∠B1 KC2 = 120? we get ? = ψ = 30? . In the same way, one shows that ∠B2 A1 B1 = ∠C2 B1 A1 = 30? . It follows that A1 B1 B2 C2 is a cyclic quadrilateral and since its opposite sides A 1 C2 and B1 B2 have equal lengths, it is an isosceles trapezoid. This implies that A 1 B1 and C2 B2 are parallel lines, hence ∠A1 B1 C2 = ∠B2 C2 B1 = 30? . Thus, B1 C2 bisects the angle C1 B1 A1 . Similarly, by cyclicity, C1 A2 and A1 B2 are the bisectors of the angles A1 C1 B1 and B1 A1 C1 , therefore they are concurrent.
A

B2 α β B1 β ψ K α ? C2 C1

C

A2

A1

B

Third solution. Consider the six vectors of equal lengths, with zero sum: ?? ?→ ?? ?→ ?? ?→ ?? ?→ ?? ?→ ?? ?→ u = B2 C1 , u = C1 C2 , v = C2 A1 , v = A1 A2 , w = A2 B1 , w = B1 B2 . Since u , v , w clearly add up to zero vector, the same is true of u, v, w. So u + v = ?w. The sum of two vectors of equal lengths is a vector of the same length only if they make an angle of 120? . This follows e. g. from the parallelogram interpretation of vector addition or from the law of cosines. Therefore the three lines B2 C1 , C2 A1 , A2 B1 de?ne an equilateral triangle. Consequently the “corner” triangles AC 1 B2 , BA1 C2 , CB1 A2 are similar, and in fact congruent, as B2 C1 = C2 A1 = A2 B1 . Thus the whole con?guration is invariant under rotation through 120 ? about O, the centre of the triangle ABC. In view of the equalities ∠B2 C1 C2 = ∠C2 A1 A2 and ∠A1 A2 B1 = ∠B1 B2 C1 the line B1 C2 is a symmetry axis of the hexagon A1 A2 B1 B2 C1 C2 , so it must pass through the rotation centre O. In conclusion, the three lines in question concur at O.

Geometry

29

G3. Let ABCD be a parallelogram. A variable line passing through the point A intersects the rays BC and DC at points X and Y , respectively. Let K and L be the centres of the excircles of triangles ABX and ADY , touching the sides BX and DY , respectively. Prove that the size of angle KCL does not depend on the choice of the line . First solution. Let ∠BAX = 2α, ∠DAY = 2β. The points K and L lie on the internal bisectors of the angles A in triangles ABX, ADY and on the external bisectors of their angles B and D. Taking B and D to be any points on the rays AB and AD beyond B and D, we have ∠KAB = ∠KAX = α, ∠LAD = ∠LAY = β, 1 ∠KBB = ∠BAD = α + β = ∠LDD , so ∠AKB = β, ∠ALD = α. 2 Let the bisector of angle BAD meet the circumcircle of triangle AKL at a second ?→ ? → ? ? ? → point M . The vectors BK, AM , DL are parallel and equally oriented.
A α β β α P C Y α β K X α B α+β B

D

α+β D α β

Q M

L

Since K and L lie on distinct sides of AM , we see that AKM L is a cyclic convex quadrilateral, and hence ∠M KL = ∠M AL = ∠M AD ? ∠LAD = α; likewise, ∠M LK = β.

Hence the triangles AKB, KLM , LAD are similar, so AK · LM = KB · KL and KM · LA = KL · LD. Applying Ptolemy’s theorem to the cyclic quadrilateral

30

Geometry

AKLM , we obtain AM · KL = AK · LM + KM · LA = (KB + LD) · KL, implying AM = BK + DL. The convex quadrilateral BKLD is a trapezoid. Denoting the midpoints of its sides BD and KL respectively by P and Q, we have 2 · P Q = BK + DL = AM ; ? ? → notice that the vector P Q is also parallel to the three vectors mentioned earlier, ?→ ? in particular to AM , and equally oriented. Now, P is also the midpoint of AC. It follows from the last few conclusions that Q is the midpoint of side CM in the triangle ACM . So the segments KL and CM have a common midpoint, which means that KCLM is a parallelogram. Thus, ?nally, 1 ∠KCL = ∠KM L = 180? ? (α + β) = 180? ? ∠BAD, 2 which is a constant value, depending on the parallelogram ABCD alone. Second solution. Let the line AK meet DC at E, and let the line AL meet BC at F . Denote again ∠BAX = 2α, ∠DAY = 2β. Then ∠BF A = β. Moreover, ∠KBF = (1/2)∠BAD = α + β = ∠KAF . Since the points A and B lie on the same side of the line KF , we infer that ABKF is a cyclic quadrilateral. Speaking less rigourously, the points A, K, B, F are concyclic. The points E and C lie on the lines AK and BF , and the segment EC is parallel to AB. Therefore the points E, K, C, F lie on a circle, too; this follows easily from an inspection of angles—one just has to consider three cases, according as two, one or none of the points E, C lie(s) on the same side of line KF as the segment AB does. Analogously, the points F , L, C, E lie on a circle. Clearly C, K, L are three distinct points. It follows that all ?ve points C, E, F, K, L lie on a circle ?. From the cyclic quadrilateral ABKF we have ∠BF K = ∠BAK = α, which combined with ∠BF A = β implies ∠KF A = α + β. Since the points A, F, L are in line, ∠KF L is either α + β or 180 ? ? (α + β); and since K, C, F, L are concyclic, also ∠KCL is either α + β or 180 ? ? (α + β). All that remains is to eliminate one of these two possibilities. To this e?ect, we will show that the points A and C lie on the same side of the line KL.

Geometry

31

Assume without loss of generality that Y , the point where cuts the ray DC, lies beyond C on that ray. Then so does E. If also F lies on the ray BC beyond C then ? does not penetrate the interior of ABCD. Hence the line KL does not separate A from C. And if F lies on the segment BC then L lies in the half-plane with edge BC, not containing A. Since K also lies in that half-plane, and since L lies on the opposite side of the line DC than A, this again implies that the line KL does not separate A from C. Notice that the circle ? intersects each one of the rays AK, AL at two points (K, E, resp. L, F ), possibly coinciding. Thus A lies outside this circle. Knowing that C and A lie on the same side of the line KL, we infer that ∠KCL > ∠KAL = α + β. This leaves the other possibility as the unique one: ∠KCL = 180? ? (α + β).
A β α α K X D C Y β α E ? B

β

F

L

Comment. Alternatively, continuity argument could be applied. If ∠KCL takes on only two values, it must be a constant. In our attempt to stay within the realm of classical geometry, we were forced to investigate the disposition of the points and lines in question. Notice that the ?rst solution is case-independent. Other solutions are available by calculation, be it with complex numbers or linear transformations in the coordinate plane; but no one of such approaches seems to be straightforward.

32

Geometry

G4. Let ABCD be a ?xed convex quadrilateral with BC = DA and BC not parallel to DA. Let two variable points E and F lie on the sides BC and DA, respectively, and satisfy BE = DF . The lines AC and BD meet at P , the lines BD and EF meet at Q, the lines EF and AC meet at R. Prove that the circumcircles of triangles P QR, as E and F vary, have a common point other than P . First solution. Let the perpendicular bisectors of the segments AC and BD meet at O. We show that the circumcircles of triangles P QR pass through O, which is ?xed. It follows from the equalities OA = OC, OB = OD and DA = BC that the triangles ODA and OBC are congruent. So the rotation about the point O through the angle BOD takes the point B to D and the point C to A. Since BE = DF , the same rotation takes the point E to F . This implies that OE = OF and ∠EOF = ∠BOD = ∠COA (= the angle of rotation) . These equalities imply that the isosceles triangles EOF , BOD and COA are similar.
C D X P F R

Q O E

A

B

Suppose ?rst that the three lines AB, CD and EF are not all parallel. Assume without loss of generality that the lines EF and CD meet at X. From the Menelaus theorem, applied to the triangles ACD and BCD, we obtain AR AF DX CE DX DQ = · = · = . RC F D XC EB XC QB

Geometry

33

In the case AB EF CD, the quadrilateral ABCD is an isosceles trapezoid, and E, F are the midpoints of its lateral sides. The equality AR/RC = DQ/QB is then obvious. It follows from the this equality and the similitude of triangles BOD and COA that the triangles BOQ and COR are similar. Thus ∠BQO = ∠CRO, which means that the points P , Q, R and O are concyclic. Second solution. This is just a variation of the preceding proof. As in the ?rst solution, we show that the triangles EOF , BOD and COA are similar. Denote by K, L, M the feet of the perpendiculars from the point O onto the lines EF , BD, AC, respectively. In view of the similarity just mentioned, OL OM OK = = =λ OE OB OC and ∠EOK = ∠BOL = ∠COM = ? .

Therefore the rotation about the point O through the angle ?, composed with the homothety with centre O and ratio λ, takes the points B, E, C to the points L, K, M , respectively. This implies that the points L, K, M are collinear. Hence by the theorem about the Simson line we conclude that the circumcircle of P QR passes through O. Comment. The proposer observes that (as can be seen from the above solutions) the point under discussion can also be identi?ed as the second common point of the circumcircles of triangles BCP and DAP .

34

Geometry

G5. Let ABC be an acute-angled triangle with AB = AC, let H be its orthocentre and M the midpoint of BC. Points D on AB and E on AC are such that AE = AD and D, H, E are collinear. Prove that HM is orthogonal to the common chord of the circumcircles of triangles ABC and ADE. Solution. Let O and O1 be the circumcentres of the triangles ABC and ADE, respectively. Since the radical axis of two circles is perpendicular to their line of centres, we have to prove that OO1 is parallel to HM . Consider the diameter AP of the circumcircle of ABC and let B 1 and C1 be the feet of the altitudes from B and C in the triangle ABC. Since AB ⊥ BP and AC ⊥ CP , it follows that HC BP and HB CP . Thus BP CH is a parallelogram; as a consequence, HM cuts the circle at P .
A

O1 C1 D Q B H

B1 E O

M

C

P

The triangle ADE is isosceles, so its circumcentre O 1 lies on the bisector of the angle BAC. We shall prove that the intersection Q of AO 1 with HP is the symmetric of A with respect to O1 . The rays AH and AO are isogonal conjugates, so the line AQ bisects ∠HAP . Then the bisector theorem in the triangle AHP yields QH AH = . QP AP Because ADE is an isosceles triangle, an easy angle computation shows that HD bisects ∠C1 HB. Hence the bisector theorem again gives DC1 HC1 = . DB HB

Geometry

35

Applying once more the fact that AH and AP are isogonal lines, we see that the right triangles C1 HA and CP A are similar, so AH C1 H C1 H = = ; AP CP BH the last equality holds because BP CH is a parallelogram, so that P C = BH. Summarizing, we conclude that QH DC1 = , DB QP that is, QD HC1 . In the same way we obtain QE HB1 . As a consequence, AQ is a diameter of the circumcircle of triangle ADE, implying that O 1 is the midpoint of AQ. Thus OO1 P Q; that is, OO1 is parallel to HM .

36

Geometry

G6. The median AM of a triangle ABC intersects its incircle ω at K and L. The lines through K and L parallel to BC intersect ω again at X and Y . The lines AX and AY intersect BC at P and Q. Prove that BP = CQ. First solution. Without loss of generality, one can assume the notation in the ?gure. Let ω1 be the image of ω under the homothety with centre A and ratio AM/AK. This homothety takes K to M and hence X to P , because KX BC. So ω1 is a circle through M and P inscribed in ∠BAC. Denote its points of tangency with AB and AC by U 1 and V1 , respectively. Analogously, let ω2 be the image of ω under the homothety with center A and ratio AM/AL. Then ω2 is a circle through M and Q also inscribed in ∠BAC. Let it touch AB and AC at U2 and V2 , respectively. Then U1 U2 = V1 V2 , as U1 U2 and V1 V2 are the common external tangents of ω1 and ω2 .

V1

E C V2 Y L K X A U2 D ω Q N M ω2 ω1 P B U1

2 By the power-of-a-point theorem in ω 1 and ω2 , one has BP = BU1 /BM and 2 /CM . Since BM = CM, it su?ces to show that BU = CV . CQ = CV2 1 2 Consider the second common point N of ω 1 and ω2 (M and N may coincide, in which case the “line M N ” is the common tangent). Let the line M N meet AB and AC at D and E, respectively. Clearly D is the midpoint of U 1 U2 because 2 2 DU1 = DM · DN = DU2 by the power-of-a-point theorem again. Likewise, E is the midpoint of V1 V2 . Note that B and C are on di?erent sides of DE, which

Geometry

37

reduces the problem to proving that BD = CE. Since DE is perpendicular to the line of centres of ω 1 and ω2 , we have ∠ADM = ∠AEM . Then the law of sines for triangles BDM and CEM gives BD = BM sin ∠BM D BM sin ∠BM D = , sin ∠BDM sin ∠ADM CE = CM sin ∠CM E . sin ∠AEM

Because BM = CM and ∠BM D = ∠CM E, the conclusion follows. Second solution. Let ω touch BC, CA and AB at D, E and F , respectively, and let I be the incentre of triangle ABC. The key step of this solution is the observation that the lines AM , EF and DI are concurrent.
A

K

X T E V

U F

I

Y B Q D

L M

Z P C

Indeed, suppose that EF and DI meet at T . Let the parallel through T to BC meet AB and AC at U and V , respectively. One has IT ⊥ U V , and since IE ⊥ AC, it follows that the points I, T , V and E are concyclic. Moreover, V and E lie on the same side of the line IT , so that ∠IV T = ∠IET . By symmetry, ∠IU T = ∠IF T . But ∠IET = ∠IF T , hence U V I is an isosceles triangle with altitude IT to its base U V . So T is the midpoint of U V , implying that AT meets BC at its midpoint M . Now observe that EF is the polar of A with respect to ω, therefore AK TK = . AL TL

38

Geometry

Furthermore, let LY meet AP at Z. Then KX AK = . LZ AL The line IT is the common perpendicular bisector of KX and LY . As we have shown, T lies on AM , i. e. on KL. Hence TK KX = . LY TL The last three relations show that L is the midpoint of Y Z, so M is the midpoint of P Q.

Geometry

39

G7. In an acute triangle ABC, let D, E, F , P , Q, R be the feet of perpendiculars from A, B, C, A, B, C to BC, CA, AB, EF , F D, DE, respectively. Prove that p(ABC)p(P QR) ≥ p(DEF )2 , where p(T ) denotes the perimeter of the triangle T . First solution. The points D, E and F are interior to the sides of triangle ABC which is acute-angled. It is widely known that the triangles ABC and AEF are similar. Equivalently, the lines BC and EF are antiparallel with respect to the sides of ∠A. Similar conclusions hold true for the pairs of lines CA, F D and AB, DE. This is a general property related to the feet of the altitudes in every triangle. In particular, it follows that P , Q and R are interior to the respective sides of triangle DEF . A K P F R
Q

L E

B

D

C

Let K and L be the feet of the perpendiculars from E and F to AB and AC, respectively. By the remark above, KL and EF are antiparallel with respect to the sides of the same ∠A. Therefore ∠AKL = ∠AEF = ∠ABC, meaning that KL BC. Now, EK and BQ are respective altitudes in the similar triangles AEF and DBF , so they divide the opposite sides in the same ratio: AK DQ = . KF QF This implies KQ AD. By symmetry, LR AD. Since KL is parallel to BC, it is perpendicular to AD. It follows that QR ≥ KL. From the similar triangles AKL, AEF , ABC we obtain KL AK AE EF = = cos ∠A = = . EF AE AB BC

40

Geometry

Hence QR ≥ EF 2 /BC. Likewise, P Q ≥ DE 2 /AB and RP ≥ F D 2 /CA. Therefore it su?ces to show that (AB + BC + CA) DE 2 EF 2 F D 2 + + AB BC CA ≥ (DE + EF + F A)2 ,

which is a direct consequence of the Cauchy-Schwarz inequality. Second solution. Let α = ∠A, β = ∠B, γ = ∠C. There is no loss of generality in assuming that triangle ABC has circumradius 1. The triangles AEF and ABC are similar in ratio cos α, so EF = BC cos α = sin 2α. By symmetry, F D = sin 2β, DE = sin 2γ. Next, since ∠BDF = ∠CDE = α, it follows that DQ = BD cos α = AB cos β cos α = 2 cos α cos β sin γ. Similarly, DR = 2 cos α sin β cos γ. Now the law of cosines for triangle DQR gives after short manipulation QR = sin 2α 1 ? sin 2β sin 2γ.

√ √ Likewise, RP = sin 2β 1 ? sin 2γ sin 2α, P Q = sin 2γ 1 ? sin 2α sin 2β. Therefore the given inequality is equivalent to 2 sin α sin 2α 1 ? sin 2β sin 2γ ≥ sin 2α
2

,

where Σ means a cyclic sum over α, β, γ, the angles of an acute triangle. In view of this, all trigonometric functions below are positive. To eliminate the square roots, observe that 1 ? sin 2β sin 2γ = sin2 (β ? γ) + cos2 α ≥ cos2 α. Hence it su?ces to establish 2 sin α sin 2α cos α ≥ ( sin 2α)2 . This is yet another immediate consequence of the Cauchy-Schwarz inequality: 2 sin α sin 2α cos α ≥ √ √ 2 sin α sin 2α cos α
2

=

sin 2α

2

.

Third solution. A stronger conclusion is true, namely: p(ABC) p(DEF ) ≥2≥ . p(DEF ) p(P QR) The left inequality is a known fact, so we consider only the right one.

Geometry

41

It is immediate that the points A, B and C are the excentres of triangle DEF . Therefore P , Q and R are the tangency points of the excircles of this triangle with its sides. For the sake of clarity, let us adopt the notation a = EF , b = F D, c = DE, α = ∠D, β = ∠E, γ = ∠F now for the sides and angles of triangle DEF . Also, let s = (a+b+c)/2. Then ER = F Q = s ? a, F P = DR = s ? b, DQ = EP = s ? c. Now we regard the line DE as an axis by choosing the direction from D to E as the positive direction. The signed length of a line segment U V on this axis will be denoted by U V . Let X and Y be the orthogonal projections onto DE of P and Q, respectively. On one hand, DE = DY + Y X + XE. On the other hand, DY = DQ cos α, XE = EP cos β. Observe that these inequalities hold true in all cases, regardless of whether or not α and β are acute. Finally, it is clear that Y X ≤ P Q. In conclusion, DE = (s ? c)(cos α + cos β) + Y X ≤ (s ? c)(cos α + cos β) + P Q. By symmetry, EF ≤ (s ? a)(cos β + cos γ) + QR, F D ≤ (s ? b)(cos γ + cos α) + RP.

Adding up yields p(DEF ) ≤ (s ? c)(cos α + cos β) + p(P QR), where again Σ denotes a cyclic sum over α, β, γ. This sum is equal to a cos α + b cos β + c cos γ, since (s ? b) + (s ? c) = a, (s ? c) + (s ? a) = b, (s ? a) + (s ? b) = c. Now it su?ces to show that a cos α + b cos β + c cos γ ≤ (1/2)p(DEF ). Suppose that a ≤ b ≤ c; then cos α ≥ cos β ≥ cos γ, so one can apply Chebyshev’s inequality to the triples (a, b, c) and (cos α, cos β, cos γ). This gives a cos α + b cos β + c cos γ ≤ 1 (a + b + c)(cos α + cos β + cos γ). 3

But cos α + cos β + cos γ ≤ 3/2 for every triangle, and the result follows. Comment. This last solution shows that the proposed inequality splits into two independent ones, which can be expressed in words: In every triangle, the perimeter of its orthic triangle is not greater than half the perimeter of the triangle itself, and the perimeter of its Nagel triangle is not smaller than half the perimeter of the triangle itself. Whereas the ?rst of these inequalities is indeed a very well-known fact, this seems not to be the case with the second one.

42

Number Theory

Number Theory
N1. Determine all positive integers relatively prime to all terms of the in?nite sequence an = 2n + 3n + 6n ? 1 (n = 1, 2, 3, . . . ). Solution. We claim that 1 is the only such number. This amounts to showing that every prime p is a divisor of a certain a n . This is true for p = 2 and p = 3 as a2 = 48. Fix a prime p > 3. All congruences that follow are considered modulo p. By Fermat’s little theorem, one has 2p?1 ≡ 1, 3p?1 ≡ 1, 6p?1 ≡ 1. Then the evident congruence 3 + 2 + 1 ≡ 6 can be written as 3 · 2p?1 + 2 · 3p?1 + 6p?1 ≡ 6, or 6 · 2p?2 + 6 · 3p?2 + 6 · 6p?2 ≡ 6.

Simplifying by 6 shows that ap?2 = 2p?2 + 3p?2 + 6p?2 ? 1 is divisible by p, and the proof is complete.

Number Theory

43

N2. Let a1 , a2 , . . . be a sequence of integers with in?nitely many positive and in?nitely many negative terms. Suppose that for every positive integer M the numbers a1 , a2 , . . . , aM leave di?erent remainders upon division by M . Prove that every integer occurs exactly once in the sequence a 1 , a2 , . . . . Solution. The hypothesis of the problem can be reformulated by saying that for every positive integer M the numbers a 1 , a2 , . . . , aM form a complete system of residue classes modulo M . Note that if i < j then a i = aj , otherwise the set {a1 , . . . , aj } would contain at most j ?1 distinct residues modulo j. Furthermore, if i < j ≤ n, then |ai ?aj | ≤ n?1, for if m = |ai ?aj | ≥ n, then the set {a1 , . . . , am } would contain two numbers congruent modulo m, which is impossible. Given any n ≥ 1, let i(n), j(n) be the indices such that a i(n) , aj(n) are respectively the smallest and the largest number among a 1 , . . . , an . The above arguments show that |ai(n) ? aj(n) | = n ? 1, therefore the set {a1 , . . . , an } consists of all integers between ai(n) and aj(n) . Now let x be an arbitrary integer. Since a k < 0 for in?nitely many k and the terms of the sequence are distinct, we conclude that there exists i such that ai < x. By a similar argument, there exists j such that x < a j . Hence, if n > max{i, j}, we conclude that every number between a i and aj (x in particular) is in {a1 , . . . , an }. Comment. Proving that for every M the set {a 1 , . . . , aM } is a block of consecutive integers can be also achieved by induction.

44

Number Theory

N3. Let a, b, c, d, e and f be positive integers. Suppose that the sum S = a + b + c + d + e + f divides both abc + def and ab + bc + ca ? de ? ef ? f d. Prove that S is composite. Solution. By hypothesis, all coe?cients of the quadratic polynomial f (x) = (x + a)(x + b)(x + c) ? (x ? d)(x ? e)(x ? f )

= Sx2 + (ab + bc + ca ? de ? ef ? f d)x + (abc + def )

are multiples of S. Evaluating f at d we get that f (d) = (a + d)(b + d)(c + d) is a multiple of S. This readily implies that S is composite because each of a+d, b+d and c + d is less than S.

Number Theory

45

N4. Find all positive integers n > 1 for which there exists a unique integer a with 0 < a ≤ n! such that an + 1 is divisible by n! . Solution. The answer is “n is prime.” If n = 2, the only solution is a = 1. If n > 2 is even, then a n is a square, therefore an + 1 is congruent to 1 or 2 modulo 4, while n! is divisible by 4. So there is no appropriate a in this case. From now on, n is odd. Assume that n = p is a prime and that p! | a p + 1 for some a, 0 < a ≤ p!. By Fermat’s little theorem, a p + 1 ≡ a + 1 (mod p). So, if p does not divide a + 1, then ap?1 + · · · + a + 1 = (ap + 1)/(a + 1) ≡ 1 (mod p), which is a contradiction. Thus, p | a + 1. We shall show that (ap + 1)/(a + 1) has no prime divisors q < p. This will be enough to deduce the uniqueness of a. Indeed, the relation (p ? 1)! | (a + 1) ap + 1 a+1

forces (p ? 1)! | a + 1. Combined with p | a + 1, this leads to p! | a + 1, and hence showing a = p! ? 1. Suppose on the contrary that q | (ap + 1)/(a + 1), where q < p is prime. Note that q is odd. We get ap ≡ ?1 (mod q), therefore a2p ≡ 1 (mod q). Clearly, q is coprime to a, so aq?1 ≡ 1 (mod q). Writing d = gcd(q ? 1, 2p), we obtain ad ≡ 1 (mod q). Since q < p, we have d = 2. Hence, a ≡ ±1 (mod q). The case a ≡ 1 (mod q) gives (ap + 1)/(a + 1) ≡ 1 (mod q), which is impossible. The case a ≡ ?1 (mod q) gives ap + 1 a+1 ≡ ap?1 ? ap?2 + · · · + 1 ≡ (?1)p?1 ? (?1)p?2 + · · · + 1 ≡ p (mod q), leading to q | p which is not possible as q < p. So, we see that primes ful?ll the conditions under discussion. It remains to deal with the case when n is odd and composite. Let p < n be the least prime divisor of n. Let pα be the highest power of p which divides n!. Since 2p < p2 ≤ n, we have n! = 1 . . . p . . . (2p) . . . , so α ≥ 2. Write m = n!/p α , and take any integer a satisfying a ≡ ?1 mod pα?1 m . Write a = ?1 + pα?1 k. Then ap = (?1 + pα?1 k)p = ?1 + pα k + pα
p

(1)

(?1)p?j
j=2

p j(α?1) j p k = ?1 + pα M, j

46

Number Theory

where M is an integer because j(α ? 1) ≥ α for all j ≥ 2 and α ≥ 2. Thus p α divides ap + 1, and hence also an + 1, because p | n and n is odd. Furthermore, m too is a divisor of a + 1, and hence of a n + 1. Since m is coprime to p, (an + 1)/n! is an integer for all a satisfying congruence (1). Since it is clear that there are p > 2 integers in the interval [1, n!] satisfying (1), we conclude that composite values of n do not satisfy the condition given in the problem. Comment. The fact that no prime divisor of (a p + 1)/(a + 1) is smaller than p is not a mere curiosity. More is true and can be deduced easily from the above proof, namely that if q is a prime factor of the above number, then either q = p (and this happens if and only if p | a + 1) or q ≡ 1 (mod p).

Number Theory

47

N5. Denote by d(n) the number of divisors of the positive integer n. A positive integer n is called highly divisible if d(n) > d(m) for all positive integers m < n. Two highly divisible integers m and n with m < n are called consecutive if there exists no highly divisible integer s satisfying m < s < n. (a) Show that there are only ?nitely many pairs of consecutive highly divisible integers of the form (a, b) with a | b. (b) Show that for every prime number p there exist in?nitely many positive highly divisible integers r such that pr is also highly divisible. Solution. This problem requires an analysis of the structure of the highly divisible integers. Recall that if n has prime factorization n=
pαp (n) ||n

pαp (n) ,

where p stands for a prime, then d(n) = pαp ||n (αp (n) + 1). Let us start by noting that since d(n) takes arbitrarily large values (think of d(m!), for example, for arbitrary large m’s), there exist in?nitely many highly divisible integers. Furthermore, it is easy to see that if n is highly divisible and n = 2α2 (n) 3α3 (n) . . . pαp (n) , then α2 (n) ≥ · · · ≥ αp (n). Thus, if q < p are primes and p | n, then q | n. We show that for every prime p all but ?nitely many highly divisible integers are multiples of p. This is obviously so for p = 2. Assume that this were not so, that p is the rth prime (r > 1), and that n is one of the in?nitely many highly divisible integers whose largest prime factor is less than p. For such an n, (α2 (n) + 1)r?1 ≥ d(n), therefore α2 (n) takes arbitrarily large values. Let n be such that 2α2 (n)?1 > p2 and look at m = np/2 α2 (n)/2 . Clearly, m < n, while d(m) = 2d(n) α2 (n) ? α2 (n)/2 + 1 > d(n) α2 (n) + 1

contradicting the fact that n is highly divisible. We now show a stronger property, namely that for any prime p and constant κ, there are only ?nitely many highly divisible positive integers n such that αp (n) ≤ κ. Indeed, assume that this were not so. Let κ be a constant such that αp (n) ≤ κ for in?nitely many highly divisible n. Let q be a large prime satisfying q > p2κ+1 . All but ?nitely many such positive integers n are multiples of q. Look at the number m = pαp (n)αq (n)+αp (n)+αq (n) n/q αq (n) . An immediate calculation shows that d(m) = d(n), therefore m > n. Thus, p2αp (n)αq (n)+αq (n) ≥ pαp (n)αq (n)+αq (n)+αp (n) > q αq (n) ,

48

Number Theory

giving p2αp (n)+1 > q > p2κ+1 , and we get a contradiction with the fact that αp (n) ≤ κ. We are now ready to prove both (a) and (b). For (a), let n be highly divisible and such that α3 (n) ≥ 8. All but ?nitely many highly divisible integers n have this property. Now 8n/9 is an integer and 8n/9 < n, therefore d(8n/9) < d(n). This implies (α2 (n) + 4)(α3 (n) ? 1) < (α2 (n) + 1)(α3 (n) + 1), which is equivalent to 3α3 (n) ? 5 < 2α2 (n). (1) Assume now that n | m are consecutive and highly divisible. Since already d(2n) > d(n), we get that there must be a highly divisible integer in (n, 2n]. Thus m = 2n, leading to d(3n/2) ≤ d(n) (or else there must be a highly divisible number between n and 3n/2). This gives α2 (n)(α3 (n) + 2) ≤ (α2 (n) + 1)(α3 (n) + 1), which is equivalent to α2 (n) ≤ α3 (n) + 1, which together with α3 (n) ≥ 8 contradicts inequality (1). This proves (a). For part (b), let k be any positive integer and look at the smallest highly divisible positive integer n such that α p (n) ≥ k. All but ?nitely many highly divisible integers n satisfy this last inequality. We claim that n/p is also highly divisible. If this were not so, then there would exist a highly divisible positive integer m < n/p with d(m) ≥ d(n/p). Note that, by assumption, α p (m) < αp (n). Then, αp (n) + 1 αp (m) + 2 ≥ d(n/p) = d(n), d(mp) = d(m) αp (m) + 1 αp (n) where for the above inequality we used the fact that the function (x + 1)/x is decreasing. However, mp < n, so the above inequality contradicts the fact that n is highly divisible. This contradiction shows that n/p is highly divisible, and since k can be taken to be arbitrarily large, we get in?nitely many examples of highly divisible integers n such that n/p is also highly divisible. Comment. The notion of a highly divisible integer ?rst appeared in a paper of Ramanujan in 1915. Eric Weinstein’s World of Mathematics has one web page mentioning some properties of these numbers (called highly composite) and giving some bibliographical references, while Ross Honsberger’s Mathematical

Number Theory

49

Gems (Third Edition) has a chapter dedicated to them. In spite of all these references, the properties of these numbers mentioned in the above sources have little relevance for the problem at hand and we believe that if given to the exam, the students who have seen these numbers before will not have any signi?cant advantage over the ones who encounter them for the ?rst time.

50

Number Theory

N6. Let a and b be positive integers such that a n + n divides bn + n for every positive integer n. Show that a = b. Solution. Assume that b = a. Taking n = 1 shows that a + 1 divides b + 1, so that b ≥ a. Let p > b be a prime and let n be a positive integer such that n ≡ 1 (mod p ? 1) and n ≡ ?a (mod p).

Such an n exists by the Chinese remainder theorem. (Without the Chinese remainder theorem, one could notice that n = (a + 1)(p ? 1) + 1 has this property.) By Fermat’s little theorem, an = a(ap?1 · · · ap?1 ) ≡ a (mod p), and therefore n + n ≡ 0 (mod p). So p divides the number a n + n, hence also bn + n. However, a by Fermat’s little theorem again, we have analogously b n + n ≡ b ? a (mod p). We are therefore led to the conclusion p | b ? a, which is a contradiction. Comment. The ?rst thing coming to mind is to show that a and b share the same prime divisors. This is easily established by using Fermat’s little theorem or Wilson’s theorem. However, we know of no solution which uses this fact in any meaningful way. For the conclusion to remain true, it is not su?cient that a n + n | bn + n holds for in?nitely many n. Indeed, take a = 1 and any b > 1. The given divisibility relation holds for all positive integers n of the form p ? 1, where p > b is a prime, but a = b.

Number Theory

51

N7. Let P (x) = an xn + an?1 xn?1 + · · · + a0 , where a0 , . . . , an are integers, an > 0, n ≥ 2. Prove that there exists a positive integer m such that P (m!) is a composite number. Solution. We may assume that a0 = ±1, otherwise the conclusion is immediate. Observe that if p > k ≥ 1 and p is a prime then where t?1 denotes the multiplicative inverse (mod p) of t. Indeed, this is proved by writing (p ? 1)! = (p ? k)![p ? (k ? 1)][p ? (k ? 2)] · · · (p ? 1), reducing modulo p and using Wilson’s theorem. With (1) in mind, we see that it might be worth looking at the rational numbers P (?1)k (k ? 1)! = (?1)kn Q((?1)k (k ? 1)!), ((k ? 1)!)n (p ? k)! ≡ (?1)k ((k ? 1)!)?1 (mod p), (1)

where Q(x) = an + an?1 x + · · · + a0 xn . If k ? 1 > a2 , then an | (k ? 1)! and (k ? 1)!/an = 1 · 2 · · · (a2 /an ) · · · (k ? 1) n n is divisible by all primes ≤ k ? 1. Hence, for such k we have Q((k ? 1)!) = a n bk , where bk = 1 + an?1 (k ? 1)!/an + · · · has no prime factors ≤ k ? 1. Clearly, Q(x) is not a constant polynomial, because its leading term is a 0 = ±1. Therefore |Q((k ? 1)!)| becomes arbitrarily large when k is large, and so does |b k |. In particular, |bk | > 1 if k is large enough. Take such an even k and choose any prime factor p of b k . The above argument, combined with (1), shows that p > k and that P ((p ? k)!) ≡ 0 (mod p). In order to complete the proof, we only need to ensure that k can be chosen so that |P ((p ? k)!)| > p. We do not know p, but we know that p ≥ k. Our best bet is to take k such that the ?rst possible prime following k is “far away” from it; i. e., p?k is large. For this, we may choose k = m!, where m = q?1 > 2 and q is a prime. Then m! is composite, m!+1 is also composite (because m!+1 > m+1 = q and m! + 1 is a multiple of q by Wilson’s theorem), and m! + is also composite for all = 2, . . . , m. So, p = m! + m + t for some t ≥ 1, therefore p ? k = m + t. For large m, (m + t)! , P ((p ? k)!) = P ((m + t)!) > 2 because an > 0. So it su?ces to observe that (m + t)! > m! + m + t, 2 which is obviously true for m large enough and t ≥ 1.