BASE CINQUE FORUM

Sopra un tavolo da laboratorio, a 20 centimetri di altezza, sta sospesa una lamina metallica di forma quadrata. Su di una faccia è disegnata una scacchiera nxn contenente i numeri da 1 a n, in un certo ordine, mentre sul retro semplicemente c’è scritta la lettera R.
Abbiamo una formica addestrata a camminare in linea retta e ad attraversare le caselle numerate passando per i centri di due lati opposti, oppure per due spigoli opposti.
Quando l’animale viene posato sulla casella col numero r esso si mette in cammino contando su quante caselle numerate passa, fino a fermarsi nell’r-esima. Se il nuovo numero è diverso da r, per esempio s, si gira e riparte in una nuova direzione passando su s caselle numerate. Se invece il numero di arrivo è uguale a quello di partenza allora torna indietro.
Facciamo un esempio con la scacchiera 3x3 numerata come il quadrato magico sotto:

4…3…8
9…5…1
2…7…6

Mettendo la formica sul 9 essa potrebbe fare (9) 5 1 R 9 5 1 R 9 5 1 R 9, numero di partenza, quindi torna indietro e riparte in altra direzione, magari fa (9) 3 R 9 3 R 9 3 R 9 3 R 9 3, poi dal 3 magari fa (3) 5 7 R 3 e allora torna indietro, eccetera.

Se il percorso della formica è composto di n caselle diverse diremo che ha fatto un “cammino hamiltoniano”. Ad esempio, con partenza dalla casella col numero 1:

(1) 8 5 2 4 3 9 7 6 è un cammino hamiltoniano

Se la formica dall’ultima casella di un cammino hamiltoniano riesce ad andare nella casella iniziale di tale cammino, diremo che ha fatto un “circuito hamiltoniano”.


Problema 1. Trovare un cammino hamiltoniano per il quadrato magico 4x4 qui sotto:

07…11…10…06
14…02…03…15
04…16…13…01
09…05…08…12

Problema 2. Dimostrare che in nessun quadrato magico 4x4 esiste un circuito hamiltoniano.

Problema 3. Penso che lo stesso valga per quadrati magici 5x5 ma non saprei dimostrarlo, allora trovare un circuito hamiltoniano per la scacchiera 5x5 qui sotto:

24…05…01…09…06
21…02…03…04…07
08…11…12…13…10
25…14…16…22…19
18…17…20…15…23

Giobimbo,

...una scacchiera nxn contenente i numeri da 1 a n,...

intendi: "da 1 a n^2"?

...passando per i centri di due lati opposti, oppure per due spigoli opposti.

non ho capito le regole per muoversi sulla scacchiera.
Potresti per favore spiegare più in dettaglio le regole?

Sono mortificatissimo, intendevo proprio da 1 a nxn. Tra l'altro ho pure dimenticato che la formica viene messa al "centro" di una casella numerata.
Quanto al movimento pensavo che l'esempio lo chiarisse, comunque l'animale si muove in 3 direzioni possibili, verticale in su o in giù, laterale a destra o a sinistra, oppure in diagonale a 45 gradi, verso destra o verso sinistra. La formica memorizza il numero di partenza, sceglie una direzione e percorre le due facce della lamina in modo che se la lamina fosse trasparente i due percorsi si sovrappongono. Essa conta solo le caselle numerate, la casella R serve solo per capire dove passa.
Il problema è di un bel po' di mesi fa, nello scriverlo mi sono sfuggite delle cose, in altre sono stato ridondante, potevo tralasciarle. Spero di far meglio in futuro.

Grazie Giobimbo, ora è chiaro, per me. Non avevo capito (a causa della mia ottusità mentale) la faccenda del percorso R che si sovrappone "in trasparenza" a quello di andata.