### 14th APMO 2002
**Problem 1**
x_{i} are non-negative integers. Prove that x_{1}! x_{2}! ... x_{n}! ≥ ( [(x_{1} + ... + x_{n})/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_{1} + x_{2} + ... + 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^{2} - n divides m + n^{2} and n^{2} - m divides m^{2} + n.
**Solution**
Assume n ≥ m.
(m+1)^{2} - m = (m+1) + m^{2}. Clearly n^{2} increases faster than n, so n^{2} - m > n + m^{2} 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^{2} - n divides n^{2} + n. If n > 3, then n^{2} > 3n, so 2(n^{2} - n) > n^{2} + n. Obviously n^{2} - n < n^{2} + n, so if n > 3, then n^{2} - n cannot divide n^{2} + 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^{2} - m - 1 divides m^{2} + 3m + 1. If m >= 6, then m(m - 5) > 3, so 2(m^{2} - m - 1) > m^{2} + 3m + 1. Obviously m^{2} - m - 1 < m^{2} + 3m + 1, so m^{2} - m - 1 cannot divide m^{2} + 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)^{2} ≥ 0.
**Problem 5**
Find all real-valued functions f on the reals which have at most finitely many zeros and satisfy f(x^{4} + y) = x^{3}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^{4}) = x^{3}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^{4}) = h^{3}f(h) = 0, so f(x) = 0 for any of the distinct values x = h, h^{4}, h^{16}, h^{64}, ... . Contradiction (only finitely many zeros). So f(h) is not 0 for any non-zero h.
Given any x, put z = f(x^{4}) - x^{4}. Then f(x^{4}) = f(f(x^{4})) = f(x^{4} + z) = x^{3}f(x) + f(z). But f(x^{4}) = x^{3}f(x), so f(z) = 0. Hence z = 0. So for any positive x we have f(x) = x. But f(x^{4}) = f( (-x)^{4} ) = - x^{3} f(-x). Hence f(-x) = - f(x). So f(x) = x for all x.
### 15th APMO 2003
**Problem 1**
The polynomial a_{8}x^{8} +a_{7}x^{7} + ... + a_{0} has a_{8} = 1, a_{7} = -4, a_{6} = 7 and all its roots positive and real. Find the possible values for a_{0}.
**Answer**
1/2^{8}
**Solution**
*Thanks to Jonathan Ramachandran*
Let the roots be x_{i}. We have Sum x_{i}^{2} = 4^{2} - 2·7 = 2. By Cauchy we have (x_{1}·1 + ... + x_{8}·1) ≤ (x_{1}^{2} + ... + x_{8}^{2})^{1/2}(1^{2} + ... + 1^{2})^{1/2} with equality iff all x_{i} are equal. Hence all x_{i} are equal. So they must all be 1/2.
**Problem 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^{2}. 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)^{2} ≥ k^{2}/16. If k > 16, this is a contradiction. If k = 15 or 16, then p = 13 and k ≥ (q-1)^{2} gives q ≤ 5, so n = q^{2} ≤ 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^{n} + b^{n})^{1/n} + (b^{n} + c^{n})^{1/n} + (c^{n} + a^{n})^{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**
*Thanks to Olena Bormashenko*
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)^{n} = b^{n} + n/2 c b^{n-1} + other positive terms > b^{n} + c^{n}. Hence (b^{n} + c^{n})^{1/n} < b + c/2. Similarly, (c^{n} + a^{n})^{1/n} < a + c/2. Adding we get (b^{n} + c^{n})^{1/n} + (c^{n} + a^{n})^{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.
*Comment. This all seems complicated, and certainly much harder work than questions 1-3. So maybe I am missing something. Does anyone have a simpler solution?*
### 16th APMO 2004
**Problem 1**
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}
**Solution**
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_{1}, n_{2}, ... , n_{7} 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_{1} + n_{2} + n_{3}. So d_{AB} + d_{BC} + d_{CA} = (n_{1} + n_{2} + n_{3}) + (n_{1} + n_{4} + n_{5}) + (n_{1} + n_{6} + n_{7}) = n_{1} + n_{2} + n_{3} + n_{4} + n_{5} + n_{6} + n_{7} = (2004 - 3) = 1 mod 2.
*Thanks to Dinu Razvan*
**Problem 4**
Show that [(n-1)!/(n^{2}+n)] is even for any positive integer n.
**Solution**
*Thanks to Juan Ignacio Restrepo*
For n = 1, 2, 3, 4, 5 we have [(n-1)!/(n^{2}+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^{2}+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^{2}+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^{2}+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*^{2}* = 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*^{3}*, ... , 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} + 2)(y^{2} + 2)(z^{2} + 2) ≥ 9(xy + yz + zx) for any positive reals x, y, z.
**Solution**
Expanding lhs we get x^{2}y^{2}z^{2} + 2(x^{2}y^{2} + y^{2}z^{2} + z^{2}x^{2}) + 4(x^{2} + y^{2} + z^{2}) + 8.
By AM/GM we have 3(x^{2} + y^{2} + z^{2}) ≥ 3(xy + yz + zx) and (2x^{2}y^{2} + 2) + (2y^{2}z^{2} + 2) + (2z^{2}x^{2} + 2) ≥ 4(xy + yz + zx). That leaves us needing x^{2}y^{2}z^{2} + x^{2} + y^{2} + z^{2} + 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^{3} + v^{3} + w^{3} + 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^{3} + v^{3} + w^{3} + 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^{2} + y^{2} + z^{2} + 3(xyz)^{2/3} ≥ 2(xy + yz + zx) (**).
Thus we have x^{2}y^{2}z^{2} + x^{2} + y^{2} + z^{2} + 2 ≥ ≥ (x^{2} + y^{2} + z^{2}) + 3(xyz)^{2/3}, by applying AM/GM to x^{2}y^{2}z^{2}, 1, 1, and now (**) gives the required (*).
*Thanks to Jacob Tsimerman*
- -
**Share with your friends:** |