such that for all real numbers 
and 
,![\[f(xf(y))+f(y)=f(x+y)+f(xy).\]](http://latex.artofproblemsolving.com/d/2/f/d2ff6ed448cf39e7ec9bce6b944965d5e89b9878.png)
-
,
-
,
for every 
.
is given. Determine the smallest natural number 
,
to tangent 
disjoint from 
on 
and 
.
is tangent to two fixed circles.
of natural numbers such that for every pair of natural numbers 
and 
,![\[
\frac{1}{2} < \frac{\gcd(a_r, a_s)}{\gcd(r, s)} < 2
\]](http://latex.artofproblemsolving.com/1/6/7/167679c1707b957d87311298ea5b72347a9bdc45.png)
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 
be an integer. Consider an 
chessboard consisting of 
unit squares. A configuration of 
rooks on this board is peaceful if every row and every column contains exactly one rook. Find the greatest positive integer 
such that, for each peaceful configuration of rooks, there is a 
square which does not contain a rook on any of its 
unit squares.
be an integer. Consider an 
chessboard consisting of 
unit squares. A configuration of 
rooks on this board is peaceful if every row and every column contains exactly one rook. Find the greatest positive integer 
such that, for each peaceful configuration of rooks, there is a 
square which does not contain a rook on any of its 
unit squares.
where 
.
squares and a 
block above.
rooks yet to place in the 
to 
higher than the column before until we can't do it anymore.
)
s
b
,
.![$k=[\sqrt{n-1}]$](http://latex.artofproblemsolving.com/2/0/6/206f46c05e5562823a62441d48e61a2268d37ab3.png)
.
,
squares 
disjoint from them and from each other. Totally 
sets, by pigeonhole principle one of them does not contain a rook, and it is a square. If 
,
.
,
and put rooks with coordinates 
for 
.
the largest such square has side length 
for the following configuration:
,
,
,
,
,
,
,
,
.
,
(I omit my counterexample for redundancy's sake). Now we show that there exists a 
square in the board. Assume for the sake of contradiction that in each 
such squares, counting each rook at most 
times. Therefore, there must be at least 
rooks, a contradiction. Therefore, 
,
,
;
.
square there is at least one rook. Then there are 
disjoint sets of squares and 
rooks, so the pigeonhole principle tells us that there exists an unoccupied square. Therefore, 
and 
for all 
.
.
,
.
to 
be any group of 
squares, made by the rows in 
,
for 
.
sub-table with 
,
.
.
square for 
.
,
where 
subsquares can be found in this arrangement, so 
.
gives the same upper bound.
Consider some column of 
subsquares. Only 
subsquare. Therefore, a 
with 
and 
with 
.
,
and suddenly understood the square root structure. Everybody can solve this problem by working and a little bit of guessing.
with 
.
and for 
we get that 
and after that we are done.
where 
square. Assume the contrary. Consider any 
horizontal subset of the chessboard which shares the left-most side with the main chessboard and tile it into 
subset which shares the top-left corner with the original chessboard, it must have 
rooks which occupy 
chessboard which has no 
horizontal subset, the rooks are in different rows. More simply, place the origin at the bottom right corner and place rooks on the points 
Drawing a diagram makes this construction obvious.
where 
.
empty columns. These columns must stay empty until last 
.
where in every 
block there is a rook. This will be enough since the asked value is non-decreasing.![\[
(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)
\]](http://latex.artofproblemsolving.com/9/4/8/9487915ade2dbfc7cbb9c089398605580316e207.png)
then there is a 
chessboard consider the column with the rook on its top square. Consider any 
rows excluding the top. By pigeonhole, there are 
has a board that doesn't have a 
of 
first take 
and then for each 
if 
then let 
Otherwise, take 
to be the smallest number that is not one of 
For example, the sequence when 
goes 
t
is to split the board into 
then take 
![$\left[ \sqrt{n-1}\right]$](http://latex.artofproblemsolving.com/7/f/b/7fbbb7a6b6d70fce4e25cd2295d2c5ef9a044087.png)
.
below. This also gives an example for 
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]](http://latex.artofproblemsolving.com/e/5/1/e51cf0c8f289f2fc4b53bc0f8d9eb934dc847588.png)
.
,
for all 
,
. Then, note that there must be at least 
square inside the 
.
.
is increasing (not strict), since if we can fit such a 
,
square, since there are no extra rooks there. Thus, it suffices to show that 
since 
,
.
,
.
.
in this configuration (shown for 
,
, where the red 
(by assumption of the contrary), we can fit a 
in this process that contains no rook (there must have been a first time, since we know that there exists a 
contained a rook, so it must have been in any of the 
orthogonal directions will land you inside 
was 
is not at least 
,
,
Take 
,
,
,
.
square for 
.
for some 
,
square in an 
peaceful configuration. Suppose there was not such an 
squares contained in the top 
sub board. However, we can partition this sub board into 
disjoint 
squares, so one of them must not have a rook in them, absurd. 
with 
that there exists a 
square.
square for 
.
board remaining without any empty 
square. If this board has 
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 
has a peaceful configuration without any empty 
board has a peaceful configuration without any 
square. Give each square coordinates, where the bottom left cell has coordinate 
.
.
and 
to be 
.
.
squares in this configuration also, as desired.
.
rows and exactly 
satisfy 
so by PP there exists 
,
is impossible, simply consider the following generalizable grid
.
such that 
.
,
if and only if there exists a 
,
,
,
.
is a permutation of 
.
.
,
,
.
then 
,![\[(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)\]](http://latex.artofproblemsolving.com/6/e/f/6ef67a3da3e9a432a79c6719627336339501d4ac.png)
Here rook in row 
.
are 
,
for any 
represents the minimal value of 
.
,
square into 
,
squares. Let 
for 
.
if possible, as depicted below.
the greatest positive integer s.t. for each peaceful configuration of 
square which does not contain a rook on any of its 
unit squares:
subsquare of a 
rooks on it, then clearly 
.
,
(the construction for this can be found above). Suppose FTSOC that 
square without a rook. Note that we have 
squares of size 
squares, 
rooks, which is a contradiction. Therefore 
,
disjoint sets in the following way: take 
that 
,
,
arrangements, and they are symmetrical to each other:![\[
\begin{array}{|c|c|}
\hline
\spadesuit & \\ \hline
& \spadesuit \\ \hline
\end{array}
\]](http://latex.artofproblemsolving.com/2/1/8/21807444b0757fdcb13207b4119fffe504cba36e.png)
.
arrangement gives us a new such arrangement.
.
denote the maximal possible 
is nondecreasing, so we will show that 
and 
for each 
grid into 
for 
,
according to position. Then placing a rook at position 
be the row numbers of the other rooks in these 
for 
sum to 
,
and 
for this index 
comes from a double counting estimate of pairs 
where ![\[k = \left\lfloor \sqrt{n-1} \right\rfloor\]](http://latex.artofproblemsolving.com/1/a/3/1a329af047a7141ba51fd5c1b2962a0967407b0d.png)
There is only one key claim we need to prove:
,
empty square.}
.
columns and the top 
potential 
-
of these 
rooks from the 2nd to the 
such squares.![\[2(L+1) - 2L - (L-1) \times 2L = 2\]](http://latex.artofproblemsolving.com/5/a/1/5a1320fd21434142d0ffafc4305a313682f11e72.png)
This means that at least two of the possible 
,
where 
,![\[2(L+c) - 2L - (L-1) \times 2L\]](http://latex.artofproblemsolving.com/6/c/9/6c95902a3b5991da9ac419bb3e99c83bacf7cfbc.png)
which exceeds 2 when 
.
,
empty square appears on the board.
as found in the ISL official solution. The same construction idea applies to all perfect squares.
