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.
I'll post my answer after you guys, It's just for sharing a new ideas, thanks:)
This is a messy proof but I don't have time to proof read it super carefully as I have an exam coming up soon, but here's a proof. Let me know if you have any questions or need more detail anywhere or if I made a mistake somewhere.
$M=2^{n-2}+1$
@Ross Millikan gave us the lower bound $M\geq 2^{n-2}+1$ so I will focus on $M\leq 2^{n-2}+1$. For the sake of ease let $k=2^{n-2}+1$.
Assume to the contrary that there exists a collection of $c$ sets of $k$ flags $\{S_1,S_2,..,S_c\}$ that aren't diverse. First observe that any such set could not contain a column in which every flag is blue and another column in which every flag is yellow since $k>2^{n-2}$. For each such set $S_i$, we can look though all possible $n$ element subsets and all possible ordering of these $n$ flags and find one that has the maximum number of blue tiles, $b_i$ along the diagonal and the maximum number of yellow tiles $y_i$ along the diagonal. Then for each $S_i$, define $x_i=max\{b_i,y_i\}$ if for each column $S_i$ has one flag with that tile yellow and one flag with that tile blue, or $x_i=b_i$($y_i$ resp.) if $S_i$ has a column where every flag's tile is yellow(blue resp.). then find some $S=S_k$ with $x_k=min\{x_i|1\leq i\leq c\}:=a$.
Now, observe that we may assume that an arrangement of $n$ flags in $S$ that has $a$ tiles along the diagonal actually has these $a$ tiles in the first $a$ columns of the $nxn$ array of flags since we can "shift" the columns to allow for this as long as the shift is done to every flag in $S$(this technically replaces $S$ with a different subset of the total set of flags that is guaranteed to have the same properties as $S$). We can also assume that for the color that for each column there is at least one flag having that color in that spot, the maximum length diagonal is the color blue. Then each of the last $n-a$ tiles on the $k-a$ flags that are not part of the longest blue diagonal must be yellow. There are only $2^a$ flags that have the last $n-a$ tiles all yellow, so $k-a\leq\frac{2^n}{2^{n-a}}=2^a$ or $2^{n-2}\leq 2^a+a-1$ giving us that $a\geq n-2$.
I claim $a\neq n-2$. To see this assume otherwise. Then the $k-n+2$ flags not used in the longest blue diagonal must have yellow tiles in their last two spots. By the defining characteristic of $S$ we know that there exists some flag $f$ used in the longest diagonal such that the second to last tile of $f$ is blue. Assume WLOG that $f$ is used as the first flag in the longest diagonal. Then each of the unused $k-n+2$ flags most be all yellow in the first, last and second to last spots since otherwise we could build a longer blue diagonal. Then $k-n+2\leq \frac{2^n}{2^3}$, but $2^{n-2}-n+3\geq 2^{n-3}$ for $n\geq 4$. Thus $a\neq n-2$.
I claim $a\neq n-1$. To see this assume to the contrary that $a=n-1$. Then all of the $k-n+1$ flags not used in the longest blue diagonal have yellow in their last spot. Since our choice of $S$ guarantees that we have at least one flag that has blue in the last spot, one of the $n-1$ flags that is part of the longest diagonal must have a blue tile in their last spot. call this $f$ and assume WLOG that $f$ is used as the first flag in the diagonal. Then all of the unused flags must have yellow in their first column as well as their last since otherwise the diagonal could be longer. If $f$ is the only flag with blue in either the first or the last column, then the $2^{n-2}$ flags in $S-{f}$ make up the entire collection of flags with yellow in both the first and last coordinate, so we can find a set of $n$ flags that gives us a yellow diagonal. thus there exists some other flag $g$ with either the first coordinate or the last coordinate blue. assume WLOG that $g$ is the second flag in the assortment that gives us the longest blue diagonal, and that the last tile of $g$ is blue. Then every one of the unused $k-n+1$ flags must have all yellow in the first, second and last column, but that would imply that $k-n+1\leq\frac{2^n}{2^3}$ but $2^{n-2}-n+2>2^{n-3}$ for $n\geq 4$. Thus $a\neq n-1$
Thus $a=n$, which is a contradiction, so $M=2^{n-2}+1$.