I having problem to solve the below question:
Given $2020\times 2020$ chessboard, what is the maximum number of warriors you can put on its cells such that no two warriors attack each other.
Warrior is a special chess piece which can move either:
- $3$ steps forward and one step sideways in any direction, or
- $2$ steps forward and $2$ steps sideways in any direction.
Answer Given: 2020 *505
Got Solution from one friend:
Strategy: Put the warriors in $(4k+1)$ columns.
Proof 1)We can easily notice that warriors can't attack warriors in his own column. So we can arrange the warriors in the above mentioned arrangement.
2) The warriors of $(4k+1)$column can attack warriors of $4k,4k-1,4k-2$ columns . So we can't put the warriors in those cells.
So the maximum number of warriors that can be put is $2020 \times 505$
Best Answer
A configuration that yields a better fill than the 1/4 of the given answer:
Rectangles of 5x6 that have 8 squares with a "warrior", yielding a 8/30 fill:
Blue = warrior Yellow = empty
2020 is not exactly divided by 6 so you'll have space on one side filled partially so the exact fill value is not 8/30 - but slightly more!
The 2020 x 2016 can be filled with $8 / 15 - 1 / 4 = 1 / 60$ more warriors than the simple solution and the remaining 2020 x 4 can be filled with $11 / 40 - 1 / 4 = 1 / 40$ more warriors, resulting in:
$2020 * 2016 / 60 + 2020 * 4 / 40 = 68074$ more warriors than the simple pattern.
simple pattern: $2020 * 505 = 1020100$
pattern above: $1020100 + 68074 = 1088174$
Variant problem
Addition for the problem variant, where the warriors can face any of 4 directions and they attack only 4 cells forward (the ones numbered 2,3,4,5 in the image)
$$ \begin{array}{|c|c|c|c|c|c|c|c|c|} \hline &&& &&& &&\\ \hline &&&4 &&3& && \\ \hline &&5& &&& 2&& \\ \hline &6&& &&& &1& \\ \hline &&& &0&& && \\ \hline &7&& &&& &12& \\ \hline &&8& &&& 11& \\ \hline &&& 9&&10& & \\ \hline &&& &&& & \\ \hline \end{array} $$
The best fill I could find is 1/2 (8 cells out of 16 in a 4x4 pattern). The arrows show which direction the warriors should be facing: