MathDB
IMO ShortList 2008, Combinatorics problem 6

Source: IMO ShortList 2008, Combinatorics problem 6

July 9, 2009
combinatoricsSubsetsExtremal combinatoricsIMO Shortlist

Problem Statement

For n≥2 n\ge 2, let S1 S_1, S2 S_2, … \ldots, S2n S_{2^n} be 2n 2^n subsets of A \equal{} \{1, 2, 3, \ldots, 2^{n \plus{} 1}\} that satisfy the following property: There do not exist indices a a and b b with a<b a < b and elements x x, y y, z∈A z\in A with x<y<z x < y < z and y y, z∈Sa z\in S_a, and x x, z∈Sb z\in S_b. Prove that at least one of the sets S1 S_1, S2 S_2, … \ldots, S2n S_{2^n} contains no more than 4n 4n elements. Proposed by Gerhard Woeginger, Netherlands
Back to ProblemsView on AoPS