Gli enigmi di Coelum: l'ossessione di Clarke

Continua la serie degli approfondimenti sugli enigmi da me pubblicati sulla rivista Coelum Astronomia. Questa volta tocca ai polimini, argomento da me già trattato anni fa su questo blog nei post "Come giocare su una scacchiera con i pezzi del Tetris" e "Ancora sui polimini".
Alcune delle informazioni che troverete in questo approfondimento, quindi, non saranno del tutto nuove per i lettori di Mr. Palomar: ma non credo che sia male rinfrescarle...
Anche il Sommo Popinga aveva parlato di polimini in un bel post del lontano 2012.

Per cominciare, cosa sono questi polimini? Beh, sono figure geometriche piane ottenute congiungendo tra di loro quadrati uguali e facendo in modo che ogni quadrato confini, tramite un lato, con almeno un altro quadrato. Se i quadrati da mettere insieme sono tre, esistono soltanto due possibili configurazioni (quella con i tre quadratini in fila e quella a L), che possiamo chiamare trimini.

Con quattro quadratini, possiamo costruire invece i tetramini, che sono in tutto cinque (vedi figura a lato).
Ciascuno di questi pezzi viene considerato sempre lo stesso tetramino anche se viene ruotato o riflesso in qualsiasi direzione. Ciò non avviene nel Tetris, dove non è possibile riflettere (o, se preferite, capovolgere) i pezzi. Per questo motivo i tetramini cadenti del celebre videogioco erano sette e non cinque: i pezzi a L e a S venivano rappresentati nelle due forme speculari.

Se abbiamo cinque quadratini, ecco i pentamini, che sono ben dodici, e per comodità memonica vengono contrassegnati ciascuno con una lettera dell’alfabeto (vedi figura a lato).

Analogamente, si può parlare di esamini (polimini da sei), eptamini (da sette), ottomini (da otto), e così via. I polimini formati da due soli quadratini, invece, sono molto meno interessanti dal punto di vista della matematica ricreativa, anche perché esiste una sola possibilità di costruire una forma siffatta. Qualcuno sostiene che questi polimini “banali” devono essere chiamati domini, e che ciò spiegherebbe l’origine del nome del celebre gioco del domino.
In realtà il gioco del domino deve il suo nome al colore delle tessere con le quali si gioca, notoriamente bianche e nere: gli stessi colori caratterizzavano infatti un antico costume carnevalesco a cappuccio, simile alla bautta veneziana, chiamato appunto domino. Il nome dell’antico gioco delle tessere costituisce soltanto una curiosa coincidenza linguistica.

A inventare i polimini fu un ventiduenne studente americano ad Harvard, Solomon W. Golomb.

Nel 1953, durante una noiosa lezione, Golomb cominciò a tracciare su un foglio delle figure costituite da unioni di quadratini. Resosi conto del potenziale interesse matematico della sua scoperta, Golomb si mise a classificarle (in base al numero di quadratini), e tentò di stabilire quanti polimini esistono per ciascun tipo.
A dire il vero, le figure ideate da Golomb non erano del tutto nuove: già nel 1907 Henry Dudeney, nei suoi celebri Canterbury Puzzles, aveva proposto dei problemi di fatto basati su polimini, e altri enigmi simili vennero pubblicati tra gli anni Trenta e gli anni Cinquanta dal bimestrale enigmistico inglese Fairy Chess Review.
Golomb, comunque, fu il primo a studiare la questione da un punto di vista matematico rigoroso e sistematico. Il suo primo sforzo fu rivolto a trovare una formula semplice che permettesse di determinare il numero di polimini di una certa specie.
Ad oggi una simile formula non è nota. Quel che si sa è che questo numero cresce molto rapidamente all’aumentare del numero dei quadratini: gli esamini sono 35, gli eptamini 108, e già con 12 quadrati si arriva a ben 63600 combinazioni possibili.

Qualche tempo dopo il giovane Golomb presentò la sua idea al Club di Matematica di Harvard, e il gioco dei polimini divenne rapidamente popolarissimo tra gli studenti. Fu Martin Gardner, il più famoso dei “giocologi” matematici, a diffonderlo in tutto il mondo grazie ai suoi articoli sul Scientific American.

I polimini rappresentano senza dubbio uno dei temi prediletti dalla matematica ricreativa. Esistono numerosi giochi e rompicapi costruiti attorno a queste figure geometriche. La maggior parte di questi problemi consiste nel tentativo di tassellare figure assegnate utilizzando polimini di un certo tipo.

Tra i problemi più classici vi è la tassellatura di rettangoli di area 60 (ad esempio 6×10, 5×12, 4×15 o 3×20) utilizzando i dodici pentamini esistenti. Esistono 2339 soluzioni per il rettangolo 6×10, 1010 per il rettangolo 5×12, e 368 per il rettangolo 4×15.

Come ricordavo nell’articolo su Coelum, il problema del rettangolo 3×20, che ossessionò Arthur Clarke, è invece molto più arduo, e le soluzioni sono soltanto due, come illustrato in figura.


Un altro problema famoso, affrontato da Dudeney e da Gardner, consiste nel coprire una scacchiera 8×8 con i 12 pentamini esistenti, lasciando vuote quattro caselle. Una possibile soluzione è illustrata nella figura a fianco.

Golomb escogitò un gioco competitivo basato su questo problema, oggi in commercio con il nome Quintillions: a turno, i due giocatori devono disporre sulla scacchiera un pentamino, finché uno dei due non ha più posto per collocare un pezzo. Golomb calcolò che una partita può durare dalle 5 alle 12 mosse.
Nella variante nota come Blokus, oltre ai pentamini si possono usare anche altri tipi di polimini.
Un altro problema molto citato, ideato dal matematico americano Raphael Robinson, è quello della triplicazione: mettendo insieme nove pentamini, si deve costruire una figura con la stessa forma di uno dei pentamini, ma tre volte più grande.

Nella figura a lato sono illustrati alcuni esempi, uno per ogni tipo di pentamino.

E i tetramini? Il fatto è che questi tipi di polimini sono meno interessanti dal punto di vista dei giochi matematici. Ad esempio, è stato provato che non esiste alcun modo di sistemare i 5 tetramini in un rettangolo di area 20.
Si deve quindi ricorrere a tassellature alternative: una di queste consiste nel sistemare i 5 pezzi in un rettangolo 3×7, con un quadratino escluso. Oppure, è possibile coprire un rettangolo di 5×8 celle con due set completi di tetramini.

La sfida di ottobre 2013 consisteva in un problema di tassellazione con tetramini, di mia invenzione. Si trattava di estendere il normale set di 5 tetramini, duplicandone uno, e di sistemare i sei pezzi così ottenuti in un rettangolo di dimensioni 4×6.

Riuscite a trovare qualche soluzione?
Attenzione che tra poco rivelerò quelle che conosco io (quindi, se desiderate cimentarvi nell'impresa, non leggete oltre!)

Le tre soluzioni a me note del problema, a meno di rotazioni e riflessioni, sono illustrate qui sotto:

Pare che non esistano altre soluzioni oltre a queste tre: è curioso notare che tutte e tre sono basate sulla duplicazione del pezzo a forma di T.
Buon divertimento a tutti con i polimini!