Let $n=k^2+r$ where $0< r \le 2k+1$. We will prove this $k$ will be that one, we want. Look to a rook in the uppermost row. Select $k$ consecutive columns which contain the previous rook in the first row. Now we can divide these columns in $k$ $k*k$ squares and a $k*r$ block above. Because there are only $k-1$ rooks yet to place in the $k$ $k*k$ squares, there is such a square empty. Hence our searched $k$ is at least this value. Now we prove there can always be a peaceful configuration with equality: We uses the coordinates of the latices from $(0,0)$ to $(n-1,n-1)$ Place a rook in the origin and in each next column we place a rook $k+1$ higher than the column before until we can't do it anymore. Now, in the next column we place a rook in row with index $1$ ($y=1$) and again going to the right by placing a rook $k$ higher each time. Each time we have to finish as we can't go $k$ higher, we place it in the smallest row yet attainable and continue the same process. It is easy to see we made a peaceful configuration. Assume there is a $(k+1)*(k+1)$square without a rook. Looking to the full $k+1$ columns ( a $(k+1)*n$block) of the square, we see except once the difference between consecutive rooks is $k+1$ and hence there isn't a gap of more than $k+1$. As there is a rook in the uppermost and lowermost $(k+1)*(k+1)$square, the assumption leads to a contradiction.

If $m^2<n\leq (m+1)^2$, then $k=m$. In other words, $k=[\sqrt{n-1}]$. If $n=m^2+1$, then without loss of generality there is no rook in right lower corner. We take lower row, right column and $m^2$ squares $m\times m$ disjoint from them and from each other. Totally $m^2+2$ sets, by pigeonhole principle one of them does not contain a rook, and it is a square. If $n>m^2+1$, remove last row and last column, add a rook if necessary and reduce the problem to $n-1$. If $n=m^2$, then enumerate rows and columns from 0 to $m^2-1$ and put rooks with coordinates $(ma+b,mb+a)$ for $0\leq a,b\leq m-1$. Straightforward check shows that there is no empty $m\times m$ square. Example for $n-1$ without empty $m\times m$ square is obtained from the example for $m\times m$ as above: remove last row and last column and add rook if necessary.

For $n=q^2$ the largest such square has side length $k(n)\le q$ for the following configuration: Place rooks on the following squares: $(1,1)$, $(2,q+1)$, $(3,2q+1)$, $\ldots$, $(q,(q-1)q+1)$ $(q+1,2)$, $(q+2,q+2)$, $\ldots$, $(2q,(q-1)q+2)$ $\ldots$ $\ldots$ $((q-1)q+1,q)$, $((q-1)q+2,2q)$, $\ldots$ $(q-1)q+q,q^2)$

A picture is worth a thousand words: edit: trying to make the image show up

Let this maximum be $f(n)$. It's obvious that $f(n)$ is nondecreasing. For $n=p^2$, we have $f(n)<p$ (I omit my counterexample for redundancy's sake). Now we show that there exists a $p-1\times p-1$ square in the board. Assume for the sake of contradiction that in each $p-1\times p-1$ square there is at least one rook. There are $(p(p-1)+2)^2$ such squares, counting each rook at most $(p-1)^2$ times. Therefore, there must be at least $\frac{(p(p-1)+2)^2}{(p-1)^2}=\left(p+\frac2{p-1}\right)^2>p^2=n$ rooks, a contradiction. Therefore, $f(p^2)=p-1$ For $n=p^2+1$, we may use the same logic. Since $f((p+1)^2)=p$, we have $f(p^2+1)\le p$; we assert that $f(p^2+1)=p$. Again, assume for the sake of contradiction that in each $p\times p$ square there is at least one rook. Then there are $p^2+2$ disjoint sets of squares and $p^2+1$ rooks, so the pigeonhole principle tells us that there exists an unoccupied square. Therefore, $f(p^2+1)=p$. Since $f(p^2+1)=f((p+1)^2)=p$ and $f(n)$ is nondecreasing, we have $f(n)=p$ for all $p^2+1\le n\le(p+1)^2$. Therefore, $f(n)=\left\lfloor\sqrt{n-1}\right\rfloor$.

The claim is this largest number $k$ is $\boxed{k=\lfloor \sqrt{n-1}\rfloor}$, thus $k^2 < n \leq (k+1)^2$. Label the rows and columns with the numbers from $0$ to $n-1$. Let $i$ be the label of the row containing a rook on column $n-1$, and let $I$ be any group of $k$ contiguous labels, including $i$. There exist $k$ disjoint $k\times k$ squares, made by the rows in $I$ and the columns in $J=\{0,1,\ldots, k^2-1\}$, and only at most $k-1$ rooks that may belong to them, hence one of these squares contains no rook. A counter-model for $n=m^2$ is given by rooks on positions $(mi+j,mj+i)$ for $0\leq i,j\leq m-1$. An immediate check shows there is no $m\times m$ square empty of rooks. And for any $n'\times n'$ sub-table with $m\leq n'< n$, a fortiori there exists no $m\times m$ square empty of rooks (since the $n'\times n'$ table may always be completed, need be, in order to become peaceful).

codyj wrote: For $n=p^2+1$, we may use the same logic. Since $f((p+1)^2)=p$, we have $f(p^2+1)\le p$; we assert that $f(p^2+1)=p$. Again, assume for the sake of contradiction that in each $p\times p$ square there is at least one rook. Then there are $p^2+2$ disjoint sets of squares and $p^2+1$ rooks, so the pigeonhole principle tells us that there exists an unoccupied square. Therefore, $f(p^2+1)=p$. There are no $p^2+2$ disjoint $p\times p$ squares, but only $p^2$. You have to do what Fedor Petrov did, and also consider a border row and a border column (with the corner unoccupied by a rook), before applying the pigeonhole principle.

My solution!

I like this problem, a perfect competition problem. I quickly settled the cases $n=2,3,4$ with $k=1$ and $n=5,6,7$ with $k=2$. For ten minutes I then tried to prove my working hypothesis $k=\lfloor \frac{n+1}{3}\rfloor$, which lead nowehere. Then I returned to the case $n=8$ and suddenly understood the square root structure. Everybody can solve this problem by working and a little bit of guessing.

math_explorer wrote: A picture is worth a thousand words: Invalid image file But note that on the IMO, one point was deducted for not proving the construction, and another point was deducted for not proving the answer is monotonic (i.e. construction for non-squares).

it is nice problem! I think the key of the problem will be: $n=m^2$ or we can say $n=m^2+r$ with $0 \le r\le 2m+1$. For example: for $n=m^2$ $ \Rightarrow $ $k=m-1$ and for $n=(m+1)^2$ $ \Rightarrow $ $k=m$ (it's clear and easy). Other hand, we have the $k$ be nondecreasing for $n$. So for $n=m^2+r$ with $1 \le r\le 2m$ we get that $k=m-1$ or $k=m$. We need to proof for $n=m^2+1$ the $k$ will be $m$ and after that we are done.

Let's call a square empty if it has no rooks inside it. Let $n= j^2+k,$ where $1 \leq k \leq 2j+1.$ I claim that a $n \times n$ chessboard must contain an empty $j \times j$ square. Assume the contrary. Consider any $(j^2) \times j$ horizontal subset of the chessboard which shares the left-most side with the main chessboard and tile it into $j$ disjoint $j \times j$ squares. Each of these squares must have a rook inside them, so there must be at least $j$ rooks inside this subset. Tile the whole chessboard with these subsets and note that each of them must have at least $j$ rooks. So if we consider the $j^2 \times j^2$ subset which shares the top-left corner with the original chessboard, it must have $j^2$ rooks which occupy $j^2$ rows and columns. The remaining rooks must be located on the $k \times k$ subset sharing the bottom-right corner of the original chessboard. Considering the $j^2 \times j^2$ subset sharing the top-right corner of the original chessboard, we see that the remaining rooks must be located on the $k \times k$ subset sharing the bottom-left corner of the original chessboard. There is no overlap between these subsets, which implies some of the remaining rooks must be in the same row, contradiction. Now, we show that there exists a peaceful configuration on a $(j+1) \times (j+1)$ chessboard which has no $(j+1) \times (j+1)$ empty square. Tile the chessboard into $(j+1)^2$ $(j+1) \times (j+1)$ disjoint tiles and place the rooks in the tiles such that in any $(j+1)^2 \times (j+1)$ horizontal subset, the rooks are in different rows. More simply, place the origin at the bottom right corner and place rooks on the points $\{((j+1)x+y, (j+1)y+x)\}_{1 \leq x,y \leq m+1}.$ Drawing a diagram makes this construction obvious. In conclusion, the answer is $\left \lfloor \sqrt{n-1} \right \rfloor.$

Let $n=k^2 + r$ where $0<r\leq 2k+1$. Suppose that in every $k\times k$ there is a rook. Observe first $k$ rows. We have $k$ disjoint $k\times k$ blocks where $r$ columns are not covered on $k+1$ ways. This means (since in every such block there is a rook) that we have $r(k+1)$ empty columns. These columns must stay empty until last $r$ rows where they can't be covered with rooks since $r(k+1)>r$. Hence, there will always be a $k\times k$ block without a rook. To show that $k$ is the answer we will construct a peaceful configuration for $n=(k+1)^2$ where in every $(k+1)\times(k+1)$ block there is a rook. This will be enough since the asked value is non-decreasing. That configuration is: \[ (1,1) \& (2, k+2) \& (3, 2k+3) \& \dots (k+1, k^2 + k+1) \\ (k+2, 2) \& (k+3, k+3) \& ( k+4, 2k+4) \dots (2k+2, k^2 + k+2) \\ \vdots \\ (k^2+ k+1, k+1) \& (k^2+k+2, 2k+2) \dots (k^2+2k+1, k^2+2k+1) \]

Lord.of.AMC wrote: But note that on the IMO, one point was deducted for not proving the construction, and another point was deducted for not proving the answer is monotonic (i.e. construction for non-squares).

Seriously though, I primarily intended these pictures to be a supplement to the many solutions in words above and below it. I didn't see much point in adding any more solutions when they were all essentially the same. Sorry if it wasn't clear.

Quote: mavropnevma wrote The claim is this largest number is , thus . Label the rows and columns with the numbers from to . Let be the label of the row containing a rook on column , and let be any group of contiguous labels, including . There exist disjoint squares, made by the rows in and the columns in , and only at most rooks that may belong to them, hence one of these squares contains no rook. A counter-model for is given by rooks on positions for . An immediate check shows there is no square empty of rooks. And for any sub-table with , a fortiori there exists no square empty of rooks (since the table may always be completed, need be, in order to become peaceful). Mavropnevma, I'm sorry but your solution is stolen. There is the same solution in an 1672 article from the mathematician Chibouleri Stravopsolev, which I found among some old papers in my fathers basement.

Well, I'm pretty sure you're not the Ömer I know And I in fact appreciate your comment - it is in the style of Jorge Luis Borges, inventing pretended references. Ha ha.

Finally got the time to write this down. The idea is quite immediate to people who have solved sudokus. We shall show that the answer is $\lceil \sqrt{n} \rceil - 1$. Let $n=q^2+r$ with $0 < r \le 2q+1$. Number the rows and columns as $1, \cdots , n$. Consider the rook in the first row. Suppose that it is in column $j$. Then, there must exist $q-1$ columns on at least one side of the rook. WLOG, let these columns be $j,j+1, \cdots j+q-1$. Now, there are exactly $q-1$ rooks left to be positioned in these $q$ columns. Discard the $q \times r$ block at the top of the chessboard. Then, we are left with a total of $q$ $q \times q$ squares. By Pigeonhole Principle, one of these must be empty. Therefore, $k \ge q$. Now, it is sufficient to find a construction with $k=q$. To do this, fill it up in the way, you'd expect to noobishly fill a $(q+1)^2 \times (q+1)^2$ sudoku. Formally speaking, fill up the squares with coordinates $((q+1)x+y, (q+1)(y-1) +(x+1))$. Then, note that this is a part of the larger $(q+1)^2 \times (q+1)^2$ sudoku. Also, this condition may not be peaceful i.e. some rows/columns may not have a rook but this could only make empty squares more abundant. However, see that the large sudoku doesn't have a $(q+1) \times (q+1)$ empty square. Therefore, neither does the smaller sudoku (empty squares do not shrink due to the addition of new rows/columns).

Let $ f(n,l) $ be wanted $ k $ for tiling $ n \times n $ board with $ l $ rooks.First,let's show that our $ f(n,n) $ is nondecreasing. Consider a $ n \times n $ board.It is obvious that inside that board exist a $ (n-1) \times (n-1) $ board which contains $ n-2 $ rooks on itself.Because of that it is trivial that $ f(n,n) >= f(n-1,n-2) >=f(n-1,n-1) $ so f is nondecreasing. Now consider the case $ n=m^2 $.In that case we can divide our board into $ m $ squares each of side $ m $.So, if some of those squares doesn't contain any rook that means that for that peaceful combination the answer will be at least $ m $.Now,if every square contains exactly one rook,because of the conditions of the task (that every row and collumn contain exactly one rook) we conclude that $ f(m^2,m^2)=m-1 $ .Also notice that,because of the squares we divided our board into we have $ f(m^2,m^2-1) >=m $.We proved that $ f(n,n) >= f(n-1,n-2) >=f(n-1,n-1) $ and that f is nondecreasing so when we apply it here we have $ f((m+1)^2,(m+1)^2) >= f(m^2+1,m^2 +1) >= f(m^2,m^2-1) $ which implies $ m>= f(m^2+1,m^2 +1)>=m$ so it means $ f(m^2+1,m^2 +1)=m $.That means that every $ f(n,n) $ is equal to the square root of $ m $ such that $ (m+1)^2>=n>m^2 $ so we conclude that the answer is always $ [\sqrt{n-1}] $.

Is the optimal placing of the rooks the only one possible?

Call a square idle if it contains no rook in it and let $n = j^2+p$ where $p \in [1,2j+1]$ Claim: A $n \times n$ chessboard must have a $p \times p$ idle square. Proof: We proceed by contradiction. So assume the contrary. Now consider any $(p)^2 \times p$ horiozontal subset of the chessboard which share the extreme left side with the main chessboard and tile it into $p$ disjoint $p \times p$ squares. Each of these squares must have a rook inside them, hence there must be at least $p$ rooks inside this subset. Tile the whole chessboard with this subset and observe that each of them must contain at least $p$ rooks. Hence if we consider the $p^2 \times p^2$ subset that shares the upper left corner with the original chessboard, it must contain $p^2$ rooks that occupy $p^2$ rows and coloumns and the remaining rooks must be placed on the $k \times k$ subset that shares the bottom right corner of the original chess board. Now we consider the $j^2 \times j^2$ subset sharing the upper right corner of the original chessboard, we observe that the remaining rooks must be located on the $k \times k$ subset sharing the bottom left corner of the original chess board. As there are no overlap between the subsets, this implies that some of the remaining rooks must be in the same row which gives us a contradiction. $\square$ We now prove that a peaceful configuration indeed exists on a $(j+1) \times (j+1)$ chessboard that contains no $(j+1) \times (j+1)$ idle square. Firstly, tile the chessboard into $(j+1)^2 (j+1) \times (j+1)$ disjoint tiles and then place the rooks in the tiles such that in any $(j+1)^2 \times (j+1)$ horizontal subset, the rooks are in different rows which gives us the answer to be $\left \lfloor \sqrt{n-1} \right \rfloor$ $\square$

We claim that when $n\ge k^2+1$ then there is a $k\times k$ square without rooks. Thus, $k=\lceil \sqrt n\rceil -1.$ $~$ For any $n\times n$ chessboard consider the column with the rook on its top square. Consider any $k$ consecutive columns containing the column mentioned. Now, draw horizontal lines through each rook in these $k$ columns. Note that there will be $k$ lines, one of which at the top. Thus, $k-1$ lines separate the $n-1\ge k^2$ rows excluding the top. By pigeonhole, there are $k$ consecutive rows without any lines. Thus, for $n\ge k^2+1$ there is a $k$ by $k$ square. $~$ Now, to prove that every $n\le k^2$ has a board that doesn't have a $k$ by $k$ square. Consider the following way of generating a permutation $(a_1,a_2,\dots,a_n)$ of $(1,2,\dots,n):$ first take $a_1=1$ and then for each $a_{i+1},$ if $a_i+k\le n$ then let $a_{i+1}=a_i+k.$ Otherwise, take $a_{i+1}$ to be the smallest number that is not one of $a_1,a_2,\dots,a_i.$ For example, the sequence when $n=11,k=4$ goes $(1,5,9,2,6,10,3,7,11,4,8).$ $~$ On the $i$th row, counting from the left, take the $a_i$th square, counting from the top to have a rook. Note that in this way, no matter how you choose $k$ consecutive columns, every "space" between the lines drawn will be at most $k-1$ size, so there is no $k$ by $k$ square.

Answer is $\lfloor \sqrt{n-1} \rfloor$ First, the construction for $n = k^2$ is to split the board into $k^2$ of $k$ by $k$ subboards, then treat each board as a box in the overall $k$ by $k$ board, and pick the square within the board which is the transpose the position of the board in the overall megaboard. To induct down, remove any edge row and edge column, delete any rooks within them, adding them to the remaining board when necessary. If $n > k^2$ then take $k^2$ instances of $k$ by $k$ boards in the top left first $k^2$ rows and columns, they must form a peaceful configuration within this subboard due to size. The same can be applied to the top right first $k^2$ rows and columns, but this is a contradiction as there are too many rooks in the first $k^2$ rows, finishing by contradiction.

We claim the answer $k=$$\left[ \sqrt{n-1}\right]$. Firstly, it's suffice to prove that for $n=m^2+1$ we can find a $m\times m$ square for any peaceful configuration. WLOG the left lower corner contains no rooks; take the union of leftmost column and lower row - it contains exactly two rooks. Then, dividing other part of chessboard by $m^2$ squares $m\times m$ we by PHP obtain a square with no rooks. Finally, we present the peaceful configuration for $n=m^2$, with no empty $m\times m$ square, as a generalization of example for $m=3$ below. This also gives an example for $(m-1)^2<n<m^2$ by removing one by one one pair of leftmost column and topmost row (and adding one new rook if needed). [asy][asy] unitsize(15); for(int k=0; k<3; ++k){ for(int l=0; l<3; ++l){ fill((3*k+l,3*l+k)--(3*k+l+1,3*l+k)--(3*k+l+1,3*l+k+1)--(3*k+l,3*l+k+1)--cycle, grey); } } for(int i = 0; i < 10; ++i){ draw((i,0)--(i,9)); draw((0,i)--(9,i)); } for(int j=0; j<10; j=j+3){ draw((j,0)--(j,9),linewidth(1.5)); draw((0,j)--(9,j),linewidth(1.5)); } [/asy][/asy]

We claim that the answer is $k=\lfloor\sqrt{n-1} \rfloor.$ Take $k$ s.t. $k^2\le n-1<(k+1)^2$, and take the ith column as x-coord i and jth row as y-coord j, and finally, call an mxm square that doesn't contain any rooks an m-peaceful, with an mxm square in general an m-square. Claim. The sequence of such k is nondecreasing. Proof. If you were able to get an m-peaceful from a m<n-square, you can get at least an m-peaceful from an n-square by looking at a corner of the square which does not have a square in it, and removing the row and column containing that corner: In this way there were two squares in the row and column removed, which reduces into n-1-square with n-2 rooks, and continuing this way until m-square, obviously there will be <m rooks, which obviously has at least an m-peaceful. $\square$ In a configuration where the squares are placed at $(1,1),(2,(k+2)+1),...,(n,(k+2)(n-1)+1)$, where indices are taken mod n, in this way, from (a,b) after k+1 moves, you get to (a+k+1,b-1), so there's k+1 squares' space vertically and k squares horizontally, so the maximum is k-peaceful. To see that we can find a k-peaceful, take an nxk (n is row length/\# of columns) rectangle whose bottom row has a rook on it. The number of disjoint kxk squares in the rectangle not containing that bottom row is $\frac{n-1}{k} \ge k$, but there are only k-1 rooks left in this top rectangle (since there's only k-1 unoccupied columns, with the first one occupied by the rook in bottom row), yet there are at least k squares, so at least one such square will be this k-peaceful, as desired. Attached diagram for n=9. um wait idt the sequencce of k is nondecreasing is needed, but whatever ill include it anyway

this was so free lol The answer is $\lfloor \sqrt{n - 1} \rfloor$. First we show that any $n\times n$ peaceful configuration has an empty $ k \times k $ square for $k = \lfloor \sqrt{n - 1} \rfloor$. We show that if $n = a^2 + b$ for some $0< b \le 2a + 1$, then there is an empty $a\times a $ square in an $n\times n $ peaceful configuration. Suppose there was not such an $a\times a $ empty square. Claim: Every corner square has a rook on it. Proof: Suppose not for some corner square. WLOG the corner square is the lower right. Then there are in total two rooks contained in the union of the rightmost column and bottommost row. This implies that there are $a^2 - 1$ squares contained in the top $a^2 \times a^2$ sub board. However, we can partition this sub board into $a^2$ disjoint $a\times a$ squares, so one of them must not have a rook in them, absurd. $\square$ Now, this implies there are two squares in the same row that both have a rook on them, which is absurd. Therefore, there must be such an $a\times a$ empty square, as desired. We now prove that for $n = a^2+ b$ with $0<b\le 2a + 1$ that there exists a $n\times n$ peaceful configuration with no empty $(a+1) \times (a + 1)$ square. Claim: If there exists a peaceful configuration with no empty $(a+1) \times (a+1)$ square for $k$, then there also exists one for $k - 1$. Proof: Consider removing a row and column that both have a corner cell in it (they are on the edge of the board). There is a $(k-1) \times (k-1)$ board remaining without any empty $(a+1)\times (a+1)$ square. If this board has $k - 1$ cells, then it must be peaceful, so we are done. If it has $k - 2$ cells, then there must be both a row and column that was never hit, so adding a cell in the intersection of that row and column gives a peaceful configuration for $k - 1$, which still obviously has no empty $(a+1) \times (a+1)$ squares. $\square$ Therefore, it suffices to show that an $(a+1)^2 \times (a+1)^2$ has a peaceful configuration without any empty $(a+1) \times (a+1)$ squares, or in other words, an $(x^2) \times (x^2)$ board has a peaceful configuration without any $x\times x $ square. Give each square coordinates, where the bottom left cell has coordinate $(1,1)$ and the top right has coordinate $(x^2, x^2)$. Let $S = \{(1,1), (x+1, 2), (2x+1,3) \ldots, (x^2 - x + 1, x)\}$. Define adding coordinates $(a,b)$ and $(c,d)$ to be $(a+c, b + d)$. Consider the construction $S \cup (S + (1,x)) \cup (S + (2,2x)) \cup (S + (x-1, x^2 - x) )$. It can be checked that no two $x$-coordinates intersect and no two $y$-coordinates intersect, so this configuration is peaceful. We can also see that there are no empty $x\times x$ squares in this configuration also, as desired.

lol how is this not 0 mohs The answer is $k = \lfloor \sqrt{n-1}\rfloor$. For this $k$, select the $k$ consecutive rows such that they contains the rook on the first column. Now there are at least $k^2 +1$ rows and exactly $k$ filled columns so the sets of subcolumns that are empty in these rows of length $a_1, a_2, \cdots a_k$ satisfy $a_1 + a_2+\dots a_k = k^2 +1-k$ so by PP there exists $a_i \geq k$, then there exists a $k\times k$ square. To show $\lfloor \sqrt{n-1}\rfloor+1$ is impossible, simply consider the following generalizable grid

We claim that the answer is $\boxed{k=\lfloor\sqrt{n-1}\rfloor}$. We first show that there must always exists a $k\times k$ 'free' square in the arrangement. A free $k\times k$ square is a square of size $k\times k$ such that none of its cells has any rook. Consider $k$ adjacent columns. Let the $k$ rooks be numbered according to their row number (starting from $1$). Suppose the numbers are $a_1,a_2,\ldots,a_k$ such that $1\leq a_1<a_2<\ldots<a_k\leq n+1=a_{k+1}$. Since the numbers are listed in an increasing order, then for any $1\leq i<j\leq n+1$, we have $a_j-a_i>k$ if and only if there exists a $k\times k$ empty square. Supppose there was no $k\times k$ empty square. Then, the following inequalities hold: $a_2-a_1\leq k$, $\ldots$, $n+1-a_k\leq k$ Adding the $k$ inequalities, we get $n+1-a_1\leq k^2\leq n-1\Longrightarrow a_1\geq2$, which contradicts the existence of a rook in the first row. The bound is therefore correct. We now provide a construction where every $(k+1)\times(k+1)$ square is covered. Suppose that for each $1\leq i\leq n$, we place the rook at column $i$ and row $\pi_i$. Here, $\pi=(\pi_1,\pi_2,\ldots,\pi_n)$ is a permutation of $(1,2,\ldots,n)$. Let $k=\lfloor\sqrt{n-1}\rfloor$. Then, if $\gcd(n,k+1)=1$, the permutation is set as $a_1=1$ and $a_{i+1}\equiv a_i+k+1\pmod{n}$, for each $1\leq i<n$. Moreover, if $\gcd(n,k+1)\ne1$ then $\gcd(n+1,k+1)=1$, and since $a_1=1$, we simply delete the first row and first column. However, this does not work when $n$ is a perfect square as $n=(k+1)^2$. In that case, we follow the contruction for $n-1$, and add a new column at bottommost and new row at rightmost end, and a rook is placed at row $n$ and column $n$. Note that the value of $k$ obtained for these constructions are weakly increasing. So, if we just prove the constructions for the perfect squares, we are done. The arrangement of rooks obtained for $n=(k+1)^2$ is \[(1,1), (2,k+2), (3,2k+3),\ldots, (k+1,k^2+k+1),(k+2,2),(k+3,k+4),\ldots,(2k+2,k^2+k+2),(2k+3,3),\ldots,(n,n)\]Here rook in row $j$ and column $i$ is placed at $(i,j)$. This works because for any rook, the distance (parallel or perpendicular to the sides of the square) between its adjacent rooks is $k$. This is because the rooks nearest to $(ik+i+j,jk+i+1-k)$ are $((i-1)k+(i-1)+j,jk+i+1-k),((i+1)k+i+1+j,jk+i+2-k),(ik+i+j-1,(j-1)k+i+1-k),(ik+i+j+1,jk+i+1)$ So, there is no $(k+1)\times(k+1)$ free triangle. The proof is complete. $\blacksquare$

Seems rather easy for an IMO P2, observed from the fact that I am not supposed to solve IMO 2's this fast we have $k=\lfloor \sqrt{n-1}\rfloor$ The construction is the same as other people have already shown. (Does someone know how to include images here? I can't figure it out, only attachements, but it seems to always appear at the end of the post) The motivation is trying around with small cases, and trying to block out the big squares. This construction turns out to feel the most efficient. Additionally, at the different square numbers, the placement of the rooks is basically forced. Now it is evident that if $k(n+1) > k(n)$, then $k(n+m) > k(n)$ for any $m$. here, $k(n)$ represents the minimal value of $k$ for a $n \times n$ board. We can therefore limit us to the case where $n=m^2+1$ for some $m$, and prove that there is no construction in this case. Now, let $k(n-1) = d < m$. We actually limit is to the $m$ leftmost columns. Within those, one can place at most $m$ rooks. But the number of rows is $m^2+1$, so there are two rooks that have distance at least $m$, . But that directly means that there is a square with the desired size $\blacksquare$

Let $k=\lfloor\sqrt{n-1}\rfloor$, which we claim to be our answer. We will first show that $k$ is attainable, then show that $k$ is maximal. To show attainability, suppose there exists a rook placed in each$k\times k$ square for the sake of contradiction. We may tile the top-left $k^2\times k^2$ square into $k^2$ squares each with dimensions $k\times k$; call this a mega-square. We must have at least one rook occupy each mega-square. In order to have this happen, each mega-column of $k$ mega-squares must contain at least $k$ rooks. Since each mega-column is only $k$ squares wide, it must be that each mega-column has at most $k$ rooks to keep things peaceful. Thus, each mega-square contains exactly $1$ rook. Now, consider the rook placed on row $m-k+1$, who we will call the frog. Call the frog's territory to be all squares that are in the frog's mega-column while being below the frog itself. Notice that the frog's territory is empty, as there exist $k$ rooks in the mega-column above it, preventing any additional rooks from being placed in the column. Since the frog's territory is at least $k$ rows long, while being $k$ columns wide, the frog's territory contains a $k\times k$ square which doesn't contain any rooks. This is a contradiction, so $k$ is attainable. Now, we will show that $k$ is maximal; that is, there exists a construction such that there do not exist empty $k+1\times k+1$ squares. Let $i=ak+b$ for $b<k$. We place the $i$th rook at coordinates $(ak+b,bk+a)$ if possible, as depicted below.

much more beautiful example is to put rook on the bottom left cell on each square with length of floor square n-1.

storage

Left unfinished, will finish tomorrow. Dropping this as a reminder.

I like this problem a lot. The answer is $\left \lceil \sqrt n \right \rceil - 1$. Let $a_n$ denote the maximal possible $k$ for each $n$. Clearly $\{a_n\}$ is nondecreasing, so we will show that $a_{k^2} \leq k-1$ and $a_{k^2+1} \geq k$ for each $k$ via construction and bound, respectively. Construction: It suffices to construct for $n = k^2$. Split the $k^2 \times k^2$ grid into $k \times k$ subgrids, which we label $(i, j)$ for $1 \leq i \leq k$, $1 \leq j \leq k$ according to position. Then placing a rook at position $(i, j)$ within square $(i, j)$ works. Bound: The bound proof is surprisingly simple. Consider any set of $k$ adjacent columns such that one of the columns contains the rook in row $1$. Let $y_1 = 1, y_2, \dots, y_k, y_{k+1} = k^2+2$ be the row numbers of the other rooks in these $k$ columns. Then the $k$ numbers given by $y_i - y_{i-1}$ for $2 \leq i \leq k+1$ sum to $k^2+1$, so one of them must be at least $k+1$. It follows that we can fit a $k \times k$ square between rows $y_\ell + 1$ and $y_{\ell+1} - 1$ for this index $\ell$, as needed. Remark: The only difficult part of the problem is guessing the answer; but $k \approx \sqrt n$ comes from a double counting estimate of pairs $(S, r)$ where $r$ is a rook and $S$ is a $k \times k$ subgrid that contains $r$.