IMO 1997 SL 3

Origin: GER

Problem

For each finite set U of nonzero vectors in the plane we define l(U) to be the length of the vector that is the sum of all vectors in U. Given a finite set V of nonzero vectors in the plane, a subset B of V is said to be maximal if l(B) is greater than or equal to l(A) for each nonempty subset A of V . (a) Construct sets of 4 and 5 vectors that have 8 and 10 maximal subsets respectively. (b) Show that for any set V consisting of n \geq1 vectors, the number of maximal subsets is less than or equal to 2n.

Solution

(a) For n = 4, consider a convex quadrilateral ABCD in which AB = BC = AC = BD and AD = DC, and take the vectors −−\to AB, −−\to BC, −−\to CD, −−\to DA. For n = 5, take the vectors −−\to AB, −−\to BC, −−\to CD, −−\to DE, −\to EA for any regular pentagon ABCDE. (b) Let us draw the vectors of V as originated from the same point O. Consider any maximal subset B \subsetV , and denote by u the sum of all vectors from B. If l is the line through O perpendicular to u, then B contains exactly those vectors from V that lie on the same side of l as u does, and no others. Indeed, if any v ̸\inB lies on the same side of l, then |u + v| \geq|u|; similarly, if some v \inB lies on the other side of l, then |u −v| \geq|u|. Therefore every maximal subset is determined by some line l as the set of vectors lying on the same side of l. It is obvious that in this way we get at most 2n sets.