11th Asian Pacific Mathematics Olympiad 1999 Problems

11th Asian Pacific Mathematics Olympiad 1999 Problems

A1.  Find the smallest positive integer n such that no arithmetic progression of 1999 reals contains just n integers.

A2.  The real numbers x₁, x₂, x₃, ... satisfy x_i+j ≤ x_i + x_j for all i, j. Prove that x₁ + x₂/2 + ... + x_n/n ≥ x_n.

A3.  Two circles touch the line AB at A and B and intersect each other at X and Y with X nearer to the line AB. The tangent to the circle AXY at X meets the circle BXY at W. The ray AX meets BW at Z. Show that BW and BX are tangents to the circle XYZ.

A4.  Find all pairs of integers m, n such that m² + 4n and n² + 4m are both squares.

A5.  A set of 2n+1 points in the plane has no three collinear and no four concyclic. A circle is said to divide the set if it passes through 3 of the points and has exactly n - 1 points inside it. Show that the number of circles which divide the set is even iff n is even.

Find the smallest positive integer n such that no arithmetic progression of 1999 reals contains just n integers.

Solution

Answer: 70.

Using a difference of 1/n , where n does not divide 1999, we can get a progression of 1999 terms with m = [1998/n] or m = [1998/n] - 1 integers. Thus {0, 1/n, 2/n, ... , 1998/n} has m+1 integers, and {1/n, 2/n, ... , 1999/n} has m integers. So we are ok until n gets so large that the gap between [1998/n] and [1998/(n+1)] is 3 or more. This could happen for 1998/n - 1998/(n+1) just over 2 or n > 31. So checking, we find [1998/31] = 64, [1998/30] = 66, [1998/29] = 68, [1998/28] = 71.

We can get 68 integers with {1/29, 2/29, ... , 1999/29} and 69 with {0, 1/29, 2/29, ... , 1998/29}. We can get 71 with {1/28, 2/28, ... , 1999/28}, but we cannot get 70. Note that a progression with irrational difference gives at most 1 integer. A progression with difference a/b, where a and b are coprime integers, gives the same number of integers as a progression with difference 1/b. So it does not help to widen the class of progressions we are looking at.

The real numbers x₁, x₂, x₃, ... satisfy x_i+j <= x_i + x_j for all i, j. Prove that x₁ + x₂/2 + ... + x_n/n >= x_n.

Solution

We use induction. Suppose the result is true for n. We have:

x₁ >= x₁

x₁ + x₂/2 >= x₂

...

x₁ + x₂/2 + ... + x_n/n >= x_n

Also: x₁ + 2x₂/2 + ... + nx_n/n = x₁ + ... + x_n

Adding: (n+1) x₁ + (n+1)x₂/2 + ... + (n+1)x_n/n >= 2(x₁ + ... + x_n). But rhs = (x₁ + x_n) + (x₂ + x_n-1) + ... + (x_n + x₁) >= n x_n+1. Hence result.

Two circles touch the line AB at A and B and intersect each other at X and Y with X nearer to the line AB. The tangent to the circle AXY at X meets the circle BXY at W. The ray AX meets BW at Z. Show that BW and BX are tangents to the circle XYZ.

Solution

Let angle ZXW = a and angle ZWX = b. XW is tangent to circle AXY at X, so angle AYX = a. AB is tangent to circle AXY at A, so angle BAX = a. AB is tangent to circle BXY at B, so angle ABX = b. Thus, considering triangle ABX, angle BXZ = a+b. Considering triangle ZXW, angle BZX = a+b.

BXYW is cyclic, so angle BYX = angle BWX = b. Hence angle AYB = angle AYX + angle XYB = a+b = angle AZB. So AYZB is cyclic. Hence angle BYZ = angle BAZ = a. So angle XYZ = angle XYB + angle BYZ = a+b. Hence angle BZX = angle XYZ, so BZ is tangent to circle XYZ at Z. Similarly angle BXY = angle XYZ, so BX is tangent to circle XYZ at X.

Find all pairs of integers m, n such that m² + 4n and n² +4m are both squares.

Solution

Answer: (m, n) or (n, m) = (0, a²), (-5, -6), (-4, -4), (a+1, -a) where a is a non-negative integer.

Clearly if one of m, n is zero, then the other must be a square and that is a solution.

If both are positive, then m² + 4n must be (m + 2k)² for some positive k, so n = km + k² > m. But similarly m > n. Contradiction. So there are no solutions with m and n positive.

Suppose both are negative. Put m = -M, n = -N, so M and N are both positive. Assume M >= N. M² - 4N is a square, so it must be (M - 2k)² for some k, so N = Mk - k². If M = N, then M(k-1) = k², so k-1 divides k² and hence k² - (k-1)(k+1) = 1, so k = 2 and M = 4, giving the solution (m, n) = (-4, -4). So we may assume M > N and hence M > Mk - k² > 0. But that implies that k = 1 or M-1 and hence N = M-1. [If M > Mk - k², then (k-1)M < k². Hence k = 1 or M < k+2. But Mk - k² > 0, so M > k. Hence k = 1 or M = k+1.].

But N² - 4M is also a square, so (M-1)² - 4M = M² - 6M + 1 is a square. But (M-3)² > M² - 6M + 1 and (M-4)² < M² - 6M + 1 for M >= 8, so the only possible solutions are M = 1, 2, ... , 7. Checking, we find that only M = 6 gives M² - 6M + 1 a square. This gives the soluton (m, n) = (-6, -5). Obviously, there is also the solution (-5, -6).

Finally, consider the case of opposite signs. Suppose m = M > 0, n = -N < 0. Then N² + 4M is a square, so by the argument above M > N. But M² - 4N is a square and so the argument above gives N = M-1. Now we can easily check that (m, n) = (M, -(M-1) ) is a solution for any positive M.

A set of 2n+1 points in the plane has no three collinear and no four concyclic. A circle is said to divide the set if it passes through 3 of the points and has exactly n - 1 points inside it. Show that the number of circles which divide the set is even iff n is even.

Solution

Take two of the points, A and B, and consider the 2n-1 circles through A and B. We will show that the number of these circles which divide the set is odd. The result then follows almost immediately, because the number of pairs A, B is (2n+1)2n/2 = N, say. The total number of circles which divide the set is a sum of N odd numbers divided by 3 (because each such circle will be counted three times). If n is even, then N is even, so a sum of N odd numbers is even. If n is odd, then N is odd, so a sum of N odd numbers is odd. Dividing by 3 does not change the parity.

Their centers all lie on the perpendicular bisector of AB. Label them C₁, C₂, ... , C_2n-1, where the center of C_i lies to the left of C_j on the bisector iff i < j. We call the two half-planes created by AB the left-hand half-plane L and the right-hand half-plane R correspondingly. Let the third point of the set on C_i be X_i. Suppose i < j. Then C_i contains all points of C_j that lie in L and C_j contains all points of C_i that lie R. So X_i lies inside C_j iff X_i lies in R and X_j lies inside C_i iff X_j lies in L

Now plot f(i), the number of points in the set that lie inside C_i, as a function of i. If X_i and X_i+1 are on opposite sides of AB, then f(i+1) = f(i). If they are both in L, then f(i+1) = f(i) - 1, and if they are both in R, then f(i+1) = f(i) + 1. Suppose m of the X_i lie in L and 2n-1-m lie in R. Now suppose f(i) = n-2, f(i+1) = f(i+2) = ... = f(i+j) = n-1, f(i+j+1) = n. Then j must be odd. For X_i and X_i+1 must lie in R. Then the points must alternate, so X_i+2 lies in L, X_i+3 lies in R etc. But X_i+j and X_i+j+1 must lie in R. Hence j must be odd. On the other hand, if f(i+j+1) = n-2, then j must be even. So the parity of the number of C₁, C₂, ... , C_i which divide the set only changes when f crosses the line n-1 from one side to the other. We now want to say that f starts on one side of the line n-1 and ends on the other, so the final parity must be odd. Suppose there are m points in L and hence 2n-1-m in R. Without loss of generality we may take m <= n-1. The first circle C₁ contains all the points in L except X₁ if it is in L. So f(1) = m or m-1. Similarly the last circle C_2n-1 contains all the points in R except X_2n-1 if it is in R. So f(2n-1) = 2n-1-m or 2n-2-m. Hence if m < n-1, then f(1) = m or m-1, so f(1) < n-1. But 2n-1-m >= n+1, so f(2n-1) > n-1. So in this case we are done.

However, there are complications if m = n-1. We have to consider 4 cases. Case (1): m = n-1, X₁ lies in R, X_2n-1 lies in L. Hence f(1) = n-1, f(2n-1) = n > n-1. So f starts on the line n-1. If it first leaves it downwards, then for the previous point i, X_i is in L and hence there were an even number of points up to i on the line. So the parity is the same as if f(1) was below the line. f(2n-1) is above the line, so we get an odd number of points on the line. If f first leaves the line upwards, then for the previous point i, X_i is in R and hence there were an odd number of points up to i on the line. So again the parity is the same as if f(1) was below the line.

Case (2): m = n-1, X₁ lies in R, X_2n-1 lies in R. Hence f(1) = f(2n-1) = n-1. As in case (1) the parity is the same as if f(1) was below the line. If the last point j with f(j) not on the line has f(j) < n-1, then (since X_2n-1 lies in R) there are an odd number of points above j, so the parity is the same as if f(2n-1) was above the line. Similarly if f(j) > n-1, then there are an even number of points above j, so again the parity is the same as if f(2n-1) was above the line.

Case (3): m = n-1, X₁ lies in L, X_2n-1 lies in L. Hence f(1) = n-2, f(2n-1) = n. So case has already been covered.

Case (4): m=n-1, X₁ lies in L, X_n-1 lies in R. So f(1) = n-2, f(2n-1) = n-1. As in case (2), the parity is the same as if f(2n-1) was above the line.