10th Asian Pacific Mathematics Olympiad 1998 Problems

10th Asian Pacific Mathematics Olympiad 1998 Problems

A1.  S is the set of all possible n-tuples (X₁, X₂, ... , X_n) where each X_i is a subset of {1, 2, ... , 1998}. For each member k of S let f(k) be the number of elements in the union of its n elements. Find the sum of f(k) over all k in S.

A2.  Show that (36m + n)(m + 36n) is not a power of 2 for any positive integers m, n.

A3.  Prove that (1 + x/y)(1 + y/z)(1 + z/x) ≥ 2 + 2(x + y + z)/w for all positive reals x, y, z, where w is the cube root of xyz.

A4.  ABC is a triangle. AD is an altitude. X lies on the circle ABD and Y lies on the circle ACD. X, D and Y are collinear. M is the midpoint of XY and M' is the midpoint of BC. Prove that MM' is perpendicular to AM.

A5.  What is the largest integer divisible by all positive integers less than its cube root.

Solutions

S is the set of all possible n-tuples (X₁, X₂, ... , X_n) where each X_i is a subset of {1, 2, ... , 1998}. For each member k of S let f(k) be the number of elements in the union of its n elements. Find the sum of f(k) over all k in S.

Solution

Answer: 1998(2¹⁹⁹⁸ⁿ - 2¹⁹⁹⁷ⁿ).

Let s(n, m) be the sum where each X_i is a subset of {1, 2, ... , m}. There are 2^m possible X_i and hence 2^mn possible n-tuples. We have s(n, m) = 2ⁿs(n, m-1) + (2ⁿ - 1)2^n(m-1) (*). For given any n-tuple {X₁, ... , X_n} of subsets of {1, 2, ... , m-1} we can choose to add m or not (2 choices) to each X_i. So we derive 2ⁿ n-tuples of subsets of {1, 2, ... , m}. All but 1 of these have f(k) incremented by 1. The first term in (*) gives the sum for m-1 over the increased number of terms and the second term gives the increments to the f(k) due to the additional element.

Evidently s(n, 1) = 2ⁿ - 1. It is now an easy induction to show that s(n, m) = m(2^nm - 2^n(m-1)).

Putting m = 1998 we get that the required sum is 1998(2¹⁹⁹⁸ⁿ - 2¹⁹⁹⁷ⁿ). 

Show that (36m + n)(m + 36n) is not a power of 2 for any positive integers m, n.

Solution

Assume there is a solution. Take m ≤ n and the smallest possible m. Now (36m + n) and (m + 36n) must each be powers of 2. Hence 4 divides n and 4 divides m. So m/2 and n/2 is a smaller solution with m/2 < m. Contradiction.

Prove that (1 + x/y)(1 + y/z)(1 + z/x) ≥ 2 + 2(x + y + z)/w for all positive reals x, y, z, where w is the cube root of xyz.

Solution

(1 + x/y)(1 + y/z)(1 + z/x) = 1 + x/y + y/x + y/z + z/y + z/x + x/z = (x + y + z)(1/x + 1/y + 1/z) - 1 ≥ 3(x + y + z)/w - 1, by the arithmetic geometric mean inequality,
= 2(x + y + z)/w + (x + y + z)/w - 1 ≥ 2(x + y + z) + 3 - 1, by the arithmetic geometric mean inequality.

ABC is a triangle. AD is an altitude. X lies on the circle ABD and Y lies on the circle ACD. X, D and Y are collinear. M is the midpoint of XY and M' is the midpoint of BC. Prove that MM' is perpendicular to AM

Solution

Take P, Q so that PADB, AQCD are rectangles. Let N be the midpoint of PQ. Then PD is a diameter of the circumcircle of ABC, so PX is perpendicular to XY. Similarly, QY is perpendicular to XY. N is the midpoint of PQ and M' the midpoint of XY, so NM is parallel to PX and hence perpendicular to XY. NADM' is a rectangle, so ND is a diameter of its circumcircle and M must lie on the circumcircle. But AM' is also a diameter, so ∠AMM' = 90^o.

Thanks to Michael Lipnowski for the above. My original solution is below.

Let P be the circumcenter of ABD and Q the circumcenter of ADC. Let R be the midpoint of AM'. P and Q both lie on the perpendicular bisector of AD, which is parallel to BC and hence also passes through R. We show first that R is the midpoint of PQ.

Let the feet of the perpendiculars from P, Q, R to BC to P', Q', R' respectively. It is sufficient to show that . BP' = BD/2. BR' = BM' + M'R' = (BD + DC)/2 + M'D/2 = (BD + DC)/2 + ( (BD + DC)/2 - DC)/2 = 3BD/4 + DC/4, so P'R' = (BD + DC)/4. Q'C = DC/2, so BQ' = BD + DC/2 and P'Q' = (BD + DC)/2 = 2P'R'.

Now the circumcircle centre P meets XY in X and D, and the circumcircle centre Q meets XY in D and Y. Without loss of generality we may take XD >= DY. Put XD = 4x, DY = 4y. The circle center R through A, M' and D meets XY in a second point, say M''. Let the feet of the perpendiculars from P, Q, R to XY be P'', Q'', R'' respectively. So on XY we have, in order, X, P'', M'', R'', D, Q'', Y. Since R is the midpoint of PQ, R'' is the midpoint of P''Q''. Now P'' is the midpoint of XD and Q'' is the midpoint of DY, so P''Q'' = XY/2 = 2(x+y), so R''Q'' = x+y. But DQ'' = 2y, so R''D = x-y. R'' is the midpoint of M''D, so M''D = 2(x-y) and hence M''Y = M''D + DY = 2(x-y) + 4y = 2(x+y) = XY/2. So M'' is just M the midpoint of XY. Now AM' is a diameter of the circle center R, so AM is perpendicular to MM'. 

What is the largest integer divisible by all positive integers less than its cube root.

Solution

Answer: 420.

Let N be a positive integer satisfying the condition and let n be the largest integer not exceeding its cube root. If n = 7, then 3·4·5·7 = 420 must divide N. But N cannot exceed 8³ - 1 = 511, so the largest such N is 420.

If n ≥ 8, then 3·8·5·7 = 840 divides N, so N > 729 = 9³. Hence 9 divides N, and hence 3·840 = 2520 divides N. But we show that no N > 2000 can satisfy the condition.

Note that 2(x - 1)³ > x³ for any x > 4. Hence [x]³ > x³/2 for x > 4. So certainly if N > 2000, we have n³ > N/2. Now let p_k be the highest power of k which does not exceed n. Then p_k > n/k. Hence p₂p₃p₅ > n³/30 > N/60. But since N > 2000, we have 7 < 11 < n and hence p², p³, p⁵, 7, 11 are all ≤ n. But 77 p²p³p⁵ > N, so N cannot satisfy the condition.