venerdì 28 gennaio 2011

Il gioco del quindici


Non è sorprendente che molti esperti di scacchi siano passati alla storia non tanto per aver lasciato importanti contributi sul gioco dei pezzi bianchi e neri, ma per avere inventato enigmi matematici o proposto tecniche algoritmiche per risolvere difficili problemi.
Abbiamo già incontrato, qualche post fa, il caso di Johann Berger, scacchista austriaco con l'hobby degli algoritmi per stilare i calendari dei tornei.
Un altro celebre scacchista fu Samuel Loyd, americano, anche lui vissuto a cavallo tra Ottocento e Novecento.


Il nome di Loyd è ben noto agli appassionati di scacchi come compositore di problemi, ma i suoi meriti vanno ben oltre le frontiere di quel gioco. Molti, tra i quali Martin Gardner, lo hanno considerato "il più grande enigmista d'America": pare che abbia inventato migliaia di giochi ed enigmi, alcuni dei quali molto sofisticati dal punto di vista matematico. Una delle sue intuizioni più geniali è un rompicapo nel quale tutti noi ci siamo prima o poi cimentati: il cosiddetto "gioco del quindici".
Lo scopo del gioco è ben noto: in una specie di scatola quadrata di plastica dobbiamo mettere in ordine quindici tesserine quadrate, numerate da 1 a 15; le tesserine possono scorrere solo in orizzontale e in verticale, ma nello spostarle dobbiamo fare i conti con il fatto che esiste un solo spazio vuoto!
Si parte solitamente da una situazione casuale, più o meno caotica, e si deve arrivare nella configurazione illustrata nella figura in alto.

Sam Loyd propose il suo gioco nel 1878. Si racconta che il successo del rompicapo fu così travolgente, che i francesi arrivarono a descriverlo come un flagello peggiore dell'alcool e del tabacco, in Germania diventò molto popolare tra i deputati del Reichstag, mentre in America venne proibito il suo utilizzo negli uffici durante le ore di lavoro!

Su disposizione di Loyd, la confezione del gioco che venne messa in commercio non aveva le tessere disposte in una configurazione caotica: semplicemente, rispetto alla situazione finale ordinata, aveva le due caselle del 14 e del 15 scambiate, come illustrato nella figura qui accanto.
Loyd offrì un premio di ben 1000 dollari al primo che avesse trovato una soluzione.
Visto che si trattava soltanto di due caselle scambiate tra loro, sulle prime si pensò che l'enigma fosse di facile risoluzione: tuttavia, i mesi e gli anni passarono senza che nessuno si facesse avanti a reclamare il premio.


Ovviamente, Loyd aveva fatto bene i suoi conti: il problema era impossibile!
Perché?
Per capire l'arcano, almeno a grandi linee, occorre considerare, in ogni configurazione del gioco dalla quale si parte per cercare di arrivare all'ordinamento totale, il numero di coppie di caselle che non si trovano nella situazione "naturale". Ad esempio, la disposizione iniziale proposta da Loyd presenta una sola coppia di caselle non ordinate tra di loro: quella del 14 e quella del 15, che sono appunto invertite l'una rispetto all'altra.


Anche la configurazione illustrata nella figura qui accanto presenta un numero di inversioni pari a 1: infatti soltanto la casella del 2 e quella dell'1 sono scambiate tra di loro.




Nella successiva figura, le inversioni sono in tutto 4: per verificarlo, osservate una per una tutte le caselle, e per ognuna controllate con quali altre caselle si verifica un "cattivo" ordinamento reciproco.


Non è difficile dimostrare (e infatti i matematici lo hanno fatto) che se il numero di inversioni di una certa disposizione iniziale è pari, allora si può risolvere il rompicapo, portando tutte le caselle nella loro situazione completamente ordinata, ma se è dispari ciò non è possibile.
Ecco perché Loyd sapeva di non correre alcun rischio, e mise in palio una somma che nessuno poté mai riscuotere!

Nessun commento:

Posta un commento

La top ten dei miei video su YouTube (1° posto)

Rullo di tamburi! Eccoci finalmente in vetta! E, devo dire, la vetta della classifica dei miei video su YouTube appare per il momento davver...