IMO 2014 Problem 2

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

6882 posts

#1 h Jul 8, 2014, 12:16 PM • 35 Y

Y by Amir Hossein, CatalinBordea, Kunihiko_Chikaya, narutomath96, Davi-8191, IMO2017BR, Tawan, Wizard_32, Combi123, MathBoy23, mathleticguyyy, ApraTrip, mathematicsy, donotoven, megarnie, thedragon01, HamstPan38825, sleepypuppy, Mogmog8, Adventure10, Mango247, Sedro, Alex-131, kiyoras_2001, and 11 other users

Let $n \ge 2$ 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$ unit squares.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

SCP

1502 posts

SCP

#2 h Jul 8, 2014, 1:00 PM • 17 Y

Y by chaotic_iak, Amir Hossein, Ygg, hoou8547, Tawan, Siddharth03, Pascal96, megarnie, Adventure10, Mango247, and 7 other users

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.

This post has been edited 1 time. Last edited by SCP, Jul 8, 2014, 1:14 PM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

Fedor Petrov

520 posts

Fedor Petrov

#3 h Jul 8, 2014, 1:00 PM • 17 Y

Y by Amir Hossein, narutomath96, mgalushka, MSTang, Tawan, megarnie, Acrylic2005, Adventure10, Mango247, and 8 other users

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.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

manuel153

324 posts

manuel153

#4 h Jul 8, 2014, 1:13 PM • 13 Y

Y by Amir Hossein, narutomath96, Tawan, megarnie, Bumfuzzle, Adventure10, and 7 other users

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)$

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

math_explorer

583 posts

math_explorer

#5 h Jul 8, 2014, 1:20 PM • 46 Y

Y by manuel153, Amir Hossein, mrjackass, CatalinBordea, droid347, infiniteturtle, swamih, narutomath96, emiliorosado, codyj, DrMath, TYERI, khalilmiri, GGPiku, Tawan, A_Math_Lover, SecondWind, Booper, opptoinfinity, khina, Combi123, ayan_mathematics_king, parola, Siddharth03, hsiangshen, Pascal96, phoenixfire, megarnie, asdf334, sleepypuppy, Ibrahim_K, Schur-Schwartz, Adventure10, Elainedelia, sabkx, amirhsz, Sedro, EpicBird08, HuYuanzhi, and 7 other users

A picture is worth a thousand words:

edit: trying to make the image show up

This post has been edited 1 time. Last edited by math_explorer, Jul 6, 2015, 1:13 PM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

codyj

723 posts

codyj

#6 h Jul 8, 2014, 3:40 PM • 10 Y

Y by Abubakir, Bumfuzzle, Adventure10, Mango247, and 6 other users

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

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

mavropnevma

15142 posts

mavropnevma

#7 h Jul 8, 2014, 10:17 PM • 15 Y

Y by Tawan, opptoinfinity, megarnie, Adventure10, and 11 other users

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

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

mavropnevma

15142 posts

mavropnevma

#8 h Jul 9, 2014, 2:10 AM • 12 Y

Y by Tawan, opptoinfinity, megarnie, Adventure10, and 8 other users

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.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

algebra1337

183 posts

algebra1337

#9 h Jul 9, 2014, 5:59 AM • 11 Y

Y by Tawan, megarnie, Adventure10, Mango247, and 7 other users

My solution!

Click to reveal hidden text

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

manuel153

324 posts

manuel153

#10 h Jul 9, 2014, 3:45 PM • 7 Y

Y by Tawan, megarnie, Adventure10, and 4 other users

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.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

Lord.of.AMC

1210 posts

Lord.of.AMC

#11 h Jul 9, 2014, 7:07 PM • 11 Y

Y by Tawan, megarnie, Adventure10, Mango247, and 7 other users

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

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

mathuz

1525 posts

mathuz

#12 h Jul 9, 2014, 7:54 PM • 10 Y

Y by Tawan, megarnie, Adventure10, Mango247, and 6 other users

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.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

AnonymousBunny

339 posts

AnonymousBunny

#13 h Jul 9, 2014, 8:04 PM • 10 Y

Y by Tawan, Adventure10, Mango247, and 7 other users

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

This post has been edited 1 time. Last edited by AnonymousBunny, Apr 16, 2017, 3:13 PM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

MarcosBH

1 post

MarcosBH

#14 h Jul 9, 2014, 10:19 PM • 10 Y

Y by Ygg, Tawan, megarnie, Adventure10, Mango247, and 5 other users

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)$

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

math_explorer

583 posts

math_explorer

#15 h Jul 9, 2014, 11:24 PM • 14 Y

Y by DrMath, Tawan, megarnie, ApraTrip, Adventure10, Mango247, Elainedelia, and 7 other users

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

hidden for size

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.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

awesomeming327.

1746 posts

awesomeming327.

#52 h Jun 24, 2022, 12:00 AM

Y by

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.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

Inconsistent

1455 posts

Inconsistent

#53 h Aug 20, 2022, 5:34 AM

Y by

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.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

JAnatolGT_00

559 posts

JAnatolGT_00

#54 h Dec 6, 2022, 9:28 PM

Y by

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] 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]$

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

vsamc

3789 posts

vsamc

#55 h Aug 1, 2023, 1:46 AM

Y by

Solution

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

signifance

140 posts

signifance

#56 h Oct 2, 2023, 7:37 PM

Y by

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

Attachments:

This post has been edited 2 times. Last edited by signifance, Oct 2, 2023, 7:40 PM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

megarnie

5609 posts

megarnie

#57 h Oct 19, 2023, 1:42 PM • 1 Y

Y by OronSH

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.

This post has been edited 3 times. Last edited by megarnie, Oct 19, 2023, 1:47 PM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

AtharvNaphade

341 posts

AtharvNaphade

#58 h Oct 19, 2023, 11:33 PM

Y by

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

Attachments:

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

Pyramix

419 posts

Pyramix

#59 h Jan 8, 2024, 11:19 AM

Y by

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$

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

Toll

23 posts

Toll

#60 h Jan 13, 2024, 12:24 AM

Y by

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$

This post has been edited 7 times. Last edited by Toll, Feb 27, 2024, 3:15 PM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

RaymondZhu

4006 posts

RaymondZhu

#61 h Apr 21, 2024, 9:54 PM

Y by

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.

Note

Attachments:

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

Afek

1 post

Afek

#62 h Apr 23, 2024, 1:43 PM

Y by

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

This post has been edited 1 time. Last edited by Afek, Apr 23, 2024, 1:47 PM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

onyqz

195 posts

onyqz

#64 h Dec 10, 2024, 11:09 PM

Y by

storage
solution

This post has been edited 1 time. Last edited by onyqz, Dec 10, 2024, 11:10 PM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

cubres

123 posts

cubres

#65 h Jan 4, 2025, 9:49 PM

Y by

Storage - grinding IMO problems
Left unfinished, will finish tomorrow. Dropping this as a reminder.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

HamstPan38825

8877 posts

HamstPan38825

#66 h Jan 6, 2025, 11:51 PM

Y by

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

This post has been edited 1 time. Last edited by HamstPan38825, Jan 6, 2025, 11:53 PM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

math-olympiad-clown

48 posts

math-olympiad-clown

#67 h Apr 17, 2025, 3:22 PM

Y by

The answer is:
$k = \left\lfloor \sqrt{n-1} \right\rfloor$ There is only one key claim we need to prove:
{If $(L+1)^2 \geq n > L^2$ , then any peaceful configuration of $n$ rooks on an $n \times n$ chessboard must contain an $L \times L$ empty square.}
First, consider the case when $n = L^2 + 1$ .
Observe that in the leftmost $L+1$ columns and the top $L+1$ rows, there are $2(L+1)$ potential $L \times L$ empty squares.
Now, consider how many of these can be \textit{covered} (or "attacked") by rooks:
The rook in the top row and the rook in the $(L+1)$ -th row together can cover at most $L$ of these $L \times L$ squares.
Each of the remaining $(L-1)$ rooks from the 2nd to the $L$ -th row can cover at most $2L$ such squares.
Even if all the covered regions are disjoint, the total number of $L \times L$ squares affected would be:
$2(L+1) - 2L - (L-1) \times 2L = 2$ This means that at least two of the possible $L \times L$ squares remain uncovered within the left region.
Furthermore, as $n$ increases beyond $L^2 + 1$ , the number of uncovered $L \times L$ squares also increases.
For $n = L^2 + c$ where $c \geq 1$ , the number of uncovered $L \times L$ squares would be:
$2(L+c) - 2L - (L-1) \times 2L$ which exceeds 2 when $c > 1$ .
Finally, we need to confirm that when $n = (L+1)^2$ , it is possible to arrange a peaceful configuration of rooks such that no $(L+1) \times (L+1)$ empty square appears on the board.

This can be accomplished by generalizing the known solution for $n = 9$ as found in the ISL official solution. The same construction idea applies to all perfect squares.

This post has been edited 1 time. Last edited by math-olympiad-clown, Apr 17, 2025, 3:25 PM

Z K Y