### 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_{0}, so that n = a_{d} 10^{d} + ... + a_{0}. Then n(k) = a_{d} 10^{d-k} + a^{d-1} 10^{d-k-1} + ... + a_{k}. Obviously s = a_{d} + ... + a_{0}. 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_{1}(9 + 1) + a_{0} = a_{d} 10^{d} + ... + a_{0} = 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_{1}, P_{2}, ... , P_{n} and the other have vertices Q_{1}, Q_{2}, ... , 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_{1}, Q_{1}, P_{2}, Q_{2}, ... , 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_{i}P_{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_{i}Q_{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_{i}P_{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^{2} + bx + c, with a, b, c rational, then p(√2 - b/2a) = 2a - b^{2}/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^{n} + 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^{n} + b r^{n-1}s + ... + u r s^{n-1} + v s^{n})/( w s^{n}). 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^{2} 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^{n}. We know that w is not divisible by q, so q must divide s. But n > 1, so q^{2} divides w s^{n}. The numerator of p(r/s) has the form a r^{n} + 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_{1}, ... , 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_{B}center 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_{3}X_{2}. Extend the side X_{2}X_{3} to X_{1}X_{4}, with X_{1}, X_{2}, X_{3}, X_{4} equally spaced in that order, so that X_{1}AX_{2} and X_{3}BX_{4} are equilateral. Then ABX_{1} and CX_{1}D are congruent, ABX_{2} and DX_{2}C are congruent, ABX_{3} and X_{3}CD are congruent, and ABX_{4} and X_{4}DC are congruent.
**Share with your friends:** |