backup del Post

Il Numero di Dio

Non so se e quanto i ragazzi di oggi lo conoscano, ma per chi ha la mia età il Cubo di Rubik è stato uno dei più grandi tormentoni tra i giochi di abilità. Un esempio che più pratico non si può delle abilità che esistevano al di là della Cortina di ferro; una struttura a prima vista impossibile – come fa il Cubo a non finire a pezzi quando lo si gira? – ma sufficientemente solida; una sensazione di sconforto quando dopo alcune mosse si scopre di non riuscire più a rimettere il Cubo nella posizione iniziale. Ora è facile trovare in rete le istruzioni per riordinarlo: ma nel 1980 si poteva solo sperare di trovare una rivista che pubblicasse un apposito inserto (io avevo quello di Pergioco), oppure cercare soluzioni creative tipo smontare e rimontare il Cubo. Ma i matematici sono sempre pronti a lavorare su un gioco, soprattutto se hanno la scusa di poter dire che stanno facendo matematica (le mosse sul cubo sono gli elementi di un gruppo algebrico), ed è davvero difficile fermarli… Insomma, cos’hanno scoperto?

Per prima cosa, non appena il Cubo è stato commercializzato si è andati alla ricerca di un modo per risolverlo, nel bene o nel male. In casi come questo si predilige la semplicità all’ottimizzazione; in pratica si imparano alcune combinazioni base di mosse e le si applica pur sapendo che si sta perdendo tempo. Contemporaneamente si è dimostrato che il numero minimo di mosse necessarie nel caso peggiore doveva essere almeno 18. Questo è stato relativamente facile: si sono contate tutte le possibili posizioni del Cubo, si sono contate tutte le possibili posizioni raggiungibili in al più 17 mosse, e si è visto che non ce n’erano a sufficienza. La prima soluzione nota richiedeva nel caso peggiore un’ottantina di mosse; quindi si poteva affermare con certezza che il Cubo poteva sempre essere risolto in N mosse, dove N era compreso tra 18 e 80. Da qui si è iniziato a limare i valori.

Il valore minimo è stato portato a 20 nel 1995, nel modo più banale possibile: è stata esibita una configurazione che non poteva essere risolta in meno di 20 mosse. Il guaio è che il numero di posizioni possibili è 43.252.003.274.489.856.000 (quarantatré miliardi di miliardi e briciole) e mettersi a testarle tutte non sembrerebbe fattibile. Così si è andati avanti con una serie di migliorie teoriche, abbassando man mano il limite massimo fino a luglio 2010, quando è stato portato a 20 e quindi è stata data una risposta definitiva alla domanda. Il sito cube20.org, da cui ho preso queste informazioni, spiega come si è riusciti ad arrivarci: essenzialmente per forza bruta. Più precisamente, il gruppo di lavoro:

1. ha suddiviso le posizioni in 2.217.093.120 insiemi di 19.508.428.800 posizioni l’uno;
2. per ragioni teoriche, ha dimostrato che in ciascun insieme le posizioni “essenzialmente diverse” erano “solo” 55.882.296;
3. per ciascuna posizione non ha cercato una soluzione nel numero minimo di mosse, ma solo una in venti mosse (il che è molto più rapido: in problemi combinatori di questo tipo le soluzioni subottimali sono così tante che è relativamente facile trovarne una, e tanto non si poteva scendere sotto le venti mosse);
4. ha scritto un programmino che in venti secondi risolveva una data posizione;
5. ha distribuito il lavoro su tanti PC, e in 35 “anni macchina” hanno trovato una soluzione per ciascuna posizione.

È chiaro che una soluzione di questo tipo è fondamentalmente inutile da un punto di vista pratico: un computer con braccia meccaniche sarebbe comunque più lento di un essere umano molto bravo, che userebbe qualche mossa in più ma non perde troppo tempo a pensarci su. Ma la teoria vince sempre sulla pratica. Inoltre il gruppo di lavoro ha scoperto qualcosa a prima vista molto strano: le configurazioni “difficili”, quelle cioè che non sono risolvibili in 19 mosse o meno, sono relativamente poche. I ricercatori stimano che siano intorno ai 300 milioni, il che significa che data una configurazione a caso la probabilità che sia “difficile” è tra uno e dieci su un miliardo. Nel sito cube20.org è indicato il numero di combinazioni diverse a seconda del numero di mosse necessario per risolverle, calcolato esattamente fino a 15 mosse e in seguito stimato. Diciamo che se uno dovesse fare una scommessa sarebbe sostanzialmente sicuro che la posizione casuale sia risolvibile in un numero di mosse compreso tra 16 e 19, con un picco a 18. Insomma, non è così facile fare troppo disordine!