L’ossessione di Clarke – approfondimenti sul quesito e soluzione

Nel numero di ottobre vi ho parlato di polimini, cioè di 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:

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:

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.

La storia

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, il problema del rettangolo 3×20, che ossessionò Arthur Clarke, è invece molto più arduo, e le soluzioni sono soltanto due:

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 seguente:

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 sono illustrati alcuni esempi, uno per ogni tipo di pentamino.

Il problema

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.

Anche la sfida di ottobre 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.

La soluzione

Conosco soltanto tre soluzioni a questo problema (a meno di rotazioni e riflessioni):

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.

Ebbene, hanno inviato soluzioni corrette i lettori Iacopo Longo, Daniele Borré e gulliver14 (tutti hanno inviato la soluzione 1).

L’abbonamento semestrale è però andato a GIORGIA HOFER, che è stata la più rapida di tutti (e l’unica a proporre la soluzione 2).

A tutti i lettori che si sono cimentati nel problema vanno i nostri più vivi complimenti!

Letture consigliate

• Solomon W. Golomb, Polyominoes: Puzzles Patterns, Problems, and Packings, Princeton University Press, 1994.
• Martin Gardner, Enigmi e giochi matematici, Milano, Rizzoli, 2001.
• Henry Dudeney, The Canterbury Puzzles.

• Dal blog Popinga di Marco Fulvio Barozzi.
• Dal sito del progetto Polymath.

• Dal mio blog “Mr. Palomar”:

http://misterpalomar.blogspot.it/2011/01/ancora-sui-polimini.html

http://misterpalomar.blogspot.it/2011/01/come-giocare-su-una-scacchiera-con-i.html