MathDB
Partition into k nonintersecting subsets ISL 1978

Source:

July 28, 2010
pigeonhole principlecombinatoricspartitionSet systemsExtremal combinatoricsIMO Shortlist

Problem Statement

The set M={1,2,...,2n}M = \{1, 2, . . . , 2n\} is partitioned into kk nonintersecting subsets M1,M2,…,Mk,M_1,M_2, \dots, M_k, where n≥k3+k.n \ge k^3 + k. Prove that there exist even numbers 2j1,2j2,…,2jk+12j_1, 2j_2, \dots, 2j_{k+1} in MM that are in one and the same subset MiM_i (1≤i≤k)(1 \le i \le k) such that the numbers 2j1−1,2j2−1,…,2jk+1−12j_1 - 1, 2j_2 - 1, \dots, 2j_{k+1} - 1 are also in one and the same subset Mj(1≤j≤k).M_j (1 \le j \le k).
Back to ProblemsView on AoPS