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, X1, ... , Xn, so that AB is not equal to CD, but for each i the two triangles ABXi and CDXi 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 ad, ad-1, ... , a0, so that n = ad 10d + ... + a0. Then n(k) = ad 10d-k + ad-1 10d-k-1 + ... + ak. Obviously s = ad + ... + a0. Hence s + 9 n(1) + ... + 9 n(d) = ad(9.10d-1 + 9.10d-2 + ... + 9 + 1) + ad-1(9.10d-2 + ... + 9 + 1) + ... + ad-k(9.10d-k-1 + ... + 9 + 1) + a1(9 + 1) + a0 = ad 10d + ... + a0 = 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 P1, P2, ... , Pn and the other have vertices Q1, Q2, ... , Qn. Each side of the 2n-gon forms a triangle with one of the Pi or Qi. Note that Pi and Qj must alternate as we go around the 2n-gon. For convenience assume that the order is P1, Q1, P2, Q2, ... , Pn, Qn. Let the length of the side which forms a triangle with Pi be pi, and the length of the side which forms a triangle with Qi be qi. Each of these triangles has one angle (180o - 360o/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 Pi have lengths ai, bi, pi, then the side PiPi+1 is bi + qi + ai+1, and ai/ai+1 = bi/bi+1 = pi/pi+1. Similarly, if the sides of the triangle vertex Qi have lengths ci, di, qi, then the side QiQi+1 is di + pi+1 + ci+1 and ci/ci+1 = di/di+1 = qi/qi+1. But ai/bi = di/ci (not ci/di), because the triangles alternate in orientation.
Put ai/pi = h, bi/pi = k. Note that ai + bi > pi, so h + k - 1 > 0. We have also ci/qi = k, di/qi = h. Adding the expressions for PiPi+1 we get perimeter Pi = ∑(bi + qi + ai+1) = k ∑ pi + ∑ qi + h ∑ pi. Similarly, perimeter Qi = (h + k) ∑ qi + ∑ pi. The two n-gons are equal, so (h + k - 1) ∑ pi = (h + k - 1) ∑ qi. Hence ∑ pi = ∑ qi, 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) = ax2 + bx + c, with a, b, c rational, then p(√2 - b/2a) = 2a - b2/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 xn + b xn-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 rn + b rn-1s + ... + u r sn-1 + v sn)/( w sn). 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 q2 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 sn. We know that w is not divisible by q, so q must divide s. But n > 1, so q2 divides w sn. The numerator of p(r/s) has the form a rn + 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, X1, ... , Xn, so that AB is not equal to CD, but for each i the two triangles ABXi and CDXi 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 SA center A radius b, or on the circle SBcenter B radius b. Similarly, CX or DX = AB = a, so X lies either on the circle SC center C radius a, or on the circle SD center D radius a. Thus we have four pairs of circles, (SA, SC), (SA, SD), (SB, SC), (SB, SD) 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 (SA, SC) are included, then no points of (SB, SD) 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 (SA, SC) 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 = 180o - ∠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 (SB, SD). 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 (SB, SD), as required. That completes the proof that n ≤ 4.
For an example with n = 4, take a regular hexagon ACDBX3X2. Extend the side X2X3 to X1X4, with X1, X2, X3, X4 equally spaced in that order, so that X1AX2 and X3BX4 are equilateral. Then ABX1 and CX1D are congruent, ABX2 and DX2C are congruent, ABX3 and X3CD are congruent, and ABX4 and X4DC are congruent.
Labels:
APMO
Previous Article
