soal IMO 2003

1. 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 :
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.
2.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.
3. 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.
. 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).