Puzzle-ul Tromino de Norton Starr

Sursă Originală:  https://nstarr.people.amherst.edu/trom/intro.html

Despre Puzzle – fizic și virtual

Puzzle-ul de bază constă din 21 de piese în formă de unghi drept (“țigle”) de felul arătat, compuse din trei pătrate; o singură placă pătrată singură; și un plan, 8 8 grilă pătrat ale cărui pătrate sunt de aceeași mărime ca și cele ale plăcilor. Placile ocupă un total de 3 21 + 1 = 63 + 1 = 64 pătrate, același număr de pătrate ca și pe un tablă de șah. În cele ce urmează, numim aceste tromboane sub formă deunghiuri , fiind cel mai simplu dintre numeroasele denumiri utilizate pentru acestea, care includ L-trominoame, L-triominoase și V-trominoase.

Pentru a reda o versiune fizică a acestui puzzle, folosind 21 de piese trombotice reale, o singură bucată pătrată și o bază de șuruburi de 8 8, poziționează prima piesa unică pătrată pe oricare dintre cele 64 de locații pătrate de pe bază. Apoi, umpleți cele 63 de pătrate rămase cu trominele, astfel încât să nu existe o suprapunere și nici un pătrat neinchis. O astfel de soluție la puzzle este numită o placare a pătratului 8 8. Alternativ, începeți prin introducerea succesivă a trominoanelor în baza de șah (fiecare astfel de țiglă ocupând doar trei pătrate ale modelului grilei) și atunci când toate cele 21 sunt poziționate, plasați placa țiglă unică într-o singură poziție care rămâne disponibilă.

Iată fundalul versiunii comerciale a acestui puzzle, comercializat de Kadon Enterprises . La întâlnirea anuală din ianuarie 2000 a Asociației Matematice a Americii, Arthur Benjamin a primit premiul Haimo pentru distinsul preșcolar. În discursul său de acceptare a schițat dovada lui favorită prin inducție. Acest raționament asigură faptul că un 2 n 2 n celled square (adică un tablou de bord generalizat cu 2 npătrate de-a lungul fiecărei laturi) cu o celulă ocupată, pot fi întotdeauna acoperite cu tromboane. Trei ani după ce auzisem observațiile lui Benjamin, dau o prelegere despre inducție și am reamintit dovezile sale preferate. Suplimentând exemplele mele pregătite, am anunțat acest argument clasic, datorită lui Solomon Golomb. Gândindu-ne că un puzzle real de acest fel ar adăuga un element al realității și ar putea declanșa interes în metoda de inducție, am trimis o notă lui Kadon, un producător de puzzle-uri de top, pentru a vedea dacă au ceva de cumpărat. Ei nu au făcut-o, așa că am întrebat dacă ar face unele la specificațiile mele. O serie de e-mailuri cu Kate Jones, președintele Kadon, au dus la un puzzle de felul ilustrat mai sus. Ea a sugerat folosirea mai multor culori diferite pentru gresie tromino, facand acest lucru un puzzle mai interesant decat mi-am imaginat initial. Am optat pentru plăci mai rece, translucide, mai degrabă decât cele îndrăznețe, opace, și am ales albastru, aqua și ametist pentru tromine.

Kate a întrebat dacă l-aș lăsa pe Kadon să adauge puzzle-ul la gama de produse pe care le vând și am acceptat cu ușurință – am vrut doar câteva pentru uzul meu. Spre surprinderea mea, ea a declarat că voi primi redevențe. Acesta nu a fost niciodată țelul meu, iar toate redevențele mele sunt donate Colegiului Amherst și Asociației Matematice din America .

Kadon a scos puzzle-ul sub numele de “Vee-21”; consultați www.gamepuzzles.com/polycub2.htm#V21. Această versiune comercială, în trei culori vii, translucide acrilice, vine cu o broșură de patruzeci de pagini, care oferă o serie de îmbunătățiri ale puzzle-ului de bază. Kate a contribuit cu unele extensii ale puzzle-ului, unele jocuri de strategie pentru două persoane și sugestia de cerințe de separare a culorilor pentru tiling-urile pe care le-ar putea încerca. De asemenea, a descoperit posibilitățile estetice de a face modele simetrice. Kate a invitat-o ​​pe Oriel Maxim să contribuie cu unele dintre provocările sale de tip labirint cu tromboanele, iar broșura include o varietate de șabloane dreptunghiulare cu linii alese strategic ale rețelelor întunecate pentru a servi ca bariere în care nu pot fi plasate tromi.

Două puzzle-uri de calculator interactive de acest tip sunt furnizate aici. Puzzle -ul 8-de-8 a fost dezvoltat de doi dintre studenții mei, în timp ce un coleg de departament a contribuit la puzzle -ul M-by-N . Puzzle-ul M-by-N (care se joacă pe majoritatea sistemelor, dar poate fi încărcat lent) este oarecum mai flexibil, permițând alegerea oricărui număr de rânduri și coloane între 2 și 32 inclusiv. Puzzle-ul 8-by-8 (se joacă cel mai bine cu Internet Explorer pe un PC) are o acțiune diferită a mouse-ului și este limitat în mod util la trei culori de tromino. Instrucțiunile sunt date cu fiecare. Versiunile online și Kadon au o amploare neobișnuită de recurs, interesant pentru cei de patru ani, precum și puzzle-uri condimentate.


Istoric
Dovezile că, pentru orice număr întreg pozitiv n, un pătrat2n 2ncu o celulă ocupată (un pătrat “deficient”) poate fi întotdeauna acoperit de tromine datorită lui Solomon Golomb. El a publicat-o în articolul său din 1954 [9] înAmerican Mathematical Monthly. După cum sa menționat mai sus, a fost pentru a ilustra argumentul lui Golomb pentru 2n 2n pătrate deficiente pe care puzzle-ul a fost comandat. Același articol a introdus în imprimarea termenuluitrominoși generalizarea acestuia, polyomino. Un poliomino este o matrice conectată de pătrate identice având proprietatea că oricare două pătrate nu ating sau altfel se întâlnesc de-a lungul unei margini întregi, comune.Singurele două forme tromino sunt trei pătrate la rând și forma L a acestui puzzle, iar aici “tromino” se referă numai la acesta din urmă. 

Dovada lui Golomb este un prim exemplu de inducție matematică. Dincolo de eleganța pură a argumentului, este un exemplu rar al aplicării non-numerice a metodei. Acest lucru este în contrast cu exemplele și exercițiile care se găsesc adesea în tratamentele de inducție ale manualelor, care de obicei constau într-o varietate de formule pentru sume finite, inegalități și altele asemenea. Prima apariție a probei într-un mediu popular a fost făcută de Joseph MadachyRevista de Matematică Recreativă ( RMM ), în care Golomb a inclus aceasta în prima din cele patru părți ale articolelor sale despre poliominoase publicate în RMM [10]. În coloana științifică americană din 1957, Martin Gardner, care a introdus poliominoase publicului larg, el a remarcat că “o tablă cu un pătrat care lipsește în orice moment poate fi acoperită de 21 de tromine drepte” [6, p.154]. Pentru prima sa carte de jocuri matematice colectate coloanele, Gardner a elaborat remarcandu-se că “un argument ingenios de inducție demonstrează că 21 de tromine drepte și un monomino vor acoperi placa 8-cu-8, indiferent de locul în care este plasat monomino” [8, p. 126]. 

Argumentul tromino Tigla pentru table de șah cu deficit și generală 2 n 2 n teoremă a apărut într – o succesiune de cărți încă de la lunare și RMM articole. A fost explicată înPolyominoes clasice ale lui Golomb[11, 1965, pp. 21-22] și în a doua ediție a acestei cărți [11, 1994, p. 5]. A doua ediție oferă o istorie bogată și un sondaj amplu al acestui subiect interesant și este plin de imagini și puzzle-uri. Cele 22 de pagini de referință, citând atât cărți, cât și articole, reprezintă un bonus suplimentar. Indicele de nume enumeră 81 de indivizi, destul de puțini menționați de mai multe ori în corpul cărții. Multe dintre acestea vor fi recunoscute de aventuri de joc și matematicieni amatori, precum și de profesioniști din ambele zone. O descriere a cărții este prezentată în revistă [17] de George Martin. În 1976, Ross Honsberger a dat o luciditate detaliată a argumentelor lui Golomb la bordul lui în pietrele sale matematice II[13, p. 61]. Ideea de bază a dovezii este menționată, de asemenea, în cartea lui George E. Martin dedicată polimino-tilings [16, pp. 27-28]. Revizuirea lui David Singmaster [22] din această carte din urmă este deosebit de interesantă, deoarece oferă o schiță frumoasă a subiectului și a istoriei sale.

Acest subiect este, de asemenea, un tarif din ce în ce mai obișnuit pentru texte și cărți cu probleme. De exemplu, ea apare în textele discrete de matematică ale lui Susanna Epp [5, p. 234], Richard Johnsonbaugh (care menționează înclinările de tromboane ale dreptunghiurilor ca rezultat al designului layout-ului VLSI) [14, pp. 58-59] și Kenneth Rosen [20, pp. 247-8]. Tromboanele sunt tratate, de asemenea, în cartea lui Daniel Velleman despre construirea dovezilor [26, pp. 271-275] și cărțile cu probleme ale lui John P. D’Angelo & Douglas B. West [1, p. 75] și de Jiř Herman, Radan Kučera și Jaromîr im a [12, p. 271]. Cea mai cristalină ilustrare a argumentului Golomb este “dovada fără cuvinte” de rezervă a lui Roger Nelsen, dată în cea de-a doua carte a acelui titlu [19, p. 123].

Această arie de matematică recreativă a beneficiat de un flux continuu de investigații și de probleme sugerate. În 1985 și 1986, I-Ping Chu și Richard Johnsonbaugh au studiat problema plăcilor cu placi de deficiență a plăcilor, unde nu mai trebuie să existe o putere de 2 și, mai general, plăci rectangulare deficitare și ne-deficiente [3, 4 ].Cartea lui George Martin a inclus un capitol întreg dedicat tromboanelor [16, pp. 23-37]. Problemele de culoare pentru tromboaiele sunt tratate de Ilvars Mizniks, care recunoaște pagina de selecție a culorilor Kadon Vee-21 drept sursă de inspirație pentru cercetarea sa [18]. 2004 articol[2] de J. Marshall Ash și Solomon Golomb, despre tromboașajul dreptunghiurilor deficitare, conține câteva rezultate noi și de bază, dintre care unul răspunde la o întrebare veche de Chu și Johnsonbaugh. Cenușa și Golomb se termină cu o problemă deschisă cu privire la dreptunghiurile cu 2 deficiențe (dreptunghiuri cu două celule îndepărtate). 

Internetul este o sursă bună de afișări și informații privind tigla. De exemplu, o căutare pe “tromino” și “tiling” se referă la applet-uri precum cele de Alexander Bogomolny la www.cut-the-knot.org/Curriculum/Games/TrominoPuzzle.shtml și Christopher Mawata la www.utc.edu/ Facultatea / Christopher-Mawata / trominos / , care ilustrează tromino-puzzle-uri de mai multe dimensiuni.


Variante
Aici sunt câteva extensii ale puzzle-ului tromboan pe care le-ar putea lua în considerare cititorii. Prima a fost sugerată de fratele meu Raymond (Pete), care a întrebat cum s-ar putea aranja trominele în grila 8/88 pentru a maximiza numărul de neocupațipătrate. Acest lucru poate fi elaborat: o singură rută ar presupune că plăcile și grilele sunt împachetate astfel încât să rămână în poziție, în timp ce alternativ se poate permite ca gresiile să alunece astfel încât să permită stoarcerea în cât mai multe plăci posibil (întotdeauna în liniile de rețea). Pete nu știa că versiunea velcro este o variantă a puzzle-ului de poziționare a lui Golomb, așa cum o descrie Gardner [7, p. 128] și [8, p.133]. Golomb a extins acest puzzle la un joc pentomino cu două persoane [7, p. 128] și [8, pp. 133-135], reguli pentru care ar putea fi aplicate și puzzle-ului tromino. David Klarner a relatat despre un joc pentomino de două persoane, Pan-Kāi (dezvoltat de Alex Randolph și publicat în 1961 de Phillips Publishers), care a inclus următoarea constrângere: Cea mai importantă regulă este că este interzisă să cânți o bucată în interiorul unei regiuni închise a bordului, dacă mai puțin de 5 celule ar rămâne neocupate, cu excepția cazului în care mutarea exact umple regiunea. [15, p. 8] (vezi [21, p. 75] pentru mai multe informații despre Randolph și Pan-Kai.)

O altă direcție este tridimensională. Luați în considerare un cub de lungime 2n , care conține 2 celule unitate 3n , dintre care unul este ocupat (deficiență unică). Celulele rămase pot fi acoperite cu tromine tridimensionale (trei cuburi în formă de L, al treilea pe două fețe adiacente ale acestuia din urmă)? Condiția necesară 2 n = 3k + 1 se dovedește a fi suficientă. [23, Capitolul 6: Tromboiul tridimensional cu noduri Norton], [24, pp. 72-87] și [25] Cazul unui cub 4 4 4 prezintă câteva provocări modeste care pot amuza puzderi tineri .

Problemele mai simple se sugerează cu ușurință și au fost luate în considerare de numeroși alții. De exemplu, arhitecturile pătrată 3 3 și 6 6 pot fi acoperite cu tromine? Poate fiecare defect 5 5 și 7 7 matrice pătrat? Aceste două puzzle-uri sunt mai dificile decât cele 3 3, 6 6 complete și 8 8 cazuri cu deficit. Mergând mai departe, cititorii pot lua în considerare înclinarea diferitelor rețele rectangulare – a se vedea referințele de mai jos. Când utilizați o versiune cu mai multe culori de tromino, cum ar fi Kadon Vee-21, luați în considerare diferitele constrângeri de culoare. De exemplu, încercați aranjarea plăcilor astfel încât nici două din aceeași culoare să nu împartă o margine. În direcția opusă, încercați să grupați cât mai multe plăci dintr-o singură culoare împreună. Pentru ambele tipuri de modele, încercați mai mult pentru a face ca tigla să pară simetrică pe o linie diagonală sau pe o linie orizontală sau verticală. Posibilitățile de distracție și descoperire sunt numeroase. Diferite dreptunghiuri de mărime pot fi studiate făcând clic pe M-by-Npuzzle . Pentru experimentele de tip color, puzzle-ul Kadon este cel mai bun.


Referințe

  1. JP D’Angelo și DB West, Gândirea matematică: Rezolvarea problemelor și probe , ediția a doua, Prentice Hall, River Up Sad Sad, NJ, 2000.
  2. JM Ash și SW Golomb, “Dreptunghiuri deficiențe de tiglare cu tromine”, Math. Mag ., 77 (2004), 46-55. (Disponibil la math.depaul.edu/~mash/TileRec3b.pdf )
  3. IP Chu și R. Johnsonbaugh, “Placi deficitare cu tromine”, Math. Mag ., 59 (1986), 34-40.
  4. IP Chu și R. Johnsonbaugh, “Placi de tigla cu tromine”, J. Recreational Math ., 18 (1985-86), 188-193.
  5. SS Epp, Discrete Mathematics with Applications , ediția a treia, Thomson, Belmont, CA, 2004.
  6. M. Gardner, “Despre remarcabila asemănare dintre jocul Icosian și Turnul din Hanoi”, Scientific American , 196 , (mai 1957), 150-156. Această coloană a fost dedicată în primul rând circuitelor Hamilton, dar se termină cu o secțiune privind problemele legate de placile de chenar: Gardner afirmă că problema de control a coloanei februarie / domino “a determinat Octave Levenspiel de la Universitatea Bucknell să mă atragă atenția asupra unui articol remarcabil al SW Golomb în American Mathematical Lunar pentru decembrie 1954. “
  7. M. Gardner, “Mai multe despre domino complexe, plus răspunsurile la puzzle-urile de luna trecuta”, Scientific American , 197 (decembrie 1957), 126-140. Această coloană a jocurilor matematice începe prin a raporta impactul exploziv al contractelor scurte din coloana mai despre lucrarea lui Golomb: “În anul în care acest departament a fost inaugurat, a primit mai multe scrisori despre o recreere matematică decât oricare altul” pentomino ” Problema Sute de corespondenți au trimis soluții foarte variate. Mulți au mărturisit fascinația ciudată a problemei.
  8. M. Gardner, Cartea științifică americană a puzzle- urilor și diverselor matematice , Simon și Schuster, New York, 1959. [Capitolul 13 al primei astfel de colecții ( reîncărcată și actualizată ca Hexaflexagons și alte deviații matematice , University of Chicago Press, 1988) combină materialul de tigla [6] și [7] și este intitulat “Polyominoes.”]
  9. SW Golomb, “Checker Boards și Polyominoes”, Amer. Math. Lunar , 61 (1954), 675-682.
  10. SW Golomb, “Teoria generală a poliominoilor Partea I – Domino, Pentomino și Checkerboard,” Math Recreational. Mag ., Nr. 4 (august, 1961), 3-12.
  11. SW Golomb, Polyominoes , Scribner’s, New York, 1965. (ediția a doua: Polyominoes, Puzzles, Patterns, Problems and Packaging , Princeton University Press, Princeton, 1994)
  12. J. Herman, R. Kučera și J. im a, Numărarea și configurațiile: Probleme în combinatorică, aritmetică și geometrie (Karl Dilcher, traducător), Springer-Verlag, New York, 2003.
  13. R. Honsberger, Gems Matematic II , Asociația Matematică a Americii, Washington, DC, 1976.
  14. R. Johnsonbaugh, Discrete Mathematics , a șasea ediție, Pearson Hall Hall, Upper Saddle River, NJ, 2005.
  15. D. Klarner, Box-Packing Puzzle . Notele multilingvistice, Universitatea din Waterloo, Ontario, 1973-74. 42 pagini + pagina de titlu. (Porțiuni din acest lucru sunt rezumate în capitolul 8 din Honsberger [13].)
  16. GE Martin, Polyominoes, Un ghid pentru puzzle-uri și probleme în tigla , Asociația matematică a Americii, Washington, DC, 1991.
  17. GE Martin, recenzie Polyominoes de S. Golomb (ediția 1994), recenzii matematice , MR1291821 (95k: 00006), 1995.
  18. I. Mizniks, “Analiza computerizată a problemei 3 culori pentru forme V”, Acta Societatis Mathematicae Latviensis , Rezumatele celei de-a 5-a Conferințe matematice letonice , 6-7 aprilie 2004, Daugavpils, Letonia. (Disponibil lahttp://www.de.dau.lv/matematika/lmb5/tezes/Mizniks.pdf )
  19. RB Nelsen, Dovezi fără cuvinte II, Mai multe exerciții în gândirea vizuală , Asociația matematică a Americii, Washington, DC, 2000.
  20. KH Rosen, Matematica discretă și aplicațiile sale , a cincea ediție, McGraw-Hill, New York, 2003. (Pentru a apărea ca exemplu 13, secțiunea 4.1, în a șasea ediție, 2007.)
  21. JN Silva (Ed.) Colocviul I de matematică amuzantă   (Proceedings de conferință, 29 aprilie-2 mai 2009. Universitatea din Évora), Asociația Ludus, Lisabona, 2010.
  22. D. Singmaster, revizuirea Polyominoes a lui GE Martin , Recenzii matematice , MR1140005 (93d: 00006), 1993.
  23. A. Soifer, Geometric Etudes in Combinatorial Mathematics , ediția a doua, Springer, New York, 2010.
  24. N. Starr, Cuburi cu trombocite cu deficit de trombon de lungime laterală 2 n , Geombinatorics XVIII (2) (2008), 72-87.
  25. N. Starr, Cuburi cu deficit de trombocite cu lungimea oricarei părți, http://arxiv.org/abs/0806.0524 , 3 iunie 2008.
  26. DJ Velleman, Cum să-l demonstreze: o abordare structurată , ediția a doua, Cambridge University Press, New York, 2006