MathDB
Sets of intervals

Source: Kürschák 1994, problem 3

July 19, 2014
floor functioncombinatorics unsolvedcombinatorics

Problem Statement

Consider the sets A1,A2,…,AnA_1,A_2,\dots,A_n. Set AkA_k is composed of kk disjoint intervals on the real axis (k=1,2,…,nk=1,2,\dots,n). Prove that from the intervals contained by these sets, one can choose ⌊n+12⌋\left\lfloor\frac{n+1}2\right\rfloor intervals such that they belong to pairwise different sets AkA_k, and no two of these intervals have a common point.
Back to ProblemsView on AoPS