7
$\begingroup$

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:
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:
enter image description here
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?

$\endgroup$
11
  • 1
    $\begingroup$ 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. $\endgroup$
    – Calvin Lin
    Sep 24 '21 at 15:59
  • 1
    $\begingroup$ @CalvinLin Yes, my question is regarding B. $\endgroup$
    – Oshawott
    Sep 24 '21 at 16:05
  • 1
    $\begingroup$ 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. $\endgroup$
    – Calvin Lin
    Sep 24 '21 at 16:15
  • $\begingroup$ 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. $\endgroup$
    – Calvin Lin
    Sep 24 '21 at 16:21
  • 1
    $\begingroup$ Notice that the problem decomposes into two separate problems: one for the black squares and one for the red squares. $\endgroup$
    – RobPratt
    Sep 24 '21 at 17:43
6
$\begingroup$

$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.

$\endgroup$
1
  • $\begingroup$ 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$. $\endgroup$
    – Calvin Lin
    Sep 24 '21 at 18:40
0
$\begingroup$

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).
$\endgroup$

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.