MathDB
α and β are two coverings of S [ILL 1971]

Source:

January 1, 2011
combinatorics proposedcombinatorics

Problem Statement

Let SS be a circle, and α={A1,…,An}\alpha =\{A_1,\ldots ,A_n\} a family of open arcs in SS. Let N(α)=nN(\alpha )=n denote the number of elements in α\alpha. We say that α\alpha is a covering of SS if ⋃k=1nAk⊃S\bigcup_{k=1}^n A_k\supset S. Let α={A1,…,An}\alpha=\{A_1,\ldots ,A_n\} and β={B1,…,Bm}\beta =\{B_1,\ldots ,B_m\} be two coverings of SS. Show that we can choose from the family of all sets Ai∩Bj, i=1,2,…,n, j=1,2,…,m,A_i\cap B_j,\ i=1,2,\ldots ,n,\ j=1, 2,\ldots ,m, a covering γ\gamma of SS such that N(γ)≤N(α)+N(β)N(\gamma )\le N(\alpha)+N(\beta).
Back to ProblemsView on AoPS