L’auto-organizzazione dei mercati finanziari

 

Il crollo del mercato azionario e’ un calo improvviso e drammatico dei prezzi delle azioni con conseguente perdita significativa di ricchezza. I crolli in genere sono guidati dal panico degli investitori e da fattori economici sottostanti. Spesso essi seguono le cosiddette bolle speculative del mercato azionario. I crolli sono dei veri e propri fenomeni sociali dove gli eventi economici si combinano con il comportamento e la psicologia della folla formando un loop con retroazione positiva dove la vendita iniziale da parte di un piccolo gruppo convince sempre piu’ persone a fare la stessa cosa. Sono stati individuati dei path preferenziali che portano ad una crisi del mercato:

1) Un periodo prolungato di aumento dei prezzi delle azioni e un eccessivo ottimismo economico

2) Un mercato dove i rapporti P/E superano significativamente il valore medio di lungo termine

3) L’uso estensivo del cosiddetto Margin debt da parte degli investitori (il margin debt e’ il denaro che gli investitori prendono in prestito per esempio dalle banche per acquistare delle azioni)

La caratterizzazione matematica dei movimenti dei mercati azionari e quindi la possibilita’ di prevedere i crolli del mercato sono stati da sempre un campo di interesse di economisti, matematici e ultimamente anche di fisici. L’assunzione convenzionale e’ quella di un mercato che si muove seguendo una distribuzione log-normale. In altre parole si assume che il logaritmo dei rendimenti (rapporto tra prezzo di oggi St e quello di ieri St-1) sia distribuito come una gaussiana (distribuzione a campana).

Questa assunzione comunque non e’ sempre vera come si puo’ osservare prendendo come esempio i prezzi dell’ultimo anno del titolo Google. Il test di normalita’ di Shapiro-Wilk non passa essendo il valore molto prossimo a zero (una distribuzione normale deve avere questo parametro tendente a 1).

La stessa cosa e’ vera per i rendimenti del titolo Apple nell’ultimo anno.

Per questo motivo il matematico Benoit Mandelbrot nel 1963 suggeri’ che questa statistica fosse incorretta osservando che i movimenti significativi dei prezzi (i crolli) sono molto piu’ comuni di quanto previsto da una distribuzione lognormale. Dopo le osservazioni di Mandelbrot altri studiosi hanno suggerito che i movimenti del mercato vengono spiegati meglio da concetti utilizzati in teoria del caos e dell’analisi non-lineare. Tutto questo e’ stato riassunto con linguaggio non matematico da George Soros nel suo libro “L’alchimia della finanza” dove parla di quella che lui chiama la riflessivita’ dei mercati e i loro movimenti non lineari. La tesi principale e’ che i mercati sono tutt’altro che efficienti e che l’uomo oeconomicus e’ tutt’altro che razionale. Al contrario i prezzi di mercato riflettono piu’ che altro l’ignoranza i pregiudizi e spesso l’irrazionalita’ di milioni di investitori. Essi non riflettono accuratamente le condizioni sottostanti fornendo un quadro che in un modo o nell'altro è sempre di parte o distorto. Le visioni distorte dei protagonisti del mercato ed espresse nei prezzi possono, in certe circostanze, intaccare i fondamentali del mercato. Questo circuito di andata e ritorno tra i prezzi di mercato e la realtà sottostante e’ la reflexivity, "riflessività" di Soros. I mercati finanziari riflettono sempre questo circuito a due vie e possono a tratti allontanarsi molto dal cosiddetto equilibrio. In altre parole, è tipico dei mercati finanziari essere predisposti alla creazione di bolle speculative. In economia non vince l'ordine, ma il suo contrario, perché le scelte operate ad alto livello sui mercati internazionali sono pur sempre il frutto di interessi (e di errori) di singoli individui. L'economia viene influenzata (quindi subisce un riflesso) dalle condizioni sociali vigenti, che raramente sono di stabilità; molto più spesso sono di panico, paura, euforia. Condizioni che, se portate alle estreme conseguenze, possono sfociare in situazioni d'emergenza quali una bolla immobiliare e il crollo delle borse. In economia una bolla speculativa e’ una particolare fase di mercato caratterizzata da un aumento considerevole e ingiustificato dei prezzi di uno o più beni, dovuto ad una crescita della domanda repentina e limitata nel tempo. Alla fase di nascita e di crescita della bolla segue poi la fase di scoppio che tende a ripristinare i valori originari del bene in questione. L'eccesso di domanda che spinge verso l'alto in poco tempo il valore di un bene, di un servizio, di una impresa o più semplicemente di un titolo, si può ricondurre all'irrazionale (o razionale) euforia di soggetti economici convinti che una nuova industria, un nuovo prodotto, una nuova tecnologia potranno offrire cospicui guadagni e registrare una crescita senza precedenti. Scatta, pertanto, la corsa all'acquisto del diritto, nella speranza di rivendere lo stesso ad un prezzo superiore. La corsa all'acquisto provoca un aumento del prezzo che conferma, agli occhi di molti, la bontà della precedente previsione di un futuro aumento del prezzo del diritto. Questo stimola ulteriormente gli acquisti e quindi fa aumentare ancora una volta il prezzo. La profezia in altri termini si avvera, inducendo nuovi soggetti economici ad acquistare i medesimi titoli. Tra questi, man mano che i valori crescono, si annoverano sempre più soggetti solitamente restii ad acquistare strumenti finanziari dal rischio elevato. Quando il valore dei titoli scende repentinamente e si assiste a un cambiamento radicale delle prospettive economiche retrostanti, si parla di scoppio della bolla speculativa. L'eccesso di acquisto di un diritto, infatti, ad un certo punto si arresta. Le cause possono essere almeno tre:

• è difficile trovare nuovi investitori disposti ad acquistare ulteriori diritti ad un prezzo che nel frattempo è diventato elevato;
• chi ha comperato diritti in precedenza è spinto a vendere i titoli per monetizzare il guadagno;
• le ottimistiche prospettive di guadagno precedentemente formulate possono essere riviste e ridimensionate.

Alla fase di crescita dei valori segue dunque una fase opposta, durante la quale si assiste ad un calo considerevole delle quotazioni. All'eccesso di vendite contribuiscono la consapevolezza che, di fronte a prospettive economiche meno ottimistiche, i valori dei titoli trattati sono destinati a calare e la volontà di molti possessori di titoli di cederli prima che si verifichino ulteriori diminuzioni del valore.

Torniamo alla non linearita’ dei mercati riportando una ricerca del MIT che ha evidenziato come la frequenza dei crolli di mercato segue una legge di potenza cosi’ come fanno i terremoti (vedi altri post sul mio blog su questo tema) e altri sistemi naturali. Ma la cosa strana e’ che il mercato non ha nulla di naturale essendo un mondo artificiale. Il mercato e’ pieno di casualita’, ma alla fine della giornata emerge un chiaro pattern che combacia con i pattern evidenziati in sistemi diversi come terremoti, distribuzione delle dimensioni delle citta’ e le parole in un vocabolario. Gli studiosi del MIT hanno anche trovato che le ampie fluttuazioni dei prezzi sono indotte dai partecipanti al mercato quando essi si trovano ad operare sotto pressione. Come in Giappone, per esempio, hanno costruito palazzi che resistono a sismi di forte entita’ ed evitare tante vittime, allo stesso modo bisogna fare in economia anche se e’ molto difficile. Oltre ai crolli del mercato, anche i volumi, le azioni vendute/comprate in un giorno e i prezzi delle azioni seguono una legge di potenza. Questo vuol dire per esempio, che il numero di giorni in cui il prezzo di una data azione si muove del 1% e’ 8 volte il numero di giorni in cui l’azione si muove del 2%, che a sua volta sara’ 8 volte il numero di giorni che il prezzo dell’azione si muove del 4% , che sara’ 8 volte il numero di giorni in cui il prezzo dell’azione si e’ mosso del 8% e cosi via. Per comprendere questi pattern il team del MIT ha analizzato i grossi azionisti, come i fondi comuni di investimento con piu’ di 100 milioni di dollari in attivo. Anche loro seguono una legge di potenza; il numero di azionisti che gestiscono 1 miliardo di dollari e’ il doppio di quelli che gestiscono 2 miliardi che a sua volta e’ il doppio di quelli che gestiscono 4 miliardi e cosi via (per chi di voi mi segue da tempo si sara’ accorti che questa altro non e’ che la cosiddetta legge di Zipf). Quando gli enti, come quelli che gestiscono i fondi comuni, che possono muovere grosse quantita’ di soldi si trovano a lavorare sotto pressione si possono avere grosse fluttuazioni di prezzi e la possibilita’ quindi di una bolla che a tendere puo’ diventare un vero e proprio crollo. Questi e altri studi dimostrano in modo inequivocabile che i crolli del mercato sono un chiaro segno di criticita’ auto-organizzata del mercato stesso. Le forti fluttuazioni delle quotazioni in borsa, come gli improvvisi crolli sono determinati dal loro naturale funzionamento, anche in assenza di fragilità strutturale o di interferenze malavitose criminali. Lo stato di non equilibrio è uno stato critico e quindi presenta cambiamenti improvvisi ed inspiegabili, che fortunatamente sono rari, come rari sono i terremoti catastrofici. Le gigantesche e rovinose crisi finanziarie, anche se rare (e più rare sono, più sono nefaste) sono eventi ordinari del tutto naturali e seguono le stesse leggi fisiche dei terremoti. Un’altra ricerca fatta all’Istituto dei Sistemi Complessi in New England ha trovato dei segnali premonitori dei crolli del mercato usando dei nuovi strumenti statistici sviluppati nell’ambito della teoria della complessita’. Questo lavoro suggerisce che il panico che porta ai crolli del mercato deriva da un’aumentata mimicita’ cioe’ della serie che ognuno copia l’altro. Un significativo aumento della mimica nel mercato si e’ presentato per esempio nell’anno precedente ad ognuno dei crolli degli ultimi 25 anni. Quando gli investitori copiano molto da vicino gli spunti degli altri e’ facile entrare in una situazione di panico che coinvolge il mercato. Quando i grandi investitori iniziano a vendere delle azioni, essi guidano il prezzo in basso in quanto la vendita genera paura nei piccoli investitori che iniziano a vendere anche loro. Se questo loop va fuori controllo il mercato entra in uno stato di panico. Quest’ultimo in economia come in altri aspetti della vita, puo’ essere generato da reali minacce esterne al sistema ma anche da nervosismo auto-generato internamente al sistema. Indipendentemente dal fatto che la minaccia e’ reale o immaginaria, un sistema vivente entra in uno stato di panico quando e’ sopraffatto da agitazione, ansia e paura. Maggiore e’ il numero di organismi presenti nel sistema e piu’ catastrofici sono gli effetti generati dal panico. Cercare di prevedere il comportamento di sistemi sociali ed economici in generale e’ molto complicato. Essi sono composti da agenti umani, tutti con i loro interessi personali, strategie e obiettivi. Ci sono comunque dei casi in cui le interazioni tra individui danno origine ad un comportamento collettivo. In questi casi, la previsione e’ possibile in quanto se gli individui si muovono insieme lo spazio dei possibili risultati del sistema si rimpicciolisce. In questo modo se il panico e’ realmente la causa delle crisi finanziarie, se si riesce a quantificarlo si potrebbe pensare di prevedere quando queste crisi si presenteranno. Proviamo allora a rispondere a queste due questioni:

· E’ possibile quantificare il panico?

· E’ possibile usare il panico per prevedere le crisi del mercato?

Nell’economia tradizionale i prezzi riflettono le aspettative degli individui in base alle notizie: solo le informazioni esterne al sistema possono guidare le decisioni. In realta’, i mercati sono delle vere e proprie reti di influenza (Fig. 1): le persone parlano tra loro e guardano quello che fanno gli altri prima di decidere cosa fare. Questo significa che per avere il quadro completo del sistema, bisogna considerare anche l’imitazione interna al sistema stesso.

                         Economia tradizionale                                            Sistemi complessi

Fig. 1 Confronto tra la prospettiva del mercato tradizionale, dove solo le notizie dall’esterno influenzano le decisioni dei singoli agenti (nodi), e quella complessa dove viene considerata l’interazione interna tra gli agenti.

Il gruppo di studiosi del New England ha costruito un modello includendo entrambi i fattori e verificato il comportamento di tale modello sui dati economici per quantificare i due effetti. Per semplificare, il sistema puo’ essere pensato come una rete completamente connessa con N nodi, dove ogni nodo puo’ assumere i valori binari +1 o -1. Ad ogni step temporale, un nodo guarda i primi vicini, ne prende uno a caso, e con una certa probabilita’, copia quello che sta facendo. Alcuni nodi sono fissi e non possono cambiare il loro valore. I nodi che fluttuano nel tempo rappresentano gli investitori mentre quelli fissi le notizie economiche provenienti dai mass media.

Alcune volte il valore delle azioni dipende dalle notizie e altre volte dalla copia dei primi vicini. Il valore binario che le azioni possono assumere rappresenta il segno del rendimento. Il numero di nodi fissi (notizie) che influenzano il valore delle azioni positivamente puo’ essere indicato con la lettera U mentre il numero che influenza il valore delle azioni negativamente puo’ essere indicato con D. Questo modello e’ simile a quello di Ising nel senso che riesce a descrivere la transizione da stati ordinati a disordinati e viceversa. I parametri importanti che determinano il comportamento di questo modello sono due:

· Il rapporto tra i collegamenti (links) esterni ed interni (cioe’ l’influenza delle notizie (U+D)/N)

· La frazione dei nodi positivi (cioe’ il rapporto (U-D)/N).

Qui di seguito i risultati dell’applicazione del modello a dei dati reali. E’ stato considerato l’indice Russel 3000 che comprende le 3000 azioni americane piu’ negoziate in borsa. La figura 2 indica il co-movimento delle azioni nel tempo nel senso che rappresenta il numero di giorni dell’anno in cui una frazione del mercato si muove in alto (o in basso). Intuitivamente se in media piu’ del 50% del mercato si muove nella stessa direzione (in alto o in basso) questo rappresenta un co-movimento. Nel 2000 per esempio la curva mostra un picco a 1/2 il che significa che il prezzo del 50% di azioni si sta muovendo in alto e il 50% in basso. Le linee continue rappresentano le distribuzioni sperimentali mentre le linee tratteggiate rappresentano il risultato del modello. Come si vede il fit e’ molto buono.

 

Fig. 2 Sull‘asse verticale e’ riportato la frazione di giorni dell’anno in cui una certa frazione di azioni (asse orizzontale) si e’ mossa in alto (rendimento positivo).

Nei 6 anni riportati in figura 2, si vede che avvicinandosi al 2008 la curva si appiattisce indicando che la probabilita’ di qualsiasi frazione e’ sempre la stessa. Quindi la probabilita’ che una larga parte del mercato si muova nella stessa direzione (in alto o in basso), in qualsiasi giorno dell’anno aumenta drammaticamente. Un livello cosi alto di co-movimento puo’ dare origine ad un comportamento collettivo e quindi ad una crisi finanziaria. Notare come dal 2000 al 2008 il valore del parametro U diminuisce indicando chiaramente una minore influenza delle notizie dei mass media sul sistema (i nodi fissi) e quindi una maggiore tendenza all’imitazione interna. Analiticamente la probabilita’ di co-movimento e’ data da:

dove N e’ il numero di azioni, k il numero di azioni con rendimento positivo e le parentesi indicano i coefficienti binomiali. Il comportamento del modello e’ controllato dall’intensità’ degli stimoli esterni U e D rispetto a quelli delle interazioni interne alla rete. Quando le interazioni interne sono deboli in confronto alle forze esterne (D, U>>1), la distribuzione e’ normale. Quando le interazioni interne sono forti (U e D piccoli) allora la distribuzione inizia a diventare uniforme, diventando esattamente uniforme in corrispondenza del valore critico D=U=1, dove l’influenza esterna ha l’intensita’ di un singolo nodo. Nella parte alta della figura 3 e’ riportato l’andamento temporale del parametro U. Mentre negli anni 90 c’era una situazione salutare per la borsa la stessa cosa non si puo’ dire oggi poiche’ ognuno cerca di copiare l’altro. La seconda immagine della figura 3 indica gli 8 giorni con crollo del prezzo significativo nel periodo 1985-2010 indicati con delle linee rosse. Questi sono stati raggruppati in 4 finestre temporali indicate in celeste. Come utilizzare il parametro U per individuare questi giorni?

 

Fig. 3 Il pannello in alto mostra l’andamento del parametro U nel tempo. Quello in basso invece mostra la variazione annuale del parametro U come frazione della sua standard deviation calcolata sugli anni precedenti.

Piu’ che il valore di U e’ importante considerare il cambiamento di U da un anno a quello precedente diviso la standard deviation delle sue fluttuazioni. Ogni crollo e’ preceduto da un semplice pattern. Facciamo partire il nostro orologio quando il cambiamento di U scende al di sotto di 2 standard deviations: all’interno del prossimo anno ci sara’ un crollo significativo del mercato. Si azzera l’orologio una volta che la variazione di U diventa positiva di nuovo. Se si segue questo pattern si puo’ vedere come tutti gli otto crolli vengono previsti correttamente. Non ci sono ne’ falsi positivi ne’ falsi negativi. Questo ricorda molto da vicino il comportamento collettivo dei sistemi complessi. Una volta che il sistema subisce una perturbazione (rilassamento) c’e’ un rilascio improvviso di energia e poi molto lentamente il sistema si porta di nuovo verso uno stato di criticita’ pronto a dare origine ad una nuova catastrofe (o valanga nell’esperimento del mucchietto di sabbia di Per Back...). Costruire modelli e’ divertente, e anche se tutti i modelli sono sbagliati, qualcuno di questi e’ certamente utile.

Un altro modello che merita la nostra attenzione e’ quello proposto da due fisici polacchi e che utilizza il cosiddetto esponente di Hurst per fare una previsione statistica dei crolli del mercato. Vediamo di cosa si tratta. Anche in questo studio viene evidenziata la complessita’ del sistema finanziario e della sua non predicibilità. Comunque dalla meccanica statistica sappiamo che non c’e’ bisogno di sapere dove si muovera’ esattamente una particella del sistema per trovare l’equazione di stato di questo sistema. Ricordiamo che l’equazione di stato fornisce una relazione matematica tra due o più variabili di stato associate alla materia, come temperatura, pressione, volume o energia interna. Le equazioni di stato sono utili nella descrizione delle proprietà dei fluidi (e delle loro miscele), dei solidi e persino per descrivere l'interno delle stelle. L’equazione di stato e’ sufficiente nelle applicazioni pratiche per darci un’informazione globale del sistema grazie alle variabili macroscopiche che sono legate a quelle microscopiche a noi inaccessibili. In molti casi questa conoscenza e’ sufficiente ad indicarci la direzione in cui il sistema evolvera’. Allo stesso modo i due fisici si chiedono se e’ possibile trovare dei parametri macroscopici relativi al mercato che possano essere degli indicatori delle dinamiche interne del sistema finanziario. Come gia’ detto la distribuzione dei rendimenti non segue esattamente una legge Gaussiana quanto invece una legge di potenza e quindi e’ normale attendersi delle correlazioni di lungo periodo cioe’ una sorta di lunga memoria del mercato. Quindi e’ giusto andare a cercare tali correlazioni nei dati storici dei mercati azionari. Cio’ e’ stato fatto da questo team polacco utilizzando la cosiddetta tecnica DFA (Detrended Fluctuations Analysis). Questa applicata alle serie temporali degli strumenti finanziari permette di estrarre l’esponente di Hurst che misura il livello di persistenza di un dato segnale. Se il sistema coincidesse con un cammino casuale il valore dell’esponente H sarebbe di 0.5 indicando una serie di eventi indipendenti: ogni variazione non è influenzata dalle precedenti e nemmeno influenzerà quelle future. Se invece l’esponente e’  maggiore di 0.5 questo sta a significare che la distanza coperta dal sistema è assai maggiore di quella predetta dal random walk model: il sistema risulta caratterizzato da un effetto memoria per il quale ogni osservazione è influenzata da quelle passate ed influenzerà quelle future. Se questo esponente e’ diverso da 0.5 questo implica l’esistenza di correlazioni a lungo range. In particolare se l’esponente di Hurst e’ maggiore di 0.5 allora il segnale e’ persistente mentre se e’ minore di 0.5 allora il segnale e’ anti-persistente. Per serie persistente, intendiamo una serie caratterizzata da una dipendenza positiva tra le variazioni generate dal processo: se nell’ultima osservazione abbiamo registrato un incremento (decremento) è più probabile che l’osservazione successiva registri un ulteriore incremento (decremento). La probabilità di registrare due variazioni di segno concorde risulta tanto più alta quanto piu’ H si avvicina ad uno. Per anti-persistente invece intendiamo una serie che se in un dato periodo ha subito un incremento (decremento) è più probabile registrare un successivo decremento (incremento) che un ulteriore incremento (decremento). La serie risulta più volatile di una serie casuale (poiché caratterizzata da più frequenti inversioni) tanto più il valore di H si avvicina a zero. Prima di un cambio drammatico del prezzo di uno strumento finanziario ci si aspetta che esso venga preceduto da uno stato di eccitazione del mercato (nervosismo) che a sua volta e’ riflesso dalla forma dei cambiamenti di prezzo dei giorni seguenti. Questi cambiamenti dovrebbero diventare meno correlati prima di un crollo nel trend del segnale. Al contrario quando il trend nel mercato e’ forte e ben determinato, un aumento (diminuzione) del prezzo visto nel passato recente rende piu’ probabile un segnale in crescita (decrescita) anche nel futuro immediato, In altre parole l’esponente di Hurst dovrebbe mostrare una diminuzione significativa e repentina se il trend sta cambiando velocemente la sua direzione come in caso di crollo del mercato. Tra le varie tecniche disponibili per calcolare l’esponente di Hurst i due studiosi hanno scelto quella del DFA essendo piu’ robusta e applicata all’indice Dow Jones Industrial Average (DJIA). Nella fig 4 possiamo vedere il trend dell’indice DJIA e il valore dell’esponente di Hurst indicato con alfa per diversi valori di N che indicano la lunghezza delle finestre temporali in cui viene diviso il segnale come richiesto dalla tecnica DFA. Notiamo che per N=350 e 420 l’esponente di Hurst e’ molto simile cosa non vera invece per N=210. All’aumentare di N si nota come l’andamento dell’esponente diventa piu’ liscio (smooth). Comunque la scelta di N e’ del tutto empirica e non c’e’ alcuna legge per determinarlo. Per l’analisi del segnale DJIA riportato nella figura 5 il valore di N scelto e’ stato di 240. Il primo crollo analizzato e’ stato quello del 1929 il cui dettaglio e’ mostrato in fig 6. Si vede chiaramente come l’abbassamento repentino del valore del DJIA corrisponde ad un abbassamento dell’esponente di Hurst con quest’ultimo che raggiunge il minimo assoluto del periodo a circa 0.45, 2 settimane prima del crollo. Per verificare se questa coincidenza fosse semplicemente dovuta al caso i due fisici polacchi hanno ripetuto la stessa analisi per il crollo del 1987 e 1998 confermando un abbassamento dell’esponente di Hurst (nervosismo dei mercati) alcune settimane prima del crollo del mercato. In definitiva essi hanno provato che l’esponente di Hurst si abbassa drasticamente prima di ogni crollo dell’indice DJIA. Questo conferma che l’esponente di Hurst puo’ essere usato come misura dello stato attuale di eccitazione del mercato anche se va ricordato che fattori esterni agli investitori possono accelerare o decelarare il valore dell’esponente di Hurst e mettere in crisi la previsione.

Prima di chiudere il post va precisato che i modelli descritti fin qui e tanti altri simili che si possono trovare in rete non hanno la pretesa di predire quando ci sara’ il prossimo crollo finanziario o il prossimo terremoto. Essi nascono con il solo intento di fare una previsione statistica. Nessuno sapra’ la data e l’ora esatta del prossimo crollo finanziario o terremoto. L’unica cosa possibile e’ calcolare la probabilita’ che in un certo periodo possa presentarsi una crisi finanziaria o un terremoto. E niente di piu’.

 

Fig 4, Andamento nel tempo dell’esponente di Hurst indicato con alfa per l’indice DJIA nel periodo Feb 1913-Giu 1914 per tre differenti finestre temporali N. I valori di alfa sono stati moltiplicati per 2 e spostati lungo l’asse verticale per apprezzare le differenze.

 

Fig 5. Andamento dell’indice DJIA tra il 1896 e 2003. Gli eventi economici piu’ importanti sono riportati sulla curva.

 

Fig 6. Il crollo del 1929. In alto l’andamento del DJIA e in basso il corrispondente esponente di Hurst, In corrispondenza del crollo dei prezzi si nota un repentino abbassamento dell’esponente.

Come emerge l’innovazione?

 

L’innovazione e’ una delle forze trainanti del mondo. La creazione costante di nuove idee e la loro trasformazione in tecnologie e prodotti e’ di sicuro una pietra angolare della nostra societa’. Questo spiega perche’ molte Universita’ e Istituti sono interessati a questo tipo di processo che ancora oggi appare misterioso e poco capito. Molti ricercatori hanno dedicato tempo a questo studio con lo scopo di capire come l’innovazione prende forma e i fattori che la guidano. Ad oggi questo approccio ha avuto un successo limitato. Anche se il tasso con cui avvengono le innovazioni e’ stato attentamente misurato e si e’ visto che segue dei pattern ben definiti in circostanze anche diverse tra loro, nessuno e’ ancora riuscito a spiegare come nascono le nuove idee e perche’ solo certi fattori e non altri ne influenzano la velocita’.

Tutto questo, oggi sembra cambiare grazie ad un lavoro di Vittorio Loreto della Sapienza di Roma che insieme ad altri suoi colleghi tra cui il famoso matematico Steven Strogatz noto per aver pubblicato un libro sul fenomeno della sincronizzazione, hanno creato un modello matematico che riproduce accuratamente i pattern seguiti dall’innovazione. Questo lavoro da’ vita ad un nuovo approccio nello studio dell’innovazione e di come essa emerga da quello che gia’ esiste. La nozione che l’innovazione nasca dall’interazione tra l’attuale e il possibile e’ stata formulata per la prima volta dal teorico Stuart Kauffmann nel 2002 con l’idea dell’ ”adiacente possibile” come strategia seguita dall’evoluzione biologica. L’adiacente possibile e’ l’insieme di tutte le cose (idee, parole, musica, molecole, genoma, tecnologie....) che sono molto vicine (ad un passo) a quello che esiste oggi. Esso connette la realizzazione attuale di un particolare fenomeno e lo spazio delle possibilita’ ancora inesplorate.

Illustrazione matematica dell’adiacente possibile in termini di grafo che si espande dalla situazione (a) a quella in (b) ogni volta che un passante visita un nodo per la prima volta (il nodo in bianco in (a).

Questa idea nonostante il suo fascino e’ difficile da modellizzare in quanto lo spazio delle possibilita’ inesplorate include non solo tutte le cose immaginate e aspettate ma anche quelle che sono inaspettate e difficili da immaginare. Inoltre mentre la prima e’ difficile da realizzare la seconda e’ molto prossima all’impossibile. Per non parlare del cambiamento continuo dello spazio delle possibilita’ inesplorate. Anche se la potenza creativa dell’ “adiacente possibile” e’ largamente apprezzata a livello di curiosita’ la sua importanza nella letteratura scientifica e’ sottostimata stando a quello che dice Loreto. Nonostante tutta questa complessita’, l’innovazione comunque sembra seguire dei pattern prevedibili e facilmente misurabili conosciuti oggi come leggi grazie alla loro ubiquita’. Una di questi leggi e’ quella che prende il nome di “legge di Heaps”; essa stabilisce che il numero di cose nuove cresce a un tasso sottolineare o in altre parole secondo una legge di potenza della forma:

V(n) = kn^β          dove β e’ compreso tra 0 e 1.

Questa legge attribuita ad Heaps ma in realta’ scoperta da Gustav Herdan stabilisce che in linguistica il numero di parole distinte V (asse y del grafico sotto) presenti in un documento dipende dalla sua lunghezza n (numero totale di parole – asse x del grafico). In altre parole se supponiamo di avere una lista ordinata di parole in un testo, man mano che la scorriamo troveremo delle parole nuove che non saranno mai occorse prima e quindi riportando il numero di parole diverse in funzione del numero di tutte le parole occorse fino ad un dato punto si ottiene per grandi numeri la legge di potenza di Heaps.

Le parole spesso vengono pensate come una sorta di innovazione, e il linguaggio si evolve costantemente man mano che appaiono nuove parole e quelle vecchie vanno in disuso. E questa evoluzione segue la legge di Heaps con un coefficiente β compreso tra 0 e 1. Pensiamo ad un vocabolario degli inizi del 1900 e confrontiamolo con uno dei giorni nostri. Sicuramente in quello del 1900 non troveremo termini come internet, rete sociali, crowdfunding, computer e cosi via. Il numero di parole totali contenute nel vocabolario di oggi e’ decisamente maggiore di quello del 1900 e la differenza tra i due vocabolari e’ guidata dalla legge di Heaps.

Un altro pattern statistico seguito dal processo di innovazione e’ quello della legge di Zipf’s che descrive come la frequenza di una innovazione e’ legata alla sua popolarita’. Questa legge venne descritta per la prima volta dal linguista e filologo statunitense G. K. Zipf ed oggi essa trova applicazione nei campi piu’ svariati essendo diventata la controparte della distribuzione Gaussiana nell’ambito delle scienze sociali. Questa legge mette in relazione la frequenza di un evento con la posizione in classifica del verificarsi di questo evento, in un ordinamento decrescente (rango). Fra i casi piu’ famosi in cui la legge viene verificata abbiamo le frequenze delle parole negli scritti e la distribuzione della popolazione nelle varie citta’ di uno stato. La legge matematica e’ scritta in questo modo:

f(n)=c/n

dove f e’ la frequenza, c una costante e n il rango, cioe’ la posizione in classifica. All’interno di un testo per esempio la parola piu’ frequente si presenta quasi il doppio delle volte rispetto alla parola in seconda posizione , il triplo della parola in terza posizione e cosi via. In inglese la parola piu’ frequente e’  “the” con una frequenza del 7% seguita da “of” con un 3.5%, da “and,” e cosi via. Ovviamente se un testo fosse scritto disponendo le parole in modo del tutto casuale allora la legge di Zipf non sarebbe valida. Ma non e’ cosi essendo le parole nei testi vincolate da regole (sintassi, grammatica, estetica, ecc) e quindi si ribellano alla legge Gaussiana. Zipf spiega la legge trovata che in seguito prendera’ il suo nome ricorrendo al cosiddetto principio del minimo sforzo che descrive la normale tendenza di certi fenomeni a cercare di ottenere il massimo risultato con il minimo impiego di forze. Facciamo un esempio considerando il romanzo dei promessi Sposi. Qui di seguito la classifica della parole piu’ usate dal Manzoni con la colonna E ed F del file excel contente il logaritmo in base 2 del rango e della frequenza relativa. Prendiamo il logaritmo perche’ essendo una legge di potenza in questo modo avremo una retta come si vede nel grafico qui sotto.

Sia la legge di Zipf che quella di Heaps sono leggi empiriche nel senso che le conosciamo solo perche’ le misuriamo. Ma perche’ i pattern prendono proprio questa forma nessuno lo sa. Quello che serve non e’ tanto modellizzare l’innovazione inserendo i numeri osservati in equazioni matematiche quanto avere un modello che produce questi numeri a partire da principi primi (postulati). E qui entra in gioco il lavoro di Loreto e colleghi. Il concetto di base e’ proprio quello dell’adiacente possibile. Come sappiamo l’evoluzione non procede per salti. La natura come anche la tecnologia cerca di innovare partendo dal materiale che ha gia’ a disposizione attraverso una sua opportuna ricombinazione. L’innovazione quindi puo’ essere rappresentata come l’esplorazione di uno spazio fittizio (biologico, fisico, tecnologico ecc.) possibile che si allarga di volta in volta con nuovi elementi. E’ come dire che da cosa nasce cosa.

Il team di ricercatori per la prima volta ha creato un modello di questo tipo che spiega i pattern dell’innovazione. Sono partiti da quella che e’ conosciuta come Urna di Polya: un’urna riempita con palline di diversi colori. Una pallina viene pescata a caso, esaminata e reinserita nell’urna insieme ad una certa quantita’ di nuove palline dello stesso colore. Questo aumenta la probabilita’ che nelle successive estrazioni venga selezionata una pallina proprio di questo colore. Questo modello viene utilizzato dai matematici per esplorare il cosiddetto effetto di rinforzo o del “ricco che diventa sempre piu’ ricco” da cui emerge la legge di potenza. Qui di seguito il risultato di due simulazione dell’urna di Polya partendo con 5 palline rosse, 4 nere, 3 gialle, 2 verdi e una blu. Nel primo caso (grafico a sinistra) anche se inizialmente le palline verdi sono meno di quelle rosse a partire dalla decima estrazione circa il loro numero inizia ad aumentare e da quel momento in poi’ cresce sempre di piu’ diventando quello dominante. Sulla destra una seconda simulazione dove si vede che addirittura le palline blu (le minoritarie inizialmente) iniziano a competere con quelle rosse (all’inizio quelle maggioritarie). In questo caso vediamo al lavoro il meccanismo di rinforzo ma non c’e’ nessun elemento di innovazione, cioe’ nessuna novita’.

L’urna di Polya quindi e’ un buon punto di partenza per costruire un modello dell’innovazione anche se essa non produce la crescita sottolineare di Heaps. In altre parole il modello di Polya permette tutte le conseguenze aspettate per l’innovazione (quelle di scoprire un certo colore) ma non considera le conseguenze inaspettate di come l’innovazione influenza l’adiacente possibile. Per questo motivo il gruppo di fisici ha modificato il modello dell’urna di Polya per avere la possibilita’ che una volta scoperto un nuovo colore nell’urna questo possa innescare tutta una serie di conseguenze inaspettate. Questo nuovo modello e’ stato chiamato urna di Polya che innesca innovazione.

Si parte con un’urna riempita con palline colorate. Una pallina viene prelevata a caso dall’urna, esaminata, e rimessa nell’urna. Se il colore e’ gia’ stato visto prima, allora un certo numero di palle dello stesso colore viene inserito nell’urna. Ma se il colore e’ nuovo (cioe’ visto per la prima volta) allora un certo numero di palline di un nuovo colore viene aggiunto all’urna. Nel disegno seguente a sinistra viene riportato quello che accade con il semplice modello dell’urna di Polya e a destra con quello modificato da Loreto e colleghi. Le palline colorate rappresentano canzoni che abbiamo ascoltato, pagine web visitate, invenzioni, idee o qualsiasi altra esperienza umana o prodotti della nostra creativita’. Una serie di invenzioni viene idealizzata con una sequenza S di elementi generati tramite estrazioni successive dall’urna U. Esattamente come l’adiacente possibile quando capita qualche cosa di nuovo (una pallina di colore mai visto prima), i contenuti dell’urna stessa cambiano (si allargano). Matematicamente viene considerata una sequenza ordinata S costruita prelevando le palline dall’urna contenente inizialmente un certo numero di palline distinte. Sia il numero di palline nell’urna che nella sequenza aumentano nel tempo. A sinistra vediamo come dopo l’estrazione di una pallina di colore grigio, questa viene rimessa nell’urna insieme a 4 palline dello stesso colore grigio. A destra invece il nuovo modello fa vedere come dopo l’estrazione di una pallina di colore rosso dall’urna, questa viene rimessa dentro insieme ad una copia di 4 palline dello stesso colore rosso e 4 palline di colore non contenuto nell’urna.

Eseguendo le simulazioni al computer, Loreto e i suoi colleghi hanno calcolato come cambia nel tempo il numero di nuovi colori presi dall’urna e la loro frequenza. La sorpresa e’ stata che questo modello riproduce entrambe la legge di Heaps e quella di Zipf e quindi per la prima volta sono state riprodotte le osservazioni empiriche partendo da un postulato. Il team ha mostrato anche che il modello predice come le innovazioni compaiono nel mondo reale. Il modello infatti, predice accuratamente come si presentano gli eventi di modifica delle pagine di Wikipedia, la sequenza delle parole nei testi e di come gli umani scoprono nuove canzoni in un catalogo online di musica. Qui di seguito la legge di Heap e di Zipf predette dai risultati analitici e confermati dai risultati numerici delle simulazioni.

Questi sistemi coinvolgono 2 diverse forme di scoperta. Da una parte, ci sono cose che gia’ esistono ma sono nuove per l’individuo che le trova come per esempio le canzoni online e dall’altra le cose che non esistevano prima e che sono nuove per il mondo intero come per esempio le modifiche delle pagine di Wikipedia. Il team parla di novita’ nel primo caso (una cosa nuova per l’individuo) e di innovazione nel secondo caso (una cosa nuova per il mondo). Curiosamente lo stesso modello spiega entrambi i fenomeni. Sembra che il pattern di come si scoprono le novita’ e’ lo stesso che regola l’emergenza dell’innovazione dall’adiacente possibile. Questo solleva delle questioni interessanti, non ultima quella del perche’ le cose dovrebbero andare proprio in questo modo. Ma apre anche un interno nuovo modo di pensare all’innovazione e agli eventi che portano alle novita’. Questi risultati forniscono un punto di partenza per un’analisi piu’ approfondita dell’adiacente possibile e la diversa natura degli eventi di innesco nell’evoluzione biologica, linguistica, culturale e tecnologica. Non ci resta che aspettare e vedere come lo studio dell’innovazione evolvera’ dall’adiacente possibile come risultato di questo lavoro.

Qui l’articolo di Loreto e colleghi per chi vuole approfondire l’argomento: Link

La matematica del Sudoku

 

Il gioco giapponese del sudoku, affonda le sue radici nei quadrati magici studiati da Eulero.

Un quadrato magico è uno schieramento di numeri interi distinti in una tabella quadrata tale che la somma dei numeri presenti in ogni riga, in ogni colonna e in entrambe le diagonali dia sempre lo stesso numero; tale intero è denominato la costante magica del quadrato.

Il Sudoku si e’ subito diffuso in tutto il mondo, come era gia’ successo per il cubo di Rubik, il gioco del 15 e altri puzzles che periodicamente ritornano di moda.

Le regole sono molto semplici e occorre soltanto una matita e un foglio di carta. Si gioca su una tabella di nove per nove caselle in ognuna delle quali si deve inserire una cifra, da uno a nove. Ogni riga e ogni colonna deve contenere tutte le cifre da uno a nove senza ripetizioni. Condizione ulteriore, e questa è la novità, anche ogni blocco di caselle tre per tre, contrassegnato da linee più marcate, deve contenere le nove cifre, senza ripetizioni. Il Sudoku si presenta con una parte delle cifre già inserite nelle caselle (vedi figura 1). Per essere un vero Sudoku, deve inoltre avere un’unica soluzione. Richiede normalmente dai dieci minuti alla mezz’ora per essere risolto. Il nome originale del gioco, lanciato vent’anni fa dalla Nikoli, una casa editrice giapponese specializzata in giochi, era Suji wa dokushin ni kagiru ovvero “Numeri limitati ad una sola persona”, un nome sintetizzato in Sudoku, “Numeri unici”.

 

Figura 1: Raffigurazione di un sudoku come si presenta al giocatore e la usa soluzione.

Per risolvere un Sudoku, esistono diverse tecniche a seconda della difficolta’ del Sudoku stesso. Una delle tecniche piu’ semplici e’ quella della “Singola posizione”.

Si sceglie una riga, una colonna o un box (il quadrato 3x3) e si analizzano i numeri che ancora non sono stati inseriti. A causa della presenza dei numeri iniziali, le posizioni dove poter inserire un nuovo numero sono limitate. Spesso ci sono 2 o 3 celle dove poter inserire un numero ma se si e’ fortunati ce ne sara’ solo una. Per esempio nel sudoku della figura 2, scegliendo la riga verde si vede subito che il numero 7 puo’ essere inserito solo sull’ultima celle verde verso destra.

Questo perche’ in qualsiasi altra cella verde lo avremmo inserito avrebbe generato delle colonne con due cifre 7.

 Figura 2: Tecnica della singola posizione.

Un'altra tecnica semplice e’ quella del “singolo candidato”. In questo caso ce' bisogno di una matita per scrivere in ogni cella i possibili candidati, esaminando le colonne, righe e box circostanti. Nel caso in cui il candidato e’ unico, immediatamente puo’ essere associato alla cella. In figura 3, viene mostrato un esempio di questa tecnica.

 Figura 3: Tecnica del singolo candidato (da sinistra verso destra).

Nella cella indicata in verde nel sudoku di centro, l’unico candidato e’ il 2, mentre nella cella sopra quella contenente il numero 8, i possibili candidati sono 1 e 2. A destra viene mostrato il sudoku dopo l’inserimento di tutti i candidati. Si vede immediatamente che, ci sono 3 celle (in verde) dove c’e’ un unico candidato che quindi puo’ essere associato definitivamente alla cella.

Esiste una tecnica che non dice quale numero inserire in una cella, ma aiuta invece a determinare quali sono le celle dove non e’ possibile inserire un numero. Con l’esempio riportato in figura 4, e’ facile capire come funziona questa tecnica chiamata la tecnica delle linee candidate.

 Figura 4: Tecnica della singola linea (da sinistra verso destra).

Nel quadrato indicato in verde ci sono due possibili celle (indicate in verde piu’ scuro) dove poter inserire il numero 4. Questo automaticamente fa si che e’ possibile rimuovere qualsiasi altro 4 lungo la colonna individuata dai due 4 del box in basso a sinistra come mostrato in figura 4 nelle ultime due griglie a destra.

Esistono altre tecniche simili che qui non vedremo.

Ma nel caso in cui il Sudoku sia particolarmente complicato quale tecnica usare? Ce ne sono alcune che sono molto semplici da capire ma complicate da applicare. Partiamo con la prima, la cosiddetta tecnica delle “catene forzate”. Per applicarla e’ necessario avere a disposizione piu’ di un foglio per prendere appunti.

   Figura 5: Tecnica della catena forzata (da sinistra verso destra).

Osservando la figura 5, si capisce in che modo la scelta del valore 1 nella cella C3R1 (colonna terza e riga 1) forza il valore della cella C1R4 a 5. Infatti nel primo passaggio la scelta iniziale del 1, forza il valore 4 nella cella C3R4, che a sua volta forza il valore 7 nella cella C6R4 e quindi il valore 5 nella cella C1R4.

Si ripete poi la stessa operazione ma anziche’ partire col numero 1, si parte col numero 2 (vedi figura 6).

 Figura 6: Tecnica della catena forzata (da sinistra verso destra).

In questo caso la catena che viene fuori e’ molto lunga, ma alla fine forza sempre il numero 5 nella cella C1R4. Poiche’ due diverse scelte portano allo stesso numero nella cella C1R4 questo significa che il 5 e’ il numero da associare a questa cella.

La seconda tecnica normalmente utilizzata per risolvere Sudoku complessi e’ quella che va sotto il nome di X-Wing. Osserviamo la figura 7, partendo dalla riga 4 e 9 dove abbiamo 4 celle con il 6 un possibile candidato.

   Figura 7: Tecnica X-Wing

Il trucco per capire la tecnica del X-Wing e’ quello di immaginare cosa succederebbe se uno scegliesse il 6 in una di queste quattro celle. Se scegliamo il 6 in C3R4 questo implica che non e’ possibile avere lo stesso numero in C9R4 e C3R9 come si puo’ vedere dalla griglia centrale in alto della figura 7. Questa scelta forza la cella C9R9 ad avere 6 come candidato. In altre parole un 6 nella cella in alto a sinistra del quadrato iniziale (vedi griglia in basso a sinistra) forza lo stesso valore nella cella in basso a destra. Esattamente con la stessa logica, un 6 nell’angolo in alto a destra del quadrato dovrebbe forzare lo stesso valore nella cella in basso a sinistra (vedi griglia centrale in basso della figura 7). Detto cio’ e’ chiaro che non e’ possibile avere altri 6 nelle due colonne C3 e C9. Questo ci permette di cancellare quasiasi numero 6 che compare come possibile candidato. Nell’esempio di figura 7, e’ possibile rimuovere il 6 da due celle della colonna C9, che lascia la cella C9R1 con un 8.
A causa della grande popolarita’ del Sudoku, diversi matematici e scienziati del computer hanno lavorato su diverse questioni emerse da questo gioco. La prima di queste riguarda il possibile numero di griglie. In altre parole, stabilire qual’e’ il numero di griglie possibili di Sudoku che possono essere create o equivalentemente il numero di modi in cui e’ possibile riempire una griglia 9x9 con i numeri da 1 a 9 soddisfando le regole del Sudoku.

Per rispondere a tale domanda e’ necessario utilizzare tutte le possibili permutazioni e le proprieta’ di simmetria della griglia del Sudoku.

Bertram Felgenhauer del Dipartimento di Scienza dei computer dell’Universita’ di Dresda e Frazer Jarvis del Dipartimento di Matematica dell’Universita’ di Sheffield in Inghilterra, usando la forza-bruta dei computer sono arrivati a calcolare il numero di griglie valide di Sudoku. Un numero veramente grande: 6670903752021072936960 (circa 6.67*10²¹). Senza considerare le regole del Sudoku elencate all’inizio del capitolo, il numero di possibili griglie sarebbe 9⁸¹ . Ovviamente per contare le possibili griglie questo numero dovrebbe essere ridotto eliminando tutte quelle configurazioni che non soddisfano le regole.

Se consideriamo un qualsiasi blocco del Sudoku, questo puo’ avere 9! (362880) possibili configurazioni. I possibili modi con cui arrangiare la “banda” in alto (l’insieme dei tre blocchi da 3x3 celle) saranno dati dal prodotto di 9! del primo blocco per il numero di modi in cui e’ possibile arrangiare il blocco 2 della banda superiore e il numero di modi in cui e’ possibile arrangiare il blocco 3 (quello a destra in alto della griglia del Sudoku).

Questo prodotto e’ uguale a 6.67*10²¹. Comunque se consideriamo la simmetria della griglia del Sudoku questo numero e’ destinato a diminuire. Per simmetrie, intendiamo quelle operazioni che quando applicate alla griglia del Sudoku, esse creano un’altra griglia che e’ essenzialmente equivalente all’originaria. Per prima cosa etichettiamo una griglia del Sudoku come riportato in figura 8.

 

 Figura 8: Griglia del Sudoku etichettata con le lettere.

La colonna ADG e’ chiamata una “pila”, mentre la riga ABC e’ detta una “striscia”.La selezione di specifici valori per uno qualsiasi dei quadrati e’ conosciuta come “Ri-etichettatura”. L’arrangiamento delle cifre da 1 a 9 nel blocco A, e’ un esempio di operazione di ri-etichettatura. Oltre questa operazione, sono possibili anche le:

· Permutazioni delle “strisce”

· Permutazioni delle “pile”

· Permutazioni delle colonne all’interno delle “pile”

· Permutazioni delle righe all’interno delle “strisce”

· Riflessione o rotazione della griglia.

Frazer Jarvis e Ed Russel, in un lavoro intitolato “Mathematics of Sudoku”, hanno individuato 3359323 simmetrie. Una di queste e’ quella rappresentata in figura 9, dove la griglia riportata rimane praticamente la stessa se sottoposta ad una rotazione di 90 gradi e di ri-etichettatura 1—>3—>9—>7—>1 e 2—>6—>8—>4—>2. Il 5 rimane fisso.

 Figura 9: Griglia di Sudoku che rimane la stessa in seguito ad operazione di rotazione e ri-etichettatura

Tenendo conto di tutte le simmetrie, gli autori sono arrivati a stabilire che tutte le possibili griglie differenti del Sudoku sono 5472730538.

Normalmente, il Sudoku deve avere una sola soluzione, altrimenti il puzzle non e’ valido. Per essere sicuri di cio’, i puzzles sono presentati con un numero di cifre gia’ presenti nella griglia iniziale, lasciando al giocatore la deduzione delle rimanenti cifre da inserire nelle celle libere. Al momento il migliore risultato ottenuto sul minimo numero richiesto nella griglia iniziale e’ di 17 cifre. Questo e’stato ottenuto dal professore Gordon Royle dell’Universita’ dell’Australia. Attualmente non si sa se con 16 cifre iniziali il Sudoku ammette una singola soluzione. Tutte le griglie con 17 entrate iniziali, vengono chiamate i Sudoku minimi. Al momento si conoscono 47793 diversi Sudoku minimi.

Per analizzare il gioco del Sudoku e’ possibile anche utilizzare la teoria dei grafi. E’ quello che hanno fatto Agnes M. Herzberg e M. Ram Murty in un loro lavoro apparso sul giornale Notices of the AMS di Giugno/Luglio 2007. E’ possibile pensare alla griglia del Sudoku, come agli 81 nodi di un grafo. Ogni cifra da 1 a 9 puo’ essere colorato in modo diverso, e due nodi possono essere connessi se e solo se le due celle che essi rappresentano si trovano nella stessa riga, colonna o quadrato 3x3. Poiche’ nessuna riga, colonna o blocco 3x3 puo’ contenere piu’ di una volta lo stesso numero, questo significa che il grafo non avra’ connessioni tra nodi dello stesso colore. Nel linguaggio della teoria dei grafi, un grafo colorato senza connessioni tra nodi dello stesso colore si chiama un “grafo colorato proprio”.

Quello che i giocatori di Sudoku, quindi, fanno tutti i giorni, e’ cercare di estendere un grafo parzialmente-colorato (la griglia iniziale) ad un grafo colorato proprio.
Grazie a questa analogia tra Sudoku e grafi, Herzberg e Murty hanno utilizzato le tecniche dei grafi per provare alcuni teoremi riguardanti il Sudoku.

Per esempio, hanno provato che il numero di modi per trasformare un grafo parzialmente colorato e’ dato da un polinomio. Se il valore di questo polinomio e’ zero per una certa griglia Sudoku, allora il puzzle non ha soluzione. Se il valore e’ 1, allora il puzzle ha una sola soluzione e cosi via. Essi hanno anche dimostrato che affinche’ un Sudoku abbia un’unica soluzione, ci devono essere almeno 8 delle 9 cifre presenti nella griglia iniziale come entrate. Se vengono dati solo 7 numeri, allora il puzzle ha almeno due soluzioni.

Tenendo presente, quindi, il risultato di G. Royle, per avere un’unica soluzione dobbiamo garantirci che nella griglia iniziale ci siano almeno 17 numeri e che questi siano rappresentati da 8 diverse cifre. Per esempio con una sequenza del tipo:

1, 2, 3, 4, 5, 6, 9, 2, 2, 3, 4, 1, 1, 9, 4, 7, 2

come entrate iniziali il puzzle avra’ sicuramente una soluzione unica.

E’ possibile pensare che nel caso ci sia un numero di entrate superiore a 17, sia abbastanza probabile avere un’unica soluzione del Sudoku. E invece non e’ sempre cosi. L’articolo di Herzberg e Murty, riporta un esempio di una griglia con 29 numeri iniziali che ha due differenti soluzioni. Niente male per un rompicapo come il Sudoku. Un altro ricercatore, David Eppstein dell’Universita’ della California, ha applicato anche lui la teoria dei grafi per costruire nuovi metodi di soluzione.

Supponiamo di avere un Sudoku che e’ stato risolto parzialmente. Assegniamo ad ogni cella vuota un nodo del grafo, e connettiamo i nodi con archi etichettati coi numeri candidati per la cella. Eppstein definisce un ciclo non ripetitivo, un tour chiuso che non ha due archi (edge) consecutivi con la stessa etichetta e ciclo ripetitivo uno in cui e’ possibile trovare due archi consecutivi con la stessa etichetta. I connettori consecutivi sono quelli che condividono uno stesso nodo (per esempio A e B sotto).

Vediamo come funziona il metodo nel caso di cicli non ripetitivi. In questo caso, per qualsiasi cella C del ciclo, con due archi etichettati con A e B che insistono su di essa, il valore di C puo’ essere solo A o B. Nell’esempio della figura 10, la cella C e’ quella sulla sinistra in basso della griglia. Poiche’ i due archi che insistono su questa cella hanno come numeri 2 e 3 significa che la cella C dovra’ avere uno di questi due numeri. La griglia in alto a sinistra e’ il Sudoku parzialmente completato con altri metodi. In basso a destra invece viene mostrato il puzzle risolto.

 Figura 10: Metodo del ciclo non ripetitivo di Eppstein.

In caso di ciclo ripetitivo, se ad un nodo confluiscono due archi con la stessa etichetta, la cella associata al nodo del grafo non puo’ che avere come valore l’etichetta delle connessioni. Nell’esempio di figura 11, il nodo indicato in nero non puo’ che avere come valore il numero 4.

Figura 11: Metodo del ciclo ripetitivo di Eppstein.

La camminata del cavallo ovvero la matematica della scacchiera

 

  Nel gioco degli scacchi, il cavallo e’ uno dei pezzi a disposizione dei giocatori. Insieme all’alfiere e’ uno dei cosiddetti “pezzi leggeri” in contrapposizione alla regina e la torre che invece vengono chiamati “pezzi pesanti”. La mossa del cavallo puo’ essere descritta come un passo in orizzontale o in verticale seguito da un passo in diagonale in direzione opposta alla casa d’origine. Nella figura 1, sono indicate le mosse ammesse nell’ipotesi che il cavallo occupi una posizione centrale.

 

Figura 1. Le mosse del cavallo.

Fin dall’antichita’ c’e’ stato un grande interesse per quello che va sotto il nome del puzzle del tour del cavallo: determinare  la sequenza di movimenti fatti su una scacchiera da un cavallo in modo che ogni quadrato venga visitato una ed una sola volta.

Esiste una soluzione a questo puzzle? E se si, quanti possibile tour ci sono?

I primi risultati furono riportati in un manoscritto arabo dall’autore Abu Zakaria Yahy intorno al 900 dc (vedi figura 2). Tra le due soluzioni mostrate in figura 2, c’e’ una notevole differenza. Infatti il punto iniziale per la soluzione sulla sinistra non puo’ essere raggiunto dal punto finale con una mossa del cavallo, mentre questo e’ vero per la soluzione di destra. Nel caso della soluzione di destra si parla di tour del cavallo chiuso. In figura 3, vengono riportati due esempi di tours chiusi.

 

Figura 2. Due soluzioni per il puzzle del cavallo.

 

Figura 3. Due tours chiusi.

La prima analisi matematica di questo puzzle, comunque, fu eseguita nel 1759 dal grande Eulero. L’accademia delle scienze di Berlino, aveva istituito un premio di 4000 franchi per chi riusciva a dare una soluzione matematica del puzzle, premio che molto probabilmente Eulero non prese mai in quanto essendo il direttore del dipartimento di matematica, non era tra gli eleggibili. In figura 4, vengono riportate alcune soluzioni trovate da Eulero. Partendo da qualsiasi quadrato lungo il cammino si otterra’ sempre un tour chiuso.

 

Figura 4. Alcune soluzioni trovate da Eulero.

Ma quanti tours esistono? Questo numero e’ sorprendentemente grande. In effetti e’ cosi grande che un semplice conteggio e’ al di fuori della portata dei computer piu’ veloci. Il problema e’ stato comunque affrontato in modo diverso da Martin Lobbing e Ingo Wegener che nel 1995 comunicarono che, il numero possibile di tours del cavallo era uguale a 33439123484294.

Nel 1997, Brendan McKay, usando un metodo diverso, ha stabilito che il numero possibile di tours e’ dato da 13267364410532, che se anche  piu’ piccolo di quello precedente rimane comunque un numero elevatissimo.

Esistono anche tours magici di cavalli, nel senso che se ogni passo del cammino del cavallo viene numerato, il quadrato risultante e’ magico, cioe’ la somma di tutte le righe, di tutte le colonne e delle diagonali principali e’  uguale ad una costante (vedi per esempio la figura 5).

 

Figura 5 . Due tours magici.

I tours magici non sono possibili su scacchiere n x n con n dispari. Il primo tour magico fu pubblicato nel 1848 dal suo scopritore, William Beverley (vedi figura 6) anche se si tratta nella realta’ di un tour semimagico in quanto, la somma delle diagonali non e’ uguale a 260 che e’ invece la somma delle righe e delle colonne.

 

Figura 6 . Il primo tour magico scoperto da W. Beverley.

Il quadrato di Beverley ha delle proprieta’ interessanti. Per esempio, come mostrato in figura 7 a sinistra, in ogni quadrante, la somma dei numeri corrisponde a 520 e la somma di ognuna delle righe e delle colonne equivale a 130. Inoltre la somma dei numeri in ogni quadrato 2x2 e’ uguale a 130 (figura 7 a destra).

 

Figura 7. Quadrato di Beverley

Solo dopo 62 giorni di calcoli, nel 2003 e’ stato mostrato che per una scacchiera 8x8 non esiste nessun tour magico, mentre ne esistono in totale 140 di semimagici.

Nel diciannovesimo secolo, H.C. Warnsdorff presento’ un metodo pratico per costruire dei tours del cavallo. Lo scopo era quello di evitare di creare delle estremita’ morte, cioe’ quadrati da cui il cavallo non puo’ piu’ andare avanti senza visitare un quadrato gia’ visitato in anticipo. Per questa ragione, prima di ogni mossa vengono analizzati i possibili quadrati in cui muoversi nel passo successivo, ed una volta contato il numero di nuove scelte possibili, ci si muove nel quadrato con il numero minore.

La regola di Warnsdorff, genera delle soluzioni, ma non tutte le possibili soluzioni. In figura 8, viene riportato un inizio di tour ottenuto con la regola di Warnsdorff.

 

Figura 8. La regola di Warnsdorff al lavoro

Oggi, comunque, la tecnica piu’ utilizzata per trovare i tours del cavallo su scacchiere molto grandi e’ quella della decomposizione, cioe’ quella di suddividere la scacchiera in rettangoli piccoli per i quali la soluzione e’ gia' conosciuta. Queste soluzioni sono, quindi, combinate insieme per ottenere tutti i possibili cammini del cavallo. In figura 9, viene riportato un possibile cammino del cavallo per una scacchiera 60x60.

Figura 9. Cammino del cavallo per una scacchiera 60x60 ottenuto col metodo della decomposizione.

I tours del cavallo possono anche essere rappresentati tramite i grafi, dove ogni nodo rappresenta i quadrati della scacchiera e le connessioni (o edge) corrispondono ad una mossa legale del cavallo (vedi figura 10).

 

Figura 10. Grafi per tours del cavallo su scacchiere di diverse dimensioni nxn.

Si puo’ dimostrare che se il grafo associato al movimento del cavallo su una scacchiera mxn ha un cammino Hamiltoniano allora esiste per certo un tour, e se il grafo ha un ciclo Hamiltoniano allora il tour e’ chiuso. Vediamo cosa si intende per grafo Hamiltoniano. Un grafo si dice contenere un cammino Hamiltoniano quando e’ possibile visitare tutti i vertici del grafo una e una sola volta. Per esempio in figura 10 , si vede chiaramente, che su una scacchiera 3x3 non esiste nessun tour del cavallo, in quanto non c’e’ un cammino Hamiltoniano.

Si parla invece di ciclo Hamiltoniano quando nel cammino Hamiltoniano esiste un arco che congiunge l’ultimo vertice con il primo, realizzando cosi un ciclo che visita tutti i vertici per poi ritornare al punto di partenza (vedi figura 11).

 

Figura 11. Grafo contenente un ciclo Hamiltoniano indicato con le frecce in grassetto.

Per ogni classe di grafi e’ possibile calcolare il numero di possibili cammini Hamiltoniani come nel caso della classe mostrata in figura 12. Si tratta di grafi completi con n vertici. Un grafo si dice completo quando per ogni coppia di vertice esiste una connessione o edge. La sequenza dei possibili cammini Hamiltoniani per la classe procede in questo modo (considerando anche il verso):

0, 2, 6, 24, 120, 720, ...

 

Figura 12. Classe dei Grafi cosiddetti completi.

Il numero di connessioni in un tour del cavallo su una scacchiera nxn e’ dato dalla seguente formula:

4(n-2)(n-1)

che equivale a 8 volte i numeri triangolari.

I cammini del cavallo su una scacchiera possono essere utilizzati anche per tassellare il piano. Usando i 4 insiemi di 16 movimenti illustrati nella figura 13 e’ possibile costruire 4 poligoni, che insieme possono tassellare il piano.

 

Figura 13. I 4 poligoni colorati ottenuti con i cammini del cavallo e la tassellazione del piano.