22th British Mathematical Olympiad 1986 Problems

22th British Mathematical Olympiad 1986 Problems - Further International Selection Test

1.  A rational point is a point both of whose coordinates are rationals. Let A, B, C, D be rational points such that AB and CD are not both equal and parallel. Show that there is just one point P such that the triangle PCD can be obtained from the triangle PAB by enlargement and rotation about P. Show also that P is rational.

2.  Find the maximum value of x²y + y²z + z²x for reals x, y, z with sum zero and sum of squares 6.

3.  P₁, P₂, ... , P_n are distinct subsets of {1, 2, ... , n} with two elements. Distinct subsets P_i and P_j have an element in common iff {i, j} is one of the P_k. Show that each member of {1, 2, ... , n} belongs to just two of the subsets.

4.  m ≤ n are positive integers. nCm denotes the binomial coefficient n!/(m! (n-m)! ). Show that nCm nC(m-1) is divisible by n. Find the smallest positive integer k such that k nCm nC(m-1) nC(m-2) is divisible by n² for all m, n such that 1 < m ≤ n. For this value of k and fixed n, find the greatest common divisor of the n - 1 integers ( k nCm nC(m-1) nC(m-2) )/n² where 1 < m ≤ n.

5.  C and C' are fixed circles. A is a fixed point on C, and A' is a fixed point on C'. B is a variable point on C. B' is the point on C' such that A'B' is parallel to AB. Find the locus of the midpoint of BB'. 

Problem 1

A rational point is a point both of whose coordinates are rationals. Let A, B, C, D be rational points such that AB and CD are not both equal and parallel. Show that there is just one point P such that the triangle PCD can be obtained from the triangle PAB by enlargement and rotation about P. Show also that P is rational.

Solution

 

If AB is parallel to CD, then we can take the intersection Y of the two diagonals AC and BD. We have immediately ∠YAB = ∠YCD, ∠YBA = ∠YDC, so YAB and YCD are directly similar. For uniqueness, note that AB is parallel to CD, so the rotation must be through an angle 180^o, hence the center of rotation must lie on AC and on BD.

Suppose the x-axis is not perpendicular to AB. Let x_A denote the x-coordinate of A etc. Then AB/CD = |x_A-x_B|/|x_C-x_D|, which is rational. If the x-axis is perpendicular to AB, then we can use the y-axis. Either way we get that AB/CD = k for some rational k. Then BY/BD = k/(k+1), so the x-coordinate of Y is (x_B + kx_D)/(k+1), which is rational. Similarly the y-coordinate.

If AB is not parallel to CD, take X to be the intersection of AB and CD. Let Y be the other point of intersection of the circles through A,C,X and D,B,X. Then we have ∠YAB = 180^o - ∠XCY (AYCX cyclic) = ∠YCD. Similarly, ∠YDC = 180o - ∠YBX (DYBX cyclic) = ∠&YBA, so YAB and YCD are similar. For uniqueness, note that AB must be rotated through an angle 180^o - ∠AXD, so the center of rotation must lie on the circle through A,C,X. For the same reason it must lie on the circle through DBX.

The lines AB and CD have rational equations (since A, B, C, D are all rational). So X is a rational point. Hence the midpoint of XC is rational, and the gradient of XC is rational, so the perpendicular bisector of XC has a rational equation. Similarly, the perpendicular bisector of CA. Hence the circumcenter of ACX is rational. Hence the (quadratic) equation of the circumcircle of ACX has rational coefficients. Similarly, the equation of the circumcircle of DBX. So we get a quadratic equation for the x-coordinates of the intersections of the two circles which has rational coefficients. But one root, the x-coordinate of X is rational, so the other is also. In other words, Y has a rational x-coordinate. Similarly, it has a rational y-coordinate.

Problem 2

Find the maximum value of x²y + y²z + z²x for reals x, y, z with sum zero and sum of squares 6.

Answer

6 (eg x = 2 cos 40^o, y = 2 cos 80^o, z = 2 cos 160^o).

Solution

Put u = x²y+y²z+z²x, v = xy²+yz²+zx², and w = xyz.

We have 0 = (x+y+z)² = x²+y²+z²+2(xy+yz+zx), so xy+yz+zx = -3. Squaring, 9 = x²y²+y²z²+z²x²+2(x²yz+xy²z+xyz²) = x²y²+y²z²+z²x² + 2xyz(x+y+z) = x²y²+y²z²+z²x².

We have x³+y³+z³ = (x+y+z)(x²+y²+z²-xy-yz-zx) + 3xyz = 3w. Hence also x³y³+y³z³+z³x³ = (xy+yz+zx)(x²y²+y²z²+z²x²-xy²z-xyz²-x²yz) + 3x²y²z² = (xy+yz+zx)(x²y²+y²z²+z²x²) + 3w² = -3·9 + 3w² = -27 + 3w².

Also (x+y+z)(xy+yz+zx) = u+v+3w, so u+v = -3w. Multiplying out, we find uv = (x³y³+y³z³+z³x³) + 3x²y²z² + xyz(x³+y³+z³) = -27 + 3w² + 3w² + 3w² = 9w² - 27. Hence u is a root of the quadratic u² + 3wu + (9w²-27) = 0. Completing the square in w (not u) we get (3w + u/2)² + 3u²/4 - 27 = 0, so 3u²/4 - 27 ≤ 0 and hence u ≤ 6.

For equality we need w = -1. Remembering that x+y+z = 0, xy+yz+zx = -3, x, y, z are the roots of k³ - 3k + 1 = 0. If we put k = 2 cos θ, then 8 cos³θ - 6 cos θ + 1 = 0. But cos 3θ = 4 cos³θ - 3 cos θ, so cos 3θ = -1/2. Hence 3θ = 2π/3, 4π/3 or 8π/3, so x, y, z = 2 cos 2π/9, 2 cos 4π/9, 2 cos 8π/9.

Comment. This is all fairly unmotivated. Does anyone have a more straightforward solution?

Problem 3

P₁, P₂, ... , P_n are distinct subsets of {1, 2, ... , n} with two elements. Distinct subsets P_i and P_j have an element in common iff {i, j} is one of the P_k. Show that each member of {1, 2, ... , n} belongs to just two of the subsets.

Solution

Let a_k be the number of P_i that contain k. Then ∑ a_k = 2n. The number of unordered pairs Pi, Pj that both contain k is a_k(a_k-1)/2. But P_i and P_j can have at most one element in common, and they have an element in common iff {i,j} is one of the n pairs P_m. So ∑ a_k(a_k-1)/2 = n. Hence ∑ a_k² = 4n. So (∑ a_k)² = n ∑ a_k², but by Cauchy-Schwartz that implies all a_k are equal and hence all a_k = 2.

Problem 4

m ≤ n are positive integers. nCm denotes the binomial coefficient n!/(m! (n-m)! ). Show that nCm nC(m-1) is divisible by n. Find the smallest positive integer k such that k nCm nC(m-1) nC(m-2) is divisible by n² for all m, n such that 1 < m ≤ n. For this value of k and fixed n, find the greatest common divisor of the n - 1 integers ( k nCm nC(m-1) nC(m-2) )/n² where 1 < m ≤ n.

Answer

k = 2, gcd = n-1

Solution

nCm = (n/m) n-1Cm-1, so m(nCm)(nCm-1) = n n-1Cm-1 nCm-1. Similarly (m-1) nCm n-1Cm-1 = n nCm n-1Cm-2. Subtracting, nCm nCm-1 = n( nCm-1 n-1Cm-1 - nCm n-1Cm-1), which shows explicitly that n divides nCm nCm-1.

Note that nC2 nC1 nC0 = n²(n-1)/2, so for n even we need k divisible by 2. We show that k = 2 always works. Let x = (2/n²) nCm nCm-1 nCm-2. Then (using the same basic idea, nCm = (n/m) n-1Cm-1) we have m(m-1)x = 2 n-1Cm-1 n-1Cm-2 nCm-2 = 2A, where A is an integer. Similarly, m(m-2)x = 2B, (m-1)(m-2)x = 2C, where B and C are integers. Hence (-m(m-1) + 2m(m-2) - (m-1)(m-2)) x = 4B-2A-2C, or 2x = 4B-2A-2C, or x = 2B-A-C, which is an integer.

The case nC2 nC1 nC0 shows that the gcd must be a factor of n-1. Playing around with other cases suggests that the gcd is n-1. But applying the result already proved in the first part we see that n-1 divides n-1Cm-1 n-1Cm-2 and hence A. Similarly, n-1 divides n-1Cm-2 n-1Cm-3 and hence C = nCm n-1Cm-2 n-1Cm-3. It remains to show that n-1 divides 2B = 2 n-1Cm-1 nCm-1 n-1Cm-3. We suspect it will divide 2 n-1Cm-1 n-1Cm-3. Indeed the same argument works: (m-1) n-1Cm-1 n-1Cm-3 = (n-1) n-2Cm-2 n-1Cm-3, and (m-3) n-1Cm-1 n-1Cm-3 = (n-1) n-1Cm-1 n-2Cm-4, so subtracting 2 n-1Cm-1 n-1Cm-3 = (n-1)(n-2Cm-2 n-1Cm-3 - n-1Cm-1 n-2Cm-4).

Problem 5

C and C' are fixed circles. A is a fixed point on C, and A' is a fixed point on C'. B is a variable point on C. B' is the point on C' such that A'B' is parallel to AB. Find the locus of the midpoint of BB'.

Solution

 

Consider first the case where A = A' (shown in the diagram above). Take M as the midpoint of BB', take O,O' as the centers and r, r' as the radii of the two circles, and X as the other point of intersection of the two circles. We have the familiar result that MB·MA = MO² - r² if M is outside the circle or r² - MO² if M is inside the circle. Similarly, MB'·MA = ±(MO'² - r'²). Note that since M is the midpoint, MB·MA = MB'·MA. Since M is always inside one circle and outside the other, we always have MO² + MO'² = |r² - r'²|. If Y is the midpoint of OO', then we have the familiar result (prove by applying the cosine formula to MYO and MYO') that MO² + MO'² = 2MY² + 2OY². Hence MY² = |r² - r'²|/2 - OY², which is constant, so M lies on a circle center Y. X obviously lies on the circle, so it is the circle center Y radius YX. 

Now given the general situation, translate C to C" so that A coincides with A'. Then B is translated to a point B" on C" which is on the line A'B'. Take M' to be the midpoint of B'B". Then by the result above the locus of M' is a circle. Take M to be the midpoint of BB'. Then MM' is the midline of the triangle BB'B", so MM' = BB"/2 = AA'/2, which is fixed, so M also lies on a circle, namely the circle containing M' translated by A'A/2.