Problemiércoles

En un planeta, hay $2^N$ países; $(N \geq 4).$ Cada país tiene una bandera de $N$ de largo y 1 de ancho, es decir, un tablero de $N$ cuadritos con tamaño $1 \times 1,$ cada uno de ellos coloreado rojo o blanco. Se sabe que no hay dos países con la misma bandera. Llamamos a un conjunto de $N$ banderas diverso, si se pueden acomodar las banderas en un tablero de $N \times N$ tal que las $N$ casillas de la diagonal principal (la que empieza en la esquina superior izquierda) tengan el mismo color, ya sea rojo o blanco. Determina el menor entero positivo $M$ tal que entre cualesquiera $M$ banderas distintas, siempre se van a poder encontrar $N$ banderas que hacen un conjunto diverso.