Trominška puzzle

z
Norton Starr

O puzzleu  Zgodovina  Variacije  Reference  Igraj

 

O puzzle – fizično in virtualno

v-21 puzzle Osnovna uganka je sestavljena iz 21 pravokotnih kosov (“ploščice”) prikazane vrste, sestavljene iz treh kvadratov; ena dodatna enojna kvadratna ploščica; in ravnino, 8 × 8 kvadratnih mrež, katerih kvadratki so enake velikosti kot ploščice. Ploščice zasedajo skupno 3 × 21 + 1 = 63 + 1 = 64 kvadratov, enako številko kvadratov kot na šahovnici. V nadaljevanju jih imenujemo tromini kot najpreprostejši od več imen, ki jih za njih uporabljamo, med katerimi so L-tromini, L-triomini in V-tromini.

Če želite igrati fizično verzijo te sestavljanke, uporabite 21 dejanskih tromino ploščic, en kvadratni del in 8 × 8 podnožje, podobno kotni plošči, najprej postavite eno kvadratasto ploščico na katero koli od 64 kvadratnih mest na dnu. Nato preostalih 63 kvadratov napolnite s tromino, tako da ni prekrivanja in brez praznega kvadrata. Takšna rešitev sestavljanke se imenuje ploščica kvadrata 8 × 8. Druga možnost je, da začnete z zaporednim postavljanjem trominov v osnovno ploščo (vsaka taka ploščica zaseda le tri kvadratke vzorca mreže) in ko so vsi položeni, postavite posamezno kvadratno ploščico v en položaj, ki je na voljo.

Tukaj je ozadje komercialne različice te uganke, ki jo tržijo podjetja Kadon Enterprises. Na letnem srečanju Matematičnega združenja Amerike januarja 2000 je Arthur Benjamin prejel nagrado Haimo za ugledno poučevanje koledža. V svojem sprejemnem govoru je z indukcijo skiciral svoj najljubši dokaz. Ta razlaga zagotavlja, da lahko kvadratni kvadrat 2n × 2n (tj. Splošna kontrolna plošča z 2n kvadratoma na vsaki strani) z eno celico zasedeno, lahko vedno označijo s tromino. Tri leta po zaslišanju Benjaminovih pripomb sem predavanje o indukciji in opozoril na njegov najljubši dokaz. Z dopolnjevanjem mojih pripravljenih primerov, sem zaradi Solomona Golombja razkril ta klasičen argument. Razmišljam, da bi dejanska uganka te vrste pripomogla k elementu realnosti in bi lahko spodbudila zanimanje za metodo indukcije, sem poslal temo Kadonu, vodilnemu proizvajalcu sestavljanke, da vidim, če bi jih lahko kupil. Niso, zato sem vprašal, ali bi nekaj naredili mojim specifikacijam. Serija elektronskih sporočil s predsednikom Kadona Katejem Jonesom je pripeljala do uganke, ki je prikazana zgoraj levo. Predlagala je uporabo več različnih barv za tromino ploščice, zaradi česar je to bolj zanimiva uganka, kot sem prvotno mislil. Odločil sem se za hladnejše, prosojne ploščice, ne pa drzne, neprozorne in izbrali modre, aqua in ametiste za tromine.

Kate je vprašala, ali bom dovolil, da bi Kadonu dodal uganko na paleto predmetov, ki jih prodajajo, in sem se hitro strinjal – samo nekaj sem si želel za lastno uporabo. Na moje presenečenje je izjavila, da bom prejemala licenčnine. To nikoli ni bil moj cilj, vse moje avtorske pravice pa so bile podarjene Amherstu College in Matematično združenje Amerike.

Kadon je predstavil uganko pod imenom “Vee-21”; glej www.gamepuzzles.com/polycub2.htm#V21. Ta komercialna različica, v treh živahnih, prosojnih akrilnih barvah, prinaša brošuro za štirideset strani, ki ponuja številne izboljšave osnovne uganke. Kate je prispevala nekaj podaljškov uganke, nekaj strateških iger za dve osebi in predlagal ločene barvne zahteve za nagibanje. Ugotovila je tudi estetske možnosti pri izdelavi simetričnih vzorcev. Kate je Oriel Maximé pozvala, naj prispeva nekaj njegovih izzivov, podobnih labirintu, za polaganje s tromino, brošura pa vsebuje različne pravokotne predloge s strateško izbranimi linijami mrež, ki so zatemnjene, da bi služile kot ovire, na katerih se tromini ne smejo postaviti.

Tukaj sta na voljo dve interaktivni računalniški uganki te vrste. Sestavljanka 8-do-8 sta razvila dva moji dijaki, sodelavec oddelka pa je prispeval k sestavljanki M-by-N. Uganka M-by-N (igra na večini sistemov, vendar se lahko počasi naloži) je nekoliko prožnejša, kar omogoča izbiro poljubnega števila vrstic in stolpcev med 2 in 32, vključno. 8-do-8 sestavljanke (igra najboljše z Internet Explorerjem na osebnem računalniku) ima drugačno miško in je koristno omejeno na tri barve tromina. Navodila so podana z vsakim. Spletne in Kadonove različice imajo tako nenavadno široko privlačnost, zanimivo za štiriletnike kot tudi začinjene puzzlerje.


Zgodovina

Dokaz, da je za poljubno pozitivno celo število n, kvadrat 2n × 2n z eno celico zasedeno (“pomanjkljiv” kvadrat), je vedno mogoče označiti s tromino zaradi Solomona Golomba. Objavil ga je leta 1954 v članku [9] v ameriškem matematičnem mesečnem. Kot je navedeno zgoraj, je bilo treba ponazoriti Golombov argument za 2n × 2n pomanjkljive kvadrate, za katere je bila sestavljena uganka. Njegov isti članek je v tiskani obliki predstavil izraz tromino in njegovo generalizacijo, poliomino. Poliomino je povezana matrika enakih kvadratov, ki imajo lastnost, da se katera koli dva kvadrata bodisi ne dotikajo ali se ne srečata po celotnem, skupnem robu. Edini dve tromini obliki so trije kvadratki v vrsti in L-oblika te sestavljanke, tukaj pa se “tromino” nanaša samo na slednje.

Golombov dokaz je prvi primer matematične indukcije. Poleg čiste elegancije argumenta je to redek primer nenumerične uporabe metode. To je v nasprotju s primeri in vajami, ki jih pogosto najdemo v učbenikih za indukcijo, ki običajno obsegajo različne formule za končne vsote, neenakosti in podobno. Dokaz je bil prvič nastopil v priljubljenem mediju v časopisu za rekreacijsko matematiko Josephom Madachyjem (RMM), kjer ga je Golomb vključil v prvi od štirih delnih člankov o poliominov, objavljenih v RMM [10]. V Martinu Gardnerjevem prvem majskem, 1957 znanstvenem ameriškem stolpcu, ki uvaja poliomine v širšo javnost, je pripomnil, da “lahko ploščo z enim kvadratom, ki manjka na kateri koli točki, pokriva 21 pravih tromino” [6, str. 154]. Za svojo prvo zbirko zbranih matematičnih iger stolpcev, Gardner izdelan z opozorilom, da “iznajdljivi indukcijski argument dokazuje, da bo 21 pravih tromino in en monomino pokrival 8-do-8 krovu, ne glede na to, kje se nahaja monomino” [8, str. 126].

Argument trominskega tlaka za pomanjkljive kontrolne plošče in splošna 2n × 2n izrek se je pojavil v zaporedju knjig od člankov Mesečni in RMM. Razloženo je bilo v Golombovih klasičnih polimomih [11, 1965, str. 21-22] in v drugi izdaji te knjige [11, 1994, str. 5]. Druga izdaja daje bogato zgodovino in obsežen pregled tega zanimivega predmeta in je napolnjena s slikami in uganki. Njegove 22 strani referenc, ki se sklicujejo na knjige in članke, so dodatni bonus. Indeks imen vsebuje 81 posameznikov, kar se jih je v telesu knjig večkrat omenilo. Mnogi izmed njih bodo prepoznali igralci in amaterski matematiki, pa tudi strokovnjaki na obeh področjih. Opis knjige je podan v pregledu [17] Georgea Martina. Leta 1976 je Ross Honsberger dal lucidno, podrobno uporabo Golombovega argumenta na tablo v svojih Mathematical Gems II [13, str. 61]. Temeljna ideja dokaza je omenjena tudi v knjigi Georgea E. Martina, posvečena poliomino tilings [16, str. 27-28]. Posebej zanimiva je ocena David Singmasterove [22] te nove knjige, ker daje čudovit skic predmeta in njene zgodovine.

Ta tema je tudi vse pogostejša cena za besedila in problemske knjige. Na primer, se pojavlja v diskretnih matematičnih besedilih Susane Epp [5, str. 234], Richard Johnsonbaugh (ki omenja tromine tlorisov pravokotnikov, ki nastanejo pri zasnovi VLSI) [14, str. 58-59] in Kenneth Rosen [20, str. 247-8]. Tromino polaganje je obravnavano tudi v knjigi Danielja Vellemana o izdelavi dokazov [26, str. 271-275] in problemskih knjig John P. D’Angela in Douglas B. West [1, str. 75] in Jiří Herman, Radan Kučera in Jaromír Šimša [12, str. 271]. Najbolj kristalinična ilustracija Golombovega argumenta je rezervni “dokaz brez besed” Rogerja Nelsena, ki je naveden v drugi knjigi tega naslova [19, str. 123].

To področje rekreativne matematike je imelo koristi od stalnega preiskovanja in predlaganih težav. Leta 1985 in 1986 sta I-Ping Chu in Richard Johnsonbaugh preučevala vprašanje ploščice, ki ima pomanjkljivo ploščo n × n, kjer n ni več potrebna moč 2 in, bolj splošno, pomanjkljive in nedefinirane pravokotne plošče [3, 4 ]. Knjiga Georgea Martina je vključevala celo poglavje, posvečeno trominskim tilinam [16, str. 23-37]. Težave pri barvanju trombina obdelujejo Ilvars Mizniks, ki priznava stran za izbiro barve Kadon Vee-21 kot navdih za svoje raziskave [18]. Članek iz leta 2004 [2] J. Marshall Ash in Solomon Golomb, o trominskem polaganju pomanjkljivih pravokotnikov, vsebuje nekaj novih in osnovnih rezultatov, od katerih eden odgovarja na staro vprašanje Chu in Johnsonbaugha. Pepel in Golomb končata z odprtim problemom o 2-pomanjkljivih pravokotnikih (pravokotnike z dvema celicama odstranjenim).

Internet je dober vir ploščatih zaslonov in informacij. Na primer, iskanje na “tromino” in “ploščice” prikaže aplete, kot so tiste, ki jih Alexander Bogomolny na www.cut-the-knot.org/Curriculum/Games/TrominoPuzzle.shtml in Christopher Mawata na www.utc.edu/ Fakulteta / Christopher-Mawata / trominos /, ki ponazarjajo tromino uganke več velikosti.


Variacije

Tukaj je nekaj razširitev tromino uganke, ki jo bralci lahko upoštevajo. Prvi je predlagal moj brat Raymond (Pete), ki je vprašal, kako bi lahko uredili tromino v mrežo 8 × 8, da bi povečali število nenaseljenih kvadratov. To je mogoče razložiti: ena pot bi domnevala, da so ploščice in mrežice zmečkani, da ostanejo na mestu, alternativno pa bi lahko omogočili, da bi ploščice drsile tako, da bi omogočili stiskanje čim večje število ploščic (vedno znotraj mrežnih linij). Pete se ni zavedal, da je verzija Velcro variacija na Golombovem pentominskem položaju, kot je opisal Gardner [7, str. 128] in [8, str. 133]. Golomb je to puzzle razširil na dvočlansko igro pentomina [7, str. 128] in [8, str. 133-135], pravila, ki bi se lahko uporabila tudi za tromino uganko. David Klarner je poročal o dvočlanski igri pentomina, Pan-Kāi (ki ga je razvil Alex Randolph in ga izdal Phillips Publishers leta 1961), ki je vključeval naslednjo omejitev: “najpomembnejše pravilo je, da je prepovedano igrati kos znotraj zaprto regijo tabele, če bi manj kot 5 celic ostalo neuporabljeno, razen če ta poteza natančno napolni regijo. “[15, str. 8] (glej [21, str. 75] za več informacij o Randolphu in Pan-Kāi.)

Druga smer je tridimenzionalna. Razmislite o kocki stranske dolžine 2n, ki vsebuje 23n enotske celice, od katerih je ena zasedena (posamezna pomanjkljivost.) Ali so preostale celice pokrite s tridimenzionalnimi tromini (tri kocke v obliki L, pri čemer sta dva od njih izpolnjeni tretji dve sosednji obrazi slednje)? Potreben pogoj, da 2n = 3k + 1 tudi zadostuje. [23, Poglavje 6: 3-dimenzionalna trombinska plošča Nortona Starrja], [24, str. 72-87], in [25] Primer 4 × 4 × 4 kocke predstavlja nekaj skromnih izzivov, ki lahko zabavajo mlade puzzle.

Preprostejši problemi zlahka nakazujejo sebe in jih obravnavajo številni drugi. Na primer, ali so lahko polne 3 × 3 in 6 × 6 kvadratne matrike označene s tromino? Ali je mogoče vsa pomanjkljiva kvadratka 5 × 5 in 7 × 7 kvadratnih ploščic? Te zadnje dve uganki so bolj zahtevne kot polne 3 × 3, 6 × 6 in pomanjkljivi 8 × 8 primeri. Nadalje, bralci lahko razmišljajo o različnih tleh različnih pravokotnih nizov – glejte spodnje reference. Pri uporabi različice z več kot eno barvo tromina, kot je Kadon Vee-21, upoštevajte različne barvne omejitve. Na primer, poskusite urediti ploščice, tako da nobena od dveh iste barve ne delita roba. V nasprotni smeri poskusite združiti čim več ploščic ene barve. Za obe vrsti vzorcev poskušajte še naprej postaviti ploščico simetrično glede na diagonalo ali vodoravno ali navpično črto. Priložnosti za zabavo in odkritje so številne. Različne velikosti se lahko preučijo s klikom na sestavljanko M-by-N. Za preizkuse barvnih vzorcev je najboljša sestavina Kadon.


Reference

 

 

  1. J. P. D’Angelo in D. B. West, Matematično mišljenje: Reševanje problemov in dokazi, Druga izdaja, dvorana Prentice, reka Upper Saddle, NJ, 2000.
  2. J. M. Ash in S. W. Golomb, “Pravokotniki s pomanjkljivostmi s tromini”, Math. Mag., 77 (2004), 46-55. (Na voljo na math.depaul.edu/~mash/TileRec3b.pdf)
  3. I. P. Chu in R. Johnsonbaugh, “Tiling pomanjkljive plošče s tromino,” Math. Mag., 59 (1986), 34-40.
  4. I. P. Chu in R. Johnsonbaugh, “Obloge s tromini”, J. Rekreativna matematika, 18 (1985-86), 188-193.
  5. S. S. Epp, Diskretna matematika z aplikacijami, tretja izdaja, Thomson, Belmont, CA, 2004.
  6. M. Gardner, “O izjemni podobnosti med Icosian Game in Hanojevim stolpom,” Scientific American, 196, (maj, 1957), 150-156. Ta stolpec je bil namenjen predvsem Hamiltonovim krogotokom, vendar se konča z delom na problemih s ploščicami s čeki: Gardner pravi, da je problem februarskega stolpca s checkerboard / domino problemom “spodbudil Octave Levenspiel iz Bucknell University, da mi opozarja na izjemen članek SW Golomb v ameriškem matematičnem Mesečno za december 1954. “
  7. M. Gardner, “Več o kompleksnih dominah, skupaj z odgovori na zadnje mesecne uganke”, Scientific American, 197, (december, 1957), 126-140. Ta stolpec matematičnih iger se začne s poročanjem o eksplozivnem učinku kratkega poročila stolpca v stolpcu Golombovega dela [6]: “V letu, odkar je bil ta oddelek odprt, je prejela več črk o enem matematičnem rekreaciji kot katerikoli drugi …” pentomino ” problem … Stotine korespondentov so poslali v zelo različnih rešitvah. Mnogi so pričali o nenavadni fascinaciji tega problema … “
  8. M. Gardner, Znanstvena ameriška knjiga matematičnih zagonetov in preusmeritev, Simon in Schuster, New York, 1959. (ponatisnjena in posodobljena kot heksaflekagoni in druge matematične preusmeritve, University of Chicago Press, 1988.) [Poglavje 13 prve tovrstne zbirke združuje ploščat material iz [6] in [7] in se imenuje “Polyominoes.”]
  9. S. W. Golomb, “Čeki in poliomini,” Amer. Matematika. Mesečno, 61 (1954), 675-682.
  10. S. W. Golomb, “Splošna teorija poliominov I. del – domini, pentomini in čeki,” rekreacijska matematika. Mag., Številka 4 (avgust 1961), 3-12.
  11. S. W. Golomb, Polyominoes, Scribner’s, New York, 1965. (Druga izdaja: Polyominoes, Puzzles, Patterns, Problems and Packings, Princeton University Press, Princeton, 1994.)
  12. J. Herman, R. Kučera in J. Šimša, štetje in konfiguracije: problemi v kombinatoriki, aritmetiki in geometriji (Karl Dilcher, prevajalec), Springer-Verlag, New York, 2003.
  13. R. Honsberger, Mathematical Gems II, Mathematical Association of America, Washington, DC, 1976.
  14. R. Johnsonbaugh, diskretna matematika, šesta izdaja, dvorana Pearson Prentice, reka Upper Saddle, NJ, 2005.
  15. D. Klarner, sestavljalne sestavljalne sestavljanke. Večplastna nota, University of Waterloo, Ontario, 1973-74. 42 strani + naslovna stran. (Deli tega so povzeti v poglavju 8 Honsbergerja [13].)
  16. G. E. Martin, Polyominoes, Vodnik za uganke in probleme v polaganju ploščic, Mathematical Association of America, Washington, DC, 1991.
  17. G. E. Martin, pregled polomominov S. Golomba (izdaja 1994), Matematični pregledi, MR1291821 (95k: 00006), 1995.
  18. I. Mizniks, “Računalniška analiza trojne barvne problematike za V-oblike”, Acta Societatis Mathematicae Latviensis, povzetki 5. latvijske matematične konference, 6-7 april 2004, Daugavpils, Latvija. (Na voljo na http://www.de.dau.lv/matematika/lmb5/tezes/Mjenjks.pdf)
  19. R. B. Nelsen, Dokazi brez besed II, Več vaje v vizualnem razmišljanju, Matematično združenje Amerike, Washington, DC, 2000.
  20. K. H. Rosen, Diskretna matematika in njegove aplikacije, Peta izdaja, McGraw-Hill, New York, 2003. (V 6. izdaji, 2007, se pojavi kot primer 13, oddelek 4.1)
  21. J. N. Silva (ur.) Rekreativna matematika Kolokvij I (konferenčni zbornik, 29. april-2. maj 2009. Univerza v Évori), Associação Ludus, Lisboa, 2010.
  22. D. Singer, pregled polinominov G. G. Martin, matematični pregledi, MR1140005 (93d: 00006), 1993.
  23. A. Sojen, Geometrijski Etudes v kombinatorni matematiki, 2. izdaja, Springer, New York, 2010.
  24. N. Starr, “Tromino talne defekte kocke stranske dolžine 2n”, Geombinatorics XVIII (2) (2008), 72-87.
  25. N. Starr, “Tromino kocke z dolgimi stranskimi dolžinami”, http://arxiv.org/abs/0806.0524, 3. junij 2008.
  26. D. J. Velleman, Kako to dokazati: strukturiran pristop, druga izdaja, Cambridge University Press, New York, 2006

 

Vir: http://www3.amherst.edu/~nstarr/trom/intro.html