7 rooks and 12x12 chessboard, An IMOQ 2022 problem

 Seems like there is a new exam for qualification to the regional math olympiads in India now. It is called IMOQ and is a set of fill in the blank questions, the answers typically being an integer between 0 and 99.

Here is an interesting problem I came across, where none of the folks claiming to solve it had a valid proof (though the final answer was actually correct).

The problem was:

You have a 12x12 chessboard. Find the smallest $N$ such that no matter how you place $N$ rooks on the board, one can find 7 rooks which don't attack each other.

We can easily show that $N=72$ is a lower-bound. Fill up 6 rows completely with the 72 rooks, and no matter how you pick 7 rooks, two will attack each other.

Most of the solvers got this part right, and then claimed that $N=73$ is the answer, claiming if you put the 73rd rook in the above configuration, then you can find 7. This is an invalid proof, as you have to show that, no matter which configuration you choose for the 73, you can find 7.

Below is the proof I had.

Claim: For an $n x n$ chessboard, if we place at least $nk + 1$ rooks ($0 \le k \le n-1$), then there will necessarily be atleast $k+1$ rooks that don't attack each other.

We prove by induction on $k$.

$k=0$ is easily seen.

Now suppose we are given a configuration of $nk+1$ in an $n x n$ chessboard, with $1 \le k \le n-1$

Consider a row with the minimum number of rooks. This number must be $\le \dfrac{nk+1}{n}$, and thus must be $\le k$. Without loss of generality we can assume this is the first row, and we can also assume there is a rook in the square corresponding to the first column and first row (just permute the rows and columns as needed).

Now we remove the first row and first column, resulting in a configuration of the $(n-1) x (n-1)$ chessboard, and if we can show that the resulting configuration has at least $k$ rooks, we are done, as the rook in the top left corner will not attack any of these $k$ rooks.

The maximum amounts of rooks that we remove are $k + n - 1$: $k$ rooks from the first row, and at most $n-1$ other rooks from the first column.

Thus the $(n-1)x(n-1)$ chessboard has at least $$nk + 1 - (k + n - 1) = (n-1)k -(n-1) + 1 = (n-1)(k-1)+1$$ rooks.

Now $ 0 \le k-1 \le n-2$ and so by the induction assumption, this has at least $k$ rooks that don't attack other.

Note that this proof also gives an algorithm to find $k+1$ such rooks.