35th British Mathematical Olympiad 1999 Problems

35th British Mathematical Olympiad 1999 Problems

1.  Let X_n = {1, 2, 3, ... , n}. For which n can we partition X_n into two parts with the same sum? For which n can we partition X_n into three parts with the same sum?

2.  A circle is inscribed in a hexagon ABCDEF. It touches AB, CD and EF at their midpoints (L, M, N respectively) and touches BC, DE, FA at the points P, Q, R. Prove that LQ, MR, NP are concurrent.

3.  Show that xy + yz + zx ≤ 2/7 + 9xyz/7 for non-negative reals x, y, z with sum 1.

4.  Find the smallest possible sum of digits for a number of the form 3n² + n + 1 (where n is a positive integer). Does there exist a number of this form with sum of digits 1999? 

Solutions

Problem 1

Let X_n = {1, 2, 3, ... , n}. For which n can we partition X_n into two parts with the same sum? For which n can we partition X_n into three parts with the same sum?

Solution

The sum of all the elements of X_n is n(n+1)/2. This is odd for n = 1, 2 mod 4 and even for n = 0, 3 mod 4, so a necessary condition for two parts is that n = 0 or 3 mod 4. It is also sufficient. For n = 0 mod 4, there are an even number of pairs (1, n), (2, n-1), (3, n-2), ... each with the same sum, so we can take half the pairs in one part and half in the other. For n = 3 mod 4, there are an even number of pairs (4, n), (5, n-1), (6, n-2), ... each with the same sum, so we take half in one part and half in the other. Then we put 1 and 2 in one part and 3 in the other.

A necessary condition is that 3 divides n(n+1), so n is not 1 mod 3. That is not sufficient, because we obviously cannot divide X₂ or X₃ into three equal parts. However, it is sufficient for larger n.

Let N = n(n+1)/6. For n not 1 mod 3, this is an integer. Take a subset A of X_n by using the greedy algorithm: we repeatedly pick the largest remaining element until we get the required sum N. Thus A consists of a sequence of consecutive integers ending with n and possibly one additional element. Now take another subset B of the remaining elements, using the same algorithm. The remaining elements are 1, 2, ... , m for some m with at most one element missing. The algorithm cannot fail for A and can only fail for B if either: (1) the missing element is 1 and after picking m, m-1, ... , m-k we want 1 to complete the set, or (2) the missing element is 2, and after picking m, m-1, ... , m-k we want 2 to complete the set (we can continue with 1 but then get stuck). In case (1), we can use replace m-k and pick m-k-1 and 2. In case (2) we can replace m-k (and 1 if we got that far) and pick m-k-1 and 3.

Thus we can always get two sets with sum N. But then the remaining elements must also have sum n.

Comment. This is a weaker version of the result that if 1 + 2 + 3 + ... + n = mk, with n ≥ m, then we can divide the set into k parts with equal sum. See ASU 88/20

Problem 2

A circle is inscribed in a hexagon ABCDEF. It touches AB, CD and EF at their midpoints (L, M, N respectively) and touches BC, DE, FA at the points P, Q, R. Prove that LQ, MR, NP are concurrent.

Solution

The key is that PN is perpendicular to LM. So the three lines are the altitudes of the triangle LMN and hence concurrent.

Let the center of the circle be O. Let ∠AOL = x, so ∠LOB = x (L midpoint of AB), ∠BOP = x also (BP = BL) and ∠ROA = x. Similarly, let ∠POC = y. So ∠COM = y (CM = CP), ∠DOM = y (M midpoint of CD), ∠DOQ = y (DM = DQ). Similarly, let ∠QOE = z, so ∠EON = z (EN = EQ), ∠NOF = z (N midpoint of EF), ∠FOR = z (FN = FR). Thus 4(x + y + z) = 360^o and hence x + y + z = 90^o.

∠LOM = 2x + 2y, so if OX is the perpendicular bisector of LM, then ∠LOX = x + y. Similarly, ∠PON = 4y + 2z, so if OY is the perpendicular bisector of PN, then angle POY = 2y + z. ∠LOP = 2x, so ∠LOY = 2x + 2y + z. Hence ∠XOY = 2x + 2y + z - (x + y) = x + y + z = 90^o. In other words the perpendicular bisectors of LM and PN are perpendicular. Hence LM and PN are perpendicular, which is all we need. [Obviously, a similar argument establishes that that LQ, MR are also altitudes of LMN.] 

Problem 3

Show that xy + yz + zx ≤ 2/7 + 9xyz/7 for non-negative reals x, y, z with sum 1.

Solution

If x ≥ 7/9, then 1 ≤ 9x/7, so xy ≤ 9xyz/7. Also (y + z) ≤ 2/9, so xy + xz < 2/9 < 2/7. Thus in this case xy + yz + zx < 2/7 + 9xyz/7. So assume x < 7/9, and hence 1 - 9x/7 > 0.

We have yz ≤ (y+z)²/4 with equality iff y = z and hence yz ≤ (1 - x)²/4. So it is sufficient to show that (1 - 9x/7)(1 - x)²/4 + x(1 - x) ≤ 2/7, or equivalently (7 - 9x)(1 - x)² + 28x(1 - x) <= 8. Expanding, 9x³ + 3x² - 5x + 1 >= 0 or (x + 1)(3x - 1)² ≥ 0, which is obviously true (for non-negative x), with equality iff x = 1/3. Thus the inequality holds, with equality iff x = y = z = 1/3. 

Problem 4

Find the smallest possible sum of digits for a number of the form 3n² + n + 1 (where n is a positive integer). Does there exist a number of this form with sum of digits 1999?

Solution

Answer: n = 8 gives 201 with sum of digits 3. Yes, eg take n = 10²²² - 1.

The only one digit number has sum of digits 5. 3n² + n + 1 = n(3n+1) + 1 and n and 3n+1 have opposite parity, so 3n² + n + 1 must be odd. In particular, the last digit cannot be 0, so for n > 1 the number has at least two non-zero digits (the first and the last) and hence the sum of digits is at least 2. It can only be 2 if the number is 10^a + 1 and hence n(3n+1) = 10^a. But n and 3n+1 are relatively prime, so we must have n = 2^a, 3n+1 = 5^a. But (5/2)^a > 6 for a > 1, so there are no solutions with a > 1. If a = 1, then n = 2, so 3n+1 = 7 not 5, so a = 1 is not a solution either. Thus the sum of digits cannot be 2.

n = 8 gives 201 with sum of digits 3, so that is the best possible.

We claim that if n = 10^m - 1, then 3n² + n + 1 = 29...950...03, where there are m-1 9s and m-1 0s. Thus if we take m = 222, then we get a number with 221 9s, one 2, one 3 and one 5, so the sum of digits is 1999.

To prove the assertion, note that 3n² + n + 1 = 3·10^2m - 6·10^m + 3 + 10^m = (3·10^m-1 - 1) 10^m+1 + 5·10^m + 3. Now 3·10^m-1 - 1 is an m-digit number 29...9. Multiplying by 10^m+1 means it is followed by m+1 zero digits. But 5·10^m + 3 is an m+1 digit number 50...03, so the sum is as claimed.