Wie viele Krieger kann man maximal auf ein Schachbrett stellen, damit sich nicht zwei Krieger gegenseitig angreifen?

$505\times 2020=1,\!020,\!100$ist sicher nicht optimal. Durch Fliesen a$2019\times 2020$Brett mit einem rechteckigen Muster der folgenden$3\times 5$Rechteck, können Sie passen

$$4\times \frac{2019}3\times \frac{2020}{5}=1,\!087,\!568\newcommand{\W}{\mathsf{W}}$$ Krieger auf a$2019\times 2020$allein an Bord. $$\begin{array}{|c|c|c|c|c|} \hline &&\;\W\;&&\phantom{\Big(\;\;} \\\hline &\;\W\,&&\;\W\;&\phantom{\Big(\;\;\;\,} \\\hline \phantom{\Big(\;\;\;}&&\W&& \\\hline \end{array}$$ Ihre Strategie erreicht eine Dichte von$1/4$Krieger/Quadrat, während meins eine Dichte von hat$4/15$, also sollte letzteres für ausreichend große Boards immer besser sein. Ich weiß nicht, ob man das überhaupt verbessern kann.

---

Lassen$D$die optimale Packungsdichte für Krieger sein. Neben der Untergrenze von$D\ge 4/15$, kann ich die obere Schranke beweisen$D\le 1/3$.

Stellen Sie sich vor, Sie legen für jeden Krieger einen Spielstein darauf$12$Felder, die der Krieger angreifen kann. Einige Quadrate haben mehrere Token. Sie können jedoch zeigen, dass jedes Quadrat höchstens haben wird$6$Token. In der Tat für jedes unbesetzte Feld$\mathsf X$, wenn wir die partitionieren$12$Felder, die angreifen können$\mathsf X$hinein$6$Angriffspaare, wie in dieser Tabelle gezeigt, (Paare sind gekennzeichnet$\mathsf A$durch$\mathsf F$), dann sehen wir das$\mathsf X$kann von höchstens einem Feld in jedem Paar aus angegriffen werden.

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

Dies bedeutet, dass jeder Krieger effektiv besetzt ist$1+12\times \frac16=3$Quadrate, also kannst du nicht mehr als haben$1/3$Krieger pro Quadrat.

Dies ist nur ein "langfristiges" Ergebnis, da Krieger an der Grenze eines Rasters weniger als platzieren werden$12$Token. Dieser Effekt ist jedoch langfristig vernachlässigbar.

Wenn wir 3 Felder finden, die sich gegenseitig angreifen, können wir höchstens 1 Krieger auf diesen 3 Feldern platzieren. Dies ist möglich, wie mit:
$(a, b), (a+1, b+3), (a+3, b+1)$Und$(a+ 5, b), (a+4, b+3), (a+2, b+1)$.

Jetzt mit$a = 6k+1, k \in [ 1, 336]$Und$b \in [1, 2017]$, können wir abdecken$3 \times 2 \times 336 \times 2017$des$2020^2$Quadrate. (Vergewissern Sie sich, dass diese Quadrate verschieden sind und in unserem Raster liegen.)

Diese Quadrate enthalten höchstens$2 \times 336 \times 2017$Krieger.
Fügen Sie den Rest hinzu$2020^2 - 3 \times 2 \times 336 \times 2017$Quadrate erhalten wir höchstens 1369552 Quadrate für Krieger. Dies gibt uns eine Dichte von$33.6\% < 40\%$.

---

Anmerkungen

• Ich war ursprünglich damit beschäftigt, 5 Zyklen zu betrachten (wegen des Verhältnisses$\frac{2}{5}$), bis ich Mikes Dichtegrenze sah$\frac{1}{3}$. Dies führte dazu, dass ich mich auf 3 Zyklen konzentrierte, daher die obige Lösung.
• Wir müssen nur die Grenzfälle (die in einem 2020-Raster minimal sind) aufholen, von denen es mehrere Ansätze gibt.
• Die Obergrenze für die Dichte ist$\frac{1}{3}$, die sich leicht aus dem obigen Ansatz ergibt, 3 Zyklen (auf dicht gepackte Weise) zu finden und die Anzahl der übrig gebliebenen Zellen zu berücksichtigen (~ 3 in jeder Zeile und 1-3 leere Spalten -> daher Dichte von 0).