Di solito scegliamo una partenza, eseguiamo le mosse e scopriamo che cosa succede. Qui cambiamo domanda: quale partenza dobbiamo preparare per ottenere proprio il risultato che vogliamo? Nei due problemi le operazioni inverse diventano un modo concreto di ragionare.
Apri il laboratorio: carte e Josephus, avanti e a ritroso
Due applicazioni da provare con gli amici:
Partire dalla fine
Un algoritmo a ritroso non è una serie di tentativi casuali. Partiamo da uno stato finale desiderato e annulliamo le operazioni in ordine inverso. Il risultato dell’ultima azione normale diventa il punto di partenza della prima azione inversa. Occorre conoscere quali informazioni conservare: qui manteniamo le carte sul tavolo e distinguiamo chi deve rimanere da chi deve uscire.
Problema 1: il mazzo di carte
Hai 10 carte numerate da 1 a 10. Come devi disporle perché, ripetendo sempre le mosse seguenti, escano sul tavolo nell’ordine 1, 2, 3, 4, 5, 6, 7, 8, 9, 10?
- Prendo la carta da sotto il mazzo.
- La metto sopra il mazzo.
- Prendo la carta da sotto il mazzo.
- La metto scoperta sul tavolo, sopra le precedenti.
L’ordine delle uscite è cronologico: prima 1, poi 2, fino a 10. Nella pila finale sul tavolo, invece, 10 è in cima e 1 in fondo. Queste due letture non vanno confuse.
Il filmato delle carte all’indietro
Immaginiamo di riavvolgere il video. La mano è vuota e la pila finale è sul tavolo. Riprendiamo prima il 10, poi il 9 e così via. Invertiamo sia il verso di ogni trasferimento sia l’ordine delle quattro azioni:
- Prendo la carta dalla cima della pila sul tavolo.
- La metto sotto il mazzo in mano.
- Prendo la carta da sopra il mazzo in mano.
- La metto sotto il mazzo in mano.
Le prime due azioni annullano l’uscita sul tavolo; le ultime due annullano lo spostamento da sotto a sopra. Anche quando in mano c’è una sola carta, il principio rimane lo stesso.
Dopo ogni gruppo di quattro azioni inverse, il mazzo in mano cresce di una carta. Leggiamo sempre dalla cima al fondo:
| Carta ripresa dal tavolo | Mazzo dopo il giro inverso, dalla cima al fondo |
|---|---|
| 10 | 10 |
| 9 | 9, 10 |
| 8 | 10, 8, 9 |
| 7 | 8, 9, 7, 10 |
| 6 | 9, 7, 10, 6, 8 |
| 5 | 7, 10, 6, 8, 5, 9 |
| 4 | 10, 6, 8, 5, 9, 4, 7 |
| 3 | 6, 8, 5, 9, 4, 7, 3, 10 |
| 2 | 8, 5, 9, 4, 7, 3, 10, 2, 6 |
| 1 | 5, 9, 4, 7, 3, 10, 2, 6, 1, 8 |
Disposizione iniziale, dalla cima al fondo:
5, 9, 4, 7, 3, 10, 2, 6, 1, 8
La stessa disposizione, letta dal fondo alla cima:
8, 1, 6, 2, 10, 3, 7, 4, 9, 5
Eseguendo il gioco normale con questo mazzo escono esattamente i numeri da 1 a 10. Nel laboratorio la verifica si vede una carta alla volta; puoi anche cambiare N o scegliere un ordine di uscita diverso.
Un confronto: simulazione e permutazione
Possiamo arrivare allo stesso mazzo senza annullare direttamente le mosse. Etichettiamo le posizioni iniziali da 1 a 10, contandole dal fondo. Simuliamo il gioco normale e registriamo l’ordine cronologico in cui escono queste etichette:
2, 4, 6, 8, 10, 3, 7, 1, 9, 5
Alla prima posizione uscita assegniamo il valore 1, alla seconda il valore 2 e così via. La tabella mantiene sempre lo stesso verso di lettura:
| Etichetta della posizione uscita (dal fondo) | Valore assegnato |
|---|---|
| 2 | 1 |
| 4 | 2 |
| 6 | 3 |
| 8 | 4 |
| 10 | 5 |
| 3 | 6 |
| 7 | 7 |
| 1 | 8 |
| 9 | 9 |
| 5 | 10 |
Riordinando per etichetta da 1 a 10 ritroviamo la disposizione dal fondo alla cima. I due metodi coincidono: la simulazione osserva la permutazione delle posizioni; la ricostruzione inversa annulla i trasferimenti.
Problema 2: il cerchio di Josephus
Disponiamo N persone in cerchio. Contiamo fino a K, eliminiamo la K-esima persona e ripartiamo dalla successiva. Vogliamo che, dopo P eliminazioni, rimangano V persone del gruppo dei vincenti. Come costruiamo la disposizione iniziale? Non assegniamo in anticipo i posti dei vincenti: dobbiamo scoprirli con la ricostruzione.
Nel gioco di eliminazione fissiamo il posto 1 come origine del conteggio: la persona seduta lì conta 1, la successiva 2 e così via fino a K. Dopo ogni eliminazione si ricomincia da 1 dalla persona successiva. I posti della disposizione completa si numerano in senso orario; il gioco segue il verso scelto. Negli esempi principali procediamo in senso orario.
Il posto 1 è il punto da cui comincia il conteggio per eliminare. Non è necessariamente il posto della persona identificata dal numero 1, e non è necessariamente vincente.
Il gioco mostra la simulazione in avanti. Il nuovo laboratorio costruisce invece la disposizione a ritroso e permette poi di verificarla anche nello stesso gioco.
Apri il gioco di Josephus già esistente
Ricostruire Josephus, una mossa alla volta
L’algoritmo conosce soltanto quanti sono i vincenti, quanti i perdenti e ogni quanti conteggi si elimina. All’inizio mette insieme tutti i vincenti, uno dopo l’altro. Non tiene conto di loro posizioni precedenti e non sceglie già i posti finali. Per seguire il procedimento numeriamo le persone: da 1 a V i vincenti, da V + 1 a N i perdenti.
- Mettiamo in fila i soli V vincenti, numerati 1, 2, …, V. Sono tutti insieme: non sono ancora posti numerati del gioco.
- Prendiamo il primo perdente, con numero V + 1, e lo mettiamo in testa alla fila.
- Ripetiamo K − 1 volte la stessa coppia di operazioni: prendiamo l’ultimo numero dalla coda e lo mettiamo in testa.
- Prendiamo il perdente successivo e ripetiamo inserimento e spostamenti. Continuiamo così, un perdente alla volta, fino a inserire tutti i P perdenti.
- Solo alla fine leggiamo la disposizione completa dalla testa, assegniamo i posti 1, 2, …, N e riconosciamo quelli occupati dai vincenti. Dal posto 1 partirà il conteggio per eliminare.
Il procedimento usa esattamente K − 1 spostamenti per ogni inserimento, come nel ciclo del programma. Per esempio, con K = 3: inserisco un perdente in testa, poi eseguo due volte «prendo dalla coda e metto in testa». Con K = 1 inserisco soltanto il perdente, senza spostamenti.
Durante la ricostruzione i numeri identificano le persone. Non indicano dove vinceranno. Nel cerchio del laboratorio i vincenti verdi sono inizialmente insieme; i perdenti blu aspettano separati e vengono reinseriti uno alla volta. I posti vincenti sono un risultato del procedimento, non un dato di partenza.
Un esempio piccolo: N = 4, K = 3
Usiamo V = 1 vincente, P = 3 perdenti e K = 3. Il vincente è la persona 1; i perdenti sono le persone 2, 3 e 4. Partiamo dal solo 1. Inseriamo il 2 e facciamo due spostamenti dalla coda alla testa; poi facciamo lo stesso con il 3 e con il 4. La tabella mostra ogni inserimento e ogni spostamento completato:
| Operazione | Fila: numeri delle persone, dalla testa alla coda |
|---|---|
| Metto insieme i soli vincenti | 1 |
| Inserisco il perdente 2 in testa | 2, 1 |
| Porto 1 dalla coda alla testa (1 di 2) | 1, 2 |
| Porto 2 dalla coda alla testa (2 di 2) | 2, 1 |
| Inserisco il perdente 3 in testa | 3, 2, 1 |
| Porto 1 dalla coda alla testa (1 di 2) | 1, 3, 2 |
| Porto 2 dalla coda alla testa (2 di 2) | 2, 1, 3 |
| Inserisco il perdente 4 in testa | 4, 2, 1, 3 |
| Porto 3 dalla coda alla testa (1 di 2) | 3, 4, 2, 1 |
| Porto 1 dalla coda alla testa (2 di 2) | 1, 3, 4, 2 |
La fila completa è 1, 3, 4, 2. Ora, e soltanto ora, assegniamo i posti: nel posto 1 c’è la persona 1, nel posto 2 la persona 3, nel posto 3 la persona 4 e nel posto 4 la persona 2. Il posto vincente è quindi 1. Se parto a contare da quel posto ed elimino ogni terzo, escono i posti 3, 2 e 4: rimane il posto 1.
Il compleanno: vinco sempre io!
Siamo a una festa: 9 invitati più il festeggiato, quindi N = 10. Il festeggiato compie 12 anni: scegliamo K = 12 e vogliamo un solo vincitore, V = 1. Gli invitati da eliminare sono P = 9.
Ricostruiamo il cerchio e assegniamo il posto vincente al festeggiato. Partendo dal posto 1, in senso orario vince il posto 10; in senso antiorario vince il posto 2.
Non è fortuna: abbiamo scelto il risultato e preparato la posizione adatta. Per cambiare festa imposta P uguale al numero degli invitati, V = 1 e K uguale agli anni compiuti. Il festeggiato si aggiunge agli invitati nel totale N.
Eliminazioni in senso orario:
2, 5, 9, 6, 4, 8, 7, 3, 1
La coppia: due vincitori scelti
Siamo 20 amici e vogliamo che rimangano due persone scelte prima del gioco. Impostiamo N = 20, V = 2, P = 18 e K = 11.
Ricostruendo a ritroso troviamo i posti da assegnare alla coppia: in senso orario 9 e 15; in senso antiorario 7 e 13. Il conteggio parte sempre dal posto 1.
Le due persone possono scambiarsi fra loro i due posti vincenti. Non significa che possiamo far vincere due posti arbitrari: sono proprio le due posizioni calcolate a garantire il risultato.
Eliminazioni in senso orario:
11, 2, 14, 6, 19, 13, 8, 4, 1, 20, 3, 7, 12, 18, 16, 17, 10, 5
Due gruppi di 15 persone
Un altro esempio usa due gruppi di 15 persone: V = 15, P = 15, N = 30 e K = 9. Il procedimento non cambia: partiamo da 15 vincitori e reinseriamo 15 perdenti. I posti vincenti sono:
Orario
1, 2, 3, 4, 10, 11, 13, 14, 15, 17, 20, 21, 25, 28, 29
Antiorario
1, 3, 4, 7, 11, 12, 15, 17, 18, 19, 21, 22, 28, 29, 30
Ricostruisci il cerchio di 30 persone
Un altro esempio: 2 vincenti e 28 perdenti
Con V = 2, P = 28 e K = 11, all’inizio riuniamo soltanto i vincenti 1 e 2. I perdenti da 3 a 30 vengono inseriti uno alla volta. Non fissiamo alcun posto vincente in anticipo. Alla fine numeriamo i 30 posti e, contando dal posto 1 in senso orario, troviamo questi posti vincenti:
18, 28
Prova 2 vincenti, 28 perdenti ed elimina ogni 11
Come usare il laboratorio
- Nella scheda Carte scegli N e l’ordine desiderato. In quella Josephus imposta quanti vincenti e perdenti ci sono, K e verso, oppure carica uno degli esempi.
- Usa Avanti e Indietro per le singole mosse, Avvia/Pausa per l’animazione e il cursore per tornare a un punto preciso. Il passo iniziale è di un secondo per azione; puoi cambiarlo.
- Nella ricostruzione di Josephus osserva il primo gruppo disposto in cerchio: parte dai soli vincenti verdi. I perdenti blu restano nella seconda lista durante il conteggio animato e poi entrano uno alla volta, senza diventare verdi. La forma circolare mostra il gruppo in costruzione, non posti già assegnati.
- Alla fine compare la riga dei posti, con quelli vincenti in verde. Il posto 1 è l’origine del conteggio del gioco di eliminazione. Verifica in avanti riproduce quel gioco e permette di controllare la disposizione.
Apri il laboratorio: carte e Josephus, avanti e a ritroso
Che cosa abbiamo imparato
Con le carte ricostruiamo il mazzo che produce l’ordine di uscite voluto. Con Josephus partiamo invece dai soli vincenti riuniti e reinseriamo i perdenti uno alla volta. Non imponiamo le posizioni dei vincenti: le troviamo alla fine. Numerata la disposizione completa, il posto 1 stabilisce dove iniziare a contare per eliminare. La verifica in avanti conferma il risultato.