Asian Pacific Mathematical Olympiad(apmo)

14th APMO 2002

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

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

 
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.

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.

 
Problem 5

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.

 

Solution

Putting x = 0, we get f(y) = f(f(y)) for all y (*).

Putting x = 1, y = 0, we get f(0) = 0. Hence putting y = 0, f(x⁴) = x³f(x) (**).

If f(1) = 0, then f(2) = f(1 + 1) = f(1) + f(1) = 0, so f(3) = f(1 + 2) = f(1) + f(2) = 0 and so on. Contradiction (only finitely many zeros). So f(1) = k for some non-zero k. By (*), f(k) = k.

Suppose f(h) = 0 for some h not 0 or 1. Then f(h⁴) = h³f(h) = 0, so f(x) = 0 for any of the distinct values x = h, h⁴, h¹⁶, h⁶⁴, ... . Contradiction (only finitely many zeros). So f(h) is not 0 for any non-zero h.

Given any x, put z = f(x⁴) - x⁴. Then f(x⁴) = f(f(x⁴)) = f(x⁴ + z) = x³f(x) + f(z). But f(x⁴) = x³f(x), so f(z) = 0. Hence z = 0. So for any positive x we have f(x) = x. But f(x⁴) = f( (-x)⁴ ) = - x³ f(-x). Hence f(-x) = - f(x). So f(x) = x for all x.

15th APMO 2003

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

Thanks to Jonathan Ramachandran

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.

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

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.

 
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.

 
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.

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

 

Answer

k = m + n + max(m, n) - 1

 

Solution

We have to find the smallest k so that any graph with k points has either m disjoint edges or n disjoint pairs of points with each pair not joined by an edge. Let the smallest k be f(m, n). For any graph G, there is another graph G' with the same points and the complementary set of edges (so that A, B are joined by an edge in G' iff they are not joined in G). This shows that f(m, n) = f(n, m), so there is no loss of generality in assuming that m ≤ n.

Consider the graph G with m+2n-2 points defined as follows. Let A be a subset of m-1 points and B the remaining 2n-1 points. Every point of A is joined to every other point (in A or B) and there are no other edges. Now since all points in A are joined to every other point in G, if two points are not joined then they must both be in B. So there can be at most n-1 pairs of unjoined points. If two points are joined then at least one of them must be in A (since if both are in B they are unjoined). But A has less than m points, so if there are m pairs of joined points, then they must overlap. Thus G shows that f(m, n) > m+2n-2.

We now prove by induction on m that any graph with m-1+2n points (and m <= n) has either m joined pairs or n unjoined pairs. It is trivial for m = 1 (if the graph has an edge, then we have the pair of joined points, if not then we can divide the 2n points arbitrarily into n pairs of unjoined points). So suppose it is true for m-1. We now use induction on n. We suppose that a graph G with m-1+2n points does not have m pairs of joined points or n pairs of unjoined points. We seek a contradiction.

Ignore for a moment the case n = m. Suppose that n > m and we have already established the result for n-1. Since m-1+2(n-1) < m-1+2n, and G does not have m pairs of joined points it must have n-1 pairs of unjoined points.

So let B be a set of n-1 pairs of unjoined points. Let A be the remaining m+1 points. Take any two points P and Q in A and any pair P', Q' in B. If P is not joined to P' and Q is not joined to Q', then we have a contradiction, because we could remove the pair P', Q' from B and replace it by the two pairs P, P' and Q, Q', thus getting n pairs of unjoined points. So we may assume that P is joined to P'. Now remove P from A, leaving m points and mark the pair P', Q' in B as used. We now repeat. Take any two points in the reduced A and any unmarked pair in B and conclude that one of the pair in A is joined to one of the pair in B. Remove the point from A and mark the pair in B. Since n-1 >= m we can continue in this way until we obtain m pairs of joined points (one of each pair in A and the other in B). Contradiction. So the result is true for n also.

It remains to consider the case n = m.

To get the n-1 pairs we use the induction on m. G has m-1+2m = 3m-1 points and does not have either m pairs of joined points or m pairs of unjoined points. We know by induction that f(m-1, m) = m-1+2m-1 = 3m-2, so f(m, m-1) = 3m-2 also. Since m-1+2m > 3m-2, G has either m pairs of joined points or m-1 points of unjoined points. It does not have the former (by assumption) so it must have the latter.

We now proceed as before. So B is a set of m-1 pairs of unjoined points and A the set of the remaining m+1 points. We get m-1 pairs of joined points (one of each pair in A and the other in B). But now we have run out of unmarked pairs in B. However, there are still two points in A. If they are not joined, then we would have a contradiction, because with the pairs in B they would give n pairs of unjoined points. So they are joined and hence give us an mth joined pair. Contradiction.

16th APMO 2004

Find all non-empty finite sets S of positive integers such that if m,n ∈ S, then (m+n)/gcd(m,n) ∈ S.

 

Answer

{2}

Let k ∈ S. Then (k+k)/gcd(k,k) = 2 ∈ S. Let M be the largest odd element of S. Then (M+2)/gcd(M,2) = M+2 ∈ S. Contradiction. So all elements of S are even.

Let m = 2n be the smallest element of S greater than 2. Then (m+2)/2 = n+1 ∈ S. But n must be > 1 (or m = 2), so 2n > n+1. Hence 2n = 2 (by minimality of m), so n = 1. Contradiction. So S has no elements apart from 2.

  
Problem 2

ABC is an acute-angled triangle with circumcenter O and orthocenter H (and O ≠ H). Show that one of area AOH, area BOH, area COH is the sum of the other two.

 

Solution

Let G be the centroid. Note that OH is the Euler line, so G lies on OH. wlog A is on one side of the line OH, and B, C are on the other side. Let M be the midpoint of BC. Then the length of the perpendicular from M to the line OH is the mean of the lengths of the perpendiculars from B and C. Thus if ∠MGO = θ, then area BOH + area COH = OH·GM sin θ = (OH·AG/2) sin θ = area AOH.

 
Problem 3

2004 points are in the plane, no three collinear. S is the set of lines through any two of the points. Show that the points can be colored with two colors so that any two of the points have the same color iff there are an odd number of lines in S which separate them (a line separates them if they are on opposite sides of it).

 

Solution

Let us denote by d_XY the number of points separating the points X and Y. If the result is true, then the coloring is effectively determined: take a point X and color it blue. Then for every other point Y, color it blue iff d_XY is odd. This will work provided that given any three points A, B, C, we have d_AB + d_BC + d_CA is odd. (For then if Y and Z are the same color, d_XY and d_XZ have th same parity, so d_YZ is odd, which is correct. Similarly, if Y and Z are opposite colors, then d_YZ is even, which is correct.)

We are interested in lines which pass through an interior point of one or more of AB, BC, CA. Lines cannot pass through all three. If they pass through two, then they do not affect the parity of d_AB + d_BC + d_CA. So we are interested in lines which pass through A and the (interior of) BC, and similarly for B, C. Let n₁, n₂, ... , n₇ be the number of points (excluding A, B, C) in the various regions (as shown). The number of lines through A and BC is n₁ + n₂ + n₃. So d_AB + d_BC + d_CA = (n₁ + n₂ + n₃) + (n₁ + n₄ + n₅) + (n₁ + n₆ + n₇) = n₁ + n₂ + n₃ + n₄ + n₅ + n₆ + n₇ = (2004 - 3) = 1 mod 2.

 
Problem 4

Show that [(n-1)!/(n²+n)] is even for any positive integer n.

 

Solution

For n = 1, 2, 3, 4, 5 we have [(n-1)!/(n²+n)] = 0, which is even. So assume n ≥ 6.

If n and n+1 are composite, then they must divide (n-1)!. They are coprime, so their product must divide (n-1)!. Note that just one of n, n+1 is even. For m ≥ 6, (m-2)! is divisible by more powers of 2 than m, so (n-1)!/(n²+n) is even. It remains to consider the two cases n+1 = p, a prime, and n = p a prime.

If n+1 = p, then p-1 is composite, so p-1 divides (p-2)!. Let k = (p-2)!/(p-1). By Wilson's theorem we have (p-2)! = 1 mod p, so k(p-1) = 1 mod p and hence k = -1 mod p. So (k+1)/p is an integer. But k is even, so k+1 is odd and hence (k+1)/p is odd. Now [k/p] = (k+1)/p - 1, so [k/p] = [(n-1)!/(n²+n)] is even.

If n = p, then k = (p-1)!/(p+1) is an even integer, so k+1 is an odd integer. By Wilson's theorem, k(p+1) = -1 mod p, so (k+1)/p is an integer and hence an odd integer. Hence [(n-1)!/(n²+n)] = [k/p] = (k+1)/p - 1 is even.

Wilson's theorem states that p is prime iff (p-1)! = -1 mod p. If p is composite, then it has a factor ≤ p-1, which divides (p-1)! and so does not divide (p-1)! + 1. Hence (p-1)! ≠ -1 mod p. Now suppose p is prime. If p = 2, then (p-1)! = 1 = -1 mod 2. So assume p is odd. Note first that if a² = 1 mod p and 0 < a < p, then a = 1 or p-1. For p divides (a+1)(a-1) and so it divides either a+1, giving a = p-1, or it divides a-1, giving a = 1. Now for each 0 < a < p, there is a unique a' such that aa' = 1 mod p. We have just shown that a = a' iff a = 1 or p-1. So we can divide 2, 3, ... , p-2 into pairs with the product of each pair being 1 mod p. Hence (p-2)! = 1 mod p, as required.

On the powers of 2, note that 2, 2², 2³, ... , 2^k-1 < 2^k and their product is 2^k(k-1)/2. If 2^k < n < 2^k+1, then n is divisible by at most 2^k-1. So for n ≥ 16, for example, (n-8)!/n is even. For n = 8, 9, ... , 15, (n-2)! is divisible by 2·4·6 and n is divisible by at most 8, so (n-2)!/n is even. Finally, we can easily check n = 6, 7.

 
Problem 5

Show that (x² + 2)(y² + 2)(z² + 2) ≥ 9(xy + yz + zx) for any positive reals x, y, z.

 

Solution

Expanding lhs we get x²y²z² + 2(x²y² + y²z² + z²x²) + 4(x² + y² + z²) + 8.

By AM/GM we have 3(x² + y² + z²) ≥ 3(xy + yz + zx) and (2x²y² + 2) + (2y²z² + 2) + (2z²x² + 2) ≥ 4(xy + yz + zx). That leaves us needing x²y²z² + x² + y² + z² + 2 ≥ 2(xy + yz + zx) (*). That is hard, because it is not clear how to deal with the xyz on the lhs.

By AM/GM we have (a+b)(b+c)(c+a) ≥ 8abc. So if (u+v-w), (u-v+w), (-u+v+w) are all non-negative, we can put 2a = -u+v+w, 2b = u-v+w, 2c = u+v-w and get uvw ≥ (-u+v+w)(u-v+w)(u+v-w). If u, v, w are positive, then at most one of (u+v-w), (u-v+w), (-u+v+w) is negative. In that case uvw ≥ (-u+v+w)(u-v+w)(u+v-w) is trivially true. So it holds for all positive u, v, w. Expanding, we get u³ + v³ + w³ + 3uvw ≥ uv(u+v) + vw(v+w) + wu(w+u), which is a fairly well-known inequality. Applying AM/GM to u+v etc we get, u³ + v³ + w³ + 3uvw ≥ 2(uv)^3/2 + 2(vw)^3/2 + 2(wu)^3/2. Finally, putting u = x^2/3, v = y^2/3, w = z^2/3, we get x² + y² + z² + 3(xyz)^2/3 ≥ 2(xy + yz + zx) (**).

Thus we have x²y²z² + x² + y² + z² + 2 ≥ ≥ (x² + y² + z²) + 3(xyz)^2/3, by applying AM/GM to x²y²z², 1, 1, and now (**) gives the required (*).