Don't take life too seriously: it's just a temporary situation

Polimini (numero di)

Geometria  Matematica combinatoria  Vari 

Si chiamano “polimini” le figure formate da quadrati identici, uniti per i lati.

Sono da lungo tempo alla base di numerosi problemi di costruzione e scomposizione, ma hanno anche posto difficili problemi di matematica combinatoria.

 

L’osservazione che esistono 12 figure formate da 5 quadrati connessi per almeno un lato è attribuita a un antico maestro giapponese di Go.

 

Il primo problema sui polimini risale probabilmente al 1790; grandi enigmisti successivamente proposero vari problemi di scomposizione, come il grande esperto inglese H.E. Dudeney (in Canterbury Puzzles), e una certa letteratura sull’argomento apparve sulla rivista inglese Fairy Chess Review, negli anni ’30 e ’40, principalmente sotto forma di problemi di composizione di scacchiere quadrate e rettangolari.

Prima della seconda guerra mondiale tutti i polimini composti da fino a 10 quadrati erano stati catalogati e molti erano già stati utilizzati per qualche problema, tuttavia se chiedete chi li abbia inventati, molti risponderebbero che fu Solomon Golomb, al quale va il merito di essere stato uno dei pionieri nel loro studio sistematico e d’aver pubblicato nel 1954 su American Mathematical Monthly un articolo sul modo di ricoprire il piano con varie combinazioni di polimini, tratto da una conferenza tenuta l’anno prima. L’articolo suscitò grande interesse sul tema e incoraggiò un gran numero di ricerche, che tuttora non accennano a diminuire di numero. Libri e articoli pubblicati sull’argomento nella seconda metà del ventesimo secolo riempirebbero parecchi locali: la bibliografia citata dallo stesso Golomb nel suo libro del 1994, indubbiamente accurata, ma certo non esaustiva, occupa 22 pagine!

Martin Gardner nella sua rubrica di matematica ricreativa su Scientific American li ha trattati parecchie volte, dal 1958 in poi, contribuendo alla loro popolarità.

 

Vi è un solo monomino, formato da un quadrato, un domino, formato da due quadrati uniti per un lato, e due trimini, formati da 3 quadrati, mostrati nella figura seguente.

I polimini formati da 1, 2 e 3 quadrati

Vi sono 5 tetramini, formati da 4 quadrati, mostrati nella figura seguente.

I 5 tetramini

 

Redelmeier nel 1981 utilizzò un calcolatore per enumerare i polimini fino a 24 celle. Fu poi la volta di Tomas Oliveira e Silva, che nel 1999 estese il calcolo a 28 celle quindi Tony Guttman, Iwan Jensen e Ling Heng Wong arrivarono a 46 nel 2000, mentre altri, troppo numerosi per essere citati, verificavano indipendentemente tali risultati e calcolavano i numeri delle varie varianti riportate più avanti.

La tabella seguente mostra il numero di polimini, in generale, chirali, cioè considerando distinte le immagini speculari, e orientati, cioè contando separatamente le immagini speculari e le rotazioni, se non coincidenti, per i primi numeri di quadrati (I. Jensen, Toshihiro Shirakawa e N.J.A. Sloane, The Online Encyclopedia of Integer Sequences http://oeis.org).

Quadrati

Generici

Chirali

Orientati

1

1

1

1

2

1

1

2

3

2

2

6

4

5

7

19

5

12

18

63

6

35

60

216

7

108

196

760

8

369

704

2725

9

1285

2500

9910

10

4655

9189

39446

11

17073

33896

135268

12

63600

126759

505861

13

238591

476270

1903890

14

901971

1802312

7204874

15

3426576

6849777

27394666

16

13079255

26152418

104592937

17

50107909

100203194

400795844

18

192622052

385221143

1540820542

19

742624232

1485200848

5940738676

20

2870671950

5741256764

22964779660

21

11123060678

22245940545

88983512783

22

43191857688

86383382827

345532572678

23

168047007728

336093325058

1344372335524

24

654999700403

1309998125640

5239988770268

25

2557227044764

5114451441106

20457802016011

26

9999088822075

19998172734786

79992676367108

27

39153010938487

78306011677182

313224032098244

28

153511100594603

307022182222506

1228088671826973

29

602621953061978

1205243866707468

4820975409710116

30

2368347037571252

4736694001644862

18946775782611174

31

9317706529987950

18635412907198670

74541651404935148

32

36695016991712879

73390033697855860

293560133910477776

33

144648268175306702

289296535756895985

1157186142148293638

34

570694242129491412

1141388483146794007

4565553929115769162

35

2253491528465905342

4506983054619138245

18027932215016128134

36

8905339105809603405

17810678207278478530

71242712815411950635

37

35218318816847951974

70436637624668665265

281746550485032531911

38

139377733711832678648

278755467406691820628

1115021869572604692100

39

551961891896743223274

1103923783758183428889

4415695134978868448596

40

2187263896664830239467

4374527793263174673335

17498111172838312982542

41

8672737591212363420225

17345475182286431485513

69381900728932743048483

42

34408176607279501779592

68816353214298169362691

275265412856343074274146

43

136585913609703198598627

273171827218863802383383

1092687308874612006972082

44

542473001706357882732070

1084946003411691009916361

4339784013643393384603906

45

2155600091107324229254415

4311200182212516601049225

17244800728846724289191074

46

 

 

68557762666345165410168738

47

 

 

272680844424943840614538634

48

 

 

1085035285182087705685323738

49

 

 

4319331509344565487555270660

50

 

 

17201460881287871798942420736

51

 

 

68530413174845561618160604928

52

 

 

273126660016519143293320026256

53

 

 

1088933685559350300820095990030

54

 

 

4342997469623933155942753899000

55

 

 

17326987021737904384935434351490

56

 

 

69150714562532896936574425480218

 

Non si conosce alcuna formula generale per determinare il numero di polimini costruibili con un numero fissato di quadrati, tuttavia David Klarner dimostrò nella sua tesi di laurea nel 1966 che esiste una costante K tale che il numero di n-omini, contando separatamente i diversi orientamenti che possono avere, tende a Kn al tendere di n all’infinito (v. costante di Klarner).

 

Tutti i polimini formati da un massimo di 6 quadrati tassellano il piano, ma al crescere del numero di celle aumenta anche il numero di quelli che non tassellano il piano, inclusi naturalmente tutti quelli con dei buchi.

I più semplici polimini che non possono tassellare il piano, neppure se riflessi o ruotati, sono i quattro eptamini mostrati nella figura, che includono il più piccolo polimino con un buco.

I 4 eptamini che non tassellano il piano

 

La tabella seguente riporta il numero di polimini senza buchi e quelli che tassellano il piano per i primi numeri di quadrati (Joe Keane, Joseph Myers e Tomás Oliveira e Silva, The Online Encyclopedia of Integer Sequences http://oeis.org).

Quadrati

Tassellano il piano

Senza buchi

1

1

1

2

1

1

3

2

2

4

5

5

5

12

12

6

35

35

7

104

107

8

343

363

9

1050

1248

10

3070

4460

11

6620

16094

12

23449

58937

13

38669

217117

14

109104

805475

15

279583

3001211

16

546893

11230003

17

827035

42161529

18

3057332

158781106

19

3381124

599563893

20

12126683

2269506062

21

21921192

8609442688

22

37008138

32725637373

23

53327764

124621833354

24

220908809

475368834568

25

271293803

1816103345752

26

 

6948228104703

 

Sono anche stati considerati i polimini colorati con due colori, secondo il consueto schema a scacchiera, considerando distinti due polimini che, a parità di forma, abbiano diversa colorazione.

La figura seguente mostra i polimini colorati a scacchiera, formati da fino a 3 quadrati.

I polimini colorati a scacchiera, formati da fino a 3 quadrati

 

La seguente tabella riporta i risultati noti (John Mason, Joseph Myers e N.J.A. Sloane, The Online Encyclopedia of Integer Sequences http://oeis.org).

Quadrati

Colorati

1

2

2

1

3

4

4

7

5

24

6

62

7

216

8

710

9

2570

10

9215

11

34146

12

126853

13

477182

14

1802673

15

6853152

16

26153758

17

100215818

18

385226201

19

1485248464

20

5741275753

21

22246121356

22

86383454582

23

336094015456

 

Bibliografia

  • Cipra, Barry;  Demaine, Erik D.;  Demaine, Martin L.;  Rodgers, Tom;  Tribute to a Mathemagician, Wellesley , A.K. Peters, 2005 -

    Una sorta di “atti del convegno” relativi al quinto “Gathering for Gardner”, del 2004

  • Finch, Steven R.;  Mathematical Constants, Cambridge, Cambridge University Press, 2003.
  • Gardner, Martin;  "Giochi matematici" in Le Scienze, Milano, n. 112, dicembre 1977, pag. 126 – 132.
  • Gardner, Martin;  "Giochi matematici" in Le Scienze, Milano, n. 127, marzo 1979, pag. 114 – 118.
  • Gardner, Martin;  "Giochi matematici" in Le Scienze, Milano, n. 51, novembre 1972, pag. 98 – 101.
  • Gardner, Martin;  "Giochi matematici" in Le Scienze, Milano, n. 69, maggio 1974, pag. 90.
  • Gardner, Martin;  "Giochi matematici" in Le Scienze, Milano, n. 74, ottobre 1974, pag. 108.
  • Gardner, Martin;  "Giochi matematici" in Le Scienze, Milano, n. 89, gennaio 1976, pag. 106 – 107.
  • Gardner, Martin;  "Giochi matematici" in Le Scienze, Milano, n. 93, maggio 1976, pag. 100 – 104.
  • Gardner, Martin;  Enigmi e giochi matematici 6, Firenze, Sansoni, 1969 -

    Traduzione di Martin Gardner’s New Mathematical Diversions from Scientific American, New York, Simon and Schuster, 1966.

  • Gardner, Martin;  Enigmi e giochi matematici volume 4º, Firenze, Sansoni, 1975 -

    Traduzione di The Unexpected Hanging and Other Mathematical Diversions, New York, Simon and Schuster, 1966.

  • Gardner, Martin;  Enigmi e giochi matematici volume 5º, Firenze, Sansoni, 1976 -

    trad. di Mathematical Puzzles and Diversions, New York, Simon and Schuster, 1959

  • Gardner, Martin;  Martin Gardner's Sixth Book of Mathematical Games from Scientific American, San Francisco, W.H. Freeman, 1971.
  • Gardner, Martin;  Mathematical Magic Show, Washington D.C., The Mathematical Association of America, 1990.
  • Gardner, Martin;  Mathematical Puzzles and Diversions, New York, Simon and Schuster, 1959.
  • Gardner, Martin;  Polyominoes: A Guide to Puzzles and Problems in Tiling, Washington D.C., The Mathematical Association of America, 1991.
  • Gardner, Martin;  Riddles of the Sphynx and Other Mathematical Puzzle Tales, Washington D.C., The Mathematical Association of America, 1987.
  • Gardner, Martin;  The Colossal Book of Mathematics, New York, W.W. Norton & Company, 2001.
  • Gardner, Martin;  The Colossal Book of Short Puzzles and Problems, New York, W.W. Norton & Co., 2006.
  • Gardner, Martin;  Time Travel and Other Mathematical Bewilderements, San Francisco, W.H. Freeman, 1988.
  • Golomb, S.W.;  Polyominoes: Puzzles, Patterns, Problems and Packings, Princeton, Princeton University Press, II ed. riveduta e ampliata, 1994 -

    Una riedizione a lungo attesa di Polyominoes, Scribner, New York, 1965

  • Golomb, S.W.;  Polyominoes, New York, Scribner, 1965 -

    Il testo fondamentale sull’argomento, quasi introvabile

  • Honsberger, Ross;  In Pólya’s Footsteps, The Mathematical Association of America, 1997 -

    Una magnifica raccolta di problemi a sfondo matematico e geometrico di vario tipo.

  • Klamkin, Murray S.;  International Mathematical Olympiads 1978 – 1985, Washington, The Mathematical Association of America, 1986 -

    Raccolta di problemi stimolanti, alla portata di studenti delle medie superiori.

  • Klarner, David A.;  "Cell Growth Problems" in Canadian Journal of Mathematics, n. 19, 1967, pag. 851 – 863.
  • Klarner, David A.;  The Mathematical Gardner, Wadsworth, Belmont, 1969.
  • Lunnon, W.F.;  Computers in Number Theory, Londra, Academic Press, 1971.
  • Marshall, William Rex;  "Packing Rectangles with Congruent Polyominoes" in Journal of Combinatorial Theory, 1997.
  • Redelmeier, D.H.;  "Counting Polyominoes: Yet Another Attack" in Discrete Mathematics, n. 36, 1981, pag. 191 – 203.
  • Stanley, Richard P.;  Enumerative Combinatorics, Cambridge University Press, vol. I, 1997.

Contattami

Potete contattarmi al seguente indirizzo bitman[at]bitman.name per suggerimenti o segnalazioni d'errori relativi a questo articolo.