Dodecaedro del Viaggiatore
di Sir William Hamilton
(Dublino, 1857)
Difficoltà: ◉◉◎
Numero di giocatori: 1
Regolamento
Si consideri il grafo planare, composto da 20 vertici e 30 lati, come in figura.
Fissato il percorso PCDML, si chiede al giocatore di proseguire il percorso con l’obiettivo di tornare al punto di partenza (P) toccando una e una sola volta tutti i vertici del grafo.
Un percorso come quello ottenuto come soluzione del problema si chiama circuito hamiltoniano. Osserviamo che il grafo considerato corrisponde alla proiezione sul piano dello scheletro, cioè dei lati, che compongono un dodecaedro.
Domanda bonus ◉◉◎
Proiettare sul piano lo scheletro di un cubo e trovare un circuito hamiltoniano sul grafo ottenuto
I vertici del grafo hanno tutti tre lati uscenti da esso, dunque quando giungiamo a un vertice percorrendo un lato, possiamo indicare gli altri lati uscenti dallo stesso vertice con d (destra) o s (sinistra).
Fissato un lato e un suo vertice, un percorso che parte da tale vertice può essere associato univocamente a una parola, cioè una successione di lettere, prese dall’alfabeto {d,s}.
Supponendo di giungere a P dal lato PN, la parola corrispondente al percorso rosa è sssd.
Due parole dell’alfabeto {d,s} sono dette uguali se, giungendo a un vertice da un lato fissato e proseguendo il percorso seguendo le due parole, i vertici di arrivo coincidono.
Supponendo di giungere a P dal lato PN, la parola corrispondente al percorso rosa (che è sssd) e la parola corrispondente al percorso azzurro (che è ssdss) sono uguali perchè i vertici di arrivo coincidono (in L).
Se indichiamo con 1 il percorso nullo, cioè quello con 0 passi, allora possiamo dire che ddddd = sssss = 1: infatti ddddd e sssss corrispondono a percorrere interamente il bordo di una delle celle pentagonali. Un percorso continuo che tocchi tutti i vertici una e una sola volta, corrisponde a una parola di lunghezza 20, non semplificabile, cioè che non è uguale a una parola più corta.
Supponendo di partire da Q giungendo dal lato RQ, la parola ddddd corrisponde a percorrere il bordo del pentagono QZBCP in senso antiorario, mentre sssss corrisponde a percorrere il bordo dello stesso pentagono in senso orario.
Domanda bonus ◉◉◎
Scrivere una parola corrispondente alla soluzione del gioco.