Problemi irrisolti 7. Domande in cerca di risposta

Forum dedicato ai quesiti irrisolti presenti nella collezione di Base5, nel vecchio forum ed in quello attuale.

Moderatori: Gianfranco, Bruno

Rispondi
Quelo
Livello 6
Livello 6
Messaggi: 569
Iscritto il: ven giu 16, 2006 3:34 pm

Problemi irrisolti 7. Domande in cerca di risposta

Messaggio da Quelo »

Dalla sezione "Visitare tutte le celle di una griglia"

Ecco il problema, posto solo con un disegno, senza parole.
Problema irrisolto 7.png
Problema irrisolto 7.png (15.57 KiB) Visto 194 volte
...
La soluzione è più avanti.
Visitare caselle 5x5.png
Visitare caselle 5x5.png (10.9 KiB) Visto 194 volte
...
La soluzione è solo una traccia di un possibile percorso.


Il 2 e il 5 non hanno soluzione, tutti gli altri punti di partenza di ottengono per simmetria e rotazione

7. Domande in cerca di risposta
Il problema ha sempre soluzione per n pari?


La risposta è sì.
Prendiamo il caso 2x2 la cui soluzione è banale e aggiungiamo un bordo 2 su due lati, sarà sempre possibile visitare tutte le caselle del bordo terminando sull'esterno
.
Visitare caselle 4x4.png
Visitare caselle 4x4.png (5.88 KiB) Visto 194 volte
.
con lo stesso sistema possiamo passare a 6x6, 8x8 e così via.

Dato uno schema 2nx2n e una posizione di partenza, sarà possibile individuare un nucleo 2x2 da espandere a 4x4, 6x6, ecc... fino all'angolo più vicino e poi completare tutto lo schema
.
Visitare caselle 6x6.png
Visitare caselle 6x6.png (23 KiB) Visto 194 volte
.
Gli schemi con lato dispari sono risolvibili solo per alcuni punti di partenza, cioè quelli con riga e colonna pari o riga e colonna dispari (le caselle bianche nell'immagine)
Questo perché lo schema 3x3 ha soluzioni solo per le partenze sulle diagonali e questo difetto si propaga in tutti gli schemi con lato dispari
.
Visitare caselle scacchi.png
Visitare caselle scacchi.png (6.08 KiB) Visto 194 volte
.
Se la griglia, fosse rettangolare anziché quadrata?

A intiuto direi che se il lato minore è pari, tutti i punti di partenza hanno soluzione, se il lato minore è dispari solo alcuni punti di partenza hanno soluzione (come per i quadrati con lato dispari)
Ci devo ancora lavorare

Aggiornamento:
Tutte le griglie che abbiano un lato pari sono risolvibili per ogni partenza, questo risponde anche alla domanda precedente (senza scomodare l'induzione)
Una tecnica semplice è la seguente:
1. dal punto di partenza raggiungere il lato pari più vicino
2. dirigersi verso l'altro lato dalla parte dove le caselle sono dispari
3. muoversi a serpentina tra il bordo e la casella di partenza inclusa
4. tornare indietro nello setsso modo e completare lo schema

Vediamo il caso 6x5
.
Visitare caselle 6x5.png
Visitare caselle 6x5.png (12.55 KiB) Visto 190 volte
.
Tutte le griglie che hanno entrambi i lati dispari sono risolvibili solo per partenze "a scacchiera", cioè riga e colonna dispari (1,1; 1,3; 3,3; ecc...) o pari (2,2; 2,4; 4,4; ecc...)

Vediamo il caso 7x5
.
Visitare caselle 7x5.png
Visitare caselle 7x5.png (54.47 KiB) Visto 187 volte
[Sergio]

Rispondi