If $M=2^{N-2}$, we can choose all the flags that end with yellow then blue. It is impossible to have a diverse subset of this set of flags.

Let's show that $M=2^{N-2}+1$ is optimal. Consider the $M \times N$ grid obtained by stacking the flags on top of each other. By the contrapositive of the previous exercise, if by permutation it is not possible to observe a monochromatic diagonal, then there exist $a$ rows and $a'$ columns such that $a + a' > 2^{N-2}$. However, $|A \cap B| < 2^{N-2}$, which is impossible, hence the result.
On a planet, there are $2^{N}$ countries $(N \geqslant 5)$. Each country has a flag composed of a line of $N$ squares of side 1, each being yellow or blue. The flags are all distinct from each other. A set of $N$ flags is diverse if they can be placed in a certain order to form an $N \times N$ square such that the $N$ squares on the main diagonal are of the same color. Determine the smallest integer $M$ such that any set of $M$ flags contains a diverse set of $N$ flags.

## Directed Graphs