xi are non-negative integers. Prove that x1! x2! ... xn! ≥ ( [(x1 + ... + xn)/n] ! )n (where [y] denotes the largest integer not exceeding y). When do you have equality?
Answer: Equality iff all xi 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 xi + xj the smallest value of xi! xj! is for xi and xj as nearly equal as possible.
If x1 + x2 + ... + xn = qn + r, where 0 < r < n, then we can reduce one or more xi 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 xi will not increase the lhs (by the result just proved). So it is sufficient to prove the inequality for all xi equal. But in this case it is trivial since k! = k! .
Find all pairs m, n of positive integers such that m2 - n divides m + n2 and n2 - m divides m2 + n.
Assume n ≥ m.
(m+1)2 - m = (m+1) + m2. Clearly n2increases faster than n, so n2 - m > n + m2 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 n2 - n divides n2 + n. If n > 3, then n2 > 3n, so 2(n2 - n) > n2 + n. Obviously n2 - n < n2 + n, so if n > 3, then n2 - n cannot divide n2 + 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 m2 - m - 1 divides m2 + 3m + 1. If m >= 6, then m(m - 5) > 3, so 2(m2 - m - 1) > m2 + 3m + 1. Obviously m2 - m - 1 < m2 + 3m + 1, so m2 - m - 1 cannot divide m2 + 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).
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.
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 = 60o + x, so y = 30o - x. So if x ≠ 15o, then TL ≠ RM. However, RST equilateral implies TL = RM, so x and hence also ∠BCQ = 15o.
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.
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.
Find all real-valued functions f on the reals which have at most finitely many zeros and satisfy f(x4 + y) = x3f(x) + f(f(y)) for all x, y.
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(x4) = x3f(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(h4) = h3f(h) = 0, so f(x) = 0 for any of the distinct values x = h, h4, h16, h64, ... . Contradiction (only finitely many zeros). So f(h) is not 0 for any non-zero h.
Given any x, put z = f(x4) - x4. Then f(x4) = f(f(x4)) = f(x4 + z) = x3f(x) + f(z). But f(x4) = x3f(x), so f(z) = 0. Hence z = 0. So for any positive x we have f(x) = x. But f(x4) = f( (-x)4 ) = - x3 f(-x). Hence f(-x) = - f(x). So f(x) = x for all x.
15th APMO 2003
The polynomial a8x8 +a7x7 + ... + a0 has a8 = 1, a7 = -4, a6 = 7 and all its roots positive and real. Find the possible values for a0.
Thanks to Jonathan Ramachandran
Let the roots be xi. We have Sum xi2 = 42 - 2·7 = 2. By Cauchy we have (x1·1 + ... + x8·1) ≤ (x12 + ... + x82)1/2(12 + ... + 12)1/2 with equality iff all xi are equal. Hence all xi 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.
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(45o + 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.
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.
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 = q2. 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 ≥ k2/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 = q2 ≤ 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.
Show that (an + bn)1/n + (bn + cn)1/n + (cn + an)1/n < 1 + (21/n)/2, where n > 1 is an integer and a, b, c are the sides of a triangle with unit perimeter.
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 (an + bn)1/n < 21/n/2 (*).
We have (b + c/2)n = bn + n/2 c bn-1 + other positive terms > bn + cn. Hence (bn + cn)1/n < b + c/2. Similarly, (cn + an)1/n < a + c/2. Adding we get (bn + cn)1/n + (cn + an)1/n < a+b+c = 1. Adding to (*) gives the required result.
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.
k = m + n + max(m, n) - 1
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
Find all non-empty finite sets S of positive integers such that if m,n ∈ S, then (m+n)/gcd(m,n) ∈ S.
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.
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.
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.
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).
Let us denote by dXY 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 dXY is odd. This will work provided that given any three points A, B, C, we have dAB + dBC + dCA is odd. (For then if Y and Z are the same color, dXY and dXZ have th same parity, so dYZ is odd, which is correct. Similarly, if Y and Z are opposite colors, then dYZ 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 dAB + dBC + dCA. So we are interested in lines which pass through A and the (interior of) BC, and similarly for B, C. Let n1, n2, ... , n7 be the number of points (excluding A, B, C) in the various regions (as shown). The number of lines through A and BC is n1 + n2 + n3. So dAB + dBC + dCA = (n1 + n2 + n3) + (n1 + n4 + n5) + (n1 + n6 + n7) = n1 + n2 + n3 + n4 + n5 + n6 + n7 = (2004 - 3) = 1 mod 2.
Show that [(n-1)!/(n2+n)] is even for any positive integer n.
Thanks to Juan Ignacio Restrepo
For n = 1, 2, 3, 4, 5 we have [(n-1)!/(n2+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)!/(n2+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)!/(n2+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)!/(n2+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 a2 = 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, 22, 23, ... , 2k-1 < 2k and their product is 2k(k-1)/2. If 2k < n < 2k+1, then n is divisible by at most 2k-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.
Expanding lhs we get x2y2z2 + 2(x2y2 + y2z2 + z2x2) + 4(x2 + y2 + z2) + 8.
By AM/GM we have 3(x2 + y2 + z2) ≥ 3(xy + yz + zx) and (2x2y2 + 2) + (2y2z2 + 2) + (2z2x2 + 2) ≥ 4(xy + yz + zx). That leaves us needing x2y2z2 + x2 + y2 + z2 + 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 u3 + v3 + w3 + 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, u3 + v3 + w3 + 3uvw ≥ 2(uv)3/2 + 2(vw)3/2 + 2(wu)3/2. Finally, putting u = x2/3, v = y2/3, w = z2/3, we get x2 + y2 + z2 + 3(xyz)2/3 ≥ 2(xy + yz + zx) (**).
Thus we have x2y2z2 + x2 + y2 + z2 + 2 ≥ ≥ (x2 + y2 + z2) + 3(xyz)2/3, by applying AM/GM to x2y2z2, 1, 1, and now (**) gives the required (*).