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 x_i of S, such that the sets x_i + A are all pairwise disjoint. [Note that x_i + A is the set {a + x_i | a is in A} ].
A2.  Find all pairs (m, n) of positive integers such that m²/(2mn² - n³ + 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 x₁ ≤ x₂ ≤ ... ≤ x_n, show that (∑_i,j |x_i - x_j| )² ≤ (2/3) (n² - 1) ∑_i,j (x_i - x_j)². 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 n^p - 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 x_i of S, such that the sets x_i + A are all pairwise disjoint. [Note that x_i + A is the set {a + x_i | a is in A} ].

Solution

Thanks to Li Yi
Having found x₁, x₂, ... , x_k there are k·101·100 forbidden values for x_k+1 of the form x_i + a_m - a_n with m and n unequal and another k forbidden values with m = n. Since 99·101·100 + 99 = 10⁶ - 1, we can successively choose 100 distinct x_i.
Gerhard Woeginger sent me a similar solution

Problem A2

Find all pairs (m, n) of positive integers such that m²/(2mn² - n³ + 1) is a positive integer.

Answer

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

Solution

Thanks to Li Yi
The denominator is 2mn² - n³ + 1 = n²(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 = m²/(2mn² - n³ + 1). Then we have a quadratic equation for m, namely m² - 2hn²m + (n³ - 1)h = 0. This has solutions hn² +- N, where N is the positive square root of h²n⁴ - hn³ + 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 hn² + N is greater than hn², so the smaller root < h(n³ - 1)/(hn²) < n. But note that if 2m - n > 0, then since h > 0, we must have the denominator (2m - n)n² + 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 hn² - N = n/2. Now N² = (hn² - n/2)² = h²n⁴ - hn³ + h, so h = n²/4. Thus n must be even. Put n = 2k and we get the solutions (m, n) = (k, 2k) and (8k⁴ - 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 DA² + 2 DA.EB + EB² ≥ 3(DA² - 2 DA.EB + EB²), or DA² + EB² ≤ 4 DA.EB. Similarly, we get EB² + FC² ≤ 4 EB.FC and FC² + AD² ≤ 4 FC.AD = - 4 FC.DA. Adding the three equations gives 2(DA - EB + FC)² ≤ 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 m² = a²/2 + b²/2 - c²/4. So if m² = ¾ c², it follows that a² + b² = 2c². Similarly, b² + c² = 2a². 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 <= 60^o. Suppose angle APB > 60^o. 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 60^o. 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 = 60^o. Suppose AD and CF meet at Q. The same argument shows that angle AQF = 60^o. So the hexagon angle at A is angle APB + angle AQF = 120^o. 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 120^o. 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 = 90^o. 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 x₁ <= x₂ <= ... <= x_n, show that (∑_i,j |x_i - x_j| )² ≤ (2/3) (n² - 1) ∑_i,j (x_i - x_j)². 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 |x_i - x_j| with i < j. x₁ occurs in (n-1) terms with a negative sign. x₂ occurs in one term with a positive sign and (n-2) terms with a negative sign, and so on. So we get -(n-1)x₁ - (n-3)x₂ - (n-5)x₃ - ... + (n-1)x_n = ∑ (2i-1-n)x_i.
We can now apply Cauchy-Schwartz. The square of this sum is just ∑ x_i² ∑ (2i-1-n)².
Looking at the other side of the desired inequality, we see immediately that it is n ∑ x_i² - (∑ x_i)². We would like to get rid of the second term, but that is easy because if we add h to every x_i the sums in the desired inequality are unaffected (since they use only differences of x_i), so we can choose h so that ∑ x_i is zero. Thus we are home if we can show that ∑ (2i-1-n)² ≤ n(n² - 1)/3. That is easy: lhs = 4 ∑ i² - 4(n+1) ∑ i + n(n+1)² = (2/3)n(n+1)(2n+1) - 2n(n+1) + n(n+1)² = (1/3)n(n+1)(2(2n+1) - 6 + 3(n+1) ) = (1/3)n(n² - 1) = rhs. That establishes the required inequality.
We have equality iff we have equality at the Cauchy-Schwartz step and hence iff x_i is proportional to (2i-1-n). That implies that x_i+1 - x_i is constant. So equality implies that the sequence is an AP. But if the sequence is an AP with difference d (so x_i+1 = x_i + d) and we take x₁ = -(d/2)(n-1), then we get x_i = (d/2)(2i-1-n) and ∑ x_i = 0, so we have equality.

Problem B3

Show that for each prime p, there exists a prime q such that n^p - 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 + p² + ... + p^p-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 p², which is not 1 mod p², so N must have a prime factor q which is not 1 mod p². 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 n^p = 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 = p^p - 1, we have p^p = 1 mod q. So n to the power of p² is 1 mod q. But n^q-1 = 1 mod q (the well-known Fermat little theorem). So if d = gcd(q-1, p²), then n^d = 1 mod q. We chose q so that q-1 is not divisible by p², 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, n^p = 1 mod q. But n^p = p mod q, so p = 1 mod q. Contradiction (we showed above that q does not divide p - 1).