Calea calului

Un curs de cai deschis pe o tablă de șah.

Animația unui curs de cai pe o tablă de șah 5x5.

Graficul pentru cai prezintă toate căile posibile pentru o cale pentru cai pe o tablă de șah standard 8x8. Numerele de pe fiecare nod indică numărul de mișcări posibile care pot fi făcute din acea poziție.

Calea calului rezolvată de turc , o falsă mașină de jucat șah. Această soluție specială este închisă (circulară) și poate fi completată de orice punct de pe marginea plăcii.

Calea calului este o problemă matematică referitoare la mișcarea unui cal pe o tablă de șah . Cavalerul este așezat pe scândura goală și, deplasându-se conform regulilor șahului , trebuie să ocupe fiecare pătrat exact o dată. Calea unui cal se spune că este „închisă” dacă ultima casă pe care este poziționat calul este aproape de casa din care a pornit, astfel încât calul, din poziția finală, să poată finaliza din nou aceeași cale (de exemplu, dacă cavalerul începe pe d8 și își termină cursul pe f7). Altfel calea calului se numește „deschisă”. Numărul exact al posibilelor trasee deschise de cai este încă necunoscut. Variațiile problemei traseului calului prevăd tabele de șah de diferite dimensiuni față de clasicul 8x8 și, de asemenea, de formă dreptunghiulară.

Teorie

Problema traseului calului este un exemplu al „problemei traseului hamiltonian ” mai general în teoria graficelor . În mod similar, găsirea unei căi închise a calului este un exemplu al „problemei ciclului hamiltonian”. Rețineți, totuși, că, spre deosebire de problema generală a traseului hamiltonian, problema traseului calului poate fi rezolvată în timp liniar . ^[1]

Trasee închise

Pe o tablă de șah 8x8, există exact 26.534.728.821.064 căi „directe” închise (două căi de-a lungul aceleiași căi care merg în direcții opuse sunt numărate separat, fiind rotații și reflexii). ^[2] ^[3] ^[4] Numărul căilor „indirecte” închise este jumătate din acest număr, deoarece fiecare cale poate fi trasată invers. Există 9.862 căi închise indirecte pe o placă de 6x6. ^[5] Nu există căi închise pentru plăci mai mici, cu excepția cazului 1x1 (acesta este un corolar al teoremei următoare).

Teorema lui Schwenk

Pentru orice tabla de șah m × n , cu m ≤ n , calea unui cavaler închis este întotdeauna posibilă, cu excepția cazului în care sunt îndeplinite una sau mai multe dintre următoarele condiții:

m și n sunt ambele impare; m și n sunt ambele diferite de 1
m = 1, 2 sau 4; m și n sunt ambele diferite 1
m = 3 și n = 4, 6 sau 8.

Starea 1

Condiția 1 împiedică existența unor căi închise din cauza unei chestiuni de paritate și culoare. Într-o tablă de șah standard cu pătrate alb-negru, cavalerul va trebui neapărat să se deplaseze atât de la un pătrat alb la unul negru, cât și de la un pătrat negru la unul alb. Prin urmare, într-un curs închis, calul trebuie să viziteze același număr de case albe și negre, iar numărul total de case vizitate trebuie să fie, prin urmare, egal. Cu toate acestea, dacă m și n sunt ambele impare, numărul total de pătrate de pe tablă (adică produsul m × n ) este impar (de exemplu, într-o tablă de șah 5x5 există 13 pătrate de o culoare și 12 de altă culoare), de aceea nu poate exista o cale închisă. Pot exista în schimb căi deschise (cu singura excepție a cazului 1x1).

Starea 2

Condiția 2 afirmă că, dacă latura mai scurtă are 1, 2 sau 4 case, atunci nu sunt posibile căi închise.

Când m = 1 sau 2, nu este posibilă nicio cale închisă, deoarece calul nu ar putea ajunge la fiecare pătrat (din nou, cu excepția cazului 1x1). Se poate verifica, folosind culori, că nici măcar o tablă de șah 4 × n nu poate avea o cale închisă.

Calul trebuie să alterneze între case verzi și roșii.

Să începem prin a presupune că o tablă de șah 4 × n are calea unui cavaler. Lasa-i sa fie $A_{1}$ ${\ displaystyle A_ {1}}$ $A_1$ ansamblul caselor care ar fi negre e $A_{2}$ ${\ displaystyle A_ {2}}$ $A_2$ setul de pătrate care ar fi albe, dacă ar fi colorate după modelul tablelor de damă alb-negru. Să luăm în considerare figura din dreapta. Lasa-i sa fie $B_{1}$ ${\ displaystyle B_ {1}}$ $B_ {1}$ setul de case verzi e $B_{2}$ ${\ displaystyle B_ {2}}$ $B_2$ ansamblul caselor roșii. Există același număr de case verzi și case roșii. Observăm că, începând de la o casă din $B_{1}$ ${\ displaystyle B_ {1}}$ $B_ {1}$ , calul va trebui să sară pe o casă din $B_{2}$ ${\ displaystyle B_ {2}}$ $B_2$ . Și, întrucât calul va trebui să viziteze fiecare casă o dată, când va intra $B_{2}$ ${\ displaystyle B_ {2}}$ $B_2$ atunci trebuie să se poată muta într-o casă din $B_{1}$ ${\ displaystyle B_ {1}}$ $B_ {1}$ (altfel calul va trebui apoi să treacă peste două case în $B_{1}$ ${\ displaystyle B_ {1}}$ $B_ {1}$ ).

Dacă am urma calea ipotetică a calului, am găsi o contradicție.

Prima casă la care va merge calul va fi o casă $A_{1}$ ${\ displaystyle A_ {1}}$ $A_1$ Și $B_{1}$ ${\ displaystyle B_ {1}}$ $B_ {1}$ . Dacă nu, schimbați definițiile $B_{1}$ ${\ displaystyle B_ {1}}$ $B_ {1}$ Și $B_{2}$ ${\ displaystyle B_ {2}}$ $B_2$ pentru ca acest lucru să fie adevărat.
Al doilea va trebui să fie o casă de $A_{2}$ ${\ displaystyle A_ {2}}$ $A_2$ Și $B_{2}$ ${\ displaystyle B_ {2}}$ $B_2$ .
Al treilea va trebui să fie o casă de $A_{1}$ ${\ displaystyle A_ {1}}$ $A_1$ Și $B_{1}$ ${\ displaystyle B_ {1}}$ $B_ {1}$ .
Al patrulea va trebui să fie o casă de $A_{2}$ ${\ displaystyle A_ {2}}$ $A_2$ Și $B_{2}$ ${\ displaystyle B_ {2}}$ $B_2$ .
Si asa mai departe.

Rezultă că $A_{1}$ ${\ displaystyle A_ {1}}$ $A_1$ are aceleași case ca $B_{1}$ ${\ displaystyle B_ {1}}$ $B_ {1}$ , Și $A_{2}$ ${\ displaystyle A_ {2}}$ $A_2$ are aceleași case ca $B_{2}$ ${\ displaystyle B_ {2}}$ $B_2$ . Dar acest lucru nu este în mod evident adevărat, deoarece pătratele roșii și verzi prezentate mai sus nu sunt la fel ca într-un model de tablă de șah; setul de case roșii nu este același cu setul de case negre (sau albe, de altfel).

Prin urmare, ipoteza noastră de mai sus a fost falsă și, prin urmare, nu există o cale închisă pentru nici o tablă de șah 4 × n , pentru nici un n .

Starea 3

Condiția 3 poate fi încercată prin încercare și eroare: în construirea unei căi închise pe o tablă de șah 3x4, 3x6 sau 3x8, am descoperi că acest lucru este imposibil. Se poate arăta, prin inducție (cu un model repetat), că o tablă de șah de 3 × n , cu n par și mai mare de 8, are, dimpotrivă, căi închise.

Toate celelalte cazuri

Cu toate acestea, demonstrarea celor trei condiții anterioare nu este suficientă pentru a demonstra teorema în întregime. De fapt, nu a fost încă demonstrat faptul că toate șahurile dreptunghiulare care nu îndeplinesc cele trei condiții enumerate mai sus au trasee de cai închise. ^[6]

Notă

^ A. Conrad, T. Hindrichs, H. Morsy și I. Wegener, Soluția Knight's Hamiltonian Path Problem on Chessboards , în Discrete Applied Mathematics , vol. 50, nr. 2, 1994, pp. 125–134, DOI : 10.1016 / 0166-218X (92) 00170-Q .
^ Martin Loebbing; Ingo Wegener, Numărul de tururi ale cavalerului este egal cu 33.439.123.484.294 - Numărarea cu diagrame de decizie binare , în Jurnalul electronic de combinatorie , vol. 3, nr. 1, 1996, pp. R5. Observație: Autorii au recunoscut ulterior că numărul anunțat este incorect. Conform raportului lui McKay, numărul corect este 13.267.364.410.532 și acest număr este repetat în cartea lui Wegener din 2000.
^ Brendan McKay , Knight's Tours on a 8x8 Chessboard ( ps ), in Technical Report TR-CS-97-03 , Department of Computer Science, Australian National University, 1997 (arhivat din original la 27 ianuarie 2012) .
^ Wegener, I., Branching Programs and Binary Decision Diagrams , Society for Industrial & Applied Mathematics, 2000, ISBN 0-89871-458-3 .
^ (EN) Eric W. Weisstein, Knight's Tour în MathWorld Wolfram Research.
^ John J. Watkins, Across the Board: the Mathematics of Chessboard Problems , Princeton University Press, 2004, ISBN 0-691-11503-6 .

Bibliografie

( EN ) Martin Gardner , Cavalerul Mesei Pătrate , în Mathematical Magic Show , 1990, pp. 188-203.
(EN) Richard W. Henderson, Eugene Roger Apodaca, A Knight of Egodeth: Zen raptured Quietude, 2008, ISBN 978-0-9797630-0-7 .

Elemente conexe

George Koltanowski

Alte proiecte

Wikimedia Commons conține imagini sau alte fișiere despre calea calului

linkuri externe

(EN) Regula Warnsdorff , de la warnsdorff.com.
Dan Thomasson, (EN) The Knight's Tour
Secvența A001230 din Enciclopedia on-line a secvențelor întregi
Ira Pohl, ( EN ) O metodă pentru găsirea căilor Hamilton și a turului cavalerului

Portalul de matematică

Portalul șahului

[1] A. Conrad, T. Hindrichs, H. Morsy și I. Wegener, Soluția Knight's Hamiltonian Path Problem on Chessboards , în Discrete Applied Mathematics , vol. 50, nr. 2, 1994, pp. 125–134, DOI : 10.1016 / 0166-218X (92) 00170-Q .

[2] Martin Loebbing; Ingo Wegener, Numărul de tururi ale cavalerului este egal cu 33.439.123.484.294 - Numărarea cu diagrame de decizie binare , în Jurnalul electronic de combinatorie , vol. 3, nr. 1, 1996, pp. R5. Observație: Autorii au recunoscut ulterior că numărul anunțat este incorect. Conform raportului lui McKay, numărul corect este 13.267.364.410.532 și acest număr este repetat în cartea lui Wegener din 2000.

[3] Brendan McKay , Knight's Tours on a 8x8 Chessboard ( ps ), in Technical Report TR-CS-97-03 , Department of Computer Science, Australian National University, 1997 (arhivat din original la 27 ianuarie 2012) .

[4] Wegener, I., Branching Programs and Binary Decision Diagrams , Society for Industrial & Applied Mathematics, 2000, ISBN 0-89871-458-3 .

[5] (EN) Eric W. Weisstein, Knight's Tour în MathWorld Wolfram Research.

[6] John J. Watkins, Across the Board: the Mathematics of Chessboard Problems , Princeton University Press, 2004, ISBN 0-691-11503-6 .

[1]

[2]

[3]

[4]

[5]

[6]