Beweis einer Lösung für das $ N $ -Zecken-Puzzle

Question

Angesichts eines $ N $ x $ N $ Board, nehmen Sie an, dass $ N \ GEQ 5 $ und diese $ N $ ist nicht mit $ 2 $ oder 3 $ $ . Beweisen Sie, dass die folgende Positionierung von $ N $ queens $ q_0, q_2, ..., q_ {n-1} $ funktioniert, dh nein zwei königern bedroht einander:

für $ 0 \ LEQ I \ LEQ N-1 $ Wir positionieren die Königin $ q_i $ auf Das Feld $ (I, 2i \ text {} \ pmod n) $ .

Hier verwenden wir den ( $ x $ -coordinate, $ y $ -coordinate) Koordinatensystem, wobei $ x $ die horizontale Position beschreibt, und $ y $ die vertikale. Beispielsweise wäre in der obigen Formel $ x $ $ i $ und $ y $ wäre $ 2i \ pmod n $ .

Meine Idee war, sich durch Widerspruch zu erweisen und jeden Fall aufzubrechen, wie sich die Königinnen aufstellen, um sich nicht (horizontal, vertikal und diagonal) nicht bedrohen, aber ich kann nicht sehen, was folgt. Kann jemand ihre Gedanken anbieten oder mich in die richtige Richtung zeigen?

Answer 1

senkrecht: wenn $ q_i $ und $ q_j $ dieselbe $ x $ -coordinate, $ i= J $ also sind sie die gleiche Königin.

horizontal: Wenn $ q_i $ und $ q_j $ dieselbe $ y $ -coordinate, $ 2i= 2j \ pmod n $ , so $ 2i= 2J + KN $ für einige $ k \ in \ mathbb {z} $ ; Da $ N $ nicht um 2 teilbar ist, $ K $ muss sein, und wir haben $ i= j + (2k ') n $ , so $ i= j \ pmod n $ . Da sowohl $ I $ und $ J $ $ \ Le N $ , sie sind gleich.

diagonal: Wir haben zwei Fälle: Die Diagonalen parallel zu $ (0, 0) \ bis (1, 1) $ und die 'Antidiagonals'. Erster Fall: Wenn $ i - 2i= J - 2J \ PMOD N $ , $ - i= -j \ pmod n $ , so $ i= j \ pmod n $ . Zweiter Fall: Wenn $ i + 2i= J + 2J \ PMOD N $ , so $ 3i= 3j + kN $ < / span> für einige $ k \ in \ mathbb {z} $ ; Da $ n $ nicht um 3 teilbar ist, $ K $ muss sein, und wir haben $ i= j + (3k ') n $ , so $ i= j \ pmod n $ .

Answer 2

Erwägen Sie, $ i zwischen 0 und $ n-1 $ . Natürlich kann die erste Koordinate nicht für zwei Königinnen gleich sein, daher sind sie nicht in derselben Reihe.

Nun, angenommen, für Widerspruchs willen liegen sie in derselben Spalte. Dann $ 2 (I-J)= NK $ für einige natürliche $ K $ . Nun, da n 2 nicht als Divisor enthält, $ K $ muss sogar sein. Also, entweder $ K $ ist 0, was nicht möglich ist, da dies der Annahme widerspricht, dass $ i $ und $ J $ sind nicht gleich oder $ k \ geq 2 $ . Im letzteren Fall, $ lhs= 2 (ij) <2 (n-1) <2n \ leq nk $ , und daher $ Lhs \ ne rhs $ . Daher schließen wir, dass unsere Annahme falsch gewesen sein muss, und zwei auf diese Weise positionierte Königinnen können nicht in derselben Spalte liegen.

Sie müssen den diagonalen Fall noch herausfinden.

Answer 3

für den diagonalen Fall, auf zwei Beweise aufgeteilt - eines für jede "Rotation" der Diagonallinie.

Wenn die diagonale Linie "von oben links nach rechts unten ist" ist, nehmen Sie dann den Widerspruchs willen an, wir haben zwei Königinnen $ i, J $ . Dann, damit sie auf derselben Diagonallinie liegen, muss es einige $ K $ , wobei $ i + k= J $ und $ 2i \ pmod n + k= 2j \ pmod n $ . Sowohl sowohl $ K= JI $ und $ k= 2 (ji) \ pmod n $ .

Daher muss es eine ganze Reihe von $ D $ mit $ k= 2 (ji) + dn $ < / span>. Ersatz $ k= ji $ und erhalten Sie $ ij= dn $ und daher $ ij= 0 \ pmod n $ . Aber beide $ 0 \ le i, j \ le n-1 $ , also müssen wir $ i= j $ Und deshalb haben wir einen Widerspruch.

Die andere "Rotation" der Diagonallinie verwendet dieselbe Idee.