Passeggiata spaziale
Inviato: sab ago 18, 2018 3:04 pm
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
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