Pentomino

În geometrie un pentomino este o formă geometrică compusă din cinci pătrate conectate ortogonal (adică latură la latură, nu doar la colțuri). Denumirea lor provine din prefixul penta-. Pentominourile, ca și dominourile și tetrominourile, sunt un anumit tip de poliominouri.

Cele 12 pentominouri au 18 forme diferite,
cu 6 dintre ele chirale (în oglindă)

Atunci când rotațiile și reflexiile nu sunt considerate a fi forme distincte, există 12 pentominouri diferite libere. Când reflexiile sunt considerate distincte, există 18 pentominouri unilaterale. Când rotațiile sunt și ele considerate distincte, există 63 de pentominouri fixe.

Jocurile matematice de pavare cu pentominouri sunt populare în matematica recreativă. Uzual, jocurile video imitând Tetris consideră reflexiile ca fiind distincte, deci folosesc setul complet de 18 pentominouri unilaterale. (Tetris folosește forme din patru pătrate.)

Oricare dintre cele douăsprezece pentominouri satisface criteriul Conway; prin urmare, oricare pentomino este capabil să paveze planul. Oricare pentomino chiral poate pava planul fără a fi nevoie de reflexia sa.

Istoric

Comparație a schemelor de etichetare a celor 12 pentominouri shapes. Prima schemă este cea folosită în articol. A doua este cea a lui Conway.

Cel mai vechi puzzle care conține un set complet de pentominouri a apărut în cartea lui Henry Dudeney, The Canterbury Puzzles, publicată în 1907. Cele mai vechi pavări ale dreptunghiurilor cu un set complet de pentominouri au apărut în The Problemist: Fairy Chess Supplement (PFCS) în 1935, iar alte probleme de pavare au fost explorate în PFCS și succesorul său, Fairy Chess Review.

Pentominourile au fost definite astfel de Solomon W. Golomb începând din 1953 și mai târziu în cartea sa din 1965 Polyominoes: Puzzles, Patterns, Problems, and Packings. Acestea au fost prezentate publicului larg de către Martin Gardner în rubrica Jocuri matematice din Scientific American din octombrie 1965. Golomb a inventat termenul "pentomino" din greaca veche πέντε (cinci) și -omino-ul din domino, interpretând cu fantezie " d-" din "domino" ca și cum ar fi o formă a prefixului grecesc "di-" (doi). Golomb a denumit cele 12 pentominouri libere după literele alfabetului latin cu care se aseamănă, folosind mnemonica FILiPiNo împreună cu sfârșitul alfabetului (TUVWXYZ).

John Horton Conway a propus o schemă alternativă de etichetare pentru pentomino, folosind O în loc de I, Q în loc de L, R în loc de F și S în loc de N. Asemănarea cu literele este mai ciudată, în special pentru O pentomino, dar această schemă are avantajul de a folosi 12 litere consecutive ale alfabetului. Este folosit prin convenție în discutarea Jocului Vieții al lui Conway, unde, de exemplu, se vorbește despre R-pentomino în loc de F-pentomino.

Simetrie

• F, L, N, P și Y pot fi orientate în 8 moduri: 4 prin rotație și încă 4 pentru imaginea în oglindă. Grupul lor de simetrie constă numai din transformarea identică.
• T și U pot fi orientate în 4 moduri prin rotație. Au o axă de reflexie aliniată cu grila. Grupul lor de simetrie are două elemente, identitatea și reflexia față de o dreaptă paralelă cu laturile pătratelor.
• V și W pot fi, de asemenea, orientate în 4 moduri prin rotație. Au o axă de reflexie la 45° față de grilă. Grupul lor de simetrie are două elemente, identitatea și o reflexie diagonală.
• Z poate fi orientat în 4 moduri: 2 prin rotație și încă 2 pentru imaginea în oglindă. Are simetrie punctuală de ordinul 2. Grupul său de simetrie are două elemente, identitatea și rotația de 180°.
• I poate fi orientat in 2 moduri prin rotație. Are două axe de reflexie, ambele aliniate cu grila. Grupul său de simetrie are patru elemente, identitatea, două reflexii și rotația de 180°. Este grupul diedral de ordinul 2, cunoscut și sub numele de grupul lui Klein.
• X poate fi orientat într-un singur mod. Are patru axe de reflexie, aliniate cu grila și diagonalele ei, și simetrie de rotație de ordinul 4. Grupul său de simetrie, grupul diedral de ordinul 4, are opt elemente.

Pentominourile F, L, N, P, Y și Z sunt chirale; prin adăugarea reflexiilor lor (F′, J, N′, Q, Y′, S) numărul de pentominouri unilaterale este de 18. Dacă și rotațiile sunt considerate distincte, atunci pentominourile din prima categorie se numără de opt ori, cele din următoarele trei categorii (T, U, V, W, Z) se numără de patru ori, I se numără de două ori, iar X numără o singură dată. Rezultă 5×8 + 5×4 + 2 + 1 = 63 pentominouri fixe.

În imaginile de mai jos sunt ilustrate cele opt orientări posibile ale pentominourilor F, L, N, P și Y și cele patru orientări posibile ale pentominourilor T, U, V, W și Z.

• Opt posibile orientări
• 
  F-pentomino
• 
  L-pentomino
• 
  N-pentomino
• 
  P-pentomino
• 
  Y-pentomino

• patru posibile orientări
• 
  T-pentomino
• 
  U-pentomino
• 
  V-pentomino
• 
  W-pentomino
• 
  Z-pentomino

În general, pentru figurile bidimensionale există încă două categorii:

• Orientabil în 2 moduri printr-o rotație de 90°, cu doua axe de reflexie, ambele aliniate cu diagonalele. Acest tip de simetrie necesită cel puțin un heptomino.
• Orientabil în 2 moduri, în care unul este imaginea în oglindă a celuilalt, de exemplu o svastică. Acest tip de simetrie necesită cel puțin un octomino.

Jocuri

Puzzle de pavare

Exemple de pavări

Un puzzle pentomino standard este pavarea unui dreptunghi cu un set de pentominouri, fără suprapuneri și fără goluri. Fiecare dintre cele 12 pentominouri are o suprafață de 5 pătrate, deci cutia trebuie să aibă o suprafață de 60. Dimensiunile posibile sunt 6×10, 5×12, 4×15 și 3×20.

Cazul 6×10 a fost rezolvat pentru prima dată în 1960 de Colin Brian Haselgrove și Jenifer Haselgrove. Există exact 2339 de soluții, excluzând variantele triviale obținute prin rotația și reflexia întregului dreptunghi, dar incluzând rotația și reflexia unui subset de pentominouri (care oferă uneori o soluție suplimentară într-un mod simplu). Dreptunghiul de 5×12 are 1010 soluții, cel de 4×15 are 368 de soluții, iar cel de 3×20 are doar 2 soluții (una este prezentată în figură, iar cealaltă poate fi obținută din soluția prezentată prin rotirea ansamblului format din pentominourile L, N, F, T, W, Y și Z).

Un puzzle ceva mai ușor (mai simetric), dreptunghiul de 8×8 cu o gaură de 2×2 în centru, a fost rezolvat de Dana Scott încă din 1958. Există 65 de soluții. Algoritmul lui Scott a fost una dintre primele aplicații ale unui program de calculator pentru backtracking. Variantele acestui puzzle permit ca cele patru găuri să fie plasate în orice poziție.

Au fost descriși algoritmi eficienți pentru a rezolva astfel de probleme, de exemplu de către Donald Knuth. Funcționând pe hardware modern, aceste puzzle-uri pentomino pot fi acum rezolvate în doar câteva secunde.

Modele fără soluții

Cele mai multe astfel de modele sunt rezolvabile, cu excepția plasării fiecărei perechi de găuri lângă două colțuri ale dreptunghiului, astfel încât ambele colțuri să poată fi acoperite doar de un P-pentomino sau prin forțarea unui T-pentomino sau U-pentomino într-un colț, însă astfel se creează o altă gaură.

Setul de pentominouri este singurul set de poliominouri libere care poate fi împachetat într-un dreptunghi, cu excepția seturilor triviale monomino și domino, fiecare dintre ele constând doar dintr-un singur dreptunghi.

Bibliografie

• en Chasing Vermeer, with information about the book Chasing Vermeer and a click-and-drag pentomino board.
• en Pritchard, David B. (1982). „Golomb's Game”. Brain Games. Penguin Books Ltd. pp. 83–85. ISBN 0-14-00-5682-3. 

Vezi și

• Tetromino – forma precedentă
• Hexomino – forma următoare

Legături externe

• Materiale media legate de pentomino la Wikimedia Commons

• en Pentomino configurations and solutions An exhaustive listing of solutions to many of the classic problems showing how each solution relates to the others.