Let \(n\geq2 \) 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\) roots, there is a \( k \times k \) square which does not contain a rook on any of its \(k^2 \) unit squares.

## Comments

Sort by:

TopNewestThe answer is \(\left \lfloor \sqrt{n-1} \right \rfloor.\) Rather simple for an IMO P2; I suppose it's a C2 in the shortlist. The main idea is to tile the grid into several disjoint \(j^2 \times j^2\) tiles where \(j= \left \lfloor \sqrt{n-1} \right \rfloor.\) I have posted my solution in AoPS, I can post it here if necessary. :) – Sreejato Bhattacharya · 2 years, 8 months ago

Log in to reply

– Saksham Bansal · 2 years, 8 months ago

Could you please post the full solution for this problem?Log in to reply

I didn't like the phrasing of this question because it was slightly ambiguous.

- It wasn't clear to me that \(k\) should depend on \(n\). Would have preferred if they called it \(k_n\) instead.

- It wasn't clear if the square have to be consecutive rows and columns, or could be a sub-matrix (i.e. you get to pick \(k\) rows and \(k\) columns). I'm guessing the answer is "have to be consecutive". – Calvin Lin Staff · 2 years, 8 months ago

Log in to reply

– Kenny Lau · 2 years, 8 months ago

Since \(k\times k\) is a square, it has to be consecutive.Log in to reply

Conjecture: \[k=\left\lfloor\frac n2\right\rfloor\] – Kenny Lau · 2 years, 8 months ago

Log in to reply

seems to be a counterexample to \(n=4\). There is no \( 2 \times 2 \) (consecutive) square. – Calvin Lin Staff · 2 years, 8 months ago

Log in to reply

– Kenny Lau · 2 years, 8 months ago

My mistake, I thought we're finding the maximum value of \(k\).Log in to reply

Otherwise, your solution works for the problem that you're solving. – Calvin Lin Staff · 2 years, 8 months ago

Log in to reply

– Kenny Lau · 2 years, 8 months ago

If \(k>\left\lfloor\frac n2\right\rfloor\), there will be \((n-k)\) rows and \((n-k)\) columns left, which is not enough to put all rooks, because \(2(n-k)=2n-2k<n\).Log in to reply