MathDB
Coloring subsets of a set

Source: Iran 3rd round 2012-Combinatorics exam-P4

September 20, 2012
combinatorics proposedcombinatorics

Problem Statement

a) Prove that for all m,n∈Nm,n\in \mathbb N there exists a natural number aa such that if we color every 33-element subset of the set A={1,2,3,...,a}\mathcal A=\{1,2,3,...,a\} using 22 colors red and green, there exists an mm-element subset of A\mathcal A such that all 33-element subsets of it are red or there exists an nn-element subset of A\mathcal A such that all 33-element subsets of it are green.
b) Prove that for all m,n∈Nm,n\in \mathbb N there exists a natural number aa such that if we color every kk-element subset (k>3k>3) of the set A={1,2,3,...,a}\mathcal A=\{1,2,3,...,a\} using 22 colors red and green, there exists an mm-element subset of A\mathcal A such that all kk-element subsets of it are red or there exists an nn-element subset of A\mathcal A such that all kk-element subsets of it are green.
Back to ProblemsView on AoPS