44th International Mathematical Olympiad 2003 Problems & Solutions



A1.  S is the set {1, 2, 3, ... , 1000000}. Show that for any subset A of S with 101 elements we can find 100 distinct elements xi of S, such that the sets xi + A are all pairwise disjoint. [Note that xi + A is the set {a + xi | a is in A} ].
A2.  Find all pairs (m, n) of positive integers such that m2/(2mn2 - n3 + 1) is a positive integer.
A3.  A convex hexagon has the property that for any pair of opposite sides the distance between their midpoints is (√3)/2 times the sum of their lengths. Show that all the hexagon's angles are equal.
B1.  ABCD is cyclic. The feet of the perpendicular from D to the lines AB, BC, CA are P, Q, R respectively. Show that the angle bisectors of ABC and CDA meet on the line AC iff RP = RQ.
B2.  Given n > 2 and reals x1 ≤ x2 ≤ ... ≤ xn, show that (∑i,j |xi - xj| )2 ≤ (2/3) (n2 - 1) ∑i,j (xi - xj)2. Show that we have equality iff the sequence is an arithmetic progression.
B3.  Show that for each prime p, there exists a prime q such that np - p is not divisible by q for any positive integer n.

Solutions

Problem A1

S is the set {1, 2, 3, ... , 1000000}. Show that for any subset A of S with 101 elements we can find 100 distinct elements xi of S, such that the sets xi + A are all pairwise disjoint. [Note that xi + A is the set {a + xi | a is in A} ].

Solution

Thanks to Li Yi
Having found x1, x2, ... , xk there are k·101·100 forbidden values for xk+1 of the form xi + am - an with m and n unequal and another k forbidden values with m = n. Since 99·101·100 + 99 = 106 - 1, we can successively choose 100 distinct xi.
Gerhard Woeginger sent me a similar solution

Problem A2

Find all pairs (m, n) of positive integers such that m2/(2mn2 - n3 + 1) is a positive integer.

Answer

(m, n) = (2k, 1), (k, 2k) or (8k4 - k, 2k)

Solution

Thanks to Li Yi
The denominator is 2mn2 - n3 + 1 = n2(2m - n) + 1, so 2m >= n > 0. If n = 1, then m must be even, in other words, we have the solution (m, n) = (2k, 1).
So assume n > 1. Put h = m2/(2mn2 - n3 + 1). Then we have a quadratic equation for m, namely m2 - 2hn2m + (n3 - 1)h = 0. This has solutions hn2 +- N, where N is the positive square root of h2n4 - hn3 + h. Since n > 1, h ≥ 1, N is certainly real. But the sum and product of the roots are both positive, so both roots must be positive. The sum is an integer, so if one root is a positive integer, then so is the other.
The larger root hn2 + N is greater than hn2, so the smaller root < h(n3 - 1)/(hn2) < n. But note that if 2m - n > 0, then since h > 0, we must have the denominator (2m - n)n2 + 1 smaller than the numerator and hence m > n. So for the smaller root we cannot have 2m - n > 0. But 2m - n must be non-negative (since h is positive), so 2m - n = 0 for the smaller root. Hence hn2 - N = n/2. Now N2 = (hn2 - n/2)2 = h2n4 - hn3 + h, so h = n2/4. Thus n must be even. Put n = 2k and we get the solutions (m, n) = (k, 2k) and (8k4 - k, 2k).
We have shown that any solution must be of one of the three forms given, but it is trivial to check that they are all indeed solutions.

Problem A3

A convex hexagon has the property that for any pair of opposite sides the distance between their midpoints is ½ √3 times the sum of their lengths. Show that all the hexagon's angles are equal.

Solution

Thanks to Li Yi
We use bold to denote vectors, so AB means the vector from A to B. We take some arbitrary origin and write the vector OA as A for short. Note that the vector to the midpoint of AB is (A + B)/2, so the vector from the midpoint of DE to the midpoint of AB is (A + B - D - E)/2. So the starting point is |A + B - D - E| ≥ √3 ( |A - B| + |D - E| ) and two similar equations. The key is to notice that by the triangle inequality we have |A - B| + |D - E| ≥ |A - B - D + E| with equality iff the opposite sides AB and DE are parallel. Thus we get |DA + EB| ≥ √3 |DA - EB|. Note that DA and EB are diagonals. Squaring, we get DA2 + 2 DA.EB + EB2 ≥ 3(DA2 - 2 DA.EB + EB2), or DA2 + EB2 ≤ 4 DA.EB. Similarly, we get EB2 + FC2 ≤ 4 EB.FC and FC2 + AD2 ≤ 4 FC.AD = - 4 FC.DA. Adding the three equations gives 2(DA - EB + FC)2 ≤ 0. So it must be zero, and hence DA - EB + FC = 0 and opposite sides of the hexagon are parallel.
Note that DA - EB + FC = A - D - B + E + C - F = BA + DC + FE. So BA + DC + FE = 0. In other words, the three vectors can form a triangle.

Since EF is parallel to BC, if we translate EF along the vector ED we get CG, an extension of BC. Similarly, if we translate AB along the vector BC we get an extension of ED. Since BA, DC and FE form a triangle, AB must translate to DG. Thus HAB and CDG are congruent. Similarly, if we take AF and DE to intersect at I, the triangle FIE is also congruent (and similarly oriented) to HAB and CDG. Take J, K as the midpoints of AB, ED. HIG and HAB are equiangular and hence similar. IE = DG and K is the midpoint of ED, so K is also the midpoint of IG. Hence HJ is parallel to HK, so H, J, K are collinear.
Hence HJ/AB = HK/IG = (HK - HJ)/(IG - AB) = JK/(AB + ED) = ½ √3. Similarly, each of the medians of the triangle HAB is ½ √3 times the corresponding side. We will show that this implies it is equilateral. The required result then follows immediately.
Suppose a triangle has side lengths a, b, c and the length of the median to the midpoint of side length c is m. Then applying the cosine rule twice we get m2 = a2/2 + b2/2 - c2/4. So if m2 = ¾ c2, it follows that a2 + b2 = 2c2. Similarly, b2 + c2 = 2a2. Subtracting, a = c. Similarly for the other pairs of sides.
An alternative (and rather more elegant) solution sent my some anonymous contestants at the IMO is as follows

Let the diagonals AD and BE meet at P. We show that angle APB <= 60o. Suppose angle APB > 60o. Take X and Y inside the hexagon so that ABX and DEY are equilateral (as shown). Then since angle APB > angle AXB, P lies inside the circumcircle of ABX (which we take to have center O, radius r). Similarly, it lies inside the circumcircle of DEY (which we take to have center O' radius r'), so these circles must meet and hence OO' < r + r'. Now √3 (AB + DE)/2 = MN (where M, N are the midpoints of AB, DE) ≤ MO + OO' + O'N < r/2 + (r + r') + r'/2 = (3/2)(r + r') = √3 (AB + DE)/2. Contradiction.
The same argument applies to any two long diagonals. Hence the angles must all be 60o. Also we must have MP ≤ MX with equality iff P = X, and similarly NP ≤ NY with equality iff P = Y. So MN ≤ MP + PN ≤ MX + NY = √3 (AB + DE)/2 = MN. Hence we have equality and so P = X = Y.

Hence angle APB = 60o. Suppose AD and CF meet at Q. The same argument shows that angle AQF = 60o. So the hexagon angle at A is angle APB + angle AQF = 120o. Similarly for the other angles.
Finally, note that the only possible configuration is:

The ratio AB/BC is arbitrary, but the figure is symmetrical under rotations through 120o. That follows immediately from either of the two solutions above.

Problem B1
ABCD is cyclic. The feet of the perpendicular from D to the lines AB, BC, CA are P, Q, R respectively. Show that the angle bisectors of ABC and CDA meet on the line AC iff RP = RQ.

Solution
Thanks to Li Yi

APRD is cyclic with diameter AD (because angle APD = angle ARD = 90o. Suppose its center is O and its radius r. Angle PAR = ½ angle POR, so PR = 2r sin ½POR = AD sin PAR. Similarly, RQ = CD sin RCQ. (Note that it makes no difference if R, P are on the same or opposite sides of the line AD.) But sin PAR = sin BAC, sin RCQ = sin ACB, so applying the sine rule to the triangle ABC, sin RCQ/sin PAR = AB/BC. Thus we have AD/CD = (PR/RQ) (AB/BC). Suppose the angle bisectors of B, D meet AD at X, Y. Then we have AB/BC = AX/CX and AD/CD = AY/CY. Hence (AY/CY)/(AX/CX) = PR/RQ. So PR = RQ iff X = Y, which is the required result.
Note that ABCD does not need to be cyclic! Exercise: does it need to be convex?
 
Problem B2

Given n > 2 and reals x1 <= x2 <= ... <= xn, show that (∑i,j |xi - xj| )2 ≤ (2/3) (n2 - 1) ∑i,j (xi - xj)2. Show that we have equality iff the sequence is an arithmetic progression.

Solution

Thanks to Li Yi
Notice first that if we restrict the sums to i < j, then they are halved. The lhs sum is squared and the rhs sum is not, so the the desired inequality with sums restricted to i < j has (1/3) on the rhs instead of (2/3).
Consider the sum of all |xi - xj| with i < j. x1 occurs in (n-1) terms with a negative sign. x2 occurs in one term with a positive sign and (n-2) terms with a negative sign, and so on. So we get -(n-1)x1 - (n-3)x2 - (n-5)x3 - ... + (n-1)xn = ∑ (2i-1-n)xi.
We can now apply Cauchy-Schwartz. The square of this sum is just ∑ xi2 ∑ (2i-1-n)2.
Looking at the other side of the desired inequality, we see immediately that it is n ∑ xi2 - (∑ xi)2. We would like to get rid of the second term, but that is easy because if we add h to every xi the sums in the desired inequality are unaffected (since they use only differences of xi), so we can choose h so that ∑ xi is zero. Thus we are home if we can show that ∑ (2i-1-n)2 ≤ n(n2 - 1)/3. That is easy: lhs = 4 ∑ i2 - 4(n+1) ∑ i + n(n+1)2 = (2/3)n(n+1)(2n+1) - 2n(n+1) + n(n+1)2 = (1/3)n(n+1)(2(2n+1) - 6 + 3(n+1) ) = (1/3)n(n2 - 1) = rhs. That establishes the required inequality.
We have equality iff we have equality at the Cauchy-Schwartz step and hence iff xi is proportional to (2i-1-n). That implies that xi+1 - xi is constant. So equality implies that the sequence is an AP. But if the sequence is an AP with difference d (so xi+1 = xi + d) and we take x1 = -(d/2)(n-1), then we get xi = (d/2)(2i-1-n) and ∑ xi = 0, so we have equality.

Problem B3

Show that for each prime p, there exists a prime q such that np - p is not divisible by q for any positive integer n.

Solution

Thanks to Li Yi
If p = 2, then we can take q = 3, since squares cannot be 2 mod 3. So suppose p is odd.
Consider N = 1 + p + p2 + ... + pp-1. There are p terms. Since p is odd, that means an odd number of odd terms, so N is odd. Also N = p + 1 mod p2, which is not 1 mod p2, so N must have a prime factor q which is not 1 mod p2. We will show that q has the required property.
Since N = 1 mod p, p does not divide N, so q cannot be p. If p = 1 mod q, then N = 1 + 1 + ... + 1 = p mod q. Since N = 0 mod q, that implies q divides p. Contradiction. So q does not divide p - 1.
Now suppose np = p mod q (*). We have just shown that n cannot be 1 mod q. We have also shown that q is not p, so n cannot be a multiple of q. So assume n is not 0 or 1 mod q. Take the pth power of both sides of (*). Since (p - 1)N = pp - 1, we have pp = 1 mod q. So n to the power of p2 is 1 mod q. But nq-1 = 1 mod q (the well-known Fermat little theorem). So if d = gcd(q-1, p2), then nd = 1 mod q. We chose q so that q-1 is not divisible by p2, so d must be 1 or p. But we are assuming n is not 1 mod q, so d cannot be 1. So it must be p. In other words, np = 1 mod q. But np = p mod q, so p = 1 mod q. Contradiction (we showed above that q does not divide p - 1).
[Read More...]


43rd International Mathematical Olympiad 2002 Problems & Solutions



A1.  S is the set of all (h, k) with h, k non-negative integers such that h + k < n. Each element of S is colored red or blue, so that if (h, k) is red and h' ≤ h, k' ≤ k, then (h', k') is also red. A type 1 subset of S has n blue elements with different first member and a type 2 subset of S has n blue elements with different second member. Show that there are the same number of type 1 and type 2 subsets.

A2.  BC is a diameter of a circle center O. A is any point on the circle with angle AOC > 60o. EF is the chord which is the perpendicular bisector of AO. D is the midpoint of the minor arc AB. The line through O parallel to AD meets AC at J. Show that J is the incenter of triangle CEF.
A3.  Find all pairs of integers m > 2, n > 2 such that there are infinitely many positive integers k for which (kn + k2 - 1) divides (km + k - 1).
B1.  The positive divisors of the integer n > 1 are d1 < d2 < ... < dk, so that d1 = 1, dk = n. Let d = d1d2 + d2d3 + ... + dk-1dk. Show that d < n2 and find all n for which d divides n2.
B2.  Find all real-valued functions f on the reals such that (f(x) + f(y)) (f(u) + f(v)) = f(xu - yv) + f(xv + yu) for all x, y, u, v.
B3.  n > 2 circles of radius 1 are drawn in the plane so that no line meets more than two of the circles. Their centers are O1, O2, ... , On. Show that ∑i<j 1/OiOj ≤ (n-1)π/4. 

Solutions

Problem A1
S is the set of all (h, k) with h, k non-negative integers such that h + k < n. Each element of S is colored red or blue, so that if (h, k) is red and h' ≤ h, k' ≤ k, then (h', k') is also red. A type 1 subset of S has n blue elements with different first member and a type 2 subset of S has n blue elements with different second member. Show that there are the same number of type 1 and type 2 subsets.
Solution
Let ai be the number of blue members (h, k) in S with h = i, and let bi be the number of blue members (h, k) with k = i. It is sufficient to show that b0, b1, ... , bn-1 is a rearrangement of a0, a1, ... , an-1 (because the number of type 1 subsets is the product of the ai and the number of type 2 subsets is the product of the bi).
Let ci be the largest k such that (i, k) is red. If (i, k) is blue for all k then we put ci = -1. Note that if i < j, then ci ≥ cj, since if (j, ci ) is red, then so is (i, ci ). Note also that (i, k) is red for k ≤ ci, so the sequence c0, c1, ... , cn-1 completely defines the coloring of S.
Let Si be the set with the sequence c0, c1, ... , ci, -1, ... , -1, so that Sn-1 = S. We also take S-1 as the set with the sequence -1, -1, ... , -1, so that all its members are blue. We show that the rearrangement result is true for S-1 and that if it is true for Si then it is true for Si+1. It is obvious for S-1, because both ai and bi are n, n-1, ... , 2, 1. So suppose it is true for Si (where i < n-1). The only difference between the aj for Si and for Si+1 is that ai+1 = n-i-1 for Si and (n-i-1)-(ci+1+1) for Si+1. In other words, the number n-i-1 is replaced by the number n-i-c-2, where c = ci+1. The difference in the bj is that 1 is deducted from each of b0, b1, ... , bc. But these numbers are just n-i-1, n-i-1, n-i-2, ... , n-i-c-1. So the effect of deducting 1 from each is to replace n-i-1 by n-i-c-2, which is the same change as was made to the aj. So the rearrangement result also holds for Si+1. Hence it holds for S. 

Problem A2
BC is a diameter of a circle center O. A is any point on the circle with angle AOC > 60o. EF is the chord which is the perpendicular bisector of AO. D is the midpoint of the minor arc AB. The line through O parallel to AD meets AC at J. Show that J is the incenter of triangle CEF.
Solution
F is equidistant from A and O. But OF = OA, so OFA is equilateral and hence angle AOF = 60o. Since angle AOC > 60o, F lies between A and C. Hence the ray CJ lies between CE and CF.
D is the midpoint of the arc AB, so angle DOB = ½ angle AOB = angle ACB. Hence DO is parallel to AC. But OJ is parallel to AD, so AJOD is a parallelogram. Hence AJ = OD. So AJ = AE = AF, so J lies on the opposite side of EF to A and hence on the same side as C. So J must lie inside the triangle CEF.
Also, since EF is the perpendicular bisector of AO, we have AE = AF = OE, so A is the center of the circle through E, F and J. Hence angle EFJ = ½ angle EAJ. But angle EAJ = angle EAC (same angle) = angle EFC. Hence J lies on the bisector of angle EFC.
Since EF is perpendicular to AO, A is the midpoint of the arc EF. Hence angle ACE = angle ACF, so J lies on the bisector of angle ECF. Hence J is the incenter.
Many thanks to Dirk Laurie for pointing out that the original version of this solution failed to show the relevance of angle AOC > 60o. According to the official marking scheme, one apparently lost a mark for failing to show J lies inside CEF.

Problem A3
Find all pairs of integers m > 2, n > 2 such that there are infinitely many positive integers k for which (kn + k2 - 1) divides (km + k - 1).
Solution
Answer: m = 5, n = 3.
Obviously m > n. Take polynomials q(x), r(x) with integer coefficients and with degree r(x) < n such that xm + x - 1 = q(x) (xn + x2 - 1) + r(x). Then xn + x2 - 1 divides r(x) for infinitely many positive integers x. But for sufficiently large x, xn + x2 - 1 > r(x) since r(x) has smaller degree. So r(x) must be zero. So xm + x - 1 factorises as q(x) (xn + x2 - 1), where q(x) = xm-n + am-n-1xm-n-1 + ... + a0.
At this point I use an elegant approach provided by Jean-Pierre Ehrmann
We have (xm + x - 1) = xm-n(xn + x2 - 1) + (1 - x)(xm-n+1 + xm-n - 1), so (xn + x2 - 1) must divide (xm-n+1 + xm-n - 1). So, in particular, m ≥ 2n-1. Also (xn + x2 - 1) must divide (xm-n+1 + xm-n - 1) - xm-2n+1(xn + x2 - 1) = xm-n - xm-2n+3 + xm-2n+1 - 1 (*).
At this point there are several ways to go. The neatest is Bill Dubuque's:
(*) can be written as xm-2n+3(xn-3 - 1) + (xm-(2n-1) - 1) which is < 0 for all x in (0, 1) unless n - 3 = 0 and m - (2n - 1) = 0. So unless n = 3, m = 5, it is has no roots in (0, 1). But xn + x2 - 1 (which divides it) has at least one becaause it is -1 at x = 0 and +1 at x = 1. So we must have n = 3, m = 5. It is easy to check that in this case we have an identity.
Two alternatives follow. Jean-Pierre Ehrmann continued:
If m = 2n-1, (*) is xn-1 - x2. If n = 3, this is 0 and indeed we find m = 5, n = 3 gives an identity. If n > 3, then it is x2(xn-3 - 1). But this has no roots in the interval (0, 1), whereas xn + x2 - 1 has at least one (because it is -1 at x = 0 and +1 at x = 1), so xn + x2 - 1 cannot be a factor.
If m > 2n-1, then (*) has four terms and factorises as (x - 1)(xm-n-1 + xm-n-2 + ... + xm-2n+3 + xm-2n + xm-2n-1 + ... + 1). Again, this has no roots in the interval (0, 1), whereas xn + x2 - 1 has at least one, so xn + x2 - 1 cannot be a factor.
François Lo Jacomo, having got to xn + x2 - 1 divides xm-n+1 + xm-n - 1 and looking at the case m -n + 1 > n, continues:
xn + x2 - 1 has a root r such that 0 < r < 1 (because it is -1 at x = 0 and +1 at x = 1). So rn = 1 - r2. It must also be a root of xm + x - 1, so 1 - r = rm ≤ r2n = (1 - r2)2. Hence (1 - r2)2 - (1 - r) = (1 - r) r (1 - r - r2) ≥ 0, so 1 - r - r2 ≥ 0. Hence rn = 1 - r2 ≥ r, which is impossible.
Many thanks to Carlos Gustavo Moreira for patiently explaining why the brute force approach of calculating the coefficients of q(x), starting at the low end, is full of pitfalls. After several failed attempts, I have given up on it!

Problem B1
The positive divisors of the integer n > 1 are d1 < d2 < ... < dk, so that d1 = 1, dk = n. Let d = d1d2 + d2d3 + ... + dk-1dk. Show that d < n2 and find all n for which d divides n2.
Solution
dk+1-m <= n/m. So d < n2(1/(1.2) + 1/(2.3) + 1/(3.4) + ... ). The inequality is certainly strict because d has only finitely many terms. But 1/(1.2) + 1/(2.3) + 1/(3.4) + ... = (1/1 - 1/2) + (1/2 - 1/3) + (1/3 - 1/4) + ... = 1. So d < n2.
Obviously d divides n2 for n prime. Suppose n is composite. Let p be the smallest prime dividing n. Then d > n2/p. But the smallest divisor of n2 apart from 1 is p, so if d divides n2, then d ≤ n2/p. So d cannot divide n2 for n composite. 

Problem B2
Find all real-valued functions f on the reals such that (f(x) + f(y)) (f(u) + f(v)) = f(xu - yv) + f(xv + yu) for all x, y, u, v.
Solution
Answer: there are three possible functions: (1) f(x) = 0 for all x; (2) f(x) = 1/2 for all x; or (3) f(x) = x2.
Put x = y = 0, u = v, then 4 f(0) f(u) = 2 f(0). So either f(u) = 1/2 for all u, or f(0) = 0. f(u) = 1/2 for all u is certainly a solution. So assume f(0) = 0.
Putting y = v = 0, f(x) f(u) = f(xu) (*). In particular, taking x = u = 1, f(1)2 = f(1). So f(1) = 0 or 1. Suppose f(1) = 0. Putting x = y = 1, v = 0, we get 0 = 2f(u), so f(x) = 0 or all x. That is certainly a solution. So assume f(1) = 1.
Putting x = 0, u = v = 1 we get 2 f(y) = f(y) + f(-y), so f(-y) = f(y). So we need only consider f(x) for x positive. We show next that f(r) = r2 for r rational. The first step is to show that f(n) = n2 for n an integer. We use induction on n. It is true for n = 0 and 1. Suppose it is true for n-1 and n. Then putting x = n, y = u = v = 1, we get 2f(n) + 2 = f(n-1) + f(n+1), so f(n+1) = 2n2 + 2 - (n-1)2 = (n+1)2 and it is true for n+1. Now (*) implies that f(n) f(m/n) = f(m), so f(m/n) = m2/n2 for integers m, n. So we have established f(r) = r2 for all rational r.
From (*) above, we have f(x2) = f(x)2 ≥ 0, so f(x) is always non-negative for positive x and hence for all x. Putting u = y, v = x, we get ( f(x) + f(y) )2 = f(x2 + y2), so f(x2 + y2) = f(x)2 + 2f(x)f(y) + f(y)2 ≥ f(x)2 = f(x2). For any u > v > 0, we may put u = x2 + y2, v = x2 and hence f(u) ≥ f(v). In other words, f is an increasing function.
So for any x we may take a sequence of rationals rn all less than x we converge to x and another sequence of rationals sn all greater than x which converge to x. Then rn2 = f(rn) ≤ f(x) ≤ f(sn) = sn2 for all x and hence f(x) = x2. 

Problem B3
2 circles of radius 1 are drawn in the plane so that no line meets more than two of the circles. Their centers are O1, O2, ... , On. Show that ∑i<j 1/OiOj ≤ (n-1)π/4.
Solution


Denote the circle center Oi by Ci. The tangents from O1 to Ci contain an angle 2x where sin x = 1/O1Oi. So 2x > 2/O1Oi. These double sectors cannot overlap, so ∑ 2/O1Oi < π. Adding the equations derived from O2, O3, ... we get 4 ∑ OiOj < nπ, so ∑ OiOj < nπ/4, which is not quite good enough.
There are two key observations. The first is that it is better to consider the angle OiO1Oj than the angle between the tangents to a single circle. It is not hard to show that this angle must exceed both 2/O1Oi and 2/O1Oj. For consider the two common tangents to C1 and Ci which intersect at the midpoint of O1Oi. The angle between the center line and one of the tangents is at least 2/O1Oi. No part of the circle Cj can cross this line, so its center Oj cannot cross the line parallel to the tangent through O1. In other word, angle OiO1Oj is at least 2/O1Oi. A similar argument establishes it is at least 2/O1Oj.
Now consider the convex hull of the n points Oi. m ≤ n of these points form the convex hull and the angles in the convex m-gon sum to (m-2)π. That is the second key observation. That gains us not one but two amounts π/4. However, we lose one back. Suppose O1 is a vertex of the convex hull and that its angle is θ1. Suppose for convenience that the rays O1O2, O1O3, ... , O1On occur in that order with O2 and On adjacent vertices to O1 in the convex hull. We have that the n-2 angles between adjacent rays sum to θ1. So we have ∑ 2/O1Oi < θ1, where the sum is taken over only n-2 of the i, not all n-1. But we can choose which i to drop, because of our freedom to choose either distance for each angle. So we drop the longest distance O1Oi. [If O1Ok is the longest, then we work outwards from that ray. Angle Ok-1O1Ok > 2/O1Ok-1, and angle OkO1Ok+1 > 2/O1Ok+1 and so on.]
We now sum over all the vertices in the convex hull. For any centers Oi inside the hull we use the ∑j 2/OiOj < π which we established in the first paragraph, where the sum has all n-1 terms. Thus we get ∑i,j 2/OiOj < (n-2)π, where for vertices i for which Oi is a vertex of the convex hull the sum is only over n-2 values of j and excludes 2/OiOmax i where Omax idenotes the furthest center from Oi.
Now for Oi a vertex of the convex hull we have that the sum over all j, ∑ 2/OiOj, is the sum Σ' over all but j = max i plus at most 1/(n-2) Σ'. In other words we must increase the sum by at most a factor (n-1)/(n-2) to include the missing term. For Oi not a vertex of the hull, obviously no increase is needed. Thus the full sum ∑i,j 2/OiOj < (n-1)π. Hence ∑i<j 1/OiOj < (n-1)π/4 as required.
[Read More...]


42nd International Mathematical Olympiad 2001 Problems & Solutions



A1.  ABC is acute-angled. O is its circumcenter. X is the foot of the perpendicular from A to BC. Angle C ≥ angle B + 30o. Prove that angle A + angle COX < 90o.
A2.  a, b, c are positive reals. Let a' = √(a2 + 8bc), b' = √(b2 + 8ca), c' = √(c2 + 8ab). Prove that a/a' + b/b' + c/c' ≥ 1.
A3.  Integers are placed in each of the 441 cells of a 21 x 21 array. Each row and each column has at most 6 different integers in it. Prove that some integer is in at least 3 rows and at least 3 columns.
B1.  Let n1, n2, ... , nm be integers where m is odd. Let x = (x1, ... , xm) denote a permutation of the integers 1, 2, ... , m. Let f(x) = x1n1 + x2n2 + ... + xmnm. Show that for some distinct permutations a, b the difference f(a) - f(b) is a multiple of m!.
B2.  ABC is a triangle. X lies on BC and AX bisects angle A. Y lies on CA and BY bisects angle B. Angle A is 60o. AB + BX = AY + YB. Find all possible values for angle B.
B3.  K > L > M > N are positive integers such that KM + LN = (K + L - M + N)(-K + L + M + N). Prove that KL + MN is composite. 

Solutions

Problem A1
ABC is acute-angled. O is its circumcenter. X is the foot of the perpendicular from A to BC. Angle C ≥ angle B + 30o. Prove that angle A + angle COX < 90o
 
Solution
Take D on the circumcircle with AD parallel to BC. Angle CBD = angle BCA, so angle ABD ≥ 30o. Hence angle AOD ≥ 60o. Let Z be the midpoint of AD and Y the midpoint of BC. Then AZ ≥ R/2, where R is the radius of the circumcircle. But AZ = YX (since AZYX is a rectangle).
Now O cannot coincide with Y (otherwise angle A would be 90o and the triangle would not be acute-angled). So OX > YX ≥ R/2. But XC = YC - YX < R - YX ≤ R/2. So OX > XC.
Hence angle COX < angle OCX. Let CE be a diameter of the circle, so that angle OCX = angle ECB. But angle ECB = angle EAB and angle EAB + angle BAC = angle EAC = 90o, since EC is a diameter. Hence angle COX + angle BAC < 90o.

Problem A2
a, b, c are positive reals. Let a' = √(a2 + 8bc), b' = √(b2 + 8ca), c' = √(c2 + 8ab). Prove that a/a' + b/b' + c/c' >= 1.
 
Solution
A not particularly elegant, but fairly easy, solution is to use Cauchy: (∑ xy)2 ≤ ∑ x2 ∑ y2.
To get the inequality the right way around we need to take x2 = a/a' [to be precise, we are taking x12 = a/a', x22 = b/b', x32 = c/c'.]. Take y2 = a a', so that xy = a. Then we get ∑ a/a' >= (∑ a)2/∑ a a'.
Evidently we need to apply Cauchy again to deal with ∑ a a'. This time we want ∑ a a' ≤ something. The obvious X=a, Y=a' does not work, but if we put X=a1/2, Y=a1/2a', then we have ∑ a a' ≤ (∑ a)1/2 (∑ a a'2)1/2. So we get the required inequality provided that (∑ a)3/2 ≥ (∑ a a'2)1/2 or (∑ a)3 ≥ ∑ a a'2.
Multiplying out, this is equivalent to: 3(ab2 + ac2 + ba2 + bc2 + ca2 + cb2) ≥ 18abc, or a(b - c)2 + b(c - a)2 + c(a - b)2 ≥ 0, which is clearly true. 

Problem A3
Integers are placed in each of the 441 cells of a 21 x 21 array. Each row and each column has at most 6 different integers in it. Prove that some integer is in at least 3 rows and at least 3 columns.
 
Solution
Notice first that the result is not true for a 20 x 20 array. Make 20 rectangles each 2 x 10, labelled 1, 2, ... , 20. Divide the 20 x 20 array into four quadrants (each 10 x 10). In each of the top left and bottom right quadrants, place 5 rectangles horizontally. In each of the other two quadrants, place 5 rectangles vertically. Now each row intersects 5 vertical rectangles and 1 horizontal. In other words, it contains just 6 different numbers. Similarly each column. But any given number is in either 10 rows and 2 columns or vice versa, so no number is in 3 rows and 3 columns. [None of this is necessary for the solution, but it helps to show what is going on.]
Returning to the 21 x 21 array, assume that an arrangement is possible with no integer in at least 3 rows and at least 3 columns. Color a cell white if its integer appears in 3 or more rows and black if its integer appears in only 1 or 2 rows. We count the white and black squares.
Each row has 21 cells and at most 6 different integers. 6 x 2 < 21, so every row includes an integer which appears 3 or more times and hence in at most 2 rows. Thus at most 5 different integers in the row appear in 3 or more rows. Each such integer can appear at most 2 times in the row, so there are at most 5 x 2 = 10 white cells in the row. This is true for every row, so there are at most 210 white cells in total.
Similarly, any given column has at most 6 different integers and hence at least one appears 3 or more times. So at most 5 different integers appear in 2 rows or less. Each such integer can occupy at most 2 cells in the column, so there are at most 5 x 2 = 10 black cells in the column. This is true for every column, so there are at most 210 black cells in total.
This gives a contradiction since 210 + 210 < 441.
Comment. This looks easy, but (like question 6) I found it curiously difficult (it took me well over 2 hours). For a while I could not see how to do better than a 12 x 12 array (with 2 rows of 1s, then 2 rows of 2s etc), which was disorienting. Then I got the argument almost right, but not quite right, which took more time.
The original question was phrased in terms of 21 boys and 21 girls in a competition with an unknown number of problems. Each boy, girl pair solved at least one problem. Each competitor solved at most 6 problems. One had to show that some problem was solved by at least 3 boys and at least 3 girls. The recasting in the terms above is almost immediate.
Equally, one can easily recast the solution above into the competition format. Take any boy B0. At least one of the questions he attempts must be attempted by 3 or more girls (because he attempts at most 6 questions and there are more than 6x2 girls). Hence he attempts at most 5 questions which are only attempted by less than 3 girls. So at most 5 x 2 = 10 of the 21 pairs (B0, G) attempt a question attempted by less than 3 girls. So at most 210 of the 441 pairs pairs (B, G) attempt such a question. Similarly, at most 210 pairs (B, G) attempt a question attempted by less than 3 boys. Hence at least 21 pairs (B, G) attempt a question attempted by 3 or more girls and 3 or more boys. So there must be at least one such question.
Note that the arguments above generalise immediately to show that in a 4N+1 by 4N+1 array with at most N+1 different integers in each row and column, there is some integer that appears in at least 3 rows and 3 columns, but this is not true for a 4N by 4N array.

Problem B1
Let n1, n2, ... , nm be integers, where m is odd. Let x = (x1, ... , xm) denote a permutation of the integers 1, 2, ... , m. Let f(x) = x1n1 + x2n2 + ... + xmnm. Show that for some distinct permutations a, b the difference f(a) - f(b) is a multiple of m!.
 
Solution
This is a simple application of the pigeon hole principle.
The sum of all m! distinct residues mod m! is not divisible by m! because m! is even (since m > 1). [The residues come in pairs a and m! - a, except for m!/2.].
However, the sum of all f(x) as x ranges over all m! permutations is 1/2 (m+1)! ∑ ni, which is divisible by m! (since m+1 is even). So at least one residue must occur more than once among the f(x). 

Problem B2
ABC is a triangle. X lies on BC and AX bisects angle A. Y lies on CA and BY bisects angle B. Angle A is 60o. AB + BX = AY + YB. Find all possible values for angle B.
 
Answer
Answer: 80o.
 
Solution



This is an inelegant solution, but I did get it fast! Without loss of generality we can take length AB = 1. Take angle ABY = x. Note that we can now solve the two triangles AXB and AYB. In particular, using the sine rule, BX = sin 30o/sin(150o-2x), AY = sin x/sin(120o-x), YB = sin 60o/sin(120o-x). So we have an equation for x.
Using the usual formula for sin(a + b) etc, and writing s = sin x, c = cos x, we get: 2√3 s2c - 4sc - 2√3 c3 + 2√3 c2 + 6sc - 2s - √3 = 0 or -√3 (4c3 - 2c2 - 2c + 1) = 2s(2c2 -3c + 1). This has a common factor 2c - 1. So c = 1/2 or -√3 (2c2 - 1) = 2s(c - 1) (*).
c = 1/2 means x = 60o or angle B = 120o. But in that case the sides opposite A and B are parallel and the triangle is degenerate (a case we assume is disallowed). So squaring (*) and using s2 = 1 - c2, we get: 16c4 - 8c3 - 12c2 + 8c - 1 = 0. This has another factor 2c - 1. Dividing that out we get: 8c3 - 6c + 1 = 0. But we remember that 4c3 - 3c = cos 3x, so we conclude that cos 3x = -1/2. That gives x = 40o, 80o, 160o, 200o, 280o, 320o. But we require that x < 60o to avoid degeneracy. Hence the angle B = 2x = 80o.
I subsequently found this geometric solution on the official Wolfram site (Wolfram was one of the sponsors of IMO 2001). I cannot say it is much easier, but at least it is geometric.
Extend AB to X' with BX' = BX. Extend AY to Z with YZ = YB. Then AZ = AY + YZ = AY + YB = AB + BX = AB + BX' = AX'. Angle A = 60o, so AZX' is equilateral.
Use B also to denote the angle at B. Then angle YBX = B/2. Also angle BXX' + angle BX'X = B. The triangle is isosceles by construction, so angle BX'X = B/2. Hence angle XX'Z = 60o - B/2. X lies on the bisector of A and AZ = AX', so XZ = XX'. Hence XZX' = 60o - B/2 also. But angle Z = 60o, so angle YZX = B/2 = angle YBX.
Now YZ = YB, so angle YZB = angle YBZ. Hence angle XZB = angle XBX (they are the difference of pairs of equal angles). If X does not lie on BZ, then we can conclude that XB = XZ.
In that case, since XZ = XX', we have XB = XX'. But already XB = BX' (by construction), so BXX' is equilateral and hence B/2 = 60o. But then angle B + angle A = 180o, so the triangle ABC is degenerate (with C at infinity), which we assume is disallowed. Hence X must lie on BZ, which means Z = C and angle B = 2 angle C. Hence angle B = 80, angle C = 40. 

 Problem B3
K > L > M > N are positive integers such that KM + LN = (K + L - M + N)(-K + L + M + N). Prove that KL + MN is composite.
 
Solution
Note first that KL+MN > KM+LN > KN+LM, because (KL+MN) - (KM+LN) = (K - N)(L - M) > 0 and (KM+LN) - (KN+LM) = (K - L)(M - N) > 0.
Multiplying out and rearranging, the relation in the question gives K2 - KM + M2 = L2 + LN + N2. Hence (KM + LN)(L2 + LN + N2) = KM(L2 + LN + N2) + LN(K2 - KM + M2) = KML2 + KMN2 + K2LN + LM2N = (KL + MN)(KN + LM). In other words (KM + LN) divides (KL + MN)(KN + LM).
Now suppose KL + MN is prime. Since it greater than KM + LN, it can have no common factors with KM + LN. Hence KM + LN must divide the smaller integer KN + LM. Contradiction.
Comment. This looks easy, but in fact I found it curiously difficult. It is easy to go around in circles getting nowhere. Either I am getting older, or this is harder than it looks!
Note that it is not hard to find K, L, M, N satisfying the condition in the question. For example 11, 9, 5, 1.

The Contest Problem Book V: American High School Mathematics Examinations (AHSME) / American Invitational Mathematics Examinations (AIME) 1983-1988 (Anneli Lax New Mathematical Library)






[Read More...]


41st International Mathematical Olympiad 2000 Problems & Solutions



A1.  AB is tangent to the circles CAMN and NMBD. M lies between C and D on the line CD, and CD is parallel to AB. The chords NA and CM meet at P; the chords NB and MD meet at Q. The rays CA and DB meet at E. Prove that PE = QE.

A2.  A, B, C are positive reals with product 1. Prove that (A - 1 + 1/B)(B - 1 + 1/C)(C - 1 + 1/A) ≤ 1.
A3.  k is a positive real. N is an integer greater than 1. N points are placed on a line, not all coincident. A move is carried out as follows. Pick any two points A and B which are not coincident. Suppose that A lies to the right of B. Replace B by another point B' to the right of A such that AB' = k BA. For what values of k can we move the points arbitarily far to the right by repeated moves?
B1.  100 cards are numbered 1 to 100 (each card different) and placed in 3 boxes (at least one card in each box). How many ways can this be done so that if two boxes are selected and a card is taken from each, then the knowledge of their sum alone is always sufficient to identify the third box?
B2.  Can we find N divisible by just 2000 different primes, so that N divides 2N + 1? [N may be divisible by a prime power.]
B3.  A1A2A3 is an acute-angled triangle. The foot of the altitude from Ai is Ki and the incircle touches the side opposite Ai at Li. The line K1K2 is reflected in the line L1L2. Similarly, the line K2K3 is reflected in L2L3 and K3K1 is reflected in L3L1. Show that the three new lines form a triangle with vertices on the incircle.

Solutions

Problem A1
AB is tangent to the circles CAMN and NMBD. M lies between C and D on the line CD, and CD is parallel to AB. The chords NA and CM meet at P; the chords NB and MD meet at Q. The rays CA and DB meet at E. Prove that PE = QE.
Solution
Angle EBA = angle BDM (because CD is parallel to AB) = angle ABM (because AB is tangent at B). So AB bisects EBM. Similarly, BA bisects angle EAM. Hence E is the reflection of M in AB. So EM is perpendicular to AB and hence to CD. So it suffices to show that MP = MQ.
Let the ray NM meet AB at X. XA is a tangent so XA2 = XM·XN. Similarly, XB is a tangent, so XB2 = XM·XN. Hence XA = XB. But AB and PQ are parallel, so MP = MQ. 

Problem A2
A, B, C are positive reals with product 1. Prove that (A - 1 + 1/B)(B - 1 + 1/C)(C - 1 + 1/A) ≤ 1.
Solution
An elegant solution due to Robin Chapman is as follows:
(B - 1 + 1/C) = B(1 - 1/B + 1/(BC) ) = B(1 + A - 1/B). Hence, (A - 1 + 1/B)(B - 1 + 1/C) = B(A2 - (1 - 1/B)2) ≤ B A2. So the square of the product of all three ≤ B A2 C B2 A C2 = 1.
Actually, that is not quite true. The last sentence would not follow if we had some negative left hand sides, because then we could not multiply the inequalities. But it is easy to deal separately with the case where (A - 1 + 1/B), (B - 1 + 1/C), (C - 1 + 1/A) are not all positive. If one of the three terms is negative, then the other two must be positive. For example, if A - 1 + 1/B < 0, then A < 1, so C - 1 + 1/A > 0, and B > 1, so B - 1 + 1/C > 0. But if one term is negative and two are positive, then their product is negative and hence less than 1.
Few people would manage this under exam conditions, but there are plenty of longer and easier to find solutions! 

Problem A3
k is a positive real. N is an integer greater than 1. N points are placed on a line, not all coincident. A move is carried out as follows. Pick any two points A and B which are not coincident. Suppose that A lies to the right of B. Replace B by another point B' to the right of A such that AB' = k BA. For what values of k can we move the points arbitrarily far to the right by repeated moves?
Answer
k ≥ 1/(N-1).
Solution
An elegant solution by Gerhard Woeginger is as follows:
Suppose k < 1/(N-1), so that k0 = 1/k - (N - 1) > 0. Let X be the sum of the distances of the points from the rightmost point. If a move does not change the rightmost point, then it reduces X. If it moves the rightmost point a distance z to the right, then it reduces X by at least z/k - (N-1)z = k0 z. X cannot be reduced below nil. So the total distance moved by the rightmost point is at most X0/k0, where X0 is the initial value of X.
Conversely, suppose k ≥ 1/(N-1), so that k1 = (N-1) - 1/k ≥ 0. We always move the leftmost point. This has the effect of moving the rightmost point z > 0 and increasing X by (N-1)z - z/k = k1z ≥ 0. So X is never decreased. But z ≥ k X/(N-1) ≥ k X0/(N-1) > 0. So we can move the rightmost point arbitrarily far to the right (and hence all the points, since another N-1 moves will move the other points to the right of the rightmost point). 

Problem B1
100 cards are numbered 1 to 100 (each card different) and placed in 3 boxes (at least one card in each box). How many ways can this be done so that if two boxes are selected and a card is taken from each, then the knowledge of their sum alone is always sufficient to identify the third box?
Answer
12. Place 1, 2, 3 in different boxes (6 possibilities) and then place n in the same box as its residue mod 3. Or place 1 and 100 in different boxes and 2 - 99 in the third box (6 possibilities).
Solution
An elegant solution communicated (in outline) by both Mohd Suhaimi Ramly and Fokko J van de Bult is as follows:
Let Hn be the corresponding result that for cards numbered 1 to n the only solutions are by residue mod 3, or 1 and n in separate boxes and 2 to n - 1 in the third box. It is easy to check that they are solutions. Hn is the assertion that there are no others. H3 is obviously true (although the two cases coincide). We now use induction on n. So suppose that the result is true for n and consider the case n + 1.
Suppose n + 1 is alone in its box. If 1 is not also alone, then let N be the sum of the largest cards in each of the boxes not containing n + 1. Since n + 2 ≤ N ≤ n + (n - 1) = 2n - 1, we can achieve the same sum N as from a different pair of boxes as (n + 1) + (N - n - 1). Contradiction. So 1 must be alone and we have one of the solutions envisaged in Hn+1.
If n + 1 is not alone, then if we remove it, we must have a solution for n. But that solution cannot be the n, 1, 2 to n - 1 solution. For we can easily check that none of the three boxes will then accomodate n + 1. So it must be the mod 3 solution. We can easily check that in this case n + 1 must go in the box with matching residue, which makes the (n + 1) solution the other solution envisaged by Hn+1. That completes the induction.
My much more plodding solution (which I was quite pleased with until I saw the more elegant solution above) follows. It took about half-an-hour and shows the kind of kludge one is likely to come up with under time pressure in an exam!
With a suitable labeling of the boxes as A, B, C, there are 4 cases to consider:
Case 1: A contains 1; B contains 2; C contains 3
Case 2: A contains 1,2
Case 3: A contains 1, 3; B contains 2
Case 4: A contains 1; B contains 2, 3.
We show that Cases 1 and 4 each yield just one possible arrangement and Cases 2 and 3 none.
In Case 1, it is an easy induction that n must be placed in the same box as its residue (in other words numbers with residue 1 mod 3 go into A, numbers with residue 2 go into B, and numbers with residue 0 go into C). For (n + 1) + (n - 2) = n + (n - 1). Hence n + 1 must go in the same box as n - 2 (if they were in different boxes, then we would have two pairs from different pairs of boxes with the same sum). It is also clear that this is a possible arrangement. Given the sum of two numbers from different boxes, take its residue mod 3. A residue of 0 indicates that the third (unused) box was C, a residue of 1 indicates that the third box was A, and a residue of 2 indicates that the third box was B. Note that this unique arrangement gives 6 ways for the question, because there are 6 ways of arranging 1, 2 and 3 in the given boxes.
In Case 2, let n be the smallest number not in box A. Suppose it is in box B. Let m be the smallest number in the third box, C. m - 1 cannot be in C. If it is in A, then m + (n - 1) = (m - 1) + n. Contradiction (m is in C, n - 1 is in A, so that pair identifies B as the third box, but m - 1 is in A and n is in B, identifying C). So m - 1 must be in B. But (m - 1) + 2 = m + 1. Contradiction. So Case 2 is not possible.
In Case 3, let n be the smallest number in box C, so n - 1 must be in A or B. If n - 1 is in A, then (n - 1) + 2 = n + 2. Contradiction (a sum of numbers in A and B equals a sum from C and A). If n - 1 is in B, then (n - 1) + 3 = n + 2. Contradiction ( a sum from B and A equals a sum from C and B). So Case 3 is not possible.
In Case 4, let n be the smallest number in box C. n - 1 cannot be in A, or (n - 1) + 2 = 3 + n (pair from A, B with same sum as pair from B, C), so n - 1 must be in B. Now n + 1 cannot be in A (or (n + 1) + 2 = 3 + n), or in B or C (or 1 + (n + 1) = 2 + n). So n + 1 cannot exist and hence n = 100. It is now an easy induction that all of 4, 5, ... 98 must be in B. For given that m is in B, if m + 1 were in A, we would have 100 + m = 99 + (m + 1). But this arrangement (1 in A, 2 - 99 in B, 100 in C) is certainly possible: sums 3 - 100 identify C as the third box, sum 101 identifies B as the third box, and sums 102-199 identify A as the third box. Finally, as in Case 1, this unique arrangement corresponds to 6 ways of arranging the cards in the given boxes. 

Problem B2
Can we find N divisible by just 2000 different primes, so that N divides 2N + 1? [N may be divisible by a prime power.]
Answer
Yes
Solution
Note that for b odd we have 2ab + 1 = (2a + 1)(2a(b-1) - 2a(b-2) + ... + 1), and so 2a + 1 is a factor of 2ab + 1. It is sufficient therefore to find m such that (1) m has only a few distinct prime factors, (2) 2m + 1 has a large number of distinct prime factors, (3) m divides 2m + 1. For then we can take k, a product of enough distinct primes dividing 2m + 1 (but not m), so that km has exactly 2000 factors. Then km still divides 2m + 1 and hence 2km + 1.
The simplest case is where m has only one distinct prime factor p, in other words it is a power of p. But if p is a prime, then p divides 2p - 2, so the only p for which p divides 2p + 1 is 3. So the questions are whether ah = 2m + 1 is (1) divisible by m = 3h and (2) has a large number of distinct prime factors.
ah+1 = ah(22m - 2m + 1), where m = 3h. But 2m = (ah - 1), so ah+1 = ah(ah2 - 3 ah + 3). Now a1 = 9, so an easy induction shows that 3h+1 divides ah, which answers (1) affirmatively. Also, since ah is a factor of ah+1, any prime dividing ah also divides ah+1. Put ah = 3h+1bh. Then bh+1 = bh(32h+1bh2 - 3h+2bh + 1). Now (32h+1bh2 - 3h+2bh + 1) > 1, so it must have some prime factor p > 1. But p cannot be 3 or divide bh (since (32h+1bh2 - 3h+2bh + 1) is a multiple of 3bh plus 1), so bh+1 has at least one prime factor p > 3 which does not divide bh. So bh+1 has at least h distinct prime factors greater than 3, which answers (2) affirmatively. But that is all we need. We can take m in the first paragraph above to be 32000: (1) m has only one distinct prime factor, (2) 2m + 1 = 32001 b2000 has at least 1999 distinct prime factors other than 3, (3) m divides 2m + 1. Take k to be a product of 1999 distinct prime factors dividing b2000. Then N = km is the required number with exactly 2000 distinct prime factors which divides 2N + 1. 

Problem B3
A1A2A3 is an acute-angled triangle. The foot of the altitude from Ai is Ki and the incircle touches the side opposite Ai at Li. The line K1K2 is reflected in the line L1L2. Similarly, the line K2K3 is reflected in L2L3 and K3K1 is reflected in L3L1. Show that the three new lines form a triangle with vertices on the incircle. 



Solution
 


Let O be the centre of the incircle. Let the line parallel to A1A2 through L2 meet the line A2O at X. We will show that X is the reflection of K2 in L2L3. Let A1A3 meet the line A2O at B2. Now A2K2 is perpendicular to K2B2 and OL2 is perpendicular to L2B2, so A2K2B2 and OL2B2 are similar. Hence K2L2/L2B2 = A2O/OB2. But OA3 is the angle bisector in the triangle A2A3B2, so A2O/OB2 = A2A3/B2A3.
Take B'2 on the line A2O such that L2B2 = L2B'2 (B'2 is distinct from B2 unless L2B2 is perpendicular to the line). Then angle L2B'2X = angle A3B2A2. Also, since L2X is parallel to A2A1, angle L2XB'2 = angle A3A2B2. So the triangles L2XB'2 and A3A2B2 are similar. Hence A2A3/B2A3 = XL2/B2'L2 = XL2/B2L2 (since B'2L2 = B2L2).
Thus we have shown that K2L2/L2B2 = XL2/B2L2 and hence that K2L2 = XL2. L2X is parallel to A2A1 so angle A2A1A3 = angle A1L2X = angle L2XK2 + angle L2K2X = 2 angle L2XK2 (isosceles). So angle L2XK2 = 1/2 angle A2A1A3 = angle A2A1O. L2X and A2A1 are parallel, so K2X and OA1 are parallel. But OA1 is perpendicular to L2L3, so K2X is also perpendicular to L2L3 and hence X is the reflection of K2 in L2L3.
Now the angle K3K2A1 = angle A1A2A3, because it is 90o - angle K3K2A2 = 90o - angle K3A3A2 (A2A3K2K3 is cyclic with A2A3 a diameter) = angle A1A2A3. So the reflection of K2K3 in L2L3 is a line through X making an angle A1A2A3 with L2X, in other words, it is the line through X parallel to A2A3.
Let Mi be the reflection of Li in AiO. The angle M2XL2 = 2 angle OXL2 = 2 angle A1A2O (since A1A2 is parallel to L2X) = angle A1A2A3, which is the angle betwee L2X and A2A3. So M2X is parallel to A2A3, in other words, M2 lies on the reflection of K2K3 in L2L3.
If follows similarly that M3 lies on the reflection. Similarly, the line M1M3 is the reflection of K1K3 in L1L3, and the line M1M2 is the reflection of K1K2 in L1L2 and hence the triangle formed by the intersections of the three reflections is just M1M2M3.
[Read More...]


40th International Mathematical Olympiad 1999 Problems & Solutions



A1.  Find all finite sets S of at least three points in the plane such that for all distinct points A, B in S, the perpendicular bisector of AB is an axis of symmetry for S.
A2.  Let n ≥ 2 be a fixed integer. Find the smallest constant C such that for all non-negative reals x1, ... , xn:   ∑i<j xi xj (xi2 + xj2) ≤ C ( ∑ xi )4.
Determine when equality occurs.
A3.  Given an n x n square board, with n even. Two distinct squares of the board are said to be adjacent if they share a common side, but a square is not adjacent to itself. Find the minimum number of squares that can be marked so that every square (marked or not) is adjacent to at least one marked square.
B1.  Find all pairs (n, p) of positive integers, such that: p is prime; n ≤ 2p; and (p - 1)n + 1 is divisible by np-1.
B2.  The circles C1 and C2 lie inside the circle C, and are tangent to it at M and N, respectively. C1 passes through the center of C2. The common chord of C1 and C2, when extended, meets C at A and B. The lines MA and MB meet C1 again at E and F. Prove that the line EF is tangent to C2.
B3.  Determine all functions f: R→R such that f(x - f(y) ) = f( f(y) ) + x f(y) + f(x) - 1 for all x, y in R. [R is the reals.] 

Solutions

Problem A1
Find all finite sets S of at least three points in the plane such that for all distinct points A, B in S, the perpendicular bisector of AB is an axis of symmetry for S.
 
Solution
by Gerhard Woeginger
The possible sets are just the regular n-gons (n > 2).
Let A1, A2, ... , Ak denote the vertices of the convex hull of S (and take indices mod k as necessary). We show first that these form a regular k-gon. Ai+1 must lie on the perpendicular bisector of Ai and Ai+2 (otherwise its reflection would lie outside the hull). Hence the sides are all equal. Similarly, Ai+1 and Ai+2 must be reflections in the perpendicular bisector of Ai and Ai+3 (otherwise one of the reflections would lie outside the hull). Hence all the angles are equal.
Any axis of symmetry for S must also be an axis of symmetry for the Ai, and hence must pass through the center C of the regular k-gon. Suppose X is a point of S in the interior of k-gon. Then it must lie inside or on some triangle AiAi+1C. C must be the circumcenter of AiAi+1X (since it lies on the three perpendicular bisectors, which must all be axes of symmetry of S), so X must lie on the circle center C, through Ai and Ai+1. But all points of the triangle AiAi+1X lie strictly inside this circle, except Aiand Ai+1, so X cannot be in the interior of the k-gon.

Problem A2
Let n >= 2 by a fixed integer. Find the smallest constant C such that for all non-negative reals x1, ... , xn:
  ∑i<j xi xj (xi2 + xj2) <= C (∑ xi)4.
Determine when equality occurs.
 
Answer Answer: C = 1/8. Equality iff two xi are equal and the rest zero.
 
Solution
By a member of the Chinese team at the IMO - does anyone know who?
(∑ xi)4 = (∑ xi2 + 2 ∑i<jxixj)2 ≥ 4 (∑ xi2) (2 ∑i<j xixj) = 8 ∑i<j ( xixj ∑ xk2) ≥ 8 ∑i<j xixj(xi2 + xj2).
The second inequality is an equality only if n - 2 of the xi are zero. So assume that x3 = x4 = ... = xn = 0. Then for the first inequality to be an equality we require that (x12 + x22) = 2 x1x2 and hence that x1 = x2. However, that is clearly also sufficient for equality.
 
Alternative solution by Gerhard Woeginger
Setting x1 = x2 = 1, xi = 0 for i > 2 gives equality with C = 1/8, so, C cannot be smaller than 1/8.
We now use induction on n. For n = 2, the inequality with C = 1/8 is equivalent to (x1 - x2)4 ≥ 0, which is true, with equality iff x1 = x2. So the result is true for n = 2.
For n > 2, we may take x1 + ... + xn = 1, and x1 ≤ x2 ≤ ... ≤ xn. Now replace x1 and x2 by 0 and x1 + x2. The sum on the rhs is unchanged and the sum on the lhs is increased by (x1 + x2)3 S - (x13 + x23) S - x1x2(x12 + x22), where S = x3 + x4 + ... + xn. But S is at least 1/3 (the critical case is n = 3, xi = 1/3), so this is at least x1x2(x1 + x2 - x12 - x22). This is strictly greater than 0 unless x1 = 0 (when it equals 0), so the result follows by induction.
 
Comment. The first solution is elegant and shows clearly why the inequality is true. The second solution is more plodding, but uses an approach which is more general and can be applied in many other cases. At least with hindsight, the first solution is not as impossible to find as one might think. A little playing around soon uncovers the fact that one can get C = 1/8 with two xi equal and the rest zero, and that this looks like the best possible. One just has to make the jump to replacing (xi2 + xj2) by ∑ xk2. The solution is then fairly clear. Of course, that does not detract from the contestant's achievement, because I and almost everyone else who has looked at the problem failed to make that jump.

Problem A3
Given an n x n square board, with n even. Two distinct squares of the board are said to be adjacent if they share a common side, but a square is not adjacent to itself. Find the minimum number of squares that can be marked so that every square (marked or not) is adjacent to at least one marked square.
 
Answer
Answer: n/2 (n/2 + 1) = n(n + 2)/4.
 
Solution
Let n = 2m. Color alternate squares black and white (like a chess board). It is sufficient to show that m(m+1)/2 white squares are necessary and sufficient to deal with all the black squares.
This is almost obvious if we look at the diagonals.
Look first at the odd-length white diagonals. In every other such diagonal, mark alternate squares (starting from the border each time, so that r+1 squares are marked in a diagonal length 2r+1). Now each black diagonal is adjacent to a picked white diagonal and hence each black square on it is adjacent to a marked white square. In all 1 + 3 + 5 + ... + m-1 + m + m-2 + ... + 4 + 2 = 1 + 2 + 3 + ... + m = m(m+1)/2 white squares are marked. This proves sufficiency.
For necessity consider the alternate odd-length black diagonals. Rearranging, these have lengths 1, 3, 5, ... , 2m-1. A white square is only adjacent to squares in one of these alternate diagonals and is adjacent to at most 2 squares in it. So we need at least 1 + 2 + 3 + ... + m = m(m+1)/2 white squares. 

Problem B1
Find all pairs (n, p) of positive integers, such that: p is prime; n ≤ 2p; and (p - 1)n + 1 is divisible by np-1.
 
Answer
(1, p) for any prime p; (2, 2); (3, 3).
 
Solution
by Gerhard Woeginger, Technical University, Graz
Answer: (1, p) for any prime p; (2, 2); (3, 3).
Evidently (1, p) is a solution for every prime p. Assume n > 1 and take q to be the smallest prime divisor of n. We show first that q = p.
Let x be the smallest positive integer for which (p - 1)x = - 1 (mod q), and y the smallest positive integer for which (p - 1)y = 1 (mod q). Certainly y exists and indeed y < q, since (p - 1)q-1 = 1 (mod q). We know that (p - 1)n = -1 (mod q), so x exists also. Writing n = sy + r, with 0 ≤ r < y, we conclude that (p - 1)r = -1 (mod q), and hence x ≤ r < y (r cannot be zero, since 1 is not -1 (mod q) ).
Now write n = hx + k with 0 ≤ k < x. Then   -1 = (p - 1)n = (-1)h(p - 1)k (mod q). h cannot be even, because then (p - 1)k = -1 (mod q), contradicting the minimality of x. So h is odd and hence (p - 1)k = 1 (mod q) with 0 ≤ k < x < y. This contradicts the minimality of y unless k = 0, so n = hx. But x < q, so x = 1. So (p - 1) = -1 (mod q). p and q are primes, so q = p, as claimed.
So p is the smallest prime divisor of n. We are also given that n ≤ 2p. So either p = n, or p = 2, n = 4. The latter does not work, so we have shown that n = p. Evidently n = p = 2 and n = p = 3 work. Assume now that p > 3. We show that there are no solutions of this type.
Expand (p - 1)p + 1 by the binomial theorem, to get (since (-1)p = -1): 1 + -1 + p2 - 1/2 p(p - 1)p2 + p(p - 1)(p - 2)/6 p3 - ...
The terms of the form (bin coeff) pi with i >= 3 are obviously divisible by p3, since the binomial coefficients are all integral. Hence the sum is p2 + a multiple of p3. So the sum is not divisible by p3. But for p > 3, pp-1 is divisible by p3, so it cannot divide (p - 1)p + 1, and there are no more solutions. 

Problem B2
The circles C1 and C2 lie inside the circle C, and are tangent to it at M and N, respectively. C1 passes through the center of C2. The common chord of C1 and C2, when extended, meets C at A and B. The lines MA and MB meet C1 again at E and F. Prove that the line EF is tangent to C2.
 
Solution
Solution by Jean-Pierre Ehrmann
Let O, O1, O2 and r, r1, r2 be the centers and radii of C, C1, C2 respectively. Let EF meet the line O1O2 at W, and let O2W = x. We need to prove that x = r2.
Take rectangular coordinates with origin O2, x-axis O2O1, and let O have coordinates (a, b). Notice that O and M do not, in general, lie on O1O2. Let AB meet the line O1O2 at V.
We observe first that O2V = r22/(2 r1). [For example, let X be a point of intersection of C1 and C2 and let Y be the midpoint of O2X. Then O1YO2 and XVO2 are similar. Hence, O2V/O2X = O2Y/O2O1.]
An expansion (or, to be technical, a homothecy) center M, factor r/r1 takes O1 to O and EF to AB. Hence EF is perpendicular to O1O2. Also the distance of O1 from EF is r1/r times the distance of O from AB, so (r1 - x) = r1/r (a - r22/(2 r1) ) (*).
We now need to find a. We can get two equations for a and b by looking at the distances of O from O1 and O2. We have:
  (r - r1)2 = (r1 - a)2 + b2, and
  (r - r2)2 = a2 + b2.
Subtracting to eliminate b, we get   a = r22/(2 r1) + r - r r2/r1.   Substituting back in (*), we get x = r2, as required.
Alternative solution by Marcin Kuczma, communicated Arne Smeets
Let C1 and C2 meet at X and Y, and let AN meet C2 again at D. Then AE·AM = AX·AY = AD·AN, so triangles AED and ANM are similar. Hence ∠ADE = ∠AMN.
Take the tangent AP as shown. Then ∠PAN = ∠AMN = ∠ADE, so AP and DE are parallel. The homothecy center M mapping C to C1 takes the line AP to the line ED, so ED is tangent to C1 at E. A similar argument show that it is tangent to C2 at D. The homothecy takes AB to EF, so EF is perpendicular to O1O2 (the line of centers). Hence O2EF is isosceles. So angle O2EF = angle O2FE = angle DEO2 (DE tangent). In other words, O2E bisects angle DEF. But ED is tangent to C2, so EF is also.


 Problem 6
Determine all functions f: R -> R such that f(x - f(y) ) = f( f(y) ) + x f(y) + f(x) - 1 for all x, y in R. [R is the reals.]
 
Solution
Solution communicated by Ong Shien Jin
Let c = f(0) and A be the image f(R). If a is in A, then it is straightforward to find f(a): putting a = f(y) and x = a, we get f(a - a) = f(a) + a2 + f(a) - 1, so f(a) = (1 + c)/2 - a2/2 (*).
The next step is to show that A - A = R. Note first that c cannot be zero, for if it were, then putting y = 0, we get: f(x - c) = f(c) + xc + f(x) - 1 (**) and hence f(0) = f(c) = 1. Contradiction. But (**) also shows that f(x - c) - f(x) = xc + (f(c) - 1). Here x is free to vary over R, so xc + (f(c) - 1) can take any value in R.
Thus given any x in R, we may find a, b in A such that x = a - b. Hence f(x) = f(a - b) = f(b) + ab + f(a) - 1. So, using (*):   f(x) = c - b2/2 + ab - a2/2 = c - x2/2.
In particular, this is true for x in A. Comparing with (*) we deduce that c = 1. So for all x in R we must have   f(x) = 1 - x2/2. Finally, it is easy to check that this satisfies the original relation and hence is the unique solution.
[Read More...]


School Exercise Books

 
Return to top of page Copyright © 2010 Copyright 2010 (C) High School Math - high school maths - math games high school - high school math teacher - high school geometry - high school mathematics - high school maths games - math high school - virtual high school - jefferson high school - high school online www.highschoolmath.info. All right reseved.