¿Cuál es el número máximo de guerreros que se pueden poner en un tablero de ajedrez para que no se ataquen dos guerreros?

$505\times 2020=1,\!020,\!100$ciertamente no es óptimo. Al tejar un$2019\times 2020$tablero con un patrón rectangular de la siguiente$3\times 5$rectángulo, puede caber

$$4\times \frac{2019}3\times \frac{2020}{5}=1,\!087,\!568\newcommand{\W}{\mathsf{W}}$$ guerreros en un$2019\times 2020$tablero solo. $$\begin{array}{|c|c|c|c|c|} \hline &&\;\W\;&&\phantom{\Big(\;\;} \\\hline &\;\W\,&&\;\W\;&\phantom{\Big(\;\;\;\,} \\\hline \phantom{\Big(\;\;\;}&&\W&& \\\hline \end{array}$$ Su estrategia logra una densidad de$1/4$guerreros/cuadrado, mientras que el mío tiene una densidad de$4/15$, por lo que este último siempre debería ser mejor para tableros lo suficientemente grandes. No sé si esto se puede mejorar en algo.

---

Dejar$D$ser la densidad de empaque óptima para los guerreros. Además del límite inferior de$D\ge 4/15$, puedo probar el límite superior$D\le 1/3$.

Para cada guerrero, imagina colocar una ficha en el$12$casillas que el guerrero puede atacar. Algunos cuadrados tendrán varias fichas. Sin embargo, puedes demostrar que cada cuadrado tendrá como máximo$6$fichas De hecho, para cualquier cuadrado desocupado$\mathsf X$, si particionamos el$12$cuadrados que pueden atacar$\mathsf X$en$6$pares atacantes como se muestra en esta tabla, (los pares están etiquetados$\mathsf A$a través de$\mathsf F$), entonces vemos que$\mathsf X$puede ser atacado desde como máximo una casilla en cada par.

$$\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}$$

Esto significa que cada guerrero ocupa efectivamente$1+12\times \frac16=3$cuadrados, por lo que no puede tener más de$1/3$guerreros por cuadrado.

Este es solo un resultado de "largo plazo", ya que los guerreros en el límite de una cuadrícula colocarán menos de$12$fichas Sin embargo, este efecto es despreciable a largo plazo.

Si podemos encontrar 3 casillas que se atacan entre sí, entonces podemos colocar como máximo 1 guerrero en estas 3 casillas. Esto es posible, como con:
$(a, b), (a+1, b+3), (a+3, b+1)$y$(a+ 5, b), (a+4, b+3), (a+2, b+1)$.

Ahora con$a = 6k+1, k \in [ 1, 336]$y$b \in [1, 2017]$, podemos cubrir$3 \times 2 \times 336 \times 2017$del$2020^2$cuadrícula. (Verifique que estos cuadrados sean distintos y se encuentren en nuestra cuadrícula).

Estos cuadrados contienen como máximo$2 \times 336 \times 2017$guerreros
Agregando el resto$2020^2 - 3 \times 2 \times 336 \times 2017$cuadrados, obtenemos como máximo 1369552 cuadrados para que estén los guerreros. Esto nos da una densidad de$33.6\% < 40\%$.

---

notas

• Originalmente estaba atrapado mirando 5 ciclos (debido a la relación$\frac{2}{5}$), hasta que vi el límite de densidad de Mike de$\frac{1}{3}$. Esto me llevó a centrarme en 3 ciclos, de ahí la solución anterior.
• Solo necesitamos compensar los casos límite (que son mínimos en una cuadrícula de 2020), de los cuales hay varios enfoques.
• El límite superior de la densidad es$\frac{1}{3}$, que se obtiene fácilmente del enfoque anterior de encontrar 3 ciclos (de una manera densamente empaquetada) y contabilizar la cantidad de celdas sobrantes (~ 3 en cada fila y 1-3 columnas vacías -> por lo tanto, densidad de 0).