Come tutti gli informatici sanno, con le cinque dita di una mano si può contare da 0 a 31. Basta considerare i due stati “dito alzato = 1” e “dito abbassato = 0”, e indicare i numeri da 00000 a 11111 in binario. Diciamo che questo è un ottimo esercizio per riuscire a muovere le dita in maniera indipendente.
Il passo successivo è quello di riuscire a contare in maniera non-standard: per esempio, aggiungendo dei vincoli, come il poter muovere solo un numero prefissato di dita ogni volta, cioè “cambiare lo stato”. Se si vuole muovere solo un dito per volta, non ci sono troppi problemi. Se non si vuol muovere nessun dito, non si va molto avanti; ma anche se si vogliono muovere cinque dita per volta non si possono certo ottenere tutte e 32 le configurazioni possibili.
Riuscite a trovare un modo per fare il giro completo muovendo due dita per volta, oppure tre, oppure quattro?
(un aiutino lo trovate sul mio sito, alla pagina http://xmau.com/quizzini/p123.html; la risposta verrà postata lì il prossimo mercoledì. Problema originale, su spunto di Roberto Corda. Immagine di Dug, da OpenClipArt)
Ultimo aggiornamento: 2016-06-02 22:21
Due: no perché potrò ottenere solo un numero pari di 1 ogni volta.
Quattro: idem.
Tre: 00000 -> 00111 -> 01001 -> 10000 -> 01100 -> 00001 -> 11000 -> 00010 -> 10001 -> 00100 -> 01010 -> 01000
e ho trovato tutte le posizioni con un solo dito, che generano tutto il gruppo.
Se invece si vuole trovare un percorso hamiltoniano, la risposta è BOH. Nel mio percorso parziale mi sembra di aver evitato ripetizioni, ma non so se questo sia possibile in grande. Farò qualche prova.
@valerio: non capisco il tuo ragionamento. Bisogna ottenere tutti i valori da 00000 a 11111 (in un ciclo oppure no), quindi devi trovare un percorso hamiltoniano. Cosa intendevi per “le posizioni con un solo dito generano il gruppo”, in questo contesto?
con due sole dita, non è sufficiente il codice Gray?
@elio: il codice Gray cambia un dito per volta.
Hai ragione!!!
Non credendo, inizialmente, che fosse necessaria l’hamiltonianità (cioè il divieto di ripassare per la stessa posizione più volte) ho cercato le sequenze di mosse che da 00000 portassero alle 5 posizioni con un solo dito alzato. Ottenute queste, posso concatenarle come voglio per ottenere tutti i numeri, ma è evidente che si ripassa molte volte per alcune posizioni.
Perché avevo immaginato che questo fosse accettabile? Perché non mi era evidente che muovendo un dito per volta fosse possibile avere il percorso hamiltoniano. Ma (dopo!) un ragionamento di teoria dei grafi me l’ha chiarito. Siamo in presenza di un grafo ipercubo di dimensione 5. Non solo c’è il percorso hamiltoniano ma se si vuole c’è anche il ciclo.
Il grafo che si ottiene per il caso delle tre dita per volta è differente dall’altro. I vertici sono gli stessi, ma gli spigoli sono molti di più: peccato che tra questi non ci siano quelli di prima. Non riesco a “vedere” un sottografo di questo grafo che sia isomorfo all’ipercubo, con il che il problema sarebbe risolto, ma a naso ho fiducia che ci sia. Ci devo pensare ancora un po’.
Forse ce l’ho.
Immaginiamo, partendo dalla mano chiusa, di voler lasciare sempre abbassato il quinto dito. Le mosse ammissibili sono perciò tutte quelle che muovono 3 delle altre 4 dita. Riuscirò a percorrere in modo hamiltoniano le 16 tappe del percorso ridotto?
Sì, perché sappiamo che muovendo un solo dito alla volta è possibile. Allora prendo una di quelle sequenze e ne costruisco un’altra facendo, per ogni mossa della prima, una mossa che consiste nel muovere le ALTRE tre dita.
0000 -> 0001 -> 0011 -> 0010 -> 0110…
0000 -> 1110 -> 0011 -> 1101 -> 0110…
Notiamo incidentalmente che dopo un numero pari di mosse si hanno gli stessi risultati, dopo un numero dispari i due numeri sono complementari.
Una volta completata questa sequenza, poniamo termini con 1110 (non l’ho fatta davvero ma notiamo che il numero di cifre 1 deve essere per forza dispari dopo un numero dispari di mosse, 15), opero un salto di classe facendo entrare in azione l’ultimo dito e muovendolo, assieme ad altre due dita: ad es. le prime due, 11100 -> 00101.
Poi torno a ignorarlo e rifaccio come prima un bel percorso hamiltoniano che tocchi tutte le tappe da 00001 a 11111, il che completa l’esercizio. E siccome la struttura che ho descritto è, come volevo, isomorfa all’ipercubo 5-dimensionale, se si scelgono bene le mosse si può ottenere anche il ciclo.
Lo so che non è bellissimo ma dovrebbe funzionare.