16th International Mathematical Olympiad 1974 Problems & Solutions

A1.  Three players play the following game. There are three cards each with a different positive integer. In each round the cards are randomly dealt to the players and each receives the number of counters on his card. After two or more rounds, one player has received 20, another 10 and the third 9 counters. In the last round the player with 10 received the largest number of counters. Who received the middle number on the first round?

A2.  Prove that there is a point D on the side AB of the triangle ABC, such that CD is the geometric mean of AD and DB if and only if sin A sin B ≤ sin²(C/2).

A3.  Prove that the sum from k = 0 to n of (2n+1)C(2k+1) 2^3k is not divisible by 5 for any non-negative integer n. [rCs denotes the binomial coefficient r!/(s!(r-s)!) .]

B1.  An 8 x 8 chessboard is divided into p disjoint rectangles (along the lines between squares), so that each rectangle has the same number of white squares as black squares, and each rectangle has a different number of squares. Find the maximum possible value of p and all possible sets of rectangle sizes.

B2.  Determine all possible values of a/(a+b+d) + b/(a+b+c) + c/(b+c+d) + d/(a+c+d) for positive reals a, b, c, d.

B3.  Let P(x) be a polynomial with integer coefficients of degree d > 0. Let n be the number of distinct integer roots to P(x) = 1 or -1. Prove that n ≤ d + 2. 

Solutions

Problem A1

Three players play the following game. There are three cards each with a different positive integer. In each round the cards are randomly dealt to the players and each receives the number of counters on his card. After two or more rounds, one player has received 20, another 10 and the third 9 counters. In the last round the player with 10 received the largest number of counters. Who received the middle number on the first round?

 

Solution

The player with 9 counters.

The total of the scores, 39, must equal the number of rounds times the total of the cards. But 39 has no factors except 1, 3, 13 and 39, the total of the cards must be at least 1 + 2 + 3 = 6, and the number of rounds is at least 2. Hence there were 3 rounds and the cards total 13.

The highest score was 20, so the highest card is at least 7. The score of 10 included at least one highest card, so the highest card is at most 8. The lowest card is at most 2, because if it was higher then the highest card would be at most 13 - 3 - 4 = 6, whereas we know it is at least 7. Thus the possibilities for the cards are: 2, 3, 8; 2, 4, 7; 1, 4, 8; 1, 5, 7. But the only one of these that allows a score of 20 is 1, 4, 8. Thus the scores were made up: 8 + 8 + 4 = 20, 8 + 1 + 1 = 10, 4 + 4 + 1 = 9. The last round must have been 4 to the player with 20, 8 to the player with 10 and 1 to the player with 9. Hence on each of the other two rounds the cards must have been 8 to the player with 20, 1 to the player with 10 and 4 to the player with 9. 

Problem A2

Prove that there is a point D on the side AB of the triangle ABC, such that CD is the geometric mean of AD and DB if and only if sin A sin B ≤ sin²(C/2)

 

Solution

Extend CD to meet the circumcircle of ABC at E. Then CD·DE = AD·DB, so CD is the geometric mean of AD and DB iff CD = DE. So we can find such a point iff the distance of C from AB is less than the distance of AB from the furthest point of the arc AB on the opposite side of AB to C. The furthest point F is evidently the midpoint of the arc AB. F lies on the angle bisector of C. So ∠FAB = ∠FAC = ∠C/2. Hence distance of F from AB is c/2 tan C/2 (as usual we set c = AB, b = CA, a = BC). The distance of C from AB is a sin B. So a necessary and sufficient condition is c/2 tan C/2 ≥ a sin B. But by the sine rule, a = c sin A/sin C, so the condition becomes (sin C/2 sin C)/(2 cos C/2) ≥ sin A sin B. But sin C = 2 sin C/2 cos C/2, so we obtain the condition quoted in the question. 

Problem A3

Prove that the sum from k = 0 to n of (2n+1)C(2k+1) 2^3k is not divisible by 5 for any non-negative integer n. [rCs denotes the binomial coefficient r!/(s!(r-s)!) .]

 

Solution

Let k = √8. Then (1 + k)²ⁿ⁺¹ = a + bk, where b is the sum given in the question. Similarly, (1 - k)²ⁿ⁺¹ = a - bk. This looks like a dead end, because eliminating a gives an unhelpful expression for b. The trick is to multiply the two expressions to get 7²ⁿ⁺¹ = 8b² - a². This still looks unhelpful, but happens to work, because we soon find that 7²ⁿ⁺¹ ≠ ±2 (mod 5). So if b was a multiple of 5 then we would have a square congruent to ±2 (mod 5) which is impossible. 

Problem B1

An 8 x 8 chessboard is divided into p disjoint rectangles (along the lines between squares), so that each rectangle has the same number of white squares as black squares, and each rectangle has a different number of squares. Find the maximum possible value of p and all possible sets of rectangle sizes.

 

Solution

The requirement that the number of black and white squares be equal is equivalent to requiring that the each rectangle has an even number of squares. 2 + 4 + 6 + 8 + 10 + 12 + 14 + 16 = 72 > 64, so p < 8. There are 5 possible divisions of 64 into 7 unequal even numbers: 2 + 4 + 6 + 8 + 10 + 12 + 22; 2 + 4 + 6 + 8 + 10 + 16 + 18; 2 + 4 + 6 + 8 + 12 + 14 + 18; 2 + 4 + 6 + 10 + 12 + 14 + 16. The first is ruled out because a rectangle with 22 squares would have more than 8 squares on its longest side. The others are all possible.

2 2 2 2 2 2 2 4   2 2 2 2 2 2 2 2

2 2 2 2 2 2 2 4   2 2 2 2 2 2 2 2

1 1 1 1 1 5 5 4   1 1 1 1 1 1 5 5

1 1 1 1 1 5 5 4   1 1 1 1 1 1 5 5

1 1 1 1 1 5 5 4   1 1 1 1 1 1 5 5

1 1 1 1 1 6 6 4   3 3 3 3 3 7 6 6

3 3 3 3 3 6 6 4   3 3 3 3 3 7 6 6

3 3 3 3 3 7 7 4   4 4 4 4 4 4 4 4



2 2 2 2 2 2 2 7   1 1 1 1 1 1 1 1

2 2 2 2 2 2 2 7   1 1 1 1 1 1 1 1

1 1 1 1 1 1 4 4   2 2 2 2 2 2 2 7

1 1 1 1 1 1 4 4   2 2 2 2 2 2 2 7

1 1 1 1 1 1 4 4   3 3 3 3 3 3 6 6

3 3 3 3 3 3 4 4   3 3 3 3 3 3 6 6

3 3 3 3 3 3 6 6   4 4 4 4 4 5 5 5

5 5 5 5 5 5 6 6   4 4 4 4 4 5 5 5

Problem B2

Determine all possible values of a/(a+b+d) + b/(a+b+c) + c/(b+c+d) + d/(a+c+d) for positive reals a, b, c, d.

 

Solution

We show first that the sum must lie between 1 and 2. If we replace each denominator by a+b+c+d then we reduce each term and get 1. Hence the sum is more than 1. Suppose a is the largest of the four reals. Then the first term is less than 1. The second and fourth terms have denominators greater than b+c+d, so the terms are increased if we replace the denominators by b+c+d. But then the last three terms sum to 1. Thus the sum of the last three terms is less than 1. Hence the sum is less than 2.

If we set a = c = 1 and make b and d small, then the first and third terms can be made arbitarily close to 1 and the other two terms arbitarily close to 0, so we can make the sum arbitarily close to 2. If we set a = 1, c = d and make b and c/b arbitarily small, then the first term is arbitarily close to 1 and the last three terms are all arbitarily small, so we can make the sum arbitarily close to 1. Hence, by continuity, we can achieve any value in the open interval (1,2). 

Problem B3

Let P(x) be a polynomial with integer coefficients of degree d > 0. Let n be the number of distinct integer roots to P(x) = 1 or -1. Prove that n ≤ d + 2.

 

Solution

Suppose that A(x) and B(x) are two polynomials with integer coefficients which are identical except for their constant terms, which differ by 2. Suppose A(r) = 0, and B(s) =0 with r and s integers. Then subtracting we get 2 plus a sum of terms a(rⁱ - sⁱ). Each of these terms is divisible by (r - s), so 2 must be divisible by (r - s). Hence r and s differ by 0, 1 or 2.

Now let r be the smallest root of P(x) = 1 and P(x) = -1. The polynomial with r as a root can have at most d distinct roots and hence at most d distinct integer roots. If s is a root of the other equation then s must differ from r by 0, 1, or 2. But s ≥ r, so s = r, r+1 or r+2. Hence the other equation adds at most 2 distinct integer roots.

 

Solutions are also available in:   Samuel L Greitzer, International Mathematical Olympiads 1959-1977, MAA 1978, and in   István Reiman, International Mathematical Olympiad 1959-1999, ISBN 189-8855-48-X.