domenica 23 gennaio 2011

Ancora sui polimini

La storiella di Mr. Palomar e Mr. Wilson che giocano con i pezzi del Tetris su una scacchiera generalmente riservata ad altri giochi, come gli scacchi, merita certo alcuni approfondimenti.
Innanzitutto, i polimini di Golomb: uno dei primi tentativi del matematico americano deve essere stato certamente quello di trovare una formula che permettesse di calcolare quanti polimini possono essere costruiti con un certo numero di quadrati.
Non mi risulta che sia nota una simile formula: la funzione, come si può vedere nella figura seguente, cresce molto rapidamente (già con 12 quadrati esistono ben 63600 polimini possibili).


Il problema di coprire una scacchiera 8x8 con i 12 pentamini esistenti, lasciando vuote quattro caselle, è molto vecchio: Martin Gardner, nei suoi "Enigmi e giochi matematici" raccolti dallo "Scientific American", ci racconta che una soluzione a questo rompicapo fu pubblicata nel 1907 da Henry Dudeney nel suo libro "The Canterbury puzzles", che proponeva enigmi e giochi ispirati ai personaggi dei "Canterbury Tales" di Geoffrey Chaucer.
Molte altre soluzioni vennero proposte successivamente. E' stato dimostrato che se le quattro caselle sparse vengono poste vicine, a formare un tetramino quadrato, esistono soluzioni per qualsiasi collocazione di questo tetramino. Ad esempio, se il tetramino viene posto al centro della scacchiera, come nella soluzione proposta da Mr. Wilson, esistono 65 soluzioni diverse, che vennero trovate nel 1958 dall'informatico Dana Scott, premio Turing nel 1976. Se invece si accetta che le quattro caselle sparse possano stare ovunque, le soluzioni possibili del rompicapo di Dudeney diventano molte migliaia.
Il gioco competitivo nel quale ognuno dei due giocatori dispone polimini sulla scacchiera, cercando di far sì che l'avversario si trovi a un certo punto senza spazio per porre propri pezzi, fu inventato da Golomb nel 1954. Golomb calcolò che, giocando con i pentamini, una partita può durare da 5 a 12 mosse: in altri termini, 5 è il numero minimo di pentamini diversi che devono essere sistemati sulla scacchiera in modo che non ci sia più spazio per disporre altri pentamini diversi; d'altra parte, dopo aver collocato 12 pentamini in qualsiasi maniera, sicuramente resterebbero soltanto le quattro famose caselle in sovrappiù, e non ci sarebbe spazio per un altro pentamino (e comunque non esisterebbe un tredicesimo tipo di pentamino).
Golomb suggerì anche un paio di principi strategici utili per aumentare le probabilità di vittoria:
1. "cercate di fare mosse che lascino spazio per un numero pari di pezzi";
2. "se non riuscite ad analizzare bene la situazione, fate qualcosa per complicarla ancora di più, in modo che l'avversario faccia ancora più fatica a fare la sua analisi".
Giocando con i tetramini, invece, non ho idea di come potrebbe cambiare la natura del gioco: sarebbe interessante provare!
Il gioco nel quale i due giocatori collocano tetramini sulla scacchiera rispettando la regola delle carte geografiche politiche, nelle quali regioni confinanti devono avere colori diversi, è di mia invenzione. In questo caso, ovviamente si deve disporre di più pezzi per ogni tipo di tetramino: altrimenti non si potrebbero mettere sulla scacchiera pezzi con lo stesso colore. D'altra parte, utilizzando la convenzione dei matematici e non quella del Tetris, con cinque tetramini si coprono soltanto 20 caselle: appare quindi evidente che il gioco necessita di più pezzi per ogni tipo (o colore). Con l'accorgimento di Mr. Wilson, peraltro, due dei cinque tipi di tetramini hanno una doppia colorazione, a seconda della faccia che viene scelta per la collocazione sulla scacchiera.
Anche per questo gioco, non ho prove sperimentali della giocabilità: potrebbe anche rivelarsi un gioco poco divertente o addirittura non giocabile. Anche qui non c'è che da provare a giocare: se qualche lettore volesse galileianamente sperimentare la cosa, sarei curiosissimo di conoscere i risultati.

Un'ultima nota: il nostro Golomb, oltre a fondare la matematica dei polimini, inventò anche un'altra diavoleria matematica: il "regolo" che porta il suo nome. Immaginate di avere un regolo, sul quale sono indicate le posizioni corrispondenti ai numeri interi: 1, 2, 3, e così via. Ora vogliamo tracciare alcune tacche su di esso, in corrispondenza di alcune delle posizioni intere indicate, ma in modo che non ci sia alcuna coppia di tacche poste alla stessa distanza. Trovare regoli di Golomb è semplice, ma trovare quello con il numero di tacche più grande possibile compatibilmente con la sua lunghezza è un problema computazionalmente molto difficile.

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...