domenica 5 febbraio 2012

Giocare con i polimini

Una poliforma è una figura piana che è composta da due o più copie connesse di una dato poligono di base, che è quasi sempre (ma non necessariamente) un poligono convesso che può dare una tassellazione regolare del piano. Si possono costruire poliforme, ad esempio, con i quadrati, con i triangoli isosceli, con quelli rettangoli con angoli di 30-60-90 gradi, con gli esagoni regolari, ecc. Esiste tutta una nomenclatura ufficiale per denominare tali figure. Ad esempio, unendo quadrati uguali si ottiene un polimino (con due quadrati si ha il domino), mentre con triangoli isosceli si ottiene un poliante (ovvio che due triangoli equilateri diano un diamante); con i triangoli rettangoli si ottengono le polisquadre (polydrafter in inglese).

Le regole per collegare i poligoni possono essere diverse, e devono pertanto essere dichiarate per ciascun tipo distinto di poliforma, Di solito, tuttavia, si applicano le seguenti:
1. Due poligoni di base devono essere uniti solo con un lato comune;
2. Due poligoni di base non devono mai sovrapporsi;
3. Una poliforma deve essere connessa (cioè deve costituire un pezzo solo);
4. L’immagine speculare di una poliforma asimmetrica non è considerata una poliforma distinta.

Le poliforme sono una ricca fonte di problemi, rompicapi e giochi, in gran parte basati sulla possibilità di tassellare figure assegnate o l’intero piano. La storia di questi passatempi logico-matematici attraversa tutta la storia del Novecento, e coinvolge figure straordinarie di esperti di matematica ricreativa e creatori di rompicapi, dall’inglese Henry Dudeney nella prima metà del secolo fino all’americano Martin Gardner nella seconda.

Tra le poliforme la più utilizzata è senza dubbio il polimino, cioè la figura piana formata dall’unione per il lato di due o più quadrati uguali. Fu il californiano Solomon W. Golomb (l’inventore dell’omonimo regolo) ad assegnare il nome a questa famiglia di figure, in una conferenza che tenne nel 1953. Il termine fu poi reso popolare da Martin Gardner, che volle sostituire il termine diomino, adottato da Golomb per quello formato da due quadrati, con il più corretto domino. Qui sotto sono illustrati i polimini da 1 a 4 quadrati.


Come molti rompicapi della matematica ricreativa, i polimini sono interessanti dal punto di vista combinatorio. Lo studio dei polimini consiste nello stabilire il numero di differenti tipi che si possono ottenere in funzione del numero n di celle formate dal quadrato di base e delle regole di costruzione. Purtroppo non esiste una formula generale per farlo, anche se esistono diversi algoritmi che permettono una stima affidabile. In generale si è stimato che il numero di n-polimini cresce esponenzialmente all’aumentare di n. Esistono anche diversi polimini con buchi, che di solito sono però ignorati perché si considerano solo quelli semplicemente connessi.

Esistono tre diversi modi di distinguere i polimini:
- I polimini liberi sono quelli che non derivano da alcuna trasformazione rigida (traslazione, rotazione, riflessione o antitraslazione) di altri polimini (si tratta di figure che possono essere sollevate e capovolte).
- I polimini a una sola faccia sono quelli che non derivano da traslazione o rotazione di un altro polimino.
- I polimini fissi, infine, sono quelli che non derivano da una traslazione di un altro polimino (sono figure che non possono essere capovolte o ruotate). La tabella elenca i diversi polimini con n celle fino a 6:


Di giochi con i polimini si ha notizia già nel 1907, quando Dudeney ne pubblicò uno nei Canterbury Puzzles: era un gioco con i pentamini, ma allora fu presentato come un problema di dissezione di un rettangolo. Problemi con pezzi formati da 1 a 6 celle furono pubblicati sul bimestrale enigmistico Fairy Chess Review tra il 1937 e l’anno della sua chiusura, nel 1957. I compiti richiesti al giocatore vanno dal tassellare regioni assegnate al ribaltare un polimino per creare altre figure.


Martin Gardner rese popolare il rompicapo del pentamino, che è il polimino composto da cinque quadrati identici connessi tra di loro lungo dei lati, chiedendo di riempire diversi rettangoli di area 60 utilizzando un insieme di tutti i 12 pentamini liberi esistenti (che sono identificati con le lettere dell'alfabeto più vicine alla loro forma). Il più tipico rompicapo di questo tipo consiste nel tassellare un rettangolo di 6×10 quadrati: esistono 2339 soluzioni. Anche per i rettangoli 4×15 e 5×12 ne esistono molte (368 nel primo caso e 1010 nel secondo). I rettangoli 5×12 e 6×10 possono essere divisi in rettangoli più piccoli di dimensioni 5×6: in questo caso esistono 8 soluzioni. È invece impossibile il rettangolo 2×30, perché almeno uno dei pentamini è di lunghezza 3 in due direzioni.

Assai più difficile è il rettangolo 3×20, problema così duro e affascinante da essere ampiamente citato nel racconto di Terra imperiale del grande scrittore di SF Arthur C. Clarke. In questo racconto i pentamini sono uno dei giochi più popolari tra gli abitanti di Titano, il satellite di Saturno, colonizzato dall'uomo nel XXII secolo. Il gioco viene regalato a Duncan, ultimo discendente (per clonazione) dei Mackenzie, la più grande dinastia di mercanti d’idrogeno di Titano, per mettere alla prova la sua abilità logica. Secondo Clarke, lo studio di queste dodici figure e delle loro possibili combinazioni è per Duncan la rivelazione dell'infinito. In effetti, per pavimentare con l’insieme dei dodici pentamini il rettangolo 3×20 esistono solo due soluzioni.

Anche in 2001, Odissea nello spazio, racconto di Clarke da cui Stanley Kubrick trasse uno dei suoi capolavori, doveva comparire un gioco con i pentamini, nella scena in cui gli astronauti giocano a scacchi con HAL. Kubrick decise però che quel gioco era troppo oscuro per lo spettatore medio e modificò la sceneggiatura.

Il matematico R. M. Robinson dell'Università di Berkley suggerì il cosiddetto problema della triplicazione, che consiste nel costruire un modello di ogni pentamino tre volte più grande, usando nove dei pentamini di base. Nella figura a fianco è riportato l'ingrandimento del pentamino C.

Martin Gardner, ancora lui, fu invece l’inventore del rompicapo nel quale si chiede di ricoprire, con i dodici pentamini, una scacchiera 8×8. Poiché i polimini possono ricoprire soltanto 12×5 = 60 quadretti, ne rimangono quattro vuoti in posizioni diverse, raggruppati o separati. Una delle possibili disposizioni è riportata nella figura qui sotto.

Un altro gioco con la scacchiera fu proposto da Golomb, I due giocatori sono dotati di tessere a forma di pentamini, che devono disporre a turno sulla scacchiera fino a che uno dei due non riesce più a collocare un pezzo senza che vada a sovrapporsi agli altri. Il gioco viene oggi commercializzato con il nome di Quintillions. Una variante è rappresentata da Blokus, ora disponibile anche in numerose versioni elettroniche, nel quale si utilizzano tutti i polimini liberi fino ai pentamini, con lo scopo di giungere a una configurazione in cui l’avversario non può più sistemare i suoi pezzi.

Il tetramino, che è il polimino composto da quattro quadrati identici connessi tra di loro, offre minori possibilità di gioco. Esistono cinque tetramini liberi, ma sfortunatamente, per quanto essi coprano un’area totale di 20 quadrati, essi non possono uniti a formare un rettangolo. Se guardiamo la figura in cui i tetramini sono stati colorati si può comprendere il perché. I primi quattro coprono due quadrati bianchi e due neri, ma l’ultimo ne copre tre di un colore e solo uno dell’altro. Poiché ogni rettangolo di area 20 deve avere 10 rettangoli bianchi e 10 neri, non si può costruire alcun rettangolo con un solo insieme di tetramini liberi. Con due insiemi si può invece riempire un rettangolo di 5×8 celle. Essi possono essere uniti per formare alcune figure interessanti, come ad esempio dei rettangoli di 3×7 con un quadrato escluso. 


La rivincita dei tetramini si ha però nel notissimo Tetris (creato nel 1984 dal russo Alexey Pajitnov nell’allora Unione Sovietica: una grande conquista proletaria), dove i diversi tetramini cadono uno alla volta mentre il giocatore deve ruotarli e/o muoverli in modo che creino una riga orizzontale di blocchi senza interruzioni. Quando la riga è stata creata, i mattoni spariscono e i pezzi sovrastanti (se ce ne sono) cadono a formare nuove linee. Poiché nel gioco è ammessa solo la rotazione dei pezzi e non il ribaltamento, ai cinque tetramini liberi sono aggiunti i simmetrici di quelli a forma di L e di Z , in modo da poter disporre di tutte le configurazioni che si possono ottenere componendo simmetrie su un tetramino.

Giocare con i primi giochi elettronici comparsi negli anni ’80, dopo essersi abituati ai giochi di ruolo ambientati in scenografie di qualità cinematografica fa una strana impressione. Ma il fascino di questi programmi risiede proprio nella loro semplicità. Credo che una buona maniera per concludere questa rassegna sia il proporvi una partitina a Tetris.(► e ◄ per spostare a destra e sinistra, ▲ e ▼ per ruotare). Che ne dite?

4 commenti:

  1. Ciao, complimenti, mi piacerebbe fare uno scambio di link con il mio http://latuapsicologia.blogspot.com/

    Grazie
    Francesco

    RispondiElimina
  2. Grazie Francesco per la proposta, ho visto il vostro sito è l'ho trovato ben fatto. Tuttavia non pratico lo scambio di link per principio. Ciao.

    RispondiElimina
  3. Non per vantarmi (sì, per vantarmi), ma al paese mio nei primi anni 90 avevo il record al videogioco del tetris: 800.000 punti e rotti con una sola partita, no dico...

    RispondiElimina
  4. Ho sempre pensato che Tetris e saggezza fossero compagni.

    RispondiElimina