Asian Pacific Mathematical Olympiad(apmo)

13th APMO 2001

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.

 
Problem 2

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).

 
Problem 3

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.

 
Problem 4

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.

 
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

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.