C. Traseul nebunului
Pe o tablă de sah, de dimensiuni 8x8, un nebun pornește din pozitia stânga-sus, notată cu (1,1) și trebuie să viziteze, câte o singură dată, toate cele 32 de poziții care au aceeași culoare cu cea a câmpului (1,1). Pozițiile parcurse vor fi marcate cu 1,2,...,32, în ordinea vizitării acestora. Pozițiile de pe tablă, de culoare diferită de cea a câmpului (1,1), vor fi marcate cu 0.
Numim o astfel de parcurgere traseu hamiltonian.
Dacă parcurgerea se finalizează astfel încât de la pozitia marcată cu 32 nebunul să poată ajunge cu o mutare la poziția inițială (1,1), atunci numim parcurgerea ciclu hamiltonian.
Daca pe orice linie si pe orice coloană a tablei se obține aceeași sumă, atunci numim traseul sau ciclul hamiltonian traseu, respectiv ciclu hamiltonian semi-magic.
Pentru 5 puncte, puteți indica un traseu hamiltonian?
Pentru 10 puncte, puteți indica si un ciclu hamiltonian?
Pentru 13 puncte, puteți indica si un traseu hamiltonian semi-magic?
Pentru 15 puncte, puteți indica si un ciclu hamiltonian semi-magic?
Sursă: problemă originală (Ionel-Vasile Pit-Rada)
C. Bishop’s tour
On a chessboard of size 8x8, a bishop starts from the top left position, marked with (1,1) and must visit, exactly once, all 32 positions that have the same color as (1.1). The visited positions will be marked with 1,2, ..., 32, in the order of their visit. The positions of a different color from (1,1), will be all marked with 0.
We call such a path a Hamiltonian path.
If the path is completed so that from the position marked with 32 the bishop can reach with the initial position (1,1) by single move, then we call this a Hamiltonian circuit.
If the sum on every line and every column of the chessboard is the same, then we call the path or the cycle, the semi-magical Hamiltonian path, respectively the semi-magical Hamiltonian circuit.
For 5 points, can you give a Hamiltonian path?
For 10 points, can you also give a Hamiltonian circuit?
For 13 points, can you also give a semi-magical Hamiltonian path?
For 15 points, can you also give a semi-magic Hamiltonian circuit?
Source: original puzzle (Ionel-Vasile Pit-Rada)
1) Pentru traseul hamiltonian și ciclul hamiltonian , semimagice , nebunul trebuie să plece tot din poziția (1,1) ?
Constat că problema nebunului pe tabla de șah se abate de la definiția unui graph hamiltonian. Prin vizitarea de către nebun a unei poziții se înțelege că nebunul staționează în acea poziție de unde , apoi , pleacă într-o nouă direcție permisă , adică se respectă regula de la jocul de sah pentru nebun ?
Da!