21th British Mathematical Olympiad 1985 Problems
1. Prove that ∑1n ∑1n | xi - xj | ≤ n2 for all real xi such that 0 ≤ xi ≤ 2. When does equality hold?
2. (1) The incircle of the triangle ABC touches BC at L. LM is a diameter of the incircle. The ray AM meets BC at N. Show that | NL | = | AB - AC |.
(2) A variable circle touches the segment BC at the fixed point T. The other tangents from B and C to the circle (apart from BC) meet at P. Find the locus of P.
3. Let { x } denote the nearest integer to x, so that x - 1/2 ≤ { x } < x + 1/2. Define the sequence u1, u2, u3, ... by u1 = 1. un+1 = un + { un√2 }. So, for example, u2 = 2, u3 = 5, u4 = 12. Find the units digit of u1985.
4. A, B, C, D are points on a sphere of radius 1 such that the product of the six distances between the points is 512/27. Prove that ABCD is a regular tetrahedron.
5. Let bn be the number of ways of partitioning the set {1, 2, ... , n} into non-empty subsets. For example, b3 = 5: 123; 12, 3; 13, 2; 23, 1; 1, 2, 3. Let cn be the number of partitions where each part has at least two elements. For example, c4 = 4: 1234; 12, 34; 13, 24; 14, 23. Show that cn = bn-1 - bn-2 + ... + (-1)nb1.
6. Find all non-negative integer solutions to 5a7b + 4 = 3c.
Problem 1
Prove that ∑1n ∑1n | xi - xj | ≤ n2 for all real xi such that 0 ≤ xi ≤ 2. When does equality hold?
Answer
equality holds for n even and half the xi 2, and half 0.
Solution
wlog x1 ≥ x2 ≥ ... ≥ xn. Then lhs = 2 ∑i<j (xi-xj) = 2(n-1)x1 + 2(n-3)x2 + ... - 2(n-1)xn. Suppose n = 2m. Then for i = 1, 2, ... , m the coefficient of xi is positive, so to maximise the sum we should take x1 = x2 = ... = xm = 2. Similarly for i = m+1, ... , n the coefficient of xi is negative, so to maximise the sum we should take xm+1 = xm+2 = ... = xn = 0. Then we get the maximum value 4(2m-1 + 2m-3 + ... + 1) = n2.
Similarly, if n = 2m+1, then for i = 1, 2, ... , m the coefficient of xi is positive, so to maximise the sum we should take x1 = x2 = ... = xm = 2. The coefficient of xm+1 is zero, so its value is irrelevant. The coefficients of xm+2, ... , xn are negative, so to maximise the sum we should take xm+2 = xm+2 = ... = xn = 0. Then we get the maximum value 4(2m + 2m-2 + ... + 2) = 4m(m+1) = (n-1)(n+1) = n2 - 1. So for n odd the inequality still holds, but we cannot get equality.
Problem 2
(1) The incircle of the triangle ABC touches BC at L. LM is a diameter of the incircle. The ray AM meets BC at N. Show that | NL | = | AB - AC |.
(2) A variable circle touches the segment BC at the fixed point T. The other tangents from B and C to the circle (apart from BC) meet at P. Find the locus of P.
Solution
Let the tangent to the incircle at M meet AB, AC at B',C'. Then an enlargement center A takes B',C' to B,C and the incircle to the excircle. So N must be the point at which the excircle touches BC. Now we have the familiar results (proved by chasing equal tangents around the triangle) that BL = s - b and BN = s - c, so NL = c - b, or |NL| = |AB - AC|.
We have PB - PC = PV + VB - PU - UC = VB - UC = TB - TC, which is constant. So P must lie on the hyperbola given by PB-PC = TB-TC, which has foci B, C. Note that the locus is just one branch of the hyperbola (if T is closer to C, then it is branch closer to C).
Problem 3
Let { x } denote the nearest integer to x, so that x - 1/2 ≤ { x } < x + 1/2. Define the sequence u1, u2, u3, ... by u1 = 1. un+1 = un + { un√2 }. So, for example, u2 = 2, u3 = 5, u4 = 12. Find the units digit of u1985.
Answer
9
Solution
We find the first few terms are 1, 2, 5, 12, 29, 70, which suggests that un+2 = 2un+1+un. Induction. True for n = 1. Suppose true for n. Then un+3 = un+2 + { un+2√2 } = un+2 + { un+1√2 + 2un+1} = un+2 + 2un+1 + { un+1√2 } = un+2 + un+1 + un+1 + { un+1√2 } = un+2 + un+1 + un+2, so it is true for n+1 and hence for all n.
Now calculating mod 10 we find the terms are 1, 2, 5, 2, 9, 0, 9, 8, 5, 8, 1, 0, 1, 2, so it is periodic with period 12. Hence u1985 = u5 = 9 mod 10.
Problem 4
A, B, C, D are points on a sphere of radius 1 such that the product of the six distances between the points is 512/27. Prove that ABCD is a regular tetrahedron.
Solution
For n points Pi with centroid G we have ∑i<j PiPj2 = n ∑ PiG2. To prove it take rectangular coordinates with origin G. Let Pi be (xi,yi), so ∑ xi = 0. Hence 0 = (∑ xi)2 = ∑ xi2 + 2∑i<j xixj. Hence ∑i<j (xi-xj)2 = (n-1)∑ xi2 - 2∑i<j xixj = n∑ xi2. Similarly for the other coordinates. Adding gives the result.
Similarly we have ∑ OPi2 = ∑ GPi2 + nOG2. Take coordinates with origin O. Then, considering the x-coordinates, n rhs = n ∑ xi2 - 2(∑ xi)2 + (∑ xi)2 + (∑ xi)2 = n ∑ xi2 = n lhs. Similarly for the other coordinates. Adding gives the result.
Hence we have for the points A, B, C, D on the sphere we have AB2+AC2+AD2+BC2+BD2+CD2 = 4(AG2+BG2+CG2+DG2), where G is the centroid of A, B, C, D, and hence = 16 - 16OG2, where O is the center of the sphere. So the 6 quantities AB2, ... , CD2 have arithmetic mean at most 8/3. Hence their geometric mean is also at most 8/3. In other words AB·AC·AD·BC·BD·CD ≤ (8/3)3 = 512/27. We have equality iff (1) A, B, C, D have centroid O, and (2) all sides of the tetrahedron are equal (so that AM = GM), in other words iff ABCD is a regular tetrahedron.
Problem 5
Let bn be the number of ways of partitioning the set {1, 2, ... , n} into non-empty subsets. For example, b3 = 5: 123; 12, 3; 13, 2; 23, 1; 1, 2, 3. Let cn be the number of partitions where each part has at least two elements. For example, c4 = 4: 1234; 12, 34; 13, 24; 14, 23. Show that cn = bn-1 - bn-2 + ... + (-1)nb1.
Solution
We show first that bn = cn+1 + cn (*). If we have a partition of {1, 2, ... , n} where at least one part has only one element, then we get a partition of {1, 2, ... , n+1} where all parts have at least two elements by joining all the singletons together with n+1. Conversely given a partition of {1, 2, ... , n+1} where all parts have at least two elements we can get a partition of {1, 2, ... , n} where at least one part has only one element by taking the part containing n+1 and turning it into a collection of singletons. Thus there is a bijection between the two types of partition, which establishes (*).
The relation in the question now follows by a trivial induction, since it is obvious that c2 = b1 = 1.
Problem 6
Find all non-negative integer solutions to 5a7b + 4 = 3c.
Answer
5170 + 4 = 32
Solution
Note that lhs > 4, so c ≥ 2. If a = 0, then 7b = 4 = 1 mod 3, so lhs = 2 mod 3. Contradiction. Hence a ≥ 1. So 3c = 4 mod 5, so c = 4k+2. In particular c must be even, so 5a7b = (32k+1+2)(32k+1-2). The gcd of (32k+1+2) and (32k+1-2) must divide their sum 4, but they are odd, so they are coprime. Hence one is 5a and the other is 7b. If k = 0, then we have the solution shown above. So assume k > 0. Hence (32k+1+2) and (32k+1-2) are both ≥ 25, so a ≥ 2 and b ≥ 1, and we have 5a - 7b = ± 4. So 7b = ± 4 mod 25. Contradiction, because powers of 7 must be ±1 or ±7 mod 25. So there are no solutions with k > 0.
Problem 3
Let { x } denote the nearest integer to x, so that x - 1/2 ≤ { x } < x + 1/2. Define the sequence u1, u2, u3, ... by u1 = 1. un+1 = un + { un√2 }. So, for example, u2 = 2, u3 = 5, u4 = 12. Find the units digit of u1985.
Answer
9
Solution
We find the first few terms are 1, 2, 5, 12, 29, 70, which suggests that un+2 = 2un+1+un. Induction. True for n = 1. Suppose true for n. Then un+3 = un+2 + { un+2√2 } = un+2 + { un+1√2 + 2un+1} = un+2 + 2un+1 + { un+1√2 } = un+2 + un+1 + un+1 + { un+1√2 } = un+2 + un+1 + un+2, so it is true for n+1 and hence for all n.
Now calculating mod 10 we find the terms are 1, 2, 5, 2, 9, 0, 9, 8, 5, 8, 1, 0, 1, 2, so it is periodic with period 12. Hence u1985 = u5 = 9 mod 10.
Problem 4
A, B, C, D are points on a sphere of radius 1 such that the product of the six distances between the points is 512/27. Prove that ABCD is a regular tetrahedron.
Solution
For n points Pi with centroid G we have ∑i<j PiPj2 = n ∑ PiG2. To prove it take rectangular coordinates with origin G. Let Pi be (xi,yi), so ∑ xi = 0. Hence 0 = (∑ xi)2 = ∑ xi2 + 2∑i<j xixj. Hence ∑i<j (xi-xj)2 = (n-1)∑ xi2 - 2∑i<j xixj = n∑ xi2. Similarly for the other coordinates. Adding gives the result.
Similarly we have ∑ OPi2 = ∑ GPi2 + nOG2. Take coordinates with origin O. Then, considering the x-coordinates, n rhs = n ∑ xi2 - 2(∑ xi)2 + (∑ xi)2 + (∑ xi)2 = n ∑ xi2 = n lhs. Similarly for the other coordinates. Adding gives the result.
Hence we have for the points A, B, C, D on the sphere we have AB2+AC2+AD2+BC2+BD2+CD2 = 4(AG2+BG2+CG2+DG2), where G is the centroid of A, B, C, D, and hence = 16 - 16OG2, where O is the center of the sphere. So the 6 quantities AB2, ... , CD2 have arithmetic mean at most 8/3. Hence their geometric mean is also at most 8/3. In other words AB·AC·AD·BC·BD·CD ≤ (8/3)3 = 512/27. We have equality iff (1) A, B, C, D have centroid O, and (2) all sides of the tetrahedron are equal (so that AM = GM), in other words iff ABCD is a regular tetrahedron.
Problem 5
Let bn be the number of ways of partitioning the set {1, 2, ... , n} into non-empty subsets. For example, b3 = 5: 123; 12, 3; 13, 2; 23, 1; 1, 2, 3. Let cn be the number of partitions where each part has at least two elements. For example, c4 = 4: 1234; 12, 34; 13, 24; 14, 23. Show that cn = bn-1 - bn-2 + ... + (-1)nb1.
Solution
We show first that bn = cn+1 + cn (*). If we have a partition of {1, 2, ... , n} where at least one part has only one element, then we get a partition of {1, 2, ... , n+1} where all parts have at least two elements by joining all the singletons together with n+1. Conversely given a partition of {1, 2, ... , n+1} where all parts have at least two elements we can get a partition of {1, 2, ... , n} where at least one part has only one element by taking the part containing n+1 and turning it into a collection of singletons. Thus there is a bijection between the two types of partition, which establishes (*).
The relation in the question now follows by a trivial induction, since it is obvious that c2 = b1 = 1.
Problem 6
Find all non-negative integer solutions to 5a7b + 4 = 3c.
Answer
5170 + 4 = 32
Solution
Note that lhs > 4, so c ≥ 2. If a = 0, then 7b = 4 = 1 mod 3, so lhs = 2 mod 3. Contradiction. Hence a ≥ 1. So 3c = 4 mod 5, so c = 4k+2. In particular c must be even, so 5a7b = (32k+1+2)(32k+1-2). The gcd of (32k+1+2) and (32k+1-2) must divide their sum 4, but they are odd, so they are coprime. Hence one is 5a and the other is 7b. If k = 0, then we have the solution shown above. So assume k > 0. Hence (32k+1+2) and (32k+1-2) are both ≥ 25, so a ≥ 2 and b ≥ 1, and we have 5a - 7b = ± 4. So 7b = ± 4 mod 25. Contradiction, because powers of 7 must be ±1 or ±7 mod 25. So there are no solutions with k > 0.
Labels:
British Mathematical Olympiad
Previous Article
