Welche Sammlungen von Stücken sind legal?
Nennen Sie eine Sammlung von (weißen und schwarzen) Schachfiguren legal, wenn sie in der Position eines legalen Schachspiels auftreten. Zum Beispiel KQRRBBNNPPPPPPPPkqrrbbnnppppppppist die Sammlung zu Beginn des Spiels. Es scheint, dass jede Teilmenge davon (die immer noch die beiden Könige enthält) ebenfalls möglich ist. Aber manchmal kann man viele Beförderungen haben, so dass zum Beispiel Kkqqqqqqqqmöglich ist, wenn Schwarz alle acht Bauern zu Königinnen befördert, während alle anderen Teile gefangen genommen werden.
Welche Sammlungen von Stücken sind legal?
Diese Antwort auf MathOverflow- Vermutungen / Zustände ohne den Nachweis, dass es sich bei den legalen Sammlungen um solche handelt, die mit den folgenden beiden Operationen aus der Startsammlung abgerufen werden können:
Löschen Sie jedes (Nicht-Königs-) Stück und befördern Sie höchstens einen weißen und höchstens einen schwarzen Bauern.
Löschen Sie einen Bauern und befördern Sie höchstens einen Bauern der gleichen Farbe und höchstens zwei Bauern der entgegengesetzten Farbe.
Ist diese Charakterisierung korrekt?
Antworten
Ja, die Charakterisierung ist korrekt und es gibt insgesamt 58.084.310 legale Sammlungen.
Um voranzukommen, brauchen wir das richtige Maß an Diskurs, um Genauigkeitsverluste zu vermeiden und gleichzeitig zu vermeiden, in Kleinigkeiten einzutauchen.
Notwendigkeit und Hinlänglichkeit der Löschbewegungen
Es wurde vorgeschlagen, dass zwei Arten von Operationen notwendig und ausreichend sind, um alle legalen Sammlungen zu erreichen:
(1) Delete a (non-K) officer & promote at most 1 wP and 1bP
(2) Delete a P & promote at most 1P of that color and at most 2Ps of the other color.
Erstens sind die beiden Kriterien notwendig. Um eine Datei zu entsperren, muss eine Erfassung stattfinden. Durch die Gefangennahme eines Offiziers können beide Bauern aus einer Akte befördert werden. Ein Bauer, der einen Bauern aus einer benachbarten Datei erfasst, ist effizienter, da drei Bauern befördert werden können.
Die Bedingung ist auch ausreichend, wie aus der Aufteilung der Karte in 4 Dateipaare hervorgeht. Wir müssen davon ausgehen, dass die Könige der Aktion aus dem Weg gehen können. Siehe später für ein Beispiel, das die Gültigkeit dieser Annahme untersucht.
"Angebot & Nachfrage"
Vielleicht lohnt es sich, auf die Frage einzugehen, welche Sammlungen auf diese Weise erreichbar sind:
- Zählen Sie die Anzahl der sichtbaren "nicht startenden Offiziere" für jede Seite (Königinnen jenseits der ersten; andere Offiziere jenseits der zweiten dieses Typs): N_w & N_b
- Zählen Sie die Anzahl der "Awol-Bauern" auf jeder Seite: (Bauern, die in NSOs verwandelt wurden, werden nicht gezählt): A_w & A_b
- Zählen Sie die Anzahl der "vermissten Offiziere" für jede Seite (fehlende Königin oder andere Offiziere, die kleiner als die Sekunde dieses Typs sind): M_w & M_b
Dann sind die folgenden eleganten Ungleichheiten zwischen Angebot und Nachfrage notwendig und ausreichende Kriterien für eine legale Sammlung:
M_b + 2*A_b >= N_w - M_w - A_w
M_w + 2*A_w >= N_b - M_b - A_b
Wenn Sie die Begriffe nach Weiß und Schwarz gruppieren, ist die linke Seite das "Angebot", die rechte Seite die "Nachfrage". Das Angebot ist immer nicht negativ. Wenn also die Nachfrage Null oder weniger beträgt, ist es immer zufrieden. Ebenso wird ein Angebot von 8+ jede Nachfrage befriedigen, die auftreten kann.
Hier ist ein Beispiel. Können wir 18 Königinnen auf dem Brett haben? Ja!
N_w = N_b = 8
(because 8 promoted pawns on each side)
A_w = A_b = 0
(every missing pawn was promoted)
M_w = M_b = 6
(all Rs, Bs & Ns were captured)
M_b + 2*A_b >= N_w - M_w - A_w
translates to:
6 + 2*0 >= 8 - 6 - 0
6 >= 2
Das ist also legal. Ähnliches gilt für das Weißangebot für die Schwarznachfrage. Selbst wenn wir die Ritter noch auf dem Brett hätten, also M_b = M_w = 4, wäre die Ungleichung 4> = 4, also immer noch legal.
Neben Kumpel / Patt
Einige fragen sich, ob eine solche Position ohne Partner oder Patt erreicht werden kann, was eine faire Frage ist. Die Antwort ist ja. Es ist wie zu fragen, ob 450 g Cornflakes in eine Schachtel passen. Es ist eine übliche Erfahrung, dass man die Packung einfach schütteln kann und sich die Cornflakes beruhigen. Es sind nicht zu viele Cornflakes in der Box. Obwohl es offensichtlich illegal ist, ist es möglich, die Könige und bis zu 34 (!) Weiße Königinnen auf dem Brett anzuordnen, ohne dass sich ein Kumpel oder eine Pattsituation abzeichnet. Bei dieser Dichte wird es ein bisschen eng, aber dieses Gedankenexperiment zeigt, dass es sich bei nur 18 Königinnen, bei denen außerdem freundliche Königinnen vor feindlichen schützen können, um eine enorme Menge an Spielraum handelt und keine Notwendigkeit besteht, sich um Zwangsverwandte zu sorgen oder Pattsituationen. Selbst mit 18 Königinnen ist das Schachbrett eine sehr leere Schachtel mit Cornflakes :-)
Sammlungen zählen
Konzentrieren wir uns zuerst nur auf die weißen Einheiten. Wie viele legale weiße Sammlungen gibt es? 8,694. Hier ist ein schneller Beweis.
Sei k die Anzahl der sichtbaren Beförderungen von Turm, Ritter oder Bischof (dh Offiziere, die über die ursprüngliche Ergänzung von 2 für einen dieser Typen hinausgehen). (Aus Symmetriegründen werden Königinnen stattdessen in einigen Absätzen behandelt.)
Sei v (k) die Anzahl verschiedener Kombinationen von R, N, B, die dies erreichen.
v(0) = 27:
because there may be 0-2 remaining of each of R,N,B.
For k>0, v(k) = (k^2 + 15*k + 38)/2
e.g.:
v(1) = again 27:
3 ways to pick one of R,N,B to be 3;
& 0-2 possible for each of the other two types.
v(2) = 36:
27 ways to have 4,0-2,0-2;
& 9 ways to have 3,3,0-2.
Dann können die anderen 8-k-Bauern immer noch Ps sein oder in Qs umgewandelt oder gefangen genommen werden.
Sei q die Anzahl der sichtbaren Beförderungen von Königinnen (dh Königinnen, die über die ursprüngliche Ergänzung von 1 hinausgehen).
Sei u_k (q) die Anzahl der verschiedenen kombinatorischen Möglichkeiten, wie wir dies erreichen können (in Bezug auf überlebende Bauern, Königinnen und gefangene Bauern).
u_k(0) = 2*(9-k)
because we can have 0 to 8-k pawns, and the rest are captured,
independently we have 0 or 1 queen.
For q>0, u_k(q) = (9-k-q)
s(k) = sum(q=0,...,8-k) [u_k(q)]
= 2*(9-k) + (8-k) + (7-k) + ... 1
= (9-k)(12-k)/2.
Check:
s(8) = 2: 0-1Q
s(7) = 5: 0P,0-2Q; 1P;0-1Q
...
s(0) = 54: = 55-1
So the total number of of legal White collections is:
sum(k=0...8) [s(k)*v(k)]
= 8,694
Alle diese weißen Sammlungen sind in der Tat erreichbar, z. B. wenn Schwarz nur noch einen bloßen König hat, aber auch in vielen anderen Situationen: Die Ungleichheiten zwischen Angebot und Nachfrage sind nicht sehr anspruchsvoll.
In der nächsten Übung wird für jede Kombination von N_w, M_w, A_w gezählt, wie viele weiße Sammlungen vorhanden sind.
Ich habe die folgende Tabelle mit der Anzahl der Sammlungen berechnet, sortiert nach der Gesamtzahl der Teile auf der Tafel, wie in dieser Tabelle gezeigt:
Dies zeigt für jede Anzahl von Einheiten von 2-32
- v_0: die Anzahl der Basiskandidaten ohne Sorge um Angebot und Nachfrage,
- v_1: die Zahl, die einen einzigen Fehler gegen Angebot-Nachfrage hat,
- v_2: Die Zahl, die einen doppelten Fehler gegen Angebot und Nachfrage hat.
Um Doppelzählungen zu vermeiden, wird die Anzahl der Rechtspositionen als v_1 - 2 * v_2 + v_3 berechnet. Meine Berechnungen stimmen genau mit den früheren Ergebnissen von Kryukov überein .
Beachten Sie, dass es keine Fehler gibt, bis man 25 Einheiten erreicht. Das liegt daran, dass mit 8 Captures alle Kandidaten-Promotion-Sammlungen erreicht werden können.
Eine offene Frage "Extra Credit" (in Arbeit)
Retro-Enthusiasten unterscheiden weiter zwischen der Farbe der Quadrate, auf denen die Bischöfe stehen, da dies eine Invariante ist. Dies hat erhebliche sichtbare Auswirkungen auf die potenzielle Legalität, ist Teil der wesentlichen Klassifizierung für Schachtischplatten und ist auch ein ästhetisches Problem bei der Komposition. Der entsprechende Begriff lautet dann "nicht standardisierte Offiziere" (Königinnen oder "getönte" Bischöfe jenseits des ersten; Türme oder Ritter jenseits des zweiten). Die Anzahl der vermissten Offiziere basiert auf den gleichen 5 Typen. Die Bestimmung, welche zusätzlichen Ungleichheiten notwendig und ausreichend sind, um juristische Sammlungen zu charakterisieren, ist jetzt wesentlich komplizierter.
Der beste Ansatz könnte darin bestehen, zunächst die angepassten Ungleichheiten zwischen Angebot und Nachfrage anzuwenden. Können Sie sich dann fragen, wie viele zusätzliche Bauernfänge erforderlich sind, um bestimmte Bischöfe auf den richtigen Farbton zu bringen?
Eine Bauerneroberung eines Offiziers / Bauern führt zu einer Charge von jeweils 2/3 Bauern, die alle auf denselben Farbfeldern befördert werden. Es scheint jedoch, dass wir für jede solche Charge die Farbe unabhängig wählen können.