Passeggiata spaziale

Il forum di Base5, dove è possibile postare problemi, quiz, indovinelli, rompicapo, enigmi e quant'altro riguardi la matematica ricreativa e oltre.

Moderatori: Gianfranco, Bruno

Rispondi
giobimbo
Livello 5
Livello 5
Messaggi: 343
Iscritto il: sab nov 19, 2005 5:14 pm
Località: Biella

Passeggiata spaziale

Messaggio da giobimbo »

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

Gianfranco
Supervisore del sito
Supervisore del sito
Messaggi: 1707
Iscritto il: ven mag 20, 2005 9:51 pm
Località: Sestri Levante
Contatta:

Re: Passeggiata spaziale

Messaggio da Gianfranco »

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?
Pace e bene a tutti.
Gianfranco

giobimbo
Livello 5
Livello 5
Messaggi: 343
Iscritto il: sab nov 19, 2005 5:14 pm
Località: Biella

Re: Passeggiata spaziale

Messaggio da giobimbo »

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.

Gianfranco
Supervisore del sito
Supervisore del sito
Messaggi: 1707
Iscritto il: ven mag 20, 2005 9:51 pm
Località: Sestri Levante
Contatta:

Re: Passeggiata spaziale

Messaggio da Gianfranco »

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.
Pace e bene a tutti.
Gianfranco

Rispondi