51st IMO Shortlisted Problems

When speaking about the diagonal of a square, we will always mean the main diagonal.

Let $M_N$ be the smallest positive integer satisfying the problem condition. First, we show that $M_N>2^{N-2}$. Consider the collection of all $2^{N-2}$ flags having yellow first squares and blue second ones. Obviously, both colors appear on the diagonal of each $N\times N$ square formed by these flags.

We are left to show that $M_N\le 2^{N-2}+1$, thus obtaining the desired answer. We start with establishing this statement for $N=4$.

Suppose that we have 5 flags of length 4. We decompose each flag into two parts of 2 squares each; thereby, we denote each flag as $LR$, where the $2\times 1$ flags $L,R\in \mathcal{S}=\{\mathrm{BB},\mathrm{BY},\mathrm{YB},\mathrm{YY}\}$ are its left and right parts, respectively. First, we make two easy observations on the flags $2\times 1$ which can be checked manually.

(i) For each $A\in \mathcal{S}$, there exists only one $2\times 1$ flag $C\in \mathcal{S}$ (possibly $C=A$) such that $A$ and $C$ cannot form a $2\times 2$ square with monochrome diagonal (for part BB, that is YY, and for BY that is YB).

(ii) Let $A_1,A_2,A_3\in \mathcal{S}$ be three distinct elements; then two of them can form a $2\times 2$ square with yellow diagonal, and two of them can form a $2\times 2$ square with blue diagonal (for all parts but BB, a pair (BY, YB) fits for both statements, while for all parts but BY, these pairs are $(\mathrm{YB},\mathrm{YY})$ and $(\mathrm{BB},\mathrm{YB})$).

Now, let $\ell$ and $r$ be the numbers of distinct left and right parts of our 5 flags, respectively. The total number of flags is $5\le r\ell$, hence one of the factors (say, $r$) should be at least 3. On the other hand, $\ell ,r\le 4$, so there are two flags with coinciding right part; let them be $L_1{R}_1$ and $L_2{R}_1$ ($L_1\ne L_2$).

Next, since $r\ge 3$, there exist some flags $L_3{R}_3$ and $L_4{R}_4$ such that $R_1,R_3,R_4$ are distinct. Let $L^{\prime }{R}^{\prime }$ be the remaining flag. By (i), one of the pairs ($L^{\prime }$, $L_1$) and ($L^{\prime }$, $L_2$) can form a $2\times 2$ square with monochrome diagonal; we can assume that $L^{\prime }$, $L_2$ form a square with a blue diagonal. Finally, the right parts of two of the flags $L_1{R}_1,L_3{R}_3,L_4{R}_4$ can also form a $2\times 2$ square with a blue diagonal by (ii). Putting these $2\times 2$ squares on the diagonal of a $4\times 4$ square, we find a desired arrangement of four flags.

We are ready to prove the problem statement by induction on $N$; actually, above we have proved the base case $N=4$. For the induction step, assume that $N>4$, consider any $2^{N-2}+1$ flags of length $N$, and arrange them into a large flag of size $(2^{N-2}+1)\times N$. This flag contains a non-monochrome column since the flags are distinct; we may assume that this column is the first one. By the pigeonhole principle, this column contains at least $\lceil \frac{2^{N-2}+1}{2}\rceil =2^{N-3}+1$ squares of one color (say, blue). We call the flags with a blue first square good.

Consider all the good flags and remove the first square from each of them. We obtain at least $2^{N-3}+1\ge M_{N-1}$ flags of length $N-1$; by the induction hypothesis, $N-1$ of them can form a square $Q$ with the monochrome diagonal. Now, returning the removed squares, we obtain a rectangle $(N-1)\times N$, and our aim is to supplement it on the top by one more flag.

If $Q$ has a yellow diagonal, then we can take each flag with a yellow first square (it exists by a choice of the first column; moreover, it is not used in $Q$). Conversely, if the diagonal of $Q$ is blue then we can take any of the $\ge 2^{N-3}+1-(N-1)>0$ remaining good flags. So, in both cases we get a desired $N\times N$ square.

---

Alternative solution.

We present a different proof of the estimate $M_N\le 2^{N-2}+1$. We do not use the induction, involving Hall's lemma on matchings instead.

Consider arbitrary $2^{N-2}+1$ distinct flags and arrange them into a large $(2^{N-2}+1)\times N$ flag. Construct two bipartite graphs $G_{\mathrm{y}}=(V\cup V^{\prime },E_{\mathrm{y}})$ and $G_{\mathrm{b}}=(V\cup V^{\prime },E_{\mathrm{b}})$ with the common set of vertices as follows. Let $V$ and $V^{\prime }$ be the set of columns and the set of flags under consideration, respectively. Next, let the edge $(c,f)$ appear in $E_{\mathrm{y}}$ if the intersection of column $c$ and flag $f$ is yellow, and $(c,f)\in E_{\mathrm{b}}$ otherwise. Then we have to prove exactly that one of the graphs $G_{\mathrm{y}}$ and $G_{\mathrm{b}}$ contains a matching with all the vertices of $V$ involved.

Assume that these matchings do not exist. By Hall's lemma, it means that there exist two sets of columns $S_{\mathrm{y}},S_{\mathrm{b}}\subset V$ such that $|E_{\mathrm{y}}(S_{\mathrm{y}})|\le |S_{\mathrm{y}}|-1$ and $|E_{\mathrm{b}}(S_{\mathrm{b}})|\le |S_{\mathrm{b}}|-1$ (in the left-hand sides, $E_{\mathrm{y}}(S_{\mathrm{y}})$ and $E_{\mathrm{b}}(S_{\mathrm{b}})$ denote respectively the sets of all vertices connected to $S_{\mathrm{y}}$ and $S_{\mathrm{b}}$ in the corresponding graphs). Our aim is to prove that this is impossible. Note that $S_{\mathrm{y}},S_{\mathrm{b}}\ne V$ since $N\le 2^{N-2}+1$.

First, suppose that $S_{\mathrm{y}}\cap S_{\mathrm{b}}\ne \varnothing$, so there exists some $c\in S_{\mathrm{y}}\cap S_{\mathrm{b}}$. Note that each flag is connected to $c$ either in $G_{\mathrm{y}}$ or in $G_{\mathrm{b}}$, hence $E_{\mathrm{y}}(S_{\mathrm{y}})\cup E_{\mathrm{b}}(S_{\mathrm{b}})=V^{\prime }$. Hence we have $2^{N-2}+1=|V^{\prime }|\le |E_{\mathrm{y}}(S_{\mathrm{y}})|+|E_{\mathrm{b}}(S_{\mathrm{b}})|\le |S_{\mathrm{y}}|+|S_{\mathrm{b}}|-2\le 2N-4$; this is impossible for $N\ge 4$.

So, we have $S_{\mathrm{y}}\cap S_{\mathrm{b}}=\varnothing$. Let $y=|S_{\mathrm{y}}|,b=|S_{\mathrm{b}}|$. From the construction of our graph, we have that all the flags in the set $V^{\prime \prime }=V^{\prime }\setminus (E_{\mathrm{y}}(S_{\mathrm{y}})\cup E_{\mathrm{b}}(S_{\mathrm{b}}))$ have blue squares in the columns of $S_{\mathrm{y}}$ and yellow squares in the columns of $S_{\mathrm{b}}$. Hence the only undetermined positions in these flags are the remaining $N-y-b$ ones, so $2^{N-y-b}\ge |V^{\prime \prime }|\ge |V^{\prime }|-|E_{\mathrm{y}}(S_{\mathrm{y}})|-|E_{\mathrm{b}}(S_{\mathrm{b}})|\ge 2^{N-2}+1-(y-1)-(b-1)$, or, denoting $c=y+b$, $2^{N-c}+c>2^{N-2}+2$. This is impossible since $N\ge c\ge 2$.