**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.

No vote yet

1 vote

×

Problem Loading...

Note Loading...

Set Loading...

Easy Math Editor

`*italics*`

or`_italics_`

italics`**bold**`

or`__bold__`

boldNote: you must add a full line of space before and after lists for them to show up correctlyparagraph 1

paragraph 2

`[example link](https://brilliant.org)`

`> This is a quote`

Remember to wrap math in \( ... \) or \[ ... \] to ensure proper formatting.`2 \times 3`

`2^{34}`

`a_{i-1}`

`\frac{2}{3}`

`\sqrt{2}`

`\sum_{i=1}^3`

`\sin \theta`

`\boxed{123}`

## 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. :)

Log in to reply

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".

Log in to reply

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

Log in to reply

Conjecture: \[k=\left\lfloor\frac n2\right\rfloor\]

Log in to reply

\( \begin{array} {| l | l | l | l |} \hline x & & & \\ \hline & & x & \\ \hline & x & & \\ \hline & & & x \\ \hline \end{array}\)

seems to be a counterexample to \(n=4\). There is no \( 2 \times 2 \) (consecutive) square.

Log in to reply

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.

Log in to reply

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