IMO 1972 SL 4

Origin: GDR

Problem

Let n1, n2 be positive integers. Consider in a plane E two dis- joint sets of points M1 and M2 consisting of 2n1 and 2n2 points, respec- tively, and such that no three points of the union M1 \cupM2 are collinear. Prove that there exists a straightline g with the following property: Each of the two half-planes determined by g on E (g not being included in either) contains exactly half of the points of M1 and exactly half of the points of M2.

Solution

Choose in E a half-line s beginning at a point O. For every \alpha in the interval [0, 180◦], denote by s(\alpha) the line obtained by rotation of s about O by \alpha, and by g(\alpha) the oriented line containing s(\alpha) on which s(\alpha) defines the positive direction. For each P in Mi, i = 1, 2, let P(\alpha) be the foot of the perpendicular from P to g(\alpha), and lP (\alpha) the oriented (positive, negative or zero) distance of P(\alpha) from O. Then for i = 1, 2 one can arrange the lP (\alpha) (P \inMi) in ascending order, as l1(\alpha), l2(\alpha), . . . , l2ni(\alpha). Call Ji(\alpha) the interval [lni(\alpha), lni+1(\alpha)]. It is easy to see that any line perpendicular to g(\alpha) and passing through the point with the distance l in the interior of Ji(\alpha) from O, will divide the set Mi into two subsets of equal cardinality. Therefore it remains to show that for some \alpha, the interiors of intervals J1(\alpha) and J2(\alpha) have a common point. If this holds for \alpha = 0, then

we have finished. Suppose w.l.o.g. that J1(0) lies on g(0) to the left of J2(0); then J1(180◦) lies to the right of J2(180◦). Note that J1 and J2 cannot simultaneously degenerate to a point (otherwise, we would have four collinear points in M1 \cupM2); also, each of them degenerates to a point for only finitely many values of \alpha. Since J1(\alpha) and J2(\alpha) move continuously, there exists a subinterval I of [0, 180◦] on which they are not disjoint. Thus, at some point of I, they are both nondegenerate and have a common interior point, as desired.