12th USAMO 1983

S₁, S₂, ... , S_n are subsets of the real line. Each S_i is the union of two closed intervals. Any three S_i have a point in common. Show that there is a point which belongs to at least half the S_i.

Solution

We can write S_i = [a_i, b_i] ∪ [c_i, d_i], where a_i ≤ b_i ≤ c_i <= d_i. Put a = max a_i, d = min d_i. Then a belongs to some S_h, and d belongs to some S_k. Suppose there is some S_i which does not contain a or d. Then b_i < a, so any point in S_i and S_h does not belong to [a_i, b_i]. Similarly c_i > b, so that any point in S_i and S_k does not belong to [c_i, d_i]. But that means that S_i, S_h and S_k cannot have a point in common. Contradiction. So every S_i must contain a or d. Hence either a or d belongs to at least half of them.

12th USAMO 1983

© John Scholes
jscholes@kalva.demon.co.uk
24 Aug 2002