15th Asian Pacific Mathematics Olympiad 2003 Problems

15th Asian Pacific Mathematics Olympiad 2003 Problems

1.  The polynomial a₈x⁸ +a₇x⁷ + ... + a₀ has a₈ = 1, a₇ = -4, a₆ = 7 and all its roots positive and real. Find the possible values for a₀.

2.  A unit square lies across two parallel lines a unit distance apart, so that two triangular areas of the square lie outside the lines. Show that the sum of the perimeters of these two triangles is independent of how the square is placed.

3.  k > 14 is an integer and p is the largest prime smaller than k. k is chosen so that p ≥ 3k/4. Prove that 2p does not divide (2p - k)!, but that n does divide (n - k)! for composite n > 2p.

4.  Show that (aⁿ + bⁿ)^1/n + (bⁿ + cⁿ)^1/n + (cⁿ + aⁿ)^1/n < 1 + (2^1/n)/2, where n > 1 is an integer and a, b, c are the sides of a triangle with unit perimeter.

5.  Find the smallest positive integer k such that among any k people, either there are 2m who can be divided into m pairs of people who know each other, or there are 2n who can be divided into n pairs of people who do not know each other.

15th APMO 2003 Problem 1

The polynomial a₈x⁸ +a₇x⁷ + ... + a₀ has a₈ = 1, a₇ = -4, a₆ = 7 and all its roots positive and real. Find the possible values for a₀.

Answer 1/2⁸

Solution

Let the roots be x_i. We have Sum x_i² = 4² - 2·7 = 2. By Cauchy we have (x₁·1 + ... + x₈·1) ≤ (x₁² + ... + x₈²)^1/2(1² + ... + 1²)^1/2 with equality iff all x_i are equal. Hence all x_i are equal. So they must all be 1/2.

15th APMO 2003 Problem 2

A unit square lies across two parallel lines a unit distance apart, so that two triangular areas of the square lie outside the lines. Show that the sum of the perimeters of these two triangles is independent of how the square is placed.

Solution

15th APMO 2003 Problem 3

k > 14 is an integer and p is the largest prime smaller than k. k is chosen so that p ≥ 3k/4. Prove that 2p does not divide (2p - k)!, but that n does divide (n - k)! for composite n > 2p.

Solution

Since k > p, we have p > 2p-k and hence p does not divide any of 1, 2, 3, ... , 2p-k. But p is prime, so it does not divide (2p - k)! So 2p does not either.

Now consider composite n > 2p. Note that k > 14, so p ≥ 13, so n > 26. Take q to be the largest prime divisor of n and put n = qr. We now have three cases.

(1) q > r ≥ 3. Then n > 2p ≥ 3k/2, so 2n/3 > k. Hence n-k > n-2n/3 = n/3 ≥ n/r = q > r. So q and r are distinct integers < n-k. Hence n = qr divides (n-k)!.

(2) r = 2. Then n = 2q > 2p. But p is the largest prime < k. Hence q ≥ k, so n-k ≥ n-q = q. Obviously q > 2 (since n > 26), so q and 2 are distinct integers < n-k. Hence n = 2q divides (n-k)! .

(3) The final case is n = q². We show that 2q ≤ n-k. Suppose not. Then 2q ≥ n-k+1 ≥ (2p+1)-k+1 ≥ 3k/2 + 1 - k + 1 = k/2 + 2. So q ≥ k/4 + 1. Also since 2q ≥ n-k+1, we have k ≥ n-2q+1 = (q-1)² ≥ k²/16. If k > 16, this is a contradiction. If k = 15 or 16, then p = 13 and k ≥ (q-1)² gives q ≤ 5, so n = q² ≤ 25. But n > 2p = 26. Contradiction. So we have established that 2q ≤ n-k. But that means that q and 2q are distinct integers ≤ n-k and so their product 2n divides (n-k)!.

Thanks to Gerhard Woeginger for this.

15th APMO 2003 Problem 4

Show that (aⁿ + bⁿ)^1/n + (bⁿ + cⁿ)^1/n + (cⁿ + aⁿ)^1/n < 1 + (2^1/n)/2, where n > 1 is an integer and a, b, c are the sides of a triangle with unit perimeter.

Solution

We may take a ≥ b ≥ c. Since a + b + c = 1 and a < b+c, we have b ≤ a < 1/2. Hence (a_n + b_n)^1/n < 2^1/n/2 (*).

We have (b + c/2)ⁿ = bⁿ + n/2 c b^n-1 + other positive terms > bⁿ + cⁿ. Hence (bⁿ + cⁿ)^1/n < b + c/2. Similarly, (cⁿ + aⁿ)^1/n < a + c/2. Adding we get (bⁿ + cⁿ)^1/n + (cⁿ + aⁿ)^1/n < a+b+c = 1. Adding to (*) gives the required result.

 

 

Let the lines be L, L'. Let the square be ABA'B', with A, A' the two vertices not between L and L'. Let L meet AB at X and AB' at Y. Let L' meet A'B' at X' and A'B at Y'. So AXY and A'X'Y' are similar. Suppose angle AXY = x. If we move L towards A by a distance d perpendicular to itself, then AX is shortened by d cosec x. If L' remains a distance 1 from L, then A'X' is lengthened by d cosec x. The new triangle AXY is similar to the old. Suppose that perimeter AXY = k·AX, then perimeter AXY is increased by kd cosec x. Since AXY and A'X'Y' are similar, perimeter A'X'Y' is shortened by kd cosec x, so the sum of their perimeters is unchanged. It remains to show that the sum of the perimeters does not depend on the angle x.

Let us move L towards A until L' passes through A', at which point the perimeter of A'X'Y' is zero. Now if h is the height of AXY (from the base XY), then 1 + h = AA' sin(45^o + x) = sin x + cos x. The perimeter of AXY is h/sin x + h/cos x + h/(sin x cos x) = h(sin x + cos x + 1)/(sin x cos x) = (sin x + cos x - 1)(sin x + cos x + 1)/(sin x cos x) = 2, which is independent of x.

[more...]

14th Asian Pacific Mathematics Olympiad 2002 Problems

14th Asian Pacific Mathematics Olympiad 2002 Problems

A1.  x_i are non-negative integers. Prove that x₁! x₂! ... x_n! ≥ ( [(x₁ + ... + x_n)/n] ! )ⁿ (where [y] denotes the largest integer not exceeding y). When do you have equality?

A2.  Find all pairs m, n of positive integers such that m² - n divides m + n² and n² - m divides m² + n.

A3.  ABC is an equilateral triangle. M is the midpoint of AC and N is the midpoint of AB. P lies on the segment MC, and Q lies on the segment NB. R is the orthocenter of ABP and S is the orthocenter of ACQ. The lines BP and CQ meet at T. Find all possible values for angle BCQ such that RST is equilateral.

A4.  The positive reals a, b, c satisfy 1/a + 1/b + 1/c = 1. Prove that √(a + bc) + √(b + ca) + √(c + ab) ≥ √(abc) + √a + √b + √c.

A5.  Find all real-valued functions f on the reals which have at most finitely many zeros and satisfy f(x⁴ + y) = x³f(x) + f(f(y)) for all x, y. 

14th APMO 2002 Problem 1

x_i are non-negative integers. Prove that x₁! x₂! ... x_n! ≥ ( [(x₁ + ... + x_n)/n] ! )ⁿ (where [y] denotes the largest integer not exceeding y). When do you have equality?

Solution

Answer: Equality iff all x_i equal.

For given 2m the largest binomial coefficient is (2m)!/(m! m!) and for 2m+1 the largest binomial coefficient is (2m+1)!/( m! (m+1)!). Hence for fixed x_i + x_j the smallest value of x_i! x_j! is for x_i and x_j as nearly equal as possible.

If x₁ + x₂ + ... + x_n = qn + r, where 0 < r < n, then we can reduce one or more x_i to reduce the sum to qn. This will not affect the rhs of the inequality in the question, but will reduce the lhs. Equalising the x_i will not increase the lhs (by the result just proved). So it is sufficient to prove the inequality for all x_i equal. But in this case it is trivial since k! = k! . 

14th APMO 2002 Problem 2

Find all pairs m, n of positive integers such that m² - n divides m + n² and n² - m divides m² + n.

Solution

Assume n ≥ m.

(m+1)² - m = (m+1) + m². Clearly n² increases faster than n, so n² - m > n + m² for n > m+1 and hence there are no solutions with n > m+1. It remains to consider the two cases n = m and n = m+1.

Suppose n = m. Then we require that n² - n divides n² + n. If n > 3, then n² > 3n, so 2(n² - n) > n² + n. Obviously n² - n < n² + n, so if n > 3, then n² - n cannot divide n² + n. It is easy to check that the only solutions (with n = m) less than 3 are n = 2 and n = 3.

Finally suppose n = m+1. We require m² - m - 1 divides m² + 3m + 1. If m >= 6, then m(m - 5) > 3, so 2(m² - m - 1) > m² + 3m + 1. Obviously m² - m - 1 < m² + 3m + 1, so m² - m - 1 cannot divide m² + 3m + 1 for m >= 6. Checking the smaller values, we find the solutions less than 6 are m = 1 and m = 2.

Summarising, the only solutions are: (n, m) = (2, 2), (3, 3), (1, 2), (2, 1), (2, 3), (3, 2). 

14th APMO 2002 Problem 3

ABC is an equilateral triangle. M is the midpoint of AC and N is the midpoint of AB. P lies on the segment MC, and Q lies on the segment NB. R is the orthocenter of ABP and S is the orthocenter of ACQ. The lines BP and CQ meet at T. Find all possible values for angle BCQ such that RST is equilateral.

Answer 15^o.

Solution

 

Suppose CP < BQ. Since R is the intersection of BM and the perpendicular from P to AB, and S is the intersection of CN and the perpendicular from Q to AC, we have MR > NS. Hence (treating BC as horizontal), R is below S. But T must be to the right of the midpoint of BC. Hence T is to the right of the perpendicular bisector of RS, so RST cannot be equilateral. Contradiction. Similarly if CP > BQ. So CP = BQ. 

Let L be the midpoint of BC. Put ∠CBP = x and ∠RAM = y. So RM = AM tan y, TL = BL tan x = AM tan x. But ∠APB = 60^o + x, so y = 30^o - x. So if x ≠ 15^o, then TL ≠ RM. However, RST equilateral implies TL = RM, so x and hence also ∠BCQ = 15^o.

14th APMO 2002 Problem 4

The positive reals a, b, c satisfy 1/a + 1/b + 1/c = 1. Prove that √(a + bc) + √(b + ca) + √(c + ab) ≥ √(abc) + √a + √b + √c.

Solution

Thanks to Suat Namli for this.

Multiplying by √(abc), we have √(abc) = √(ab/c) + √(bc/a) + √(ca/b). So it is sufficient to prove that √(c + ab) ≥ √c + √(ab/c).

Squaring, this is equivalent to c + ab ≥ c + ab/c + 2√(ab) or c + ab ≥ c + ab(1 - 1/a - 1/b) + 2√(ab) or a + b >= 2√(ab) or (√a - √b)² ≥ 0.

[more...]

13th Asian Pacific Mathematics Olympiad 2001 Problems

13th Asian Pacific Mathematics Olympiad 2001 Problems

A1.  If n is a positive integer, let d be the number of digits in n (in base 10) and s be the sum of the digits. Let n(k) be the number formed by deleting the last k digits of n. Prove that n = s + 9 n(1) + 9 n(2) + ... + 9 n(d).

A2.  Find the largest n so that the number of integers less than or equal to n and divisible by 3 equals the number divisible by 5 or 7 (or both).

A3.  Two equal-sized regular n-gons intersect to form a 2n-gon C. Prove that the sum of the sides of C which form part of one n-gon equals half the perimeter of C.

A4.  Find all real polynomials p(x) such that x is rational iff p(x) is rational.

A5.  What is the largest n for which we can find n + 4 points in the plane, A, B, C, D, X₁, ... , X_n, so that AB is not equal to CD, but for each i the two triangles ABX_i and CDX_i are congruent? 

Solutions

13th APMO 2001 Problem 1

If n is a positive integer, let d+1 be the number of digits in n (in base 10) and s be the sum of the digits. Let n(k) be the number formed by deleting the last k digits of n. Prove that n = s + 9 n(1) + 9 n(2) + ... + 9 n(d).

Solution

Let the digits of n be a_d, a_d-1, ... , a₀, so that n = a_d 10^d + ... + a₀. Then n(k) = a_d 10^d-k + a^d-1 10^d-k-1 + ... + a_k. Obviously s = a_d + ... + a₀. Hence s + 9 n(1) + ... + 9 n(d) = a_d(9.10^d-1 + 9.10^d-2 + ... + 9 + 1) + a_d-1(9.10^d-2 + ... + 9 + 1) + ... + a_d-k(9.10^d-k-1 + ... + 9 + 1) + a₁(9 + 1) + a₀ = a_d 10^d + ... + a₀ = n. 

13th APMO 2001 Problem2

Find the largest n so that the number of integers less than or equal to n and divisible by 3 equals the number divisible by 5 or 7 (or both).

Solution

Answer: 65.

Let f(n) = [n/3] - [n/5] - [n/7] + [n/35]. We are looking for the largest n with f(n) = 0. Now [n/5] + [n/7} <= [n/5 + n/7] = [12n/35] = [n/3 + n/105]. So for [n/5] + [n/7] to exceed [n/3] we certainly require n/105 ≥ 1/3 or n ≥ 35. Hence f(n) ≥ 0 for n ≤ 35. But f(n+35) = [n/3 + 11 + 2/3] - [n/5 + 7] - [n/7 + 5] + [n/35 + 1] = [n/3 + 2/3] - [n/5] - [n/7] + [n/35] ≥ f(n) (*). Hence f(n) ≥ 0 for all n. But f(n+105) = [n/3 + 35] - [n/5 + 21] - [n/7 + 15] + [n/35 + 3] = f(n) + 2. Hence f(n) ≥ 2 for all n ≥ 105.

Referring back to (*) we see that f(n+35) > f(n), and hence f(n+35) > 0, unless n is a multiple of 3. But if n is a multiple of 3, then n + 35 is not and hence f(n+70) > f(n+35) > 0. So f(n) > 0 for all n ≥ 70.

f(70) = 1. So f(69) = 2 (we have lost 70, a multiple of 7). So f(68) = f(67) = f(66) = 1 (we have lost 69, a multiple of 3). Hence f(65) = 0 (we have lost 66, a multiple of 3). 

13th APMO 2001 Problem3

Two equal-sized regular n-gons intersect to form a 2n-gon C. Prove that the sum of the sides of C which form part of one n-gon equals half the perimeter of C.

Solution

Let one regular n-gon have vertices P₁, P₂, ... , P_n and the other have vertices Q₁, Q₂, ... , Q_n. Each side of the 2n-gon forms a triangle with one of the P_i or Q_i. Note that P_i and Q_j must alternate as we go around the 2n-gon. For convenience assume that the order is P₁, Q₁, P₂, Q₂, ... , P_n, Q_n. Let the length of the side which forms a triangle with P_i be p_i, and the length of the side which forms a triangle with Q_i be q_i. Each of these triangles has one angle (180^o - 360^o/n). Adjacent triangles have one of their other angles equal (alternate angles), so all the triangles are similar. If the sides of the triangle vertex P_i have lengths a_i, b_i, p_i, then the side P_iP_i+1 is b_i + q_i + a_i+1, and a_i/a_i+1 = b_i/b_i+1 = p_i/p_i+1. Similarly, if the sides of the triangle vertex Q_i have lengths c_i, d_i, q_i, then the side Q_iQ_i+1 is d_i + p_i+1 + c_i+1 and c_i/c_i+1 = d_i/d_i+1 = q_i/q_i+1. But a_i/b_i = d_i/c_i (not c_i/d_i), because the triangles alternate in orientation.

Put a_i/p_i = h, b_i/p_i = k. Note that a_i + b_i > p_i, so h + k - 1 > 0. We have also c_i/q_i = k, d_i/q_i = h. Adding the expressions for P_iP_i+1 we get perimeter P_i = ∑(b_i + q_i + a_i+1) = k ∑ p_i + ∑ q_i + h ∑ p_i. Similarly, perimeter Q_i = (h + k) ∑ q_i + ∑ p_i. The two n-gons are equal, so (h + k - 1) ∑ p_i = (h + k - 1) ∑ q_i. Hence ∑ p_i = ∑ q_i, which is the required result.

13th APMO 2001 Problem4

Find all real polynomials p(x) such that x is rational iff p(x) is rational.

Solution

It is necessary for all the coefficients of x to be rational. This is an easy induction on the number of coefficients. For p(0) must be rational, hence ( p(x) - p(0) )/x must be rational for all rational x and so on.

Clearly this condition is also sufficient for polynomials of degree 0 or 1.

There are obviously no quadratics, for if p(x) = ax² + bx + c, with a, b, c rational, then p(√2 - b/2a) = 2a - b²/4a + c, which is rational.

We prove that if there are also no higher degree polynomials. The idea is to show that there is a rational value k which must be taken for some real x, but which cannot be taken by any rational x.

Suppose p(x) has degree n > 1. Multiplying through by the lcm of the denominators of the coefficients, we get p(x) = (a xⁿ + b x^n-1 + ... + u x + v)/w, where a, b, ... , w are all integers. Put x = r/s, where r and s are coprime integers, then p(r/s) = (a rⁿ + b r^n-1s + ... + u r s^n-1 + v sⁿ)/( w sⁿ). Let q be any prime which does not divide a or w. Consider first a > 0. p(x) must assume all sufficiently large positive values. So it must in particular take the value k = m + 1/q, where m is a sufficiently large integer. So k = (mq + 1)/q. The denominator is divisible by q, but not q² and the numerator is not divisible by q. Suppose p(r/s) = k for some integers r, s. The denominator of p(r/s) is w sⁿ. We know that w is not divisible by q, so q must divide s. But n > 1, so q² divides w sⁿ. The numerator of p(r/s) has the form a rⁿ + h s. Neither a nor r is divisible by q, so the numerator is not divisible by q. Thus no cancellation is possible and we cannot have p(r/s) = k. Thus there must be some irrational x such that p(x) = k.

If a < 0, then the same argument works except that we take k = m + 1/q, where m is a sufficiently large negative integer.

13th APMO 2001 Problem 5

What is the largest n for which we can find n + 4 points in the plane, A, B, C, D, X₁, ... , X_n, so that AB is not equal to CD, but for each i the two triangles ABX_i and CDX_i are congruent?

Answer 4

Solution

Many thanks to Allen Zhang for completing the proof

Assume AB = a, CD = b with a > b. If ABX and CDX are congruent, then either AX or BX = CD = b, so X lies either on the circle S_A center A radius b, or on the circle S_Bcenter B radius b. Similarly, CX or DX = AB = a, so X lies either on the circle S_C center C radius a, or on the circle S_D center D radius a. Thus we have four pairs of circles, (S_A, S_C), (S_A, S_D), (S_B, S_C), (S_B, S_D) each with at most 2 points of intersection. X must be one of these 8 points.

However, we show that if two points of intersection of (S_A, S_C) are included, then no points of (S_B, S_D) can be included. The same applies to each pair of circles, so at most 4 points X are possible. Finally, we will give an example of n = 4, showing that the maximum of 4 is achieved.

So suppose (S_A, S_C) intersect at X and Y. We must have BX = DX and BY = DY, so X and Y both lie on the perpendicular bisector of BD. In other words, XY is the perpendicular bisector of BD, so D is the reflection of B in the line XY. There is no loss of generality in taking B (and D) to be on the same side of AC as X. Let A' be the reflection of A in the line XY. Since B lies on the circle center A radius a, D must lie on the circle center A' radius A. Thus the triangles A'XC and CDA' are congruent.

(Note that A and C can be on the same side of XY or opposite sides.) Hence D is the same height above AC as X, so DX is perpendicular to XY. Hence X is the midpoint of BD. Also ∠A'CD = ∠CA'X = 180^o - ∠CAX, so AX and CD are parallel. They are also equal, so ACDX is a parallelogram and hence AC = DX = BD/2. In the second configuration above, both A and C are on the same side of XY as D, so the midpoint M of AC lies on the same side of XY as D. In the first configuration, since AX = b < a = CX, M lies to the right of XY.

Now suppose there is a solution for the configuration (S_B, S_D). Thus there is a point Z such that ABZ and ZDC are congruent. Then AZ = CZ, so Z lies on the perpendicular bisector of AC and hence on the same side of XY as D. But it is also a distance a from D and a distance b from B, and a > b, so it must lie on the same side of XY as B. Contradiction. So there are no solutions for the configuration (S_B, S_D), as required. That completes the proof that n ≤ 4.

For an example with n = 4, take a regular hexagon ACDBX₃X₂. Extend the side X₂X₃ to X₁X₄, with X₁, X₂, X₃, X₄ equally spaced in that order, so that X₁AX₂ and X₃BX₄ are equilateral. Then ABX₁ and CX₁D are congruent, ABX₂ and DX₂C are congruent, ABX₃ and X₃CD are congruent, and ABX₄ and X₄DC are congruent.

[more...]

12th Asian Pacific Mathematics Olympiad 2000 Problems

12th Asian Pacific Mathematics Olympiad 2000 Problems

A1.  Find a₁³/(1 - 3a₁ + 3a₁²) + a₂³/(1 - 3a₂ + 3a₂²) + ... + a₁₀₁³/(1 - 3a₁₀₁ + 3a₁₀₁²), where a_n = n/101.

A2.  Find all permutations a₁, a₂, ... , a₉ of 1, 2, ... , 9 such that a₁ + a₂ + a₃ + a₄ = a₄ + a₅ + a₆ + a₇ = a₇ + a₈ + a₉ + a₁ and a₁² + a₂² + a₃² + a₄² = a₄² + a₅² + a₆² + a₇² = a₇² + a₈² + a₉² + a₁².

A3.  ABC is a triangle. The angle bisector at A meets the side BC at X. The perpendicular to AX at X meets AB at Y. The perpendicular to AB at Y meets the ray AX at R. XY meets the median from A at S. Prove that RS is perpendicular to BC.

A4.  If m < n are positive integers prove that nⁿ/(m^m (n-m)^n-m) > n!/( m! (n-m)! ) > nⁿ/( m^m(n+1) (n-m)^n-m).

A5.  Given a permutation s₀, s₂, ... , s_n of 0, 1, 2, .... , n, we may transform it if we can find i, j such that s_i = 0 and s_j = s_i-1 + 1. The new permutation is obtained by transposing s_i and s_j. For which n can we obtain (1, 2, ... , n, 0) by repeated transformations starting with (1, n, n-1, .. , 3, 2, 0)? 

Solutions

Find a₁³/(1 - 3a₁ + 3a₁²) + a₂³/(1 - 3a₂ + 3a₂²) + ... + a₁₀₁³/(1 - 3a₁₀₁ + 3a₁₀₁²), where a_n = n/101.

Solution

Answer: 51.

The nth term is a_n³/(1 - 3a_n + 3a_n²) = a_n³/( (1 - a_n)³ + a_n³) = n³/( (101 - n)³ + n³). Hence the sum of the nth and (101-n)th terms is 1. Thus the sum from n = 1 to 100 is 50. The last term is 1, so the total sum is 51.

Find all permutations a₁, a₂, ... , a₉ of 1, 2, ... , 9 such that a₁ + a₂ + a₃ + a₄ = a₄ + a₅ + a₆ + a₇ = a₇ + a₈ + a₉ + a₁ and a₁² + a₂² + a₃² + a₄² = a₄² + a₅² + a₆² + a₇² = a₇² + a₈² + a₉² + a₁².

Solution

We may start by assuming that a₁ < a₄ < a₇ and that a₂ < a₃, a₅ < a₆, a₈ < a₉.

Note that 1 + ... + 9 = 45 and 1² + ... + 9² = 285. Adding the three square equations together we get (a₁² + ... + a₉²) + a₁² + a₄² + a₇² = 285 + a₁² + a₄² + a₇². The total must be a multiple of 3. But 285 is a multiple of 3, so a₁² + a₄² + a₇² must be a multiple of 3. Now 3², 6² and 9² are all congruent to 0 mod 3 and the other squares are all congruent to 1 mod 3. Hence either a₁, a₄ and a₇ are all multiples of 3, or none of them are. Since 45 is also a multiple of three a similar argument with the three linear equations shows that a₁ + a₄ + a₇ is a multiple of 3. So if none of a₁, a₄, a₇ are multiples of 3, then they are all congruent to 1 mod 3 or all congruent to 2 mod 3. Thus we have three cases: (1) a₁ = 3, a₄ = 6, a₇ = 9, (2) a₁ = 1, a₄ = 4, a₇ = 7, and (3) a₁ = 2, a₄ = 5, a₇ = 8.

In case (1), we have that each sum of squares equals 137. Hence a₈² + a₉² = 47. But 47 is not a sum of two squares, so this case gives no solutions.

In case (2), we have that each sum of squares is 117. Hence a₅² + a₆² = 52. But the only way of writing 52 as a sum of two squares is 4² + 6² and 4 is already taken by a₄, so this case gives no solutions.

In case (3), we have that each sum of squares is 126 and each linear sum 20. We quickly find that the only solution is 2, 4, 9, 5, 1, 6, 8, 3, 7.

Obviously, this generates a large number of equivalent solutions. We can interchange a₂ and a₃, or a₅ and a₆, or a₈ and a₉. We can also permute a₁, a₄ and a₇. So we get a total of 2 x 2 x 2 x 6 =48 solutions. 

ABC is a triangle. The angle bisector at A meets the side BC at X. The perpendicular to AX at X meets AB at Y. The perpendicular to AB at Y meets the ray AX at R. XY meets the median from A at S. Prove that RS is perpendicular to BC.

Solution

Let the line through C parallel to AX meet the ray BA at C'. Let the perpendicular from B meet the ray C'C at T and the ray AX at U. Let the line from C parallel to BT meet BA at V and let the perpendicular from V meet BT at W. So CVWT is a rectangle.

AU bisects ∠CAV and CV is perpendicular to AU, so U is the midpoint of WT. Hence the intersection N of AU and CW is the center of the rectangle and, in particular, the midpoint of CW. Let M be the midpoint of BC. Then since M, N are the midpoints of the sides CB and CW of the triangle CBW, MN = BW/2.

Since CC' is parallel to AX, ∠CC'A = ∠BAX = ∠CAX = ∠C'CA, so AC' = AC. Let A' be the midpoint of CC'. Then AU = C'T - C'A'. But N is the center of the rectangle CTWV, so NU = CT/2 and AN = AU - NU = C'T - C'A' - CT/2 = C'T/2. Hence MN/AN = BW/C'T. But MN is parallel to BW and XY, so SX/AX = MN/AN = BW/C'T.

Now AX is parallel to VW and XY is parallel to BW, so AXY and VWB are similar and AX/XY = VW/BW = CT/BW. Hence SX/XY = (SX/AX) (AX/XY) = CT/C'T.

YX is an altitude of the right-angled triangle AXR, so AXY and YXR are similar. Hence XY/XR = XA/XY. But AXY and C'TB are similar, so XA/XY = C'T/BT. Hence SX/XR = (SX/XY) (XY/XR) = (CT/C'T) (C'T/BT) = CT/BT. But angles CTB and SXR are both right angles, so SXR and CTB are similar. But XR is perpendicular to BT, so SR is perpendicular to BC. 

If m < n are positive integers prove that nⁿ/(m^m (n-m)^n-m) > n!/( m! (n-m)! ) > nⁿ/( m^m(n+1) (n-m)^n-m).

Solution

The key is to consider the binomial expansion (m + n-m)ⁿ. This is a sum of positive terms, one of which is nCm m^m(n-m)^n-m, where nCm is the binomial coefficient n!/( m! (n-m)! ). Hence nCm m^m(n-m)^n-m < nⁿ, which is one of the required inequalities.

We will show that nCm m^m(n-m)^n-m is the largest term in the binomial expansion. It then follows that (n+1) nCm m^m(n-m)^n-m > nⁿ, which is the other required inequality.

Comparing the rth term nCr m^r(n-m)^n-r with the r+1th term nCr+1 m^r+1(n-m)^n-r-1 we see that the rth term is strictly larger for r ≥ m and smaller for r < m. Hence the mth term is larger than the succeeding terms and also larger than the preceding terms.

Given a permutation s₀, s₂, ... , s_n of 0, 1, 2, .... , n, we may transform it if we can find i, j such that s_i = 0 and s_j = s_i-1 + 1. The new permutation is obtained by transposing s_i and s_j. For which n can we obtain (1, 2, ... , n, 0) by repeated transformations starting with (1, n, n-1, .. , 3, 2, 0)?

Solution

Experimentation shows that we can do it for n=1 (already there), n = 2 (already there), 3, 7, 15, but not for n = 4, 5, 6, 8, 9, 10, 11, 12, 13, 14. So we conjecture that it is possible just for n = 2^m - 1 and for n = 2.

Notice that there is at most one transformation possible. If n = 2m, then we find that after m-1 transformations we reach

1  n  0  n-2  n-1  n-4  n-3 ... 4  5  2  3

and we can go no further. So n even fails for n > 2.

If n = 15 we get successively:

1 15 14 13 12 11 10 9 8 7 6 5 4 3 2 0 start
1 0 14 15 12 13 10 11 8 9 6 7 4 5 2 3 after 7 moves
1 2 3 0 12 13 14 15 8 9 10 11 4 5 6 7 after 8 more moves
1 2 3 4 5 6 7 0 8 9 10 11 12 13 14 15 after 8 more moves

1   2   3   4   5   6   7   8   9  10  11  12  13  14  15   0   after 8 more moves

This pattern is general. Suppose n = 2^m - 1. Let P₀ be the starting position and P_r be the position:

1   2   3 ... R-1   0,   n-R+1  n-R+2  n-R+3 ... n,   n-2R+1  n-2R+2 ... n-R, ... , R  R+1 ... 2R-1 

Here R denotes 2^r and the commas highlight that, after the initial 1 2 ... R-1 0, we have increasing runs of R terms. If we start from P_r, then the 0 is transposed successively with R, 3R, 5R, ... , n-R+1, then with R+1, 3R+1, ... , n-R+2, and so on up to 2R-1, 4R-1, ... , n. But that gives P_r+1. It is also easy to check that P₀ leads to P₁ and that P_m is the required finishing position. Thus the case n = 2^m - 1 works. Now suppose n is odd but not of the form 2^m - 1. Then we can write n = (2a + 1)2^b - 1 (just take 2^b as the highest power of 2 dividing n + 1). We can now define P₀, P₁, ... , P_b as before. As before we will reach P_b:

1 2 ¼ B-1 0, 2aB 2aB+1¼ (2a+1)B-1, (2a-1)B ¼ 2aB-1, ¼ , 3B, 3B+1, ¼ 4B-1, 2B, 2B+1, ¼ , 3B-1, B, B+1, ¼ , 2B-1 

where B = 2^b - 1. But then the 0 is transposed successively with B, 3B, 5B, ... , (2a-1)B, which puts it immediately to the right of (2a+1)B-1 = n, so no further transformations are possible and n = (2a+1)2^b - 1 fails.

[more...]

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.

[more...]

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.

[more...]

9th Asian Pacific Mathematics Olympiad 1997 Problems

9th Asian Pacific Mathematics Olympiad 1997 Problems

A1.  Let T_n = 1 + 2 + ... + n = n(n+1)/2. Let S_n= 1/T₁ + 1/T₂ + ... + 1/T_n. Prove that 1/S₁ + 1/S₂ + ... + 1/S₁₉₉₆ > 1001.

A2.  Find an n in the range 100, 101, ... , 1997 such that n divides 2ⁿ + 2.

A3.  ABC is a triangle. The bisector of A meets the segment BC at X and the circumcircle at Y. Let r_A = AX/AY. Define r_B and r_C similarly. Prove that r_A/sin²A + r_B/sin²B + r_C/sin²C ≥ 3 with equality iff the triangle is equilateral.

A4.  P₁ and P₃ are fixed points. P₂ lies on the line perpendicular to P₁P₃ through P₃. The sequence P₄, P₅, P₆, ... is defined inductively as follows: P_n+1 is the foot of the perpendicular from P_n to P_n-1P_n-2. Show that the sequence converges to a point P (whose position depends on P₂). What is the locus of P as P₂ varies?

A5.  n people are seated in a circle. A total of nk coins are distributed amongst the people, but not necessarily equally. A move is the transfer of a single coin between two adjacent people. Find an algorithm for making the minimum number of moves which result in everyone ending up with the same number of coins?

Let T_n = 1 + 2 + ... + n = n(n+1)/2. Let S_n= 1/T₁ + 1/T₂ + ... + 1/T_n. Prove that 1/S₁ + 1/S₂ + ... + 1/S₁₉₉₆ > 1001.

Solution

1/T_m = 2(1/m - 1/(m+1) ). Hence S_n/2 = 1 - 1/(n+1). So 1/S_n = (1 + 1/n)/2. Hence 1/S₁ + 1/S₂ + ... + 1/S_n = 1996/2 + (1+ 1/2 + 1/3 + ... + 1/1996)/2.

Now 1 + 1/2 + (1/3 + 1/4) + (1/5 + 1/6 + 1/7 + 1/8) + (1/9 + ... + 1/16) + (1/17 + ... + 1/32) + (1/33 + ... + 1/64) + (1/65 + ... + 1/128) + (1/129 + ... + 1/256) + (1/257 + ... + 1/512) + (1/513 + ... + 1/1024) > 1 + 1/2 + 1/2 + ... + 1/2 = 6. So 1/S₁ + 1/S₂ + ... + 1/S_n = 1996/2 + 6/2 = 998 + 3 = 1001. 

Find an n in the range 100, 101, ... , 1997 such that n divides 2ⁿ + 2.

Solution

Answer: the only such number is 946.

We have 2^p-1 = 1 mod p for any prime p, so if we can find h in {1, 2, ... , p-2} for which 2^h = -2 mod p, then 2^k= -2 mod p for any h = k mod p. Thus we find that 2^k = -2 mod 5 for k = 3 mod 4, and 2^k = -2 mod 11 for k = 6 mod 10. So we might then hope that 5·11 = 3 mod 4 and = 6 mod 10. Unfortunately, it does not! But we try searching for more examples.

The simplest would be to look at pq. Suppose first that p and q are both odd, so that pq is odd. If k = h mod p-1, then we need h to be odd (otherwise pq would have to be even). So the first step is to get a list of primes p with 2^h = -2 mod p for some odd h < p. We always have 2^p-1 = 1 mod p, so we sometimes have 2^(p-1)/2 = -1 mod p and hence 2^(p+1)/2 = -2 mod p. If (p+1)/2 is to be odd then p =1 mod 4. So searching such primes we find 3 mod 5, 7 mod 13, 15 mod 29, 19 mod 37, 27 mod 53, 31 mod 61. We require pq to lie in the range 100-1997, so we check 5·29 (not = 3 mod 4), 5·37 (not = 3 mod 4), 5·53 (not = 3 mod 4), 5·61 (not = 3 mod 4), 13·29 (not = 7 mod 12), 13·37 (not = 7 mod 12), 13.53 (not = 7 mod 12), 13·61 (not = 7 mod 12), 29·37 (not = 15 mod 28), 29·53 (not = 15 mod 28), 29·61 (not = 15 mod 28), 37·53 (not = 19 mod 36). So that does not advance matters much!

2p will not work (at least with h = (p+1)/2) because we cannot have 2p = (p+1)/2 mod p-1. So we try looking at 2pq. This requires that p and q = 3 mod 4. So searching for suitable p we find 6 mod 11, 10 mod 19, 22 mod 43, 30 mod 59, 34 mod 67, 42 mod 83. So we look at 2·11·43 = 946, which works.

Proving that it is unique is harder. The easiest way is to use a computer to search (approx 5 min to write a Maple program or similar and a few seconds to run it). 

ABC is a triangle. The bisector of A meets the segment BC at X and the circumcircle at Y. Let r_A = AX/AY. Define r_B and r_C similarly. Prove that r_A/sin²A + r_B/sin²B + r_C/sin²C >= 3 with equality iff the triangle is equilateral.

Solution

AX/AB = sin B/sin AXB = sin B/sin(180 - B - A/2) =sin B/sin(B + A/2). Similarly, AB/AY = sin AYB/sin ABY = sin C/sin(B + CBY) = sin C/sin(B + A/2). So AX/AY = sin B sin C/sin²(B + A/2). Hence r_A/sin²A = s_A/sin²(B + A/2), where s_A = sin B sin C/sin²A. Similarly for r_B and r_C. Now s_As_Bs_C = 1, so the arithmetic/geometric mean result gives s_A + s_B + s_C ≥ 3. But 1/sin k ≥ 1 for any k, so r_A/sin²A + r_B/sin²B + r_C/sin²C ≥ 3.

A necessary condition for equality is that sin²(B + A/2) = sin²(B + A/2) = sin²(B + A/2) = 1 and hence A = B = C. But it is easily checked that this is also sufficient.

P₁ and P₃ are fixed points. P₂ lies on the line perpendicular to P₁P₃ through P₃. The sequence P₄, P₅, P₆, ... is defined inductively as follows: P_n+1 is the foot of the perpendicular from P_n to P_n-1P_n-2. Show that the sequence converges to a point P (whose position depends on P₂). What is the locus of P as P₂ varies?

Solution

P_nP_n+1P_n+2 lies inside P_n-1P_nP_n+1. So we have sequence of nested triangles whose size shrinks to zero. Each triangle is a closed set, so there is just one point P in the intersection of all the triangles and it is clear that the sequence P_n converges to it.

Obviously all the triangles P_nP_n+1P_n+2 are similar (but not necessarily with the vertices in that order). So P must lie in the same position relative to each triangle and we must be able to obtain one triangle from another by rotation and expansion about P. In particular, P₅P₄P₆ is similar (with the vertices in that order) to P₁P₂P₃, and P₄P₅ is parallel to P₁P₂, so the rotation to get one from the other must be through π and P must lie on P₁P₅. Similarly P₃P₄P₅ must be obtained from P₁P₂P₃ by rotation about P through π/2 and expansion. But this takes P₁P₅ into a perpendicular line through P₃. Hence P₁P is perpendicular to P₃P. Hence P lies on the circle diameter P₁P₃.

However, not all points on this circle are points of the locus. P₃P₅ = P₃P₄ cos P₁ = P₃P₁ sin P₁ cos P₂ = 1/2 P₃P₁ sin 2P₁, so we can obtain all values of P₃P₅ up to P₁P₃/2. [Of course, P₂, and hence P₅, can be on either side of P₃.]. Thus the locus is an arc XP₃Y of the circle with XP₃ = YP₃ and ∠XP₁Y = 2 tan^-11/2. If O is the midpoint of P₁P₃, then O is the center of the circle and ∠XOY = 4 tan^-11/2 (about 106^o).

n people are seated in a circle. A total of nk coins are distributed amongst the people, but not necessarily equally. A move is the transfer of a single coin between two adjacent people. Find an algorithm for making the minimum number of moves which result in everyone ending up with the same number of coins?

Solution

Label the people from 1 to n, with person i next to person i+1, and person n next to person 1. Let person i initially hold c_i coins. Let d_i = c_i - k.

It is not obvious how many moves are needed. Clearly at least 1/2 ∑ |d_i| are needed. But one may need more. For example, suppose the starting values of d_i are 0, 1, 0, -1, 0. Then one needs at least 2 moves, not 1.

Obviously ∑ d_i = 0, so not all d_i can be negative. Relabel if necessary so that d₁ ≥= 0. Now consider X = |d₁| + |d₁ + d₂| + |d₁ + d₂ + d₃| + ... + |d₁ + d₂ + ... + d_n-1|. Note first that X is zero iff all d_i are zero. Any move between i and i+1, except one between n and 1, changes X by 1, because only the term |d₁ + d₂ + ... + d_i| is affected. Thus if we do not make any moves between n and 1, then we need at least X moves to reach the desired final position (with all d_i zero).

Assume X > 1. We show how to find a move which reduces X by 1. This requires a little care to avoid specifying a move which might require a person with no coins to transfer one. We are assuming that d₁ ≥ 0. Take the first i for which d_i+1 < 0. There must be such an i, otherwise all d_i would be non-negative, but they sum to 0, so they would all have to be zero, contradicting X > 0. If d₁ + ... + d_i > 0, then we take the move to be a transfer from i to i+1. This will reduce |d₁ + ... + d_i| by 1 and leave the other terms in X unchanged, so it will reduce X by 1. If d₁ + ... + d_i is not strictly positive, then by the minimality of i we must have d₁ = d₂ = ... = d_i = 0. We know that d_i+1 < 0. Now find the first j > i+1 such that d_j ≥ 0. There must be such a j, otherwise we would have ∑ d_m < 0. We have d₁ + ... + d_j-1 < 0, so a transfer from j to j-1 will reduce |d₁ + ... + d_j-1| and hence reduce X. Finally note that the move we have chosen leaves d₁ ≥ 0. Thus we can repeat the process and reduce X to zero in X moves.

We have proved that this procedure minimises the number of moves if we accept the restriction that we do not make any transfers between 1 and n. Thus the full algorithm is: calculate the effect of the transfers from 1 to n and from n to 1 on X. If either of these transfers reduces X by more than 1, then take the move with the larger reduction; otherwise, find a move as above which reduces X by 1; repeat.

[more...]

8th Asian Pacific Mathematics Olympiad 1996 Problems

8th Asian Pacific Mathematics Olympiad 1996 Problems

A1.  ABCD is a fixed rhombus. P lies on AB and Q on BC, so that PQ is perpendicular to BD. Similarly P' lies on AD and Q' on CD, so that P'Q' is perpendicular to BD. The distance between PQ and P'Q' is more than BD/2. Show that the perimeter of the hexagon APQCQ'P' depends only on the distance between PQ and P'Q'.

A2.  Prove that (n+1)^mn^m ≥ (n+m)!/(n-m)! ≥ 2^mm! for all positive integers n, m with n ≥ m.

A3.  Given four concyclic points. For each subset of three points take the incenter. Show that the four incenters from a rectangle.

A4.  For which n in the range 1 to 1996 is it possible to divide n married couples into exactly 17 single sex groups, so that the size of any two groups differs by at most one.

A5.  A triangle has side lengths a, b, c. Prove that √(a + b - c) + √(b + c - a) + √(c + a - b) ≤ √a + √b + √c. When do you have equality?

ABCD is a fixed rhombus. P lies on AB and Q on BC, so that PQ is perpendicular to BD. Similarly P' lies on AD and Q' on CD, so that P'Q' is perpendicular to BD. The distance between PQ and P'Q' is more than BD/2. Show that the perimeter of the hexagon APQCQ'P' depends only on the distance between PQ and P'Q'.

Solution

BPQ and DQ'P' are similar. Let PQ meet BD at X and P'Q' meet BD at Y. XY is fixed, so BX + DY is fixed. Hence also, BP + DQ' and BQ + DP' and PQ + P'Q' are fixed. So PQ + P'Q' - BP - BQ - DP' - DQ' is fixed, so PQ + P'Q' + (AB - BP) + (BC - BQ) + (CD - DP') + (DA - DQ') is fixed, and that is the perimeter of the hexagon.

Prove that (n+1)^mn^m ≥ (n+m)!/(n-m)! ≥ 2^mm! for all positive integers n, m with n ≥ m.

Solution

For any integer k ≥ 1, we have (n + k)(n - k + 1) = n² + n - k² + k ≤ n(n + 1). Taking the product from k = 1 to m we get (n + m)!/(n - m)! ≤ (n + 1)^mn^m.

For k = 1, 2, ... , m, we have n ≥ k and hence n + k ≥ 2k. Taking the product from k = 1 to m, we get (n + m)!/(n - m)! ≥ 2^mm! .

Given four concyclic points. For each subset of three points take the incenter. Show that the four incenters from a rectangle.

Solution

Take the points as A, B, C, D in that order. Let I be the incenter of ABC. The ray CI bisects the angle ACB, so it passes through M, the midpoint of the arc AB. Now ∠MBI = ∠MBA + ∠IBA = ∠MCA + ∠IBA = (∠ACB + ∠ABC)/2 = 90^o - (∠CAB) /2 = 90^o - ∠CMB/2 = 90^o - ∠IMB/2. So the bisector of ∠IMB is perpendicular to IB. Hence MB = MI. Let J be the incenter of ABD. Then similarly MA = MJ. But MA = MB, so the four points A, B, I, J are concyclic (they lie on the circle center M). Hence ∠BIJ = 180^o - ∠BAJ = 180^o - ∠BAD/2.

Similarly, if K is the incenter of ADC, then ∠BJK = 180^o - ∠BDC/2. Hence ∠IJK = 360^o - ∠BIJ - ∠BJK = (180^o - ∠BIJ) + (180^o - ∠BJK) = (∠BAD + ∠BDC)/2 = 90^o. Similarly, the other angles of the incenter quadrilateral are 90^o, so it is a rectangle.

For which n in the range 1 to 1996 is it possible to divide n married couples into exactly 17 single sex groups, so that the size of any two groups differs by at most one.

Solution

Answer: 9, 10, 11, 12, 13, 14, 15, 16, 18, 19, 20, 21, 22, 23, 24, 27, 28, 29, 30, 31, 32, 36, 37, 38, 39, 40, 45, 46, 47, 48, 54, 55, 56, 63, 64, 72.

If n = 17k, then the group size must be 2k. Hence no arrangement is possible, because one sex has at most 8 groups and 8.2k < n.

If 2n = 17k+h with 0 < h < 17, then the group size must be k or k+1. One sex has at most 8 groups, so 8(k+1) ≥ n. Hence 16k + 16 ≥ 17k + h, so 16 - h ≥ k (*). We also require that 9k ≤ n. Hence 18k < 2n = 17k + h, so k ≤ h (**). With (*) this implies that k ≤ 8. So n ≤ 75.

Each group has at least one person, so we certainly require n ≥ 9 and hence k ≥ 1. It is now easiest to enumerate. For k = 1, we can have h = 1, 3, ... 15, giving n = 9-16. For k = 2, we can have h = 2, 4, ... 14, giving n = 18-24. For k = 3, we can have h = 3, 5, ... 13, giving n = 27-32. For k = 4, we can have h = 4, 6, ... 12, giving n = 36-40. For k = 5 we can have h = 5, 7, 9, 11, giving n = 45-48. For k = 6, we can have h = 6, 8, 10, giving n = 54, 55, 56. For k = 7, we can have h = 7, 9, giving n = 63, 64. For k = 8, we can have h = 8, giving n = 72.

A triangle has side lengths a, b, c. Prove that √(a + b - c) + √(b + c - a) + √(c + a - b) ≤ √a + √b + √c. When do you have equality?

Solution

Let A² = b + c - a, B² = c + a - b, C² = a + b - c. Then A² + B² = 2c. Also A = B iff a = b. We have (A - B)² ≥ 0, with equality iff A = B. Hence A² + B² ≥ 2AB and so 2(A² + B²) ≥ (A + B)² or 4c ≥ (A + B)² or 2√c ≥ A + B, with equality iff A = B. Adding the two similar relations we get the desired inequality, with equality iff the triangle is equilateral.

[more...]

7th Asian Pacific Mathematics Olympiad 1995 Problems

7th Asian Pacific Mathematics Olympiad 1995 Problems

A1.  Find all real sequences x₁, x₂, ... , x₁₉₉₅ which satisfy 2√(x_n - n + 1) ≥ x_n+1 - n + 1 for n = 1, 2, ... , 1994, and 2√(x₁₉₉₅ - 1994) ≥ x₁ + 1.

A2.  Find the smallest n such that any sequence a₁, a₂, ... , a_n whose values are relatively prime square-free integers between 2 and 1995 must contain a prime. [An integer is square-free if it is not divisible by any square except 1.]

A3.  ABCD is a fixed cyclic quadrilateral with AB not parallel to CD. Find the locus of points P for which we can find circles through AB and CD touching at P.

A4.  Take a fixed point P inside a fixed circle. Take a pair of perpendicular chords AC, BD through P. Take Q to be one of the four points such that AQBP, BQCP, CQDP or DQAP is a rectangle. Find the locus of all possible Q for all possible such chords.

A5.  f is a function from the integers to {1, 2, 3, ... , n} such that f(A) and f(B) are unequal whenever A and B differ by 5, 7 or 12. What is the smallest possible n? 

Solution

A1. Find all real sequences x₁, x₂, ... , x₁₉₉₅ which satisfy 2√(x_n - n + 1) ≥ x_n+1 - n + 1 for n = 1, 2, ... , 1994, and 2√(x₁₉₉₅ - 1994) ≥ x₁ + 1.

Solution

Answer: the only such sequence is 1, 2, 3, ... , 1995.

Put x₁₉₉₅ = 1995 + k. We show by induction (moving downwards from 1995) that x_n ≥ n + k. For suppose x_n+1 ≥ n + k + 1, then 4(x_n - n + 1) ≥ (x_n+1- n + 1)² ≥ (k+2)² ≥ 4k + 4, so x_n ≥ n + k. So the result is true for all n ≥ 1. In particular, x₁ ≥ 1 + k. Hence 4(x₁₉₉₅ - 1994) = 4(1 + k) ≥ (2 + k)² = 4 + 4k + k², so k² ≤ 0, so k = 0.

Hence also x_n ≥ n for n = 1, 2, ... , 1994. But now if x_n = n + k, with k > 0, for some n < 1995, then the same argument shows that x₁ ≥ 1 + k and hence 4 = 4(x₁₉₉₅ - 1994) ≥ (x₁ + 1)² ≥ (2 + k)² = 4 + 4k + k² > 4. Contradiction. Hence x_n = n for all n ≤ 1995.

Find the smallest n such that any sequence a₁, a₂, ... , a_n whose values are relatively prime square-free integers between 2 and 1995 must contain a prime. [An integer is square-free if it is not divisible by any square except 1.]

Solution

Answer: n = 14.

We can exhibit a sequence with 13 terms which does not contain a prime: 2·101 = 202, 3·97 = 291, 5·89 = 445, 7·83 = 581, 11·79 = 869, 13·73 = 949, 17·71 = 1207, 19·67 = 1273, 23·61 = 1403, 29·59 = 1711, 31·53 = 1643, 37·47 = 1739, 41·43 = 1763. So certainly n ≥ 14.

If there is a sequence with n ≥ 14 not containing any primes, then since there are only 13 primes not exceeding 41, at least one member of the sequence must have at least two prime factors exceeding 41. Hence it must be at least 43·47 = 2021 which exceeds 1995. So n =14 is impossible.

ABCD is a fixed cyclic quadrilateral with AB not parallel to CD. Find the locus of points P for which we can find circles through AB and CD touching at P.

Solution

Answer: Let the lines AB and CD meet at X. Let R be the length of a tangent from X to the circle ABCD. The locus is the circle center X radius R. [Strictly you must exclude four points unless you allow the degenerate straight line circles.]

Let X be the intersection of the lines AB and CD. Let R be the length of a tangent from X to the circle ABCD. Let C₀ be the circle center X radius R. Take any point P on C₀. Then considering the original circle ABCD, we have that R² = XA·XB = XC·XD, and hence XP² = XA·XB = XC·XD.

If C₁ is the circle through C, D and P, then XC.XD = XP², so XP is tangent to the circle C₁. Similarly, the circle C₂ through A, B and P is tangent to XP. Hence C₁ and C₂ are tangent to each other at P. Note that if P is one of the 4 points on AB or CD and C₀, then this construction does not work unless we allow the degenerate straight line circles AB and CD.

So we have established that all (or all but 4) points of C₀ lie on the locus. But for any given circle through C, D, there are only two circles through A, B which touch it (this is clear if you consider how the circle through A, B changes as its center moves along the perpendicular bisector of AB), so there are at most 2 points on the locus lying on a given circle through C, D. But these are just the two points of intersection of the circle with C₀. So there are no points on the locus not on C₀. 

Take a fixed point P inside a fixed circle. Take a pair of perpendicular chords AC, BD through P. Take Q to be one of the four points such that ASCQ, ASDQ, BSCQ or BSDQ is a rectangle. Find the locus of all possible Q for all possible such chords.

Solution

Let O be the center of the fixed circle and let X be the center of the rectangle ASCQ. By the cosine rule we have OQ² = OX² + XQ² - 2·OX·XQ cos θ and OP² = OX² + XP² - 2·OX·XP cos(θ+π), where θ is the angle OXQ. But cos(θ+π) = -cos θ, so OQ² + OP²= 2OX² + 2XQ². But since X is the center of the rectangle XQ = XC and since X is the midpoint of AC, OX is perpendicular to AC and hence XO² + XC² = OC². So OQ² = 2OC² - OP². But this quantity is fixed, so Q must lie on the circle center O radius √(2R² - OP²), where R is the radius of the circle.

Conversely, it is easy to see that all points on this circle can be reached. For given a point Q on the circle radius √(2R² - OP²) let X be the midpoint of PQ. Then take the chord AC to have X as its midpoint.

f is a function from the integers to {1, 2, 3, ... , n} such that f(A) and f(B) are unequal whenever A and B differ by 5, 7 or 12. What is the smallest possible n?

Solution

Answer: n = 4.

Each pair of 0, 5, 12 differ by 5, 7 or 12, so f(0), f(5), f(12) must all be different, so n ≥ 3.

We can exhibit an f with n = 4. Define f(m) = 1 for m = 1, 3, 5, 7, 9, 11 (mod 24), f(m) = 2 for m = 2, 4, 6, 8, 10, 12 (mod 24), f(m) = 3 for m = 13, 15, 17, 19, 21, 23 (mod 24), f(m) = 4 for m = 14, 16, 18, 20, 22, 0 (mod 24).

[more...]