42nd International Mathematical Olympiad

Washington, DC, United States of America
July 8–9, 2001

Problems

Each problem is worth seven points.

Let A  B  C be an acute-angled triangle with circumcentre O. Let P on B  C be the foot of the altitude from A.

Suppose that ∠  B  C  
          A ≥ ∠  A  B  C + (30^◦).

Prove that ∠  C  A  B + ∠  C  O  
            P < (90^◦).

Prove that

(a/(Sqrt[(a^2) + 8  b  c])) + (b/(Sqrt[(b^2) + 8  c  a])) + 
        (c/(Sqrt[(c^2) + 8  a  b])) ≥ 1

for all positive real numbers a, b and c.

Twenty-one girls and twenty-one boys took part in a mathematical contest.

Prove that there was a problem that was solved by at least three girls and at least three boys.

Let n be an odd integer greater than 1, and let (Subscript[k, 1]), (Subscript[k, 2]), …, (Subscript[k, n]) be given integers. For each of the n! permutations a = ((Subscript[a, 1]), (Subscript[a, 2]), …, (Subscript[a, n])) of 1, 2, …, n, let

S(a)=(∑_(i = 1)^n)(Subscript[k, i])(Subscript[a, i]).

Prove that there are two permutations b and c, b ≠ c, such that n! is a divisor of S(b) - S(c).

In a triangle A  B  C, let A  P bisect ∠  B  A  C, with P on B  C, and let B  Q bisect ∠  A  B  C, with Q on C  A.

It is known that ∠  B  A  C = (60^◦) and that A  B + B  P = A  Q + Q  B.

What are the possible angles of triangle A  B  C?

Let a, b, c, d be integers with a > b > c > d > 0. Suppose that

a  c + 
        b  d = (b + d + a - 
            c) (b + d - a + c).

Prove that a  b + c  d is not prime.

Problems with Solutions

Let A  B  C be an acute-angled triangle with circumcentre O. Let P on B  C be the foot of the altitude from A.

Suppose that ∠  B  C  
          A ≥ ∠  A  B  C + (30^◦).

Prove that ∠  C  A  B + ∠  C  O  
            P < (90^◦).

Solution 1

Let α = ∠  C  A  B, β = ∠  A  B  C, γ = ∠  B  C  A, and δ = ∠  C  O  P. Let K and Q be the reflections of A and P, respectively, across the perpendicular bisector of B  C. Let R denote the circumradius of △  A  B  C. Then O  A = O  B = O  C = O  K = R. Furthermore, we have Q  P = K  A because K  Q  P  A is a rectangle. Now note that ∠  A  O  
          K = ∠  A  O  B - ∠  K  O  
              B = ∠  A  O  B - ∠  A  O  C = 
            2  γ - 2  β ≥ 
              (60^◦).

It follows from this and from O  A = O  K = R that K  A ≥ R and Q  P ≥ R. Therefore, using the Triangle Inequality, we have O  P + R = O  Q + O  C > Q  C = 
          Q  P + P  C ≥ R + P  C. It follows that O  P > P  C, and hence in △  C  O  P, ∠  P  C  O > δ. Now since α = (1/2) ∠  B  O  
            C = (1/2) ((180^◦) - 
                  2  ∠  P  C  O) = 
            (90^◦) - ∠  P  C  O, it indeed follows that α + δ < (90^◦).

Solution 2

As in the previous solution, it is enough to show that O  P > P  C. To this end, recall that by the (Extended) Law of Sines, A  B = 2  R  sin  γ and A  C = 2  R  sin  β. Therefore, we have

BP-PC=ABcosβ - 
            A  C  cos  γ = 2  R(
                sin  γ  cos  β - 
                  sin  β  cos  γ) = 
            2  R  sin(γ - β).

It follows from this and from

\(TraditionalForm\`30\^◦ ≤ γ - β < γ < 90\^◦\)

that B  P - P  C ≥ R. Therefore, we obtain that R + O  P = 
        B  O + O  P > B  P ≥ R + P  C, from which O  P > O  C, as desired.

Solution 3

We first show that (R^2) > C  P·C  B. To this end, since C  B = 2  R  sin  α and C  P = A  C  cos  γ = 
          2  R  sin  β  cos  γ, it suffices to show that (1/4) > 
        sin  α  sin  β  cos  γ. We note that 1 > sin  α = sin(γ + β) = 
          sin  γ  cos  β + sin  β  cos  γ and (1/2) ≤ sin(γ - β) = 
        sin  γ  cos  β - sin  β  cos  γ since \(TraditionalForm\`30\^◦ ≤ γ - β < 90\^◦\). It follows that (1/4) > sin  β  cos  γ and that (1/4) > 
        sin  α  sin  β  cos  γ.

Now we choose a point J on B  C so that C  J·C  P = (R^2). It follows from this and from (R^2) > C  P·C  B that C  J > C  B, so that ∠  O  B  C > ∠  O  J  C. Since O  C/C  J = P  C/C  O and ∠  J  C  O = ∠  O  C  P, we have △  J  C  
          O ≅ △  O  C  P and ∠  O  J  
          C = ∠  P  O  C = δ. It follows that δ < ∠  O  B  C = 
        (90^◦) - α or α + δ < (90^◦).

Solution 4

On the one hand, as in the third solution, we have (R^2) > C  P·C  B. On the other hand, the power of P with respect to the circumcircle of △  A  B  C is B  P·P  C = (R^2) - O  (P^2). From these two equations we find that

O 
         (P^2) = (R^2) - B  P·P  C > 
          P  C·C  B - B  P·P  C = 
        P  (C^2),

from which O  P > P  C. Therefore, as in the first solution, we conclude that α + δ < (90^◦).

Prove that

(a/(Sqrt[(a^2) + 8  b  c])) + (b/(Sqrt[(b^2) + 8  c  a])) + 
        (c/(Sqrt[(c^2) + 8  a  b])) ≥ 1

for all positive real numbers a, b and c.

First we shall prove that

(a/(Sqrt[(a^2) + 8  b  c])) ≥ 
      ((a^((4/3)))/((a^((4/3))) + (b^((4/3))) + (c^((4/3))))),

or equivalently, that

\(TraditionalForm\`\((a\^\(4\/3\) + b\^\(4\/3\) + c\^\(4\/3\))\)\^2 ≥ \(\(\(a\^\(2\/3\)\)(
          a\^2 + 8  b  c)\)\(.\)\)\)

The AM-GM inequality yields

({{\(TraditionalForm\`\((a\^\(4\/3\) + b\^\(4\/3\) + c\^\(4\/3\))\)\^2 - \((a\^\(4\/3\))\)\^2\) ,  =  , ((b^((4/3))) + 
                        (c^((4/3)))) ((a^((4/3))) + (a^((4/3))) + 
                        (b^((4/3))) + (c^((4/3)))) }, {,  ≥  , 2  (b^((2/3))) 
                    (c^((2/3)))·4  (a^((2/3))) (b^((1/3))) 
                    (c^((1/3))) }, {,  =  , 8  (a^((2/3))) 
                  b  c.}})

Thus

({{\(TraditionalForm\`\((a\^\(4\/3\) + b\^\(4\/3\) + c\^\(4\/3\))\)\^2\) ,  ≥  , ((((a^((4/3)))))^2) + 
                    8  (a^((2/3))) b  c }, {,  =  , (a^((2/3)))(
                    (a^2) + 8  b  c), }})

so

(a/(Sqrt[(a^2) + 8  b  c])) ≥ 
      ((a^((4/3)))/((a^((4/3))) + (b^((4/3))) + (c^((4/3))).))

Similarly, we have

({{(b/(Sqrt[(b^2) + 8  c  a])) ,  ≥  , \(TraditionalForm\`b\^\(4\/3\)\/\(a\^\(4\/3\) + b\^\(4\/3\) + c\^\(4\/3\)\)\)   and}, {(c/(Sqrt[(c^2) + 8  a  b])) ,  ≥  , ((c^((4/3)))/((a^((4/3))) + 
                          (b^((4/3))) + (c^((4/3))))). }})

Adding these three inequalities yields

(a/(Sqrt[(a^2) + 8  b  c])) + (b/(Sqrt[(b^2) + 8  c  a])) + 
        (c/(Sqrt[(c^2) + 8  a  b])) ≥ 1.

Comment. It can be shown that for any a, b, c > 0 and λ ≥ 8, the following inequality holds:

(a/(Sqrt[(a^2) + λ  b  c])) + 
        (b/(Sqrt[(b^2) + λ  c  a])) + 
        (c/(Sqrt[(c^2) + λ  a  b])) ≥ 
      (3/((Sqrt[1 + λ]).))

Twenty-one girls and twenty-one boys took part in a mathematical contest.

Prove that there was a problem that was solved by at least three girls and at least three boys.

Solution 1

We introduce the following symbols: G is the set of girls at the competition and B is the set of boys, P is the set of problems, P(g) is the set of problems solved by g ∈ G, and P(b) is the set of problems solved by b ∈ B. Finally, G(p) is the set of girls that solve p ∈ P and B(p) is the set of boys that solve p. In terms of this notation, we have that for all g ∈ G and b ∈ B,

\(TraditionalForm\`\((a)\)\ \  | 
      P(g) | \(\(≤\)\(6 \(\(,\)\(\ \)\)\)\) | 
      P(b) | \(\(≤\)\(6 \(\(,\)\(\ \ \ \ \)\) \((b)\)\ \ \(P(g)\) ⋂ 
          P(b)\)\(≠\)\(\(⌀\)\(.\)\)\)\)

We wish to prove that some p ∈ P satisfies |G(
          p)|≥3 and |B(
          p)|≥3. To do this, we shall assume the contrary and reach a contradiction by counting (two ways) all ordered triples (p, q, r) such that p ∈ P(g) ⋂ P(b). With T = {(p, g, b) :  p ∈ 
            P(g) ⋂ P(b)}, condition (b) yields

|T|=(∑_(g ∈ G))(∑_(b ∈ B))|P(g)⋂P(b)|≥|G|·|B|=(21^2).

Assume that no p ∈ P satisfies |G(
          p)|≥3 and |B(
          p)|≥3. We begin by noting that

(∑_(p ∈ P))|G(p)|=(∑_(g ∈ G))|P(g)|≤6|G|    and    (∑_(p ∈ P))|B(p)|≤6|B|.

(Note. The equality in (2) is obtained by a standard double-counting technique: Let χ(g, p) = 1 if g solves p and χ(g, p) = 0 otherwise, and interchange the orders of summation in (∑_(p ∈ P))(∑_(g ∈ G))χ(g, p).) Let

\(TraditionalForm\`\(P\_+\) = {p ∈ 
            P \(\(:\)\(\ \)\) | 
          G(p) | \(\(≥\)\(3\)\)}, 
\(P\_-\) = \(\({p ∈ P \(\(:\)\(\ \)\) | 
            G(p) | \(\(≤\)\(2\)\)}\)\(.\)\)\)

Claim. (∑_(\(p ∈ \(P\_-\)\)))|G(p)|≥|G|; thus (∑_(\(p ∈ \(P\_+\)\)))|G(p)|≤5|G|. Also (∑_(\(p ∈ \(P\_+\)\)))|B(p)|≥|B|; thus (∑_(\(p ∈ \(P\_-\)\)))\(\(|\)\(B(
              p)\)\(|\)\(\(≤\)\(5\)\)\(|\)\(B\)\(|\)\).

Proof. Let g ∈ G be arbitrary. By the Pigeonhole Principle, conditions (a) and (b) imply that g solves some problem p that is solved by at least ⌈21/6⌉ = 4 boys. By assumption, |B(
          p)|≥4 implies that \(TraditionalForm\`p ∈ \(P\_-\)\), so every girl solves at least one problem in \(TraditionalForm\`\(P\_-\)\). Thus

(∑_(\(p ∈ \(P\_-\)\)))|G(p)|≥|G|.

In view of (2) and (3) we have

(∑_(\(p ∈ \(P\_+\)\)))|G(p)|=(∑_(p ∈ P))|G(p)|-(∑_(\(p ∈ \(P\_-\)\)))|G(p)|≤5|G|.

Also, each boy solves a problem that is solved by at least four girls, so each boy solves a problem \(TraditionalForm\`p ∈ \(P\_+\)\). Thus (∑_(\(p ∈ \(P\_+\)\)))|B(p)|≥|B|, and the calculation proceeds as before using (2). □ 
Using the claim just established, we find

({{\(TraditionalForm\`\(\(|\)\(T\)\(|\)\)\) ,  = , (∑_(p ∈ P))|G(p)|·|B(p)| }, {,  = , (∑_(\(p ∈ \(P\_+\)\)))|G(p)|·|B(p)|+(∑_(\(p ∈ \(P\_-\)\)))|G(p)|·|B(p)| }, {,  ≤ , 2(∑_(\(p ∈ \(P\_+\)\)))|G(p)|+2(∑_(\(p ∈ \(P\_-\)\)))|B(p)| }, {,  ≤ , 10 | 
                    G | +10 | 
                    B |  = 20·21. }})

This contradicts (1), so the proof is complete.

Solution 2

Let us use some of the notation given in the first solution. Suppose that for every p ∈ P either |G(
          p)|≤2 or |B(
          p)|≤2. For each p ∈ P, color p red if |G(
          p)|≤2 and otherwise color it black. In this way, if p is red then |G(
          p)|≤2 and if p is black then |B(
          p)|≤2. Consider a chessboard with 21 rows, each representing one of the girls, and 21 columns, each representing one of the boys. For each g ∈ G and b ∈ B, color the square corresponding to (g, b) as follows: pick p ∈ P(g) ⋂ P(b) and assign p's color to that square. (By condition (b), there is always an available choice.) By the Pigeonhole Principle, one of the two colors is assigned to at least ⌈441/2⌉ = 221 squares, and thus some row has at least ⌈221/21⌉ = 11 black squares or some column has at least 11 red squares. 
Suppose the row corresponding to g ∈ G has at least 11 black squares. Then for each of 11 squares, the black problem that was chosen in assigning the color was solved by at most 2 boys. Thus we account for at least ⌈11/2⌉ = 6 distinct problems solved by g. In view of condition (a), g solves only these problems. But then at most 12 boys solve a problem also solved by g, in violation of condition (b). 
In exactly the same way, a contradiction is reached if we suppose that some column has at least 11 red squares. Hence some p ∈ P satisfies |G(
          p)|≥3 and |B(
          p)|≥3.

Let n be an odd integer greater than 1, and let (Subscript[k, 1]), (Subscript[k, 2]), …, (Subscript[k, n]) be given integers. For each of the n! permutations a = ((Subscript[a, 1]), (Subscript[a, 2]), …, (Subscript[a, n])) of 1, 2, …, n, let

S(a)=(∑_(i = 1)^n)(Subscript[k, i])(Subscript[a, i]).

Prove that there are two permutations b and c, b ≠ c, such that n! is a divisor of S(b) - S(c).

Let ∑S(a) be the sum of S(a) over all n! permutations a = ((Subscript[a, 1]), (Subscript[a, 2]), …, (Subscript[a, n])). We compute  ∑S(a) mod n! two ways, one of which depends on the desired conclusion being false, and reach a contradiction when n is odd. 
First way. In ∑S(a), (Subscript[k, 1]) is multiplied by each i ∈ {1, …, n} a total of (n - 1)! times, once for each permutation of {1, …, n} in which (Subscript[a, 1]) = i. Thus the coefficient of (Subscript[k, 1]) in ∑S(a) is

(n - 1)! (1 + 2 + ⋯ + 
            n) = (n + 1)!/2.

The same is true for all (Subscript[k, i]), so

∑S(a)=(((n + 1)!)/2)(∑_(i = 1)^n)(Subscript[k, i]).

Second way. If n! is not a divisor of S(b) - S(c) for any b ≠ c, then each S(a) must have a different remainder mod n!. Since there are n! permutations, these remainders must be precisely the numbers 0, 1, 2, …, n! - 1. Thus

∑S(
          a) ≡ (((n! - 1) n!)/2) 
        mod n!.

Combining (1) and (2), we get

(((n + 1)!)/2)(∑_(i = 1)^n)(Subscript[k, i])≡(((n! - 1) n!)/2) 
          mod n!.

Now, for n odd, the left side of (3) is congruent to 0 modulo n!, while for n > 1 the right side is not congruent to 0 (n! - 1 is odd). For n > 1 and odd, we have a contradiction.

In a triangle A  B  C, let A  P bisect ∠  B  A  C, with P on B  C, and let B  Q bisect ∠  A  B  C, with Q on C  A.

It is known that ∠  B  A  C = (60^◦) and that A  B + B  P = A  Q + Q  B.

What are the possible angles of triangle A  B  C?

Denote the angles of A  B  C by α = (60^◦), β, and γ. Extend A  B to (P^′) so that B  (P^′) = B  P, and construct (P^′)′ on A  Q so that A  (P^′)′ = A  (P^′). Then B  (P^′) P is an isosceles triangle with base angle β/2. Since A  Q + 
          Q  (P^′)′ = A  B + B  (P^′) = A  B + B  P = 
            A  Q + Q  B, it follows that Q  (P^′)′ = Q  B. Since A  (P^′) (P^′)′ is equilateral and A  P bisects the angle at A, we have P  (P^′) = P  (P^′)′.

Claim. Points B, P, (P^′)′ are collinear, so (P^′)′ coincides with C.

Proof. Suppose to the contrary that B  P  (P^′)′ is a nondegenerate triangle. We have that ∠  P  B  
          Q = ∠  P  (P^′) 
            B = ∠  P  (P^′)′ Q = β/2. Thus the diagram appears as below, or else with P is on the other side of B  (P^′)′. In either case, the assumption that B  P  (P^′)′ is nondegenerate leads to B  P = P  (P^′)′ = 
          P  (P^′), thus to the conclusion that B  P  (P^′) is equilateral, and finally to the absurdity β/2 = (60^◦) so α + β = (60^◦) + 
            (120^◦) = (180^◦).

Thus points B, P, (P^′)′ are collinear, and (P^′)′ = C as claimed.□

Since triangle B  C  Q is isosceles, we have \(TraditionalForm\`120\^◦ - β = \(γ = β/2\)\), so β = (80^◦) and γ = (40^◦). Thus A  B  C is a 60-80-40 degree triangle.

Let a, b, c, d be integers with a > b > c > d > 0. Suppose that

a  c + 
        b  d = (b + d + a - 
            c) (b + d - a + c).

Prove that a  b + c  d is not prime.

Solution 1

Suppose to the contrary that a  b + c  d is prime. Note that

a  b + c  d = (a + d) c + (b - c) a = 
        m·gcd (a + d, b - c)

for some positive integer m. By assumption, either m = 1 or gcd(a + d, b - c) = 1. We consider these alternatives in turn. 
Case (i): m = 1. Then

({{gcd(a + d, b - c) ,  =  , a  b + c  d > 
                    a  b + c  d - (a - b + c + d) }, {,  =  , (a + d) (c - 1) + (b - 
                          c) (a + 1) }, {,  ≥  , gcd(a + d, b - c),}})

which is false. 
Case (ii): gcd(a + d, b - c) = 1. Substituting a  c + b  d = (a + d) b - (b - c) a for the left-hand side of a  c + 
          b  d = (b + d + a - c) (b + d - a + c), we obtain

(a + d) (a - c - d) = (b - 
            c) (b + c + d).

In view of this, there exists a positive integer k such that

({{a - c - d ,  =  , k(b - c), }, {b + c + d ,  =  , k(a + d).}})

Adding these equations, we obtain a + b = k(a + b - c + d) and thus k(c - d) = (k - 1) (a + b). Recall that a > b > c > d. If k = 1 then c = d, a contradiction. If k ≥ 2 then

2 ≥ 
        (k/(k - 1)) = ((a + b)/(c - d)) > 2,

a contradiction. 
Since a contradiction is reached in both (i) and (ii), a  b + c  d is not prime.

Solution 2

The equality a  c + 
          b  d = (b + d + a - c) (b + d - a + c) is equivalent to

(a^2) - a  c + (c^2) = 
      (b^2) + b  d + (d^2).

Let A  B  C  D be the quadrilateral with A  B = a, B  C = d, C  D = b, A  D = c, ∠  B  A  D = (60^◦), and ∠  B  C  D = (120^◦). Such a quadrilateral exists in view of (1) and the Law of Cosines; the common value in (1) is B  (D^2). Let ∠  A  B  C = α, so that ∠  C  D  A = 
        (180^◦) - α. Applying the Law of Cosines to triangles A  B  C and A  C  D gives

(a^2) + (d^2) - 2  a  d  cos  α = A  (C^2) = 
        (b^2) + (c^2) + 
          2  b  c  cos  α.

Hence 2  
          cos  α = ((a^2) + (d^2) - (b^2) - (c^2))/(a  d + 
              b  c), and

\(TraditionalForm\`A 
         C\^2 = \(a\^2 + d\^2 - 
          a \( \(d\)\(\ \)\) \(a\^2 + d\^2 - b\^2 - c\^2\)\/\(a  d + b  c\) = \(\((a  b + c  d)\) \((a  c + b  d)\)\)\/\(\(a  d + b  c\)\(.\)\)\)\)

Because A  B  C  D is cyclic, Ptolemy's Theorem gives

\(TraditionalForm\`\((A  C·B  D)\)\^2 = \((a  b + c  d)\)\^2\)

It follows that

(a  c + b  d) ((a^2) - a  c + (c^2)) = (a  b + 
            c  d) (a  d + b  c).

(Note. Straightforward algebra can also be used obtain (2) from (1).) Next observe that

a  b + c  d > a  c + b  d > 
      a  d + b  c.

The first inequality follows from (a - d) (b - c) > 0, and the second from (a - b) (c - d) > 0.

Now assume that a  b + c  d is prime. It then follows from (3) that a  b + c  d and a  c + b  d are relatively prime. Hence, from (2), it must be true that a  c + b  d divides a  d + b  c. However, this is impossible by (3). Thus a  b + c  d must not be prime.

Note. Examples of 4-tuples (a, b, c, d) that satisfy the given conditions are (21, 18, 14, 1) and (65, 50, 34, 11).