25 aprile 2018

Il gioco del 15

Tutti noi da bambini abbiamo giocato a quello che viene comunemente chiamato il gioco del 15. Si tratta di una cornice di legno o plastica di forma quadrata, nella quale vi sono $15$ blocchi quadrati uguali (numerati da $1$ a $15$) che possono scorrere in alto, in basso, a destra e a sinistra utilizzando lo spazio fornito dal quadrato mancante. Lo scopo del gioco è partire da una configurazione in cui i blocchi sono disordinati e arrivare alla configurazione di partenza in cui essi sono numerati consecutivamente e lo spazio vuoto è in basso a destra.

Le origini del rompicapo non sono completamente chiare. Sebbene l’enigmista Sam Loyd (1841-1911) ne reclamò spesso la paternità, sembra che sia stato in realtà inventato da un certo Noyes Palmer Chapman a New York nel 1874. Esso divenne estremamente popolare in America ed Europa a partire dal 1880.

Nel 1889 Loyd offrì un premio di 1000 dollari a chiunque fosse stato in grado di risolvere la configurazione in cui tutti i numeri sono al loro posto, tranne il $14$ e il $15$ che sono scambiati fra loro.

In realtà Loyd era sicuro di non dover sborsare nulla, dato che nel 1879 Johnson e Story avevano completato l’analisi matematica del gioco, scoprendo che un invariante completo che distingue le configurazioni ammissibili da quelle non ammissibili è costituito dalla parità della corrispondente permutazione e dalla taxicab distance (numero di righe più numero di colonne) del quadrato vuoto dal quadrato in basso a destra. Questo segue dal fatto che ogni mossa effettuata cambia contemporaneamente sia la parità della configurazione che la taxicab distance.

Di conseguenza, se lo spazio vuoto si trova in basso a destra, una configurazione è ammissibile se e solo se essa corrisponde ad una permutazione pari di $\{1, \ldots,15\}$. In particolare, la configurazione proposta da Loyd non è ammissibile, dato che corrisponde alla trasposizione $(14 \; 15)$, che è una permutazione dispari. Questo è un esempio tipico in cui un semplice controllo di parità permette di risolvere elegantemente un problema che sembra a prima vista intrattabile senza l'uso della forza bruta (enumerazione di tutte le configurazioni).

La configurazione impossibile di Sam Loyd

Esistono anche versioni del rompicapo con più di $15$ tasselli, e in generale ha senso chiedersi quale sia il massimo numero di mosse necessarie per risolvere una configurazione nel caso con $n^2-1$ tasselli. Al crescere di n questo è un problema NP-difficile.

Nel caso del gioco del $15$, il massimo numero di mosse necessarie è $80$ (vi sono esattamente $17$ configurazioni che richiedono $80$ mosse). Per il gioco con $24$ tasselli, si sa che il numero massimo di mosse è compreso fra $152$ e $208$. Per $35$ o più tasselli, limitare il numero massimo di mosse necessarie è al momento un problema aperto.


Riferimenti:

A. F. Archer: A modern treatment of the 15 puzzle, The American Mathematical Monthly 106 (1999), 793–799.

J. J. Rotman: Advanced Modern Algebra (Second Edition), Chapter I. Graduate Studies in Mathematics 114, American Mathematical Society (2010).

07 aprile 2018

Gundlagenstreit, parte II. Frosch-Mäuse Krieg

Non intendo prendere posizione in questa guerra fra rane e topi
A. Einstein (lettera a M. Born, 1928)

Il 30 ottobre 1928, C. Carathéodory rese visita a Brouwer nella sua casa a Laren, nei pressi di Amsterdam, e gli consegnò una lettera scritta da Hilbert in persona nelle quale gli veniva comunicata la sua estromissione dall'editorial board dei Mathematische Annalen, sulla base di "incompatibilità riguardo a questioni fondamentali".

Brouwer, individuo nervoso ed emotivamente instabile, non era tipo da lasciar correre quella che considerava una intollerabile offesa alla sua persona e alla sua professionalità. Dopo essersi congedato in maniera turbolenta da Carathéodory, cominciò a preparare la contromossa.

I Mathematische Annalen erano all'epoca già pubblicati da Springer, che li aveva rilevati dall'editore originale Teubner, e il frontespizio della rivista elencava due tipi di redattori: i redattori capo ("Herausgeber") D. Hilbert, A. Einstein, O. Blumenthal, C. Carathéodory e i collaboratori ("Mitarbeiter") L. Bieberbach, H. Bohr, L. E. J. Brouwer, R. Courant, W. v. Dyck, O. Hölder, T. von Karman, A. Sommerfeld. Il contratto stipulato con la casa editrice non spiegava in dettaglio la distinzione fra i due tipi di redattori, nè chiariva se un redattore capo potesse arrogarsi il diritto di licenziare un collaboratore, per cui Brouwer minacciò di portare la contesa in tribunale.

Hilbert aveva messo tutto il peso del suo prestigio e della sua autorità, che erano immensi, nella crociata contro Brouwer. Quest'ultima non era originata soltanto dalla disputa sui fondamenti, ma nasceva anche da profonde differenze personali e politiche fra i due. All'inizio le loro relazioni erano amichevoli, e Hilbert rispettava i contributi matematici di Brouwer a tal punto da offrirgli una cattedra a Gottinga (che Brouwer non accettò). Successivamente, tuttavia, Brouwer (pur essendo olandese) appoggiò le tesi del nazionalismo germanico, e giunse al punto di criticare aspramente la partecipazione della delegazione dei matematici tedeschi, guidata da Hilbert, al congresso di Bologna del 1928.

Ad Hilbert, per il quale nazionalismi e politica non dovevano avere nulla a che fare con la scienza, questo tipo di atteggiamento risultava semplicemente odioso. Inoltre, Hilbert era all'epoca malato di anemia perniciosa, e temeva che Brouwer potesse approfittare della sua debolezza fisica per impadronirsi della direzione degli Annalen. Sembra invece senza fondamento l'accusa (citata ad esempio in [R70]) secondo cui Brouwer voleva essere referee esclusivo per i lavori dei matematici olandesi spediti alla rivista, che teneva poi per anni sulla scrivania prima di formulare un giudizio.

Il maggiore alleato di Brouwer nel comitato editoriale era Bieberbach, che già molto prima dell'avvento al potere dei nazisti aveva manifestato le sue ferventi posizioni nazionaliste; ma anche Blumenthal e Carathéodory, per quanto venerassero Hilbert e non volessero contrastarlo, erano legati da sentimenti di amicizia verso Brouwer, e desideravano una soluzione della vicenda che concedesse a quest'ultimo l'onore delle armi. Essi arrivarono al punto di consigliare a Brouwer di presentare volontariamente le sue dimissioni in modo da evitare lo scandalo dell'estromissione, ma il matematico olandese fu irremovibile e ribadì che, se necessario, Hilbert e i suoi fedelissimi avrebbero dovuto rispondere al giudice delle loro azioni.

L'ago della bilancia nella contesa era Einstein: il suo prestigio scientifico e i suoi standard morali erano tali che chiunque l'avesse avuto dalla sua parte sarebbe stato quasi sicuro di vincere la partita. Nelle sue lettere private a Hilbert, Einstein afferma che Brouwer "...è, con il dovuto rispetto per la sua mente di prim'ordine, uno psicopatico" e che, dunque, "sarebbe meglio lasciarlo libero di fare il giullare", definendone l'estromissione dagli Annalen "un procedimento che non posso nè approvare nè giustificare". Pertanto, Einstein era deciso a mantenere nella faccenda la più ferma neutralità, non volendo mischiarsi in quella che, con malcelato disprezzo, chiamava "una guerra fra rane e topi" (Frosch-Mäuse Krieg).

L'impasse venne infine superata con uno stratagemma suggerito da Carathéodory: visto che Brouwer non intendeva dimettersi, e che non era chiaro se potesse essere legalmente licenziato, la soluzione migliore era sciogliere l'intero comitato editoriale e costituirne uno nuovo. La cosa era possibile da contratto, essendo giunti al Volume 100 della rivista; infatti, il Volume 101 mostra un nuovo frontespizio, nel quale compaiono solo tre redattori: D. Hilbert, O. Blumenthal e E. Hecke. Per confrontare i frontespizi dei volumi 100 e 101, si guardino i link alle rispettive versioni digitalizzate [MathAnn100] e [MathAnn101].

Apparentemente, Brouwer reagì a questa soluzione di compromesso con una certa mitezza. Per un po' continuò a lamentarsi, poi capì che la guerra era finita e che erano andati tutti a casa, e nel 1935 fondò una nuova rivista, Compositio Mathematica, ancora oggi attiva e prestigiosa. Sarebbe morto solo nel 1966, ma la sua carriera scientifica era terminata: il rinnovamento del comitato editoriale dei Mathematische Annalen sancì di fatto la fine della Grundlagenstreit.

Riferimenti:

[MathAnn100] https://gdz.sub.uni-goettingen.de/id/PPN235181684_0100
[MathAnn101] https://gdz.sub.uni-goettingen.de/id/PPN235181684_0101
[vanDalen2011] D. van Dalen: The Selected Correspondence of L.E.J. Brouwer, Springer 2011
[vanDalen2013] D. van Dalen: L.E.J. Brouwer – Topologist, Intuitionist, Philosopher, Springer 2013
[R70] C. Reid: Hilbert, Springer 1970.

Nota: Il testo [vanDalen2013] è una completa biografia di L. E. J. Brouwer, mentre [vanDalen2011] è una raccolta della sua corrispondenza privata e scientifica.