2010 IMO Shortlist C2

On some planet, there are $2^{N}$ countries $(N \geq 4)$. Each country has a flag $N$ units wide and one unit high composed of $N$ fields of size $1 \times 1$, each field being either yellow or blue. No two countries have the same flag. We say that a set of $N$ flags is diverse if these flags can be arranged into an $N \times N$ square so that all $N$ fields on its main diagonal will have the same color. Determine the smallest positive integer $M$ such that among any $M$ distinct flags, there exist $N$ flags forming a diverse set. (Croatia) Answer. $M=2^{N-2}+1$.

在某个星球上，有 $2^{N}$ 个国家 $(N \geq 4)$。每个国家/地区都有一面宽为 $N$ 个单位、高为 $N$ 个单位的国旗，由大小为 $1 \times 1$ 的 $N$ 个字段组成，每个字段为黄色或蓝色。没有两个国家拥有相同的国旗。如果一组 $N$ 标志可以排列成 $N \times N$ 正方形，使得其主对角线上的所有 $N$ 字段都具有相同的颜色，则我们说一组 $N$ 标志是多样化的。确定最小正整数 $M$，使得在任何 $M$ 个不同标志中，存在形成多样化集合的 $N$ 标志。 (克罗地亚)回答。 $M=2^{N-2}+1$。