Kürschák;s 1950/1 solution

51st Kürschák 1950

Problem 1

Several people visited a library yesterday. Each one visited the library just once (in the course of yesterday). Amongst any three of them, there were two who met in the library. Prove that there were two moments T and T' yesterday such that everyone who visited the library yesterday was in the library at T or T' (or both).

Solution

Let the people be P₁, ... P_n and suppose P_i is present during the time interval [a_i,b_i]. Let a_M = max a_i, b_m = min b_i. Now we claim that given any of the intervals [a_i,b_i] we have a_M ∈ [a_i,b_i] or b_m ∈ [a_i,b_i]. Suppose not.

So a_M ∉ [a_i,b_i]. We know that a_i ≤ a_M, so we must have b_i < a_M. Thus the intervals [a_i,b_i] and [a_M,b_M] are disjoint with [a_i,b_i] lying entirely to the left of [a_M,b_M].

Similarly, b_m ∉ [a_i,b_i], but b_m ≤ b_i, so b_m < b_i and [a^m, b_m] and [a_i,b_i] are disjoint with [a^m, b_m] lying entirely to the left of [a_i,b_i]. Thus the three intervals [a^m, b_m], [a_i,b_i] and [a_M,b_M] are disjoint. Contradiction. So we can take T, T' to be a_M and b_m.

51st Kürschák 1950