Soluzione quiz degli Anelli cinesi
QUI il quiz
Il modo più semplice per capire come va smontato un oggetto è riflettere sul modo in cui è stato montato. Quindi partiremo simulando la situazione “asola libera” e procederemo ad incatenarla con gli anelli. Dopo di che sarà sufficiente eseguire in senso inverso la sequenza in modo da liberarla di nuovo.
Il primo anello si infila facilmente, come si vede in questa figura:
Si passa il primo anello dentro l'asola trascinando il suo “gambo” verso l'alto, salendo cioè dal livello 0 al livello 1
Poi si ripiega l'anello a sinistra in modo che l'asola lo attraversi.
Se il gioco consistesse di questo unico anello il numero di mosse N per svincolare l'asola sarebbe semplicemente 1. La lunghezza della sequenza sarebbe perciò 1, ossia L1 = 1.
Aggiungendo un secondo anello, nella fase di montaggio sarà necessaria una seconda mossa e quindi la lunghezza della sequenza di mosse per svincolare l'asola diventerà 2.
Proseguendo il montaggio dal punto precedente si solleva il secondo anello sopra l'asola, lo si fa scivolare a sinistra e si passa l'asola al suo interno, in questo modo:
Se il gioco comprendesse solo 2 anelli la sequenza di smontaggio sarebbe di rimuovere prima quello in seconda posizione, facendolo scendere, e poi agire su quello in prima posizione.
Questa sequenza di 2 mosse è lunga il doppio della precedente che si componeva di una sola mossa.
L2 = 2 L1
Ma vediamo che nella figura già si presenta il terzo anello nella posizione sottostante l'asola.
Supponiamo di infilarlo nell'asola e di sollevarlo, come già fatto per gli altri due. Vediamo però che questa volta non è possibile eseguire la seconda parte della operazione perché lo scivolamento verso sinistra è impedito dai gambi dei due precedenti anelli.
In particolare occorre liberare la strada verso l'estremo sinistro dell'asola estraendo il primo anello e facendolo cadere nell'asola. Poi si farà salire il terzo anello sopra l'asola e lo si farà scivolare a sinistra fino a farlo infilare dall'asola.
Per concludere la costruzione recupereremo il primo anello e infileremo l'asola anche in esso ottenendo questa configurazione:
Le mosse supplementari che abbiamo visto sono in tutto 3, (una discesa e due salite)
Aggiungendole alle due precedenti, la sequenza di montaggio ( e anche di smontaggio) diventa di 5 mosse. La lunghezza della sequenza è quindi il doppio di quella con un anello in meno, aumentata di 1. In altri termini: L3 = 2 L2 + 1.
Descriviamo quindi le 5 operazioni da compiere per lo smontaggio della catena di 3 anelli.
Prima si fa scendere l'anello 1, poi scende l'anello 3. Si riposiziona quindi l'anello 1 e si fa scendere l'anello 2. Da ultimo resta da far scendere l'anello 1 e con ciò si è liberata l'asola.
Il fatto di saper come gestire il gruppo di tre anelli potrebbe suscitare previsioni ottimistiche sulla facilità di passare da 3 a 6 anelli, aggiungendo i rimanenti. Ma le cose, come vediamo subito, iniziano a complicarsi già soltanto per aggiungere il quarto anello.
Ora il cammino verso la punta di sinistra dell'asola è impedito da ben tre gambi.
Nella fase di montaggio dovremo spianare la strada rimuovendo i primi due di questi tre gambi.
Cominceremo facendo cadere il secondo anello e, subito dopo, il primo. Se agissimo al contrario commetteremmo un errore perché dopo il primo anello è possibile far cadere il terzo ma non il secondo.
Dopo la discesa dei primi due anelli è possibile far salire l'anello 4 ed infilarvi dentro l'asola, nel modo consueto. Recupereremo ora l'anello 1 facendolo risalire e infine, anche l'anello 2.
Ora tutti i 4 anelli sono infilati. Eseguendo in senso inverso le operazioni potremo liberare l'asola.
Le mosse supplementari sono state ben 5 ( due discese e tre salite) e portano al totale di 10 i passi della sequenza. L4 = 2 L3 .
Possiamo a questo punto ipotizzare una generalizzazione di questo tipo:
Ogni volta che viene aggiunto un anello la lunghezza della sequenza aumenta, raddoppiando nel caso di anello aggiunto in posizione pari, o raddoppiando con aggiunta di 1, nel caso di anello aggiunto in posizione dispari.
-
Numero anello Lunghezza sequenza 0 0
1 1 = (0*2 + 1) 2 2 = (1*2) 3 5 = (2*2 + 1) 4 10 = (5*2) 5 21 = (10*2 + 1) 6 42 = (21*2) 7 85 = (42*2 + 1) 8 170 = (85*2) 9 341 = (170*2 + 1) 10 682 = (341*2)
In questa tabella troviamo le risposte ad alcune delle domande iniziali. In particolare il mitico valore di 341 mosse appare giustificato dalla regola che governa la sequenza di smontaggio per il gruppo di 9 anelli. Inoltre troviamo anche la previsione che per smontare un gruppo di 6 anelli sono necessarie 42 mosse.
Il lettore, basandosi sulle precedenti descrizioni di come gestire i gruppi di 2, 3, 4 anelli, potrà espandere il metodo e constatare che è applicabile a qualsiasi gruppo formato da un qualsivoglia numero di anelli.
Resta da trovare una espressione che consenta, senza costruire progressivamente il valore della lunghezza della sequenza, di determinarlo immediatamente, dato il numero degli anelli.
La risposta si trova semplicemente osservando che:
-
Numero anelli Lunghezza sequenza smontaggio 1 1 = 20 2 2 = 21 3 5 = 22 + 20 4 10 = 23 + 21 5 21 = 24 + 22 + 20 6 42 = 25 + 23 + 21 7 85 = 26 + 24 + 22+ 20 8 170 = 27 + 25 + 23 + 21 9 341 = 28 + 26 + 24+ 22 + 20 10 682 = 29 + 27 + 25 + 23 + 21
Generalizzando, per gruppi di anelli in numero dispari
Ln = 2n-1 + 2n-1-2 + 2n-1-4 …. 20
Per gruppi di anelli in numero pari
Ln = 2n-1 + 2n-1-2 + 2n-1-4 …. 21
Proseguendo la tabella, senza fare riferimento ai valori dei gruppi precedenti, avremmo quindi...
L11 = 210 + 28 + 26 + 24 + 22 + 20 = 1024 + 256 + 64 + 16 + 4 + 1 = 1365
L12 = 211 + 29 + 27 + 25 + 23 + 21 = 2048 + 512 + 128 + 32 + 8 + 2 = 2712
E così via.
Roba da … Cinesi !
Appendice
Presento la sequenza delle 42 mosse per sciogliere l'asola dagli anelli nel caso di un gruppo di 6.
In tutto le configurazioni, comprese la prima e l'ultima, sono 43 ( delle 64 possibili).
La posizione di ciascuno dei 6 anelli è rappresentata da 0 (anello sfilato e sotto l'asola) o da 1 (anello infilato nell'asola).
Il passaggio da una configurazione alla successiva consiste nello spostamento di un singolo anello il cui stato cambia da 0 a 1 o viceversa.
111111 configurazione iniziale (tutti i 6 anelli infilati)
101111
001111
001011
101011
111011
011011
010011
110011
100011
000011
000010 espulsione dell'anello 6
100010
110010
010010
011010
111010
101010
001010
001110
101110
111110 anelli da 1 a 5 infilati
011110
010110
110110
100110
000110
000100 espulsione anello 5
100100
110100
010100
011100
111100 anelli da 1 a 4 infilati
101100
001100
001000 espulsione anello 4
101000
111000 anelli da 1 a 3 infilati
011000
010000 espulsione anello 3
110000 anelli da 1 a 2 infilati
100000 espulsione anello 2 e solo anello 1 infilato
000000 espulsione anello 1
Nella sequenza ciascuna delle configurazioni compare una sola volta.
