MathDB
There exist N flags forming a diverse set

Source: IMO Shortlist 2010, Combinatorics 2

July 17, 2011
combinatoricsIMO ShortlistHall s marriage theoremperfect matchinggraph theorymatchingHi

Problem Statement

On some planet, there are 2N2^N countries (N≥4).(N \geq 4). Each country has a flag NN units wide and one unit high composed of NN fields of size 1×1,1 \times 1, each field being either yellow or blue. No two countries have the same flag. We say that a set of NN flags is diverse if these flags can be arranged into an N×NN \times N square so that all NN fields on its main diagonal will have the same color. Determine the smallest positive integer MM such that among any MM distinct flags, there exist NN flags forming a diverse set.
Proposed by Tonći Kokan, Croatia
Back to ProblemsView on AoPS