Stay ahead of learning milestones! Enroll in a class over the summer!

G
Topic
First Poster
Last Poster
k a May Highlights and 2025 AoPS Online Class Information
jlacosta   0
May 1, 2025
May is an exciting month! National MATHCOUNTS is the second week of May in Washington D.C. and our Founder, Richard Rusczyk will be presenting a seminar, Preparing Strong Math Students for College and Careers, on May 11th.

Are you interested in working towards MATHCOUNTS and don’t know where to start? We have you covered! If you have taken Prealgebra, then you are ready for MATHCOUNTS/AMC 8 Basics. Already aiming for State or National MATHCOUNTS and harder AMC 8 problems? Then our MATHCOUNTS/AMC 8 Advanced course is for you.

Summer camps are starting next month at the Virtual Campus in math and language arts that are 2 - to 4 - weeks in duration. Spaces are still available - don’t miss your chance to have an enriching summer experience. There are middle and high school competition math camps as well as Math Beasts camps that review key topics coupled with fun explorations covering areas such as graph theory (Math Beasts Camp 6), cryptography (Math Beasts Camp 7-8), and topology (Math Beasts Camp 8-9)!

Be sure to mark your calendars for the following upcoming events:
[list][*]May 9th, 4:30pm PT/7:30pm ET, Casework 2: Overwhelming Evidence — A Text Adventure, a game where participants will work together to navigate the map, solve puzzles, and win! All are welcome.
[*]May 19th, 4:30pm PT/7:30pm ET, What's Next After Beast Academy?, designed for students finishing Beast Academy and ready for Prealgebra 1.
[*]May 20th, 4:00pm PT/7:00pm ET, Mathcamp 2025 Qualifying Quiz Part 1 Math Jam, Problems 1 to 4, join the Canada/USA Mathcamp staff for this exciting Math Jam, where they discuss solutions to Problems 1 to 4 of the 2025 Mathcamp Qualifying Quiz!
[*]May 21st, 4:00pm PT/7:00pm ET, Mathcamp 2025 Qualifying Quiz Part 2 Math Jam, Problems 5 and 6, Canada/USA Mathcamp staff will discuss solutions to Problems 5 and 6 of the 2025 Mathcamp Qualifying Quiz![/list]
Our full course list for upcoming classes is below:
All classes run 7:30pm-8:45pm ET/4:30pm - 5:45pm PT unless otherwise noted.

Introductory: Grades 5-10

Prealgebra 1 Self-Paced

Prealgebra 1
Tuesday, May 13 - Aug 26
Thursday, May 29 - Sep 11
Sunday, Jun 15 - Oct 12
Monday, Jun 30 - Oct 20
Wednesday, Jul 16 - Oct 29

Prealgebra 2 Self-Paced

Prealgebra 2
Wednesday, May 7 - Aug 20
Monday, Jun 2 - Sep 22
Sunday, Jun 29 - Oct 26
Friday, Jul 25 - Nov 21

Introduction to Algebra A Self-Paced

Introduction to Algebra A
Sunday, May 11 - Sep 14 (1:00 - 2:30 pm ET/10:00 - 11:30 am PT)
Wednesday, May 14 - Aug 27
Friday, May 30 - Sep 26
Monday, Jun 2 - Sep 22
Sunday, Jun 15 - Oct 12
Thursday, Jun 26 - Oct 9
Tuesday, Jul 15 - Oct 28

Introduction to Counting & Probability Self-Paced

Introduction to Counting & Probability
Thursday, May 15 - Jul 31
Sunday, Jun 1 - Aug 24
Thursday, Jun 12 - Aug 28
Wednesday, Jul 9 - Sep 24
Sunday, Jul 27 - Oct 19

Introduction to Number Theory
Friday, May 9 - Aug 1
Wednesday, May 21 - Aug 6
Monday, Jun 9 - Aug 25
Sunday, Jun 15 - Sep 14
Tuesday, Jul 15 - Sep 30

Introduction to Algebra B Self-Paced

Introduction to Algebra B
Tuesday, May 6 - Aug 19
Wednesday, Jun 4 - Sep 17
Sunday, Jun 22 - Oct 19
Friday, Jul 18 - Nov 14

Introduction to Geometry
Sunday, May 11 - Nov 9
Tuesday, May 20 - Oct 28
Monday, Jun 16 - Dec 8
Friday, Jun 20 - Jan 9
Sunday, Jun 29 - Jan 11
Monday, Jul 14 - Jan 19

Paradoxes and Infinity
Mon, Tue, Wed, & Thurs, Jul 14 - Jul 16 (meets every day of the week!)

Intermediate: Grades 8-12

Intermediate Algebra
Sunday, Jun 1 - Nov 23
Tuesday, Jun 10 - Nov 18
Wednesday, Jun 25 - Dec 10
Sunday, Jul 13 - Jan 18
Thursday, Jul 24 - Jan 22

Intermediate Counting & Probability
Wednesday, May 21 - Sep 17
Sunday, Jun 22 - Nov 2

Intermediate Number Theory
Sunday, Jun 1 - Aug 24
Wednesday, Jun 18 - Sep 3

Precalculus
Friday, May 16 - Oct 24
Sunday, Jun 1 - Nov 9
Monday, Jun 30 - Dec 8

Advanced: Grades 9-12

Olympiad Geometry
Tuesday, Jun 10 - Aug 26

Calculus
Tuesday, May 27 - Nov 11
Wednesday, Jun 25 - Dec 17

Group Theory
Thursday, Jun 12 - Sep 11

Contest Preparation: Grades 6-12

MATHCOUNTS/AMC 8 Basics
Friday, May 23 - Aug 15
Monday, Jun 2 - Aug 18
Thursday, Jun 12 - Aug 28
Sunday, Jun 22 - Sep 21
Tues & Thurs, Jul 8 - Aug 14 (meets twice a week!)

MATHCOUNTS/AMC 8 Advanced
Sunday, May 11 - Aug 10
Tuesday, May 27 - Aug 12
Wednesday, Jun 11 - Aug 27
Sunday, Jun 22 - Sep 21
Tues & Thurs, Jul 8 - Aug 14 (meets twice a week!)

AMC 10 Problem Series
Friday, May 9 - Aug 1
Sunday, Jun 1 - Aug 24
Thursday, Jun 12 - Aug 28
Tuesday, Jun 17 - Sep 2
Sunday, Jun 22 - Sep 21 (1:00 - 2:30 pm ET/10:00 - 11:30 am PT)
Monday, Jun 23 - Sep 15
Tues & Thurs, Jul 8 - Aug 14 (meets twice a week!)

AMC 10 Final Fives
Sunday, May 11 - Jun 8
Tuesday, May 27 - Jun 17
Monday, Jun 30 - Jul 21

AMC 12 Problem Series
Tuesday, May 27 - Aug 12
Thursday, Jun 12 - Aug 28
Sunday, Jun 22 - Sep 21
Wednesday, Aug 6 - Oct 22

AMC 12 Final Fives
Sunday, May 18 - Jun 15

AIME Problem Series A
Thursday, May 22 - Jul 31

AIME Problem Series B
Sunday, Jun 22 - Sep 21

F=ma Problem Series
Wednesday, Jun 11 - Aug 27

WOOT Programs
Visit the pages linked for full schedule details for each of these programs!


MathWOOT Level 1
MathWOOT Level 2
ChemWOOT
CodeWOOT
PhysicsWOOT

Programming

Introduction to Programming with Python
Thursday, May 22 - Aug 7
Sunday, Jun 15 - Sep 14 (1:00 - 2:30 pm ET/10:00 - 11:30 am PT)
Tuesday, Jun 17 - Sep 2
Monday, Jun 30 - Sep 22

Intermediate Programming with Python
Sunday, Jun 1 - Aug 24
Monday, Jun 30 - Sep 22

USACO Bronze Problem Series
Tuesday, May 13 - Jul 29
Sunday, Jun 22 - Sep 1

Physics

Introduction to Physics
Wednesday, May 21 - Aug 6
Sunday, Jun 15 - Sep 14
Monday, Jun 23 - Sep 15

Physics 1: Mechanics
Thursday, May 22 - Oct 30
Monday, Jun 23 - Dec 15

Relativity
Mon, Tue, Wed & Thurs, Jun 23 - Jun 26 (meets every day of the week!)
0 replies
jlacosta
May 1, 2025
0 replies
angle chasing with 2 midpoints, equal angles given and wanted
parmenides51   4
N a minute ago by Blackbeam999
Source: Ukrainian Geometry Olympiad 2017, IX p1, X p1, XI p1
In the triangle $ABC$, ${{A}_{1}}$ and ${{C}_{1}} $ are the midpoints of sides $BC $ and $AB$ respectively. Point $P$ lies inside the triangle. Let $\angle BP {{C}_{1}} = \angle PCA$. Prove that $\angle BP {{A}_{1}} = \angle PAC $.
4 replies
parmenides51
Dec 11, 2018
Blackbeam999
a minute ago
Determine all the 'good' numbers
April   4
N 3 minutes ago by DottedCaculator
Source: CGMO 2004 P1
We say a positive integer $ n$ is good if there exists a permutation $ a_1, a_2, \ldots, a_n$ of $ 1, 2, \ldots, n$ such that $ k + a_k$ is perfect square for all $ 1\le k\le n$. Determine all the good numbers in the set $ \{11, 13, 15, 17, 19\}$.
4 replies
April
Dec 27, 2008
DottedCaculator
3 minutes ago
Classical factorial number theory
Orestis_Lignos   21
N 10 minutes ago by MIC38
Source: JBMO 2023 Problem 1
Find all pairs $(a,b)$ of positive integers such that $a!+b$ and $b!+a$ are both powers of $5$.

Nikola Velov, North Macedonia
21 replies
Orestis_Lignos
Jun 26, 2023
MIC38
10 minutes ago
m^4+3^m is a perfect square number
Havu   4
N 26 minutes ago by ReticulatedPython
Find a positive integer m such that $m^4+3^m$ is a perfect square number.
4 replies
Havu
an hour ago
ReticulatedPython
26 minutes ago
No more topics!
IMO 2014 Problem 2
v_Enhance   60
N Apr 17, 2025 by math-olympiad-clown
Source: 0
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.
60 replies
v_Enhance
Jul 8, 2014
math-olympiad-clown
Apr 17, 2025
IMO 2014 Problem 2
G H J
Source: 0
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
awesomeming327.
1717 posts
#52
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
#53
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
#54
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
#55
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
#56
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
5606 posts
#57 • 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
#58
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
#59
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
#60
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
#61
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
#62
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
#64
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
119 posts
#65
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
8861 posts
#66
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
30 posts
#67
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
N Quick Reply
G
H
=
a