What is the largest number of cells that can be marked on a $100 \times 100$ board in such a way that a chess king from any cell attacks no more than two marked ones? (The cell on which a king stands is also considered to be attacked by this king.)
Problem
Source: Russian TST 2017, Day 5 P1 (Group NG)
Tags: board, combinatorics, chess king
GeoKing
01.04.2023 16:06
is 2278 the answer?
GeoKing
03.04.2023 10:40
I would like to thank Rohan Garg for providing the problem given in motivation and edfearay123 for providing very nice sol.
Problem:- Let $Q$ be a $(2n+1) \times (2n+1)$ board. Some of its cells are colored black in such a way that every $2 \times 2$ board of $Q$ has at most $2$ black cells. Find the maximum amount of black cells that the board may have.
Solution:-
Note that we can replace $100 \cdot 100$ grid by $(3n+1) \cdot (3n+1)$ grid and note that the above problem is same as. Problem:-Consider a $(3n+1) \cdot (3n+1)$ grid. There are atmost $2$ marked cells in every $3 \cdot 3$ subsquare.Find the largest number of marked cells. Solution Using the same idea as given in motivation we tile the board as follows. Note that There are $n^2$ tiles of form $3\cdot 3$. There are $n$ tiles of $L-$shape and there are $(n+1)$ squares of form $1 \cdot 1$. Note that $L$ shaped tile and $3.3$ tile each can have atmost $2$ marked cells while tile of form $1.1$ can have atmost 1 marked cell. So we have atmost $2 \cdot (n^2)+ 2 \cdot (n)+1 \cdot (n+1)=(2n +1)(n+1)$ marked cells. The following construction works for $(2n +1)(n+1)$ marked cells. Substituting $n=33$ gives $2278$ as ans for $100 \cdot 100$ grid so we are done.