3
$\begingroup$

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$

$\endgroup$
  • $\begingroup$ Every fourth row can be filled with warriors and none would attack each other. This gives the $2020\times 505$ which is the given answer. You just need to prove there is not a better configuration. $\endgroup$ – InterstellarProbe Apr 2 at 18:31
  • 1
    $\begingroup$ I am confused now. Why can't we fill the warriors every third row? Under the given rule, if they are all facing the same way, then they are not attacking each other, right? So you can do this with $2020\times\left\lceil\frac{2020}{3}\right\rceil$ warriors. Can the pieces turn left/right to attack one another? $\endgroup$ – Batominovski Apr 2 at 18:43
  • $\begingroup$ In chess, the only piece that has a facing is the pawn. No other piece does. Unless you specify that a piece has a facing, it is not clear that it does. So, if "forward" is relative, then in the middle of the board, a warrior is attacking $12$ squares, not $2$ as your diagram shows. If warriors have a facing, you should include that in their description. $\endgroup$ – InterstellarProbe Apr 2 at 18:49
  • 1
    $\begingroup$ If you cannot change the question, then you must make an assumption. If the problem does not specify, then you can choose that warriors do not have a facing, "forward" is relative, and a warrior can attack at most $12$ squares. Or you can choose that warriors do have a facing, and a warrior can attack at most $4$ squares. $\endgroup$ – InterstellarProbe Apr 2 at 18:52
  • 1
    $\begingroup$ Which of the numbered squares can the warrior at $0$ attack, assuming that the warrior is currently facing upwards? $$\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}$$ Is the answer just the four squares $2,3,4,5$, or all of the twelve numbered squares? $\endgroup$ – Batominovski Apr 2 at 18:53
4
$\begingroup$

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

enter image description here

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:

enter image description here

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ If each warrior has a facing (see the discussion under the question), do you think you can find a better configuration than the $1/3$ fill I gave in one of my comments? I think you can split this part into two different questions: (1) all must face the same way, and (2) each can choose its own facing. If you can find a better configuration, please write another answer, so I can upvote again. Cheers! $\endgroup$ – Batominovski Apr 2 at 22:15
  • $\begingroup$ I believe that in scenario (1), my 1/3 fill configuration is optimal or very close to optimal. However, I think there are better configurations in scenario (2). $\endgroup$ – Batominovski Apr 2 at 22:20
  • $\begingroup$ @WETutorialSchool possibly yes. It would also depend what facing means. Do we define the attack squares to be 2,3,4,5 as in your comment or 1,2,3,4,5,6 or etc... $\endgroup$ – ypercubeᵀᴹ Apr 2 at 22:20
  • $\begingroup$ I think according to the OP's wording, if the warrior at $0$ is facing upwards, it can only attack $2,3,4,5$. $\endgroup$ – Batominovski Apr 2 at 22:21
  • 1
    $\begingroup$ @WETutorialSchool simpler pattern with 1/2 fill: 1st row facing UP, 2nd row facing DOWN, 3-4t rows.empty, repeat. ;) $\endgroup$ – ypercubeᵀᴹ Apr 6 at 17:52

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.