6th Asian Pacific Mathematics Olympiad 1994 Problems

6th Asian Pacific Mathematics Olympiad 1994 Problems

A1.  Find all real-valued functions f on the reals such that (1) f(1) = 1, (2) f(-1) = -1, (3) f(x) ≤ f(0) for 0 < x < 1, (4) f(x + y) ≥ f(x) + f(y) for all x, y, (5) f(x + y) ≤ f(x) + f(y) + 1 for all x, y.

A2.  ABC is a triangle and A, B, C are not collinear. Prove that the distance between the orthocenter and the circumcenter is less than three times the circumradius.

A3.  Find all positive integers n such that n = a² + b², where a and b are relatively prime positive integers, and every prime not exceeding √n divides ab.

A4.  Can you find infinitely many points in the plane such that the distance between any two is rational and no three are collinear?

A5.  Prove that for any n > 1 there is either a power of 10 with n digits in base 2 or a power of 10 with n digits in base 5, but not both.

Find all real-valued functions f on the reals such that (1) f(1) = 1, (2) f(-1) = -1, (3) f(x) ≤ f(0) for 0 < x < 1, (4) f(x + y) ≥ f(x) + f(y) for all x, y, (5) f(x + y) ≤ f(x) + f(y) + 1 for all x, y.

Solution

Answer: f(x) = [x].

f(x+1) >= f(x) + f(1) = f(x) + 1 by (4) and (1). But f(x) ≥ f(x+1) + f(-1) = f(x+1) - 1 by (4) and (2). Hence f(x+1) = f(x) + 1.

In particular, 1 = f(1) = f(0+1) = f(0) + 1, so f(0) = 0. Hence, by (3), f(x) ≤ 0 for 0 < x < 1. But, by (5), 1 = f(1) = f(x + 1-x) ≤ f(x) + f(1-x) + 1, so f(x) + f(1-x) ≥ 0. But if 0 < x < 1, then also 0 < 1-x < 1, so f(x) = f(1-x) = 0.

Thus we have established that f(x) = 0 for 0 ≤ x < 1, and f(x+1) = f(x) + 1. It follows that f(x) = [x] for all x.

ABC is a triangle and A, B, C are not collinear. Prove that the distance between the orthocenter and the circumcenter is less than three times the circumradius.

Solution

We use vectors. It is well-known that the circumcenter O, the centroid G and the orthocenter H lie on the Euler line and that OH = 3 OG. Hence taking vectors with origin O, OH = 3 OG = OA + OB + OC. Hence |OH| ≤ |OA| + |OB| + |OC| = 3 x circumradius. We could have equality only if ABC were collinear, but that is impossible, because ABC would not then be a triangle.

Find all positive integers n such that n = a² + b², where a and b are relatively prime positive integers, and every prime not exceeding √n divides ab.

Solution

Answer: 2 = 1² + 1², 5 = 1² + 2², 13 = 2² + 3².

The key is to use the fact that a and b are relatively prime. We show in fact that they must differ by 1 (or 0). Suppose first that a = b. Then since they are relatively prime they must both be 1. That gives the first answer above. So we may take a > b. Then (a - b)² < a² + b² = n, so if a - b is not 1, it must have a prime factor which divides ab. But then it must divide a or b and hence both. Contradiction. So a = b + 1.

Now (b - 1)² < b² < n, so any prime factor p of b - 1 must divide ab = b(b + 1). It cannot divide b (or it would divide b and b - 1 and hence 1), so it must divide b + 1 and hence must be 2. But if 4 divides b - 1, then 4 does not divide b(b - 1), so b - 1 must be 0, 1 or 2. But it is now easy to check the cases a, b = (4, 3), (3, 2), (2, 1).

Can you find infinitely many points in the plane such that the distance between any two is rational and no three are collinear?

Solution

Answer: yes.

Let θ = cos^-13/5. Take a circle center O radius 1 and a point X on the circle. Take P_n on the circle such that angle XOP_n = 2nθ. We establish (A) that the P_n are all distinct and (B) that the distances P_mP_n are all rational.

We establish first that we can express 2 cos nx as a polynomial of degree n in (2 cos x) with integer coefficients and leading coefficient 1. For example, 2 cos 2x = (2 cos x)² - 1, 2 cos 3x = (2 cos x)³ - 3 (2 cos x). We proceed by induction. Let the polynomial be p_n(2 cos x). We have that p₁(y) = y and p₂(y) = y² - 1. Suppose we have found p_m for m ≤ n. Now cos(n+1)x = cos nx cos x - sin nx sin x, and cos(n-1)x = cos nx cos x + sin nx sin x, so cos(n+1)x = 2 cos x cos nx - cos(n-1)x. Hence p_n+1(y) = y p_n(y) - p_n-1(y). Hence the result is also true for n+1.

It follows that (1) if cos x is rational, then so is cos nx, and (2) if cos x is rational, then x/π is irrational. To see (2), suppose that x/π = m/n, with m and n integers. Then nx is a multiple of π and hence cos nx = 0, so p_n(2 cos x) = 0. Now we may write p_n(y) = yⁿ + a^n-1y^n-1 + ... + a₀. Now if also cos x = r/s, with r and s relatively prime integers, then we have, p_n(2 cos x) = rⁿ + a_n-1s r^n-1 + ... + a₀sⁿ = 0. But now s divides all terms except the first. Contradiction.

Thus we cannot have cos mθ = cos nθ for any distinct integers m, n, for then θ/π would be rational as well as cos θ. So we have established (A).

We have also established that all cos nθ are rational. But since sin(n+1)x = sin nx cos x + cos nx sin x and sin θ = 4/5, it is a trivial induction that all sin nθ are also rational. Now P_mP_n = 2 |sin(m - n)θ|, so all the distances P_mP_n are rational, thus establishing (B).

Prove that for any n > 1 there is either a power of 10 with n digits in base 2 or a power of 10 with n digits in base 5, but not both.

Solution

10^k has n digits in base 5 iff 5^n-1 < 10^k < 5ⁿ. Similarly, 10^h has n digits in base 2 iff 2^n-1 < 10^h < 2ⁿ. So if we can find both 10^k with n digits in base 5 and 10^h with n digits in base 2, then, multiplying the two inequalities, we have 10^n-1 < 10^h+k < 10ⁿ, which is clearly impossible. This establishes the "but not both" part.

Let S be the set of all positive powers of 2 or 5. Order the members of S in the usual way and let a_n be the n-1th member of the set. We claim that if a_n = 2^k, then 10^k has n digits in base 5, and if a_n = 5^h, then 10^h has n digits in base 2. We use induction on n.

a₂ = 2¹, a₃ = 2², a₄ = 5¹, a₅ = 2³, ... . Thus the claim is certainly true for n = 2. Suppose it is true for n.

Note that 10^k has n digits in base 5 iff 5^n-k-1 < 2^k < 5^n-k. Similarly, 10^h has n digits in base 2 iff 2^n-h-1 < 5^h < 2^n-h. There are 3 cases. Case (1). a_n = 2^k and a_n+1 = 2^k+1. Hence 10^k+1 has n+1 digits in base 5. Case (2). a_n = 2^k and a_n+1 is a power of 5. Hence a_n+1 must be 5^n-k. Hence 2^k < 5^n-k < 2^k+1. Hence 2ⁿ < 10^n-k < 2ⁿ⁺¹. So 10^n-k has n+1 digits in base 2. Case (3). a_n = 5^h. Since there is always a power of 2 between two powers of 5, a_n+1 must be a power of 2. Hence it must be 2^n-h. So we have 5^h < 2^n-h < 5^h+1. So 5ⁿ < 10^n-h < 5ⁿ⁺¹ and hence 10^n-h has n+1 digits in base 5.

Jacob Tsimerman pointed out that the second part can be done in a similar way to the first - which is neater than the above:

If no power of 10 has n digits in base 2 or 5, then for some h, k: 10^h < 2^n-1 < 2ⁿ < 10^h+1 and 10^k < 5^n-1 < 5ⁿ < 10^k+1. Hence 10^h+k < 10^n-1 < 10ⁿ < 10^h+k+2. But there is only one power of 10 between h+k and h+k+2.