Polyomino

Versiunea actuală a paginii nu a fost încă examinată de colaboratori experimentați și poate diferi semnificativ de versiunea revizuită pe 10 iulie 2019; verificările necesită 3 modificări .

Polyomino , sau polyomino ( engleză  polyomino ) - forme geometrice plate formate prin conectarea mai multor pătrate unicelulare pe laturile lor. Acestea sunt poliforme ale căror segmente sunt pătrate [1] .

O piesă de poliomino poate fi privită ca un subset finit conectat al unei table de șah infinite care poate fi ocolită de o turnă [1] [3] .

Denumiri de poliomino

Poliominoele ( n -minos) sunt denumite după numărul n de pătrate din care sunt formate:

n Nume n Nume
unu monomino 6 hexamino
2 domino 7 heptamino
3 tromino opt octamino
patru tetramino 9 nonamino sau enneomino
5 pentomino zece decamino

Istorie

Poliominoele au fost folosite în matematica de divertisment din cel puțin 1907 [4] [5] și sunt cunoscute încă din antichitate. Multe rezultate cu cifre care conțin de la 1 la 6 pătrate au fost publicate pentru prima dată în Fairy Chess Review între 1937 și 1957 sub titlul „ probleme de disecție ” .  Numele „poliomino” sau „poliomino” ( ing. polyomino ) a fost inventat de Solomon Golomb [1] în 1953 și apoi popularizat de Martin Gardner [6] [7] .  

În 1967 revista Science and Life a publicat o serie de articole despre pentominoe . Mai târziu, probleme legate de poliominoe și alte poliforme au fost publicate pentru un număr de ani [8] .

Generalizări ale poliominoelor

În funcție de dacă este permisă răsturnarea sau rotirea figurilor, se disting următoarele trei tipuri de poliomino [1] [2] :

În funcție de condițiile de conectivitate ale celulelor învecinate, se disting următoarele [1] [9] [10] :

Următorul tabel colectează date despre numărul de figuri poliomino și generalizările acestuia. Numărul de cvasi - n -minos este 1 pentru n  = 1 și ∞ pentru n  > 1.

n poliominoe pseudopoliomino
bilateral unilateral fix bilateral unilateral fix
toate cu gauri fara gauri
A000105 A001419 A000104 A000988 A001168 A030222 A030233 A006770
unu unu 0 unu unu unu unu unu unu
2 unu 0 unu unu 2 2 2 patru
3 2 0 2 2 6 5 6 douăzeci
patru 5 0 5 7 19 22 34 110
5 12 0 12 optsprezece 63 94 166 638
6 35 0 35 60 216 524 991 3832
7 108 unu 107 196 760 3031 5931 23 592
opt 369 6 363 704 2725 18 770 37 196 147 941
9 1285 37 1248 2500 9910 118 133 235 456 940 982
zece 4655 195 4460 9189 36 446 758 381 1 514 618 6 053 180
unsprezece 17 073 979 16 094 33 896 135 268 4 915 652 9 826 177 39 299 408
12 63 600 4663 58 937 126 759 505 861 32 149 296 64 284 947 257 105 146

Poliforme

Poliformele  sunt o generalizare a poliominoelor, ale căror celule pot fi orice poligoane sau poliedre identice. Cu alte cuvinte, o poliformă este o figură plată sau un corp spațial, constând din mai multe copii conectate ale unei forme de bază date [11] .

Poliformele plane (bidimensionale) includ poliamondele , formate din triunghiuri echilaterale; polihexuri , formate din hexagoane regulate; polyabolo , constând din triunghiuri dreptunghiulare isoscele și altele.

Exemple de poliforme spațiale (tridimensionale): policuburi, formate din cuburi tridimensionale; polironi ( ing.  polyrhons ), format din rombododecaedre [12] .

Poliformele sunt generalizate și în cazul dimensiunilor superioare (de exemplu, cele formate din hipercuburi - polihipercuburi).

Sarcini

Acoperiri de dreptunghiuri prin poliominouri congruente

Ordinea poliominoului P  este numărul minim de copii congruente ale lui P suficiente pentru a plia un dreptunghi. Pentru poliomino, din copiile cărora nu se poate adăuga niciun dreptunghi, ordinea nu este definită. Ordinul poliominoului P este egal cu 1 dacă și numai dacă P  este dreptunghi [13] .

Dacă există cel puțin un dreptunghi care poate fi acoperit de un număr impar de copii congruente ale lui P , poliomino P se numește poliomino impar ; dacă dreptunghiul poate fi pliat doar dintr-un număr par de copii P , P se numește poliomino par .

Această terminologie a fost introdusă în 1968 de D. A. Klarner [1] [14] .

Există un set de poliominoe de ordinul 2; un exemplu este așa-numitele L - poliominoe [15] .

Probleme nerezolvate la matematică : Există un poliomino a cărui ordine este un număr impar?

Poliomino de ordinul 3 nu există; o dovadă în acest sens a fost publicată în 1992 [16] . Orice poliomino ale cărui trei copii pot forma un dreptunghi este el însuși dreptunghi și are ordinul 1. Nu se știe dacă există un poliomino a cărui ordine este un număr impar mai mare decât 3 [14] .

Există poliominouri de ordinul 4 , 10 , 18 , 24 , 28 , 50 , 76 , 92 , 312 ; există o construcție care face posibilă obținerea unui poliomino de ordinul 4 s pentru orice s natural [14] .

Probleme nerezolvate la matematică : Care este cea mai mică multiplicitate impară posibilă a acoperirii unui dreptunghi cu un poliomino nedreptunghiular?

Klarner a reușit să găsească un poliomino non-dreptunghiular de ordinul 2, din care 11 copii pot forma un dreptunghi [1] [14] [17] , și niciun număr impar mai mic de copii ale acestui poliomino poate acoperi dreptunghiul. Din octombrie 2015, nu se știe dacă există un poliomino nedreptunghiular ale cărui 9, 7 sau 5 copii pot forma un dreptunghi; nu se cunosc alte exemple de poliominoe cu o multiplicitate minimă impară de acoperire 11 (cu excepția celui găsit de Klarner).

Suprafețele minime

Regiunea minimă ( ing. regiune minimă , superformă comună minimă ) pentru un set dat de poliomino - poliominoe de cea mai mică suprafață posibilă, care conține fiecare poliomino din setul dat [1] [14] [18] . Problema găsirii ariei minime pentru un set de douăsprezece pentominoe a fost pusă pentru prima dată de T. R. Dawson în Fairy Chess Review în 1942 [18] .

Pentru un set de 12 pentominoe, există două regiuni minime de nouă celule, reprezentând 2 din 1285 nonominoe [1] [14] [18] :

### ### ##### ##### # #

Vezi și

Note

  1. ↑ 1 2 3 4 5 6 7 8 9 10 Golomb S. V. Polimino, 1975
  2. ↑ 1 2 Weisstein, Eric W. Polyomino  (engleză) pe site-ul Wolfram MathWorld .
  3. ↑ 1 2 Definiția populară a poliomino-urilor folosind o turnă de șah nu este strictă: există subseturi deconectate de parchet pătrat pe care o turnă le poate ocoli (de exemplu, un grup de patru pătrate dintr-o tablă de șah a1, a8, h1, h8 nu este un tetramino , deși o turnă stă pe unul dintre aceste câmpuri, poate ocoli alte trei câmpuri în trei mișcări). O definiție mai riguroasă a poliominoelor ar fi cu ajutorul figurii „vizir” folosită în șahul lui Tamerlan : vizirul mișcă o singură celulă orizontal sau vertical.
  4. ↑ Henry E. Dudeney. Canterbury Puzzles, 1975, p. 111–113
  5. ↑ Alexandre Owen Muñiz. Câteva probleme frumoase de colorat pe Pentomino . Preluat la 24 octombrie 2015. Arhivat din original la 4 martie 2016.
  6. ↑ Gardner M. Mathematical puzzles and entertainment, 1971. - Capitolul 12. Polyomino. - p.111-124
  7. ↑ Gardner M. Romane matematice, 1974. - Capitolul 7. Pentominoes and polyominoes: five games and a series of problems. - p.81-95
  8. ↑ Știința și viața nr. 2-12 (1967), 1, 6, 9, 11 (1968), etc.
  9. ↑ Poliforme . Preluat la 22 august 2013. Arhivat din original la 11 septembrie 2015.
  10. ^ Weisstein, Eric W. Polyplet pe site- ul Wolfram MathWorld .  
  11. ^ Weisstein , Eric W. Polyform  pe site- ul Wolfram MathWorld .
  12. ↑ Col. Pagina de pornire a lui Sicherman. Polyform Curiosities Arhivat 14 decembrie 2014 la Wayback Machine . Catalog of Polyrhons Arhivat 11 septembrie 2015 la Wayback Machine
  13. ↑ Karl Dahlke. Placare dreptunghiuri cu poliominoe . Preluat la 25 august 2013. Arhivat din original la 15 februarie 2020.
  14. ↑ 1 2 3 4 5 6 Golomb, S. V. Polyominoes : Puzzle-uri, modele, probleme și pachete  . - Ed. a II-a - Princeton University Press, 1994. - ISBN 0-691-08573-0 .
  15. ^ Weisstein, Eric W. L-Polyomino pe site- ul Wolfram MathWorld .  
  16. ↑ ÎN Stewart, A. Wormstein. Polyominoes of Order 3 Do Not Exist  //  Journal of Combinatorial Theory, Seria A  : jurnal. - 1992. - Septembrie ( vol. 61 , nr. 1 ). - P. 130-136 .
  17. ↑ Michael Reid. Primele lui P hexomino . Preluat la 24 octombrie 2015. Arhivat din original la 22 martie 2016.
  18. ↑ 1 2 3 Alexandre Owen Muñiz. Superforme comune poliomino . Consultat la 24 octombrie 2015. Arhivat din original la 21 mai 2017.

Literatură

Link -uri


  Accesați articolul Wikidata  Dicționare și enciclopedii
În cataloagele bibliografice
 Poliforme
Tipuri de poliforme
Poliomino după numărul de celule
Puzzle-uri cu policuburi
Sarcina de stivuire
  • Problemă de acoperire exactă
  • Algoritmul
  • Legături
Personalități
subiecte asemănătoare
Alte puzzle-uri și jocuri