A short-sighted rook is a rook that beats all squares in the same column and in the same row for which he can not go more than $60$-steps. What is the maximal amount of short-sighted rooks that don't beat each other that can be put on a $100\times 100$ chessboard.
Problem
Source: Saint Petersburg MO 2020 Grade 11 Problem 2
Tags: combinatorics
SpecialBeing2017
25.05.2020 05:09
I got $178$ for this one. I'm not very sure tho.
we call the central $22$ columns(rows) middle columns(rows)
and the rest $78$ columns(rows) outside columns(rows)
for a column or grid, we call the central $22$grids middle grids, and the rest $78$ grids outside grids.
Observation 1 in each column(row), there are at most two rooks.
Observation 2 if a column(row) has two rooks, then these $100-2\times(100-61)=22$ middle grids are empty.
Now, if there are at least $179$ rooks, then at least $79$ columns that has two rooks.
Thus, At least $1$ of these middle columns has two rooks.
Thus, the two rooks in this column are in the [middle grids] of the two rows they are in, and that two rows both only has one rook.
Also, note that there are at least $79$ rows that has two rooks, and two of the $78$ outside rows have only one rook in each.
Thus, At least $3$ of these middle rows have two rooks.
Thus, the two rooks in each of these rows are in the [middle grids] of the two columns they are in, and that two columns both only has one rook.
Also, note that there are at least $79$ columns that has two rooks, and $2\times 3=6$ of the $78$ outside columns have only one rook in each.
Thus, At least $7$ of these middle columns have two rooks.
...
By induction, there will be too many middle columns/rows have two rooks, which is impossible.
I wish my solution works. Please point out my mistake if there is any.
CANBANKAN
12.11.2020 02:41
SpecialBeing's bounding argument and answer are correct. Here is an alternate solution. Let $(x,y)$ denote the cell on the $yth$ row and the $xth$ column. Construction: $(x,x)$ for $1\le x\le 100$ and $(x,x+61)$ for $1\le x \le 39$. Bound: Look at the first 61 rows. There may be at most $100$ rooks there since there are $100$ columns and each column may have at most one rook. The last 39 rows can have at most 78 rooks because each row can have two rooks, achieving a bound of 178, so we're done.