# What is the maximum number of warriors one can put on a chess board so that no two warriors attack each other?

In chess, a normal knight goes two steps forward and one step to the side, in some orientation. Thanic thought that he should spice the game up a bit, so he introduced a new kind of piece called a warrior. A warrior can either go three steps forward and one step to the side, or two steps forward and two steps to the side in some orientation.
Given a $$2020\times2020$$ chess board. Find, with proof, the maximum number of warriors one can put on its cells such that no two warriors attack each other.

The question is a modified version of a problem from Bangladesh Mathematical Olympiad 2019. For more clarity, here is a picture that shows example moves of a warrior:

This is my first time solving this kind of problem. I've made the following progress in solving the question:

We place the warriors in each cell of $$n$$-th column where $$n\equiv1\ (\bmod 4)$$. The following picture shows this strategy in an $$8\times8$$ board:

It can be seen that no two warriors can attack each other. Hence, the answer to our original problem should be $$2020\times505$$.

Though this result matches with the original answer, I have still some confusions. Firstly, the optimal strategy is that in the $$2020\times2020$$ board, we place a warrior in each cell of $$n$$-th column. But what if we don't place them with that strategy or we just randomly place the warriors so that they cannot attack each other? How will I know other strategies would not give a result greater than $$2020\times 505$$? More specifically, how do I write a formal proof for this kind of problems?

• Regarding your confusion, just because you have the numerical value, doesn't mean that your proof is correct. Like you realized, for a complete solution, you also need to show that "no other strategies will give a larger number". Similar to when we want to show something is a maximum, we need to show A) It can be achieved (which you have done) and B) No larger value can be achieved. Sep 24 '21 at 15:59
• @CalvinLin Yes, my question is regarding B. Sep 24 '21 at 16:05
• Note that the actual BDMO question doesn't ask to find the exact maximum, but asks to show that the maximum is $\leq \frac{2}{5} \times 2020 \times 2020$ Source - BdMO 2019 Higher Secondary Qn 10. This greatly changes how one can approach the question. Sep 24 '21 at 16:15
• In your post, you stated "This question is from Bangladesh Mathematical Olympiad 2020.", but not that you modified it (so strictly speaking, it isn't from there). $\quad$ While I haven't seen the solution, I don't think this is "a bit modified". I suspect that to find the actual maximum, it will involve a lot more machinery. Please go to the actual source when you can. Even your link states the actual problem in the second post. Sep 24 '21 at 16:21
• Notice that the problem decomposes into two separate problems: one for the black squares and one for the red squares. Sep 24 '21 at 17:43

$$505\times 2020=1,\!020,\!100$$ is certainly not optimal. By tiling a $$2019\times 2020$$ board with a rectangular pattern of the following $$3\times 5$$ rectangle, you can fit $$4\times \frac{2019}3\times \frac{2020}{5}=1,\!087,\!568\newcommand{\W}{\mathsf{W}}$$ warriors onto a $$2019\times 2020$$ board alone. $$\begin{array}{|c|c|c|c|c|} \hline &&\;\W\;&&\phantom{\Big(\;\;} \\\hline &\;\W\,&&\;\W\;&\phantom{\Big(\;\;\;\,} \\\hline \phantom{\Big(\;\;\;}&&\W&& \\\hline \end{array}$$ You strategy achieves a density of $$1/4$$ warriors/square, while mine has a density of $$4/15$$, so the latter should always be better for large enough boards. I do not know if this can be improved at all.

Let $$D$$ be the optimal packing density for warriors. In addition to the lower bound of $$D\ge 4/15$$, I can prove the upper bound $$D\le 1/3$$.

For each warrior, imagine placing a token on the $$12$$ squares that the warrior can attack. Some squares will have multiple tokens. However, you can show that every square will have at most $$6$$ tokens. Indeed, for any unoccupied square $$\mathsf X$$, if we partition the $$12$$ squares that can attack $$\mathsf X$$ into $$6$$ attacking pairs as shown in this table, (pairs are labeled $$\mathsf A$$ through $$\mathsf F$$), then we see that $$\mathsf X$$ can be attacked from at most one square in each pair. $$\begin{array}{|c|c|c|c|c|c|c|} \hline & &\mathsf C& &\mathsf D& & \\\hline &\mathsf B& & & &\mathsf C& \\\hline \mathsf A& & & & & &\mathsf D \\\hline & & &\mathsf X& & & \\\hline \mathsf B& & & & & &\mathsf E \\\hline &\mathsf A& & & &\mathsf F& \\\hline & &\mathsf F& &\mathsf E& & \\\hline \end{array}$$

This means that each warrior effectively occupies $$1+12\times \frac16=3$$ squares, so you can have no more than $$1/3$$ warriors per square.

This is only a "long-run" result, since warriors at the boundary of a grid will place fewer than $$12$$ tokens. However, this effect is negligible in the long run.

• With your idea, we can show that the inner $2014 \times 2014$ grid has at most $1/3 \times 2020^2$ warriors. Adding on at most $2020^2 - 2014^2$ warriors on the remaining border, that's still less than $2/5 \times 2020^2$. Sep 24 '21 at 18:40

If we can find 3 squares that attack each other, then we can place at most 1 warrior on these 3 squares. This is possible, like with:
$$(a, b), (a+1, b+3), (a+3, b+1)$$ and $$(a+ 5, b), (a+4, b+3), (a+2, b+1)$$.

Now, with $$a = 6k+1, k \in [ 1, 336]$$ and $$b \in [1, 2017]$$, we can cover $$3 \times 2 \times 336 \times 2017$$ of the $$2020^2$$ squares. (Verify that these squares are distinct, and lie in our grid.)

These squares contain at most $$2 \times 336 \times 2017$$ warriors.
Addining on the remaining $$2020^2 - 3 \times 2 \times 336 \times 2017$$ squares, we get at most 1369552 squares for warriors to be on. This gives us a density of $$33.6\% < 40\%$$.

Notes

• I originally was caught up looking at 5-cycles (because of the ratio $$\frac{2}{5}$$), till I saw Mike's density bound of $$\frac{1}{3}$$. This led me to focus on 3-cycles, hence the above solution.
• We just need to make up for the boundary cases (which is minimal in a 2020 grid), of which there are several approaches.
• The upper bound on density is $$\frac{1}{3}$$, which is easily obtained from the above approach of finding 3 cycles (in an densely packed manner) and accounting for the number of leftover cells (~3 in each row and 1-3 empty columns -> hence density of 0).