Den Tromino Puzzle ved Norton Starr

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

Om Puzzle – fysiske og virtuelle
v-21 puzzlev-21 puslespil Den grundlæggende puslespil består af 21 retvinklet formede stykker (“fliser”) af den slags vist, består af tre kvadrater; en ekstra enkelt firkantet flise; og et plan, 8 × 8 kvadratisk gitter, hvis firkanter er af samme størrelse som de af fliserne. Fliserne indtager i alt 3 × 21 + 1 = 63 + 1 = 64 pladser, det samme antal pladser som på et skakternet. I det følgende kalder vi disse vinklede stykker trominoes, som den enkleste af flere navne, der anvendes for dem, som omfatter L-trominoes, L-triominoes og V-trominoes.

For at afspille en fysisk udgave af dette puslespil, bruge 21 egentlige tromino fliser, en enkelt firkantet stykke, og en 8 × 8 skakbræt-lignende base, første position den enkelte firkantede fliser på et af de 64 kvadrat steder på basen. Derefter udfylde de resterende 63 pladser med trominoes så der ikke er nogen overlapning og ingen ubesatte torv. En sådan løsning på puslespillet kaldes en flisebelægning af 8 × 8 kvadrat. Alternativt kan starte ved successivt at placere trominoes i skakternet base (hver sådan flise besætter kun tre pladser i gittermønster), og når alle 21 er placeret, placere enkelt kvadrat flise i en position, der er tilbage.

Her er baggrunden for den kommercielle version af dette puslespil, der markedsføres af Kadon Enterprises. På januar 2000 årlige møde i den matematiske Association of America, Arthur Benjamin fik Haimo pris for fornem kollegium undervisning. I sin takketale skitseret han sin yndlings bevis ved induktion. Dette ræsonnement sikrer, at et 2n × 2n cellet firkantet (dvs. en generaliseret skakternet med 2n firkanter langs hver side) med en celle besat, altid kan flisebelagt af trominoes. Tre år efter at have hørt Benjamins bemærkninger jeg gav et foredrag om induktion og mindede hans foretrukne bevis. Supplere mine forberedte eksempler, jeg ad libbed denne klassiske argument, på grund af Solomon Golomb. Tænker, at en faktisk puslespil af denne slags vil tilføje et element af virkeligheden og kan gnist interesse i metoden til induktion, sendte jeg en note til Kadon, en førende puslespil maker, for at se, hvis de havde nogen jeg kunne købe. De gjorde ikke, så jeg spurgte, om de ville gøre nogle til mine specifikationer. En række e-mails med Kate Jones, formand for Kadon, førte til et puslespil af den slags vist ovenfor til venstre. Hun foreslog at bruge flere forskellige farver til tromino fliser, hvilket gør dette til et mere interessant puslespil, end jeg oprindeligt havde forestillet sig. Jeg valgte køligere, gennemskinnelige fliser snarere end fed, uigennemsigtige dem, og valgte blå, aqua og ametyst for trominoes.

Kate spurgte, om jeg ville lade Kadon tilføje puslespillet til den vifte af emner, de sælger, og jeg let aftalt – Jeg ønskede kun nogle til min egen brug. Til min overraskelse, erklærede hun, at jeg ville modtage royalties. Det var aldrig mit mål, og alle mine royalties doneret til Amherst College og matematiske Association of America.

Kadon bragt ud puslespillet under navnet “Vee-21”; se www.gamepuzzles.com/polycub2.htm#V21. Denne kommercielle version, i tre levende, gennemskinnelige akryl farver, kommer med en fyrre siders brochure tilbyder en række forbedringer til den grundlæggende puslespil. Kate bidrog nogle udvidelser i puslespillet, nogle to-personers strategispil, og forslaget om farve adskillelse krav til tilings man kunne forsøge. Hun opdagede også de æstetiske muligheder i at gøre symmetriske mønstre. Kate inviterede Oriel Maxime til at bidrage nogle af hans labyrint-lignende udfordringer for fliselægning med trominoes, og brochuren indeholder en række rektangulære skabeloner med strategisk udvalgte linjer af gitrene formørkede til at tjene som barrierer på tværs af hvilke trominoes ikke kan placeres.

To interaktive computer puslespil af denne slags leveres her. Den 8-by-8 puslespil er udviklet af to af mine studerende, mens en afdelings kollega bidraget M-for-N puslespil. M-af-N puslespil (spiller på de fleste systemer, men kan være langsom til at indlæse) er noget mere fleksibel, idet valget af et vilkårligt antal rækker og kolonner mellem 2 og 32, inklusive. Den 8-by-8 puslespil (spiller bedst med Internet Explorer på en pc) har en anden mus handling og er med fordel begrænset til tre farver tromino. Retninger er givet med hver. Online og Kadon versioner har begge usædvanlig bredde appel og fængslende for fire-årige samt krydret puslere.

Historie
Beviset for, at for ethvert positivt heltal n, en 2n × 2n torv med én celle besat (en “mangelfuld” firkant) kan altid flisebelagt af trominoes skyldes Solomon Golomb. Han udgav den i sin 1954 artikel [9] i American Mathematical Monthly. Som nævnt ovenfor, var det for at illustrere Golomb argument for 2n × 2n mangelfulde firkanter, der puslespillet blev bestilt. Hans samme artikel indført på tryk udtrykket tromino og dens generalisering, polyomino. En polyomino er en tilsluttet række af identiske kvadrater, der har den egenskab, at to pladser enten ikke røre eller også mødes langs en hel, fælles kant. De eneste to tromino figurer er tre pladser i en række og L-formen af ​​dette puslespil, og her “tromino” kun refererer til sidstnævnte.

Golomb s bevis er et førsteklasses eksempel på matematisk induktion. Ud over den blotte elegance af argumentet, det er en sjælden forekomst af en nonnumerical anvendelse af metoden. Dette står i kontrast til de eksempler og opgaver ofte findes i lærebog behandlinger af induktion, som typisk består af en række formler for finite beløb, uligheder og lignende. Beviset første optræden i et populært medie var i Joseph Madachy rekreative matematik Magazine (RMM), hvor Golomb medtaget det i den første af hans fire-del serie af artikler om polyominoes offentliggjort i RMM [10]. I Martin Gardners skelsættende maj 1957 Scientific American kolonne indføre polyominoes til den brede offentlighed, bemærkede han, at “et bræt med en firkant mangler på noget tidspunkt, kan dækkes af 21 rigtige trominoes” [6, s. 154]. For hans første bog af indsamlede Mathematical Games kolonner, Gardner udarbejdet af bemærke, at “en genial induktion argument viser, at 21 rigtige trominoes og en monomino vil dække 8-by-8 board uanset hvor monomino placeres” [8, s. 126].

Den tromino flisebelægning argument for mangelfulde Skaktern og den generelle 2n × 2n teorem har optrådt i en række bøger, eftersom de Månedlige og RMM artikler. Det blev forklaret i Golomb klassiske Polyominoes [11, 1965, pp. 21-22], og i den anden udgave af den bog [11, 1994, s. 5]. Den anden udgave giver en rig historie og en omfattende undersøgelse af denne spændende emne, og er fyldt med billeder og gåder. Dens 22 siders referencer, citerer både bøger og artikler, er en ekstra bonus. Indekset for navne lister 81 personer, en hel henvist til mere end én gang i selve bogen. Mange af disse vil blive anerkendt af spil aficionados og amatør matematikere såvel som af fagfolk i enten område. En beskrivelse af bogen er givet i revisionen [17] af George Martin. I 1976 Ross Honsberger gav en klar, detaljeret anvendelse af Golomb argument om checker bord i hans Matematisk Gems II [13, s. 61]. Den grundlæggende idé med beviset er også nævnt i George E. Martins bog helliget polyomino tilings [16, s. 27-28]. David Singmaster gennemgang [22] af sidstnævnte bog er særlig interessant, for det giver en smuk skitse af emnet og dets historie.

Dette emne er også mere og mere almindeligt billetpris for tekster og problemområder bøger. For eksempel ser det i de diskrete matematik tekster Susanna Epp [5, s. 234], Richard Johnsonbaugh (der nævner tromino tilings af rektangler som opstår i VLSI layout design) [14, s. 58-59], og Kenneth Rosen [20, s. 247-8]. Tromino flisebelægning er også behandlet i Daniel Velleman bog om konstruere beviser [26, s. 271-275] og problemet bøger af John P. D’Angelo & Douglas B. West [1, s. 75] og af Jiří Herman, Radan Kučera & Jaromír SIMSA [12, s. 271]. Den mest krystallinske illustration af Golomb argument er Roger Nelsen s reservedele “bevis uden ord”, givet i hans anden bog denne titel [19, s. 123].

Dette område af rekreative matematik har nydt godt af en fortsat strøm af undersøgelse og foreslåede problemer. I 1985 og 1986, I-Ping Chu og Richard Johnsonbaugh studeret spørgsmålet om fliselægning mangelfuld n × n bestyrelser, hvor n ikke længere behøver at være en potens af 2, og mere generelt, mangelfuld og ikke-mangelfuld rektangulære plader [3, 4 ]. George Martin bog indeholdt et helt kapitel helliget tromino tilings [16, s. 23-37]. Farvning problemer for tromino fliser behandles af Ilvars Mizniks, der anerkender den Kadon Vee-21 farvevalg side som inspiration for sin forskning [18]. Artiklen 2004 [2] af J. Marshall Ash og Solomon Golomb, om tromino flisebelægning af mangelfulde rektangler, indeholder flere nye og grundlæggende resultater, hvoraf den ene besvarer et gammelt spørgsmål om Chu og Johnsonbaugh. Aske og Golomb slutte med et åbent problem om 2-mangelfulde rektangler (rektangler med to celler fjernet).

Internettet er en god kilde til flisebelægning displays og information. For eksempel en søgning på “tromino” og “fliser” dukker op applets som dem af Alexander Bogomolny på www.cut-the-knot.org/Curriculum/Games/TrominoPuzzle.shtml og Christopher Mawata på www.utc.edu/ Fakultetet / Christopher-Mawata / trominos /, som illustrerer tromino puslespil af flere størrelser.

 

Variationer
Her er nogle udvidelser af tromino puslespil, som læserne kunne overveje. Den første blev foreslået af min bror Raymond (Pete), der spurgte, hvordan man kunne arrangere trominoes i 8 × 8 gitter for at maksimere antallet af ubesatte pladser. Dette kan uddybes: én rute ville antage fliserne og gitter er velcroed så de holder sig på plads, mens alternativt man kan tillade fliserne til at glide, så de kan presse i så mange fliser som muligt (altid inden for gitterlinjer). Pete ikke var klar over, at velcro-versionen er en variation på Golomb s pentomino positionering puslespil som beskrevet af Gardner [7, s. 128] og [8, s. 133]. Golomb udvidet dette puslespil til en to-personers pentomino spil [7, s. 128] og [8, s. 133-135], regler for, som kunne anvendes på tromino puslespillet så godt. David Klarner rapporteret på en to-personers pentomino spil, Pan-kai (udviklet af Alex Randolph og udstedt i 1961 af Phillips Publishers), som omfattede følgende begrænsning: “den vigtigste regel er, at det er forbudt at spille et stykke inde i en lukkede område af bestyrelsen, hvis færre end 5 celler så ville forblive ubesatte, medmindre flytningen præcist fylder regionen. “[15, s. 8] (Se [21, s. 75] for mere information om Randolph og Pan-kai.)
En anden retning er tredimensionalt. Overvej en terning af sidelængde 2n, som indeholder 23 n enhed celler, hvoraf den ene er besat (enkelt mangel.) Kan de resterende celler flisebelagt med tredimensionelle trominoes (tre terninger i en L-form, med to af dem mødes den tredje på to tilstødende flader af sidstnævnte)? Den nødvendige betingelse, at 2n = 3K + 1 viser sig at være tilstrækkelig samt. [23, Kapitel 6: Norton Starr 3-Dimensional Tromino Fliselægning], [. 24, pp 72-87] og [25] Sagen om en 4 × 4 × 4 terning præsenterer nogle beskedne udfordringer, der kan underholde unge puslere.
Enklere problemer let foreslå sig selv og er blevet overvejet af mange andre. For eksempel kan den fulde 3 × 3 og 6 × 6 kvadrat arrays blive flisebelagt med trominoes? Kan enhver mangelfuld 5 × 5 og 7 × 7 kvadratisk matrix blive flisebelagt? Disse sidstnævnte to gåder er mere udfordrende end den fulde 3 × 3, 6 × 6, og mangelfulde 8 × 8 sager. Går videre, kan læserne overveje tilings af forskellige rektangulære arrays – se referencer nedenfor. Ved brug af en version med mere end én farve tromino, såsom Kadon Vee-21, overveje forskellige farver begrænsninger. For eksempel, prøve at arrangere fliserne, så ikke to af samme farve deler en kant. I den modsatte retning, forsøger at gruppere så mange fliser af en farve på hinanden som muligt. For begge disse typer mønster, prøv yderligere at gøre fliselægning synes symmetrisk om en diagonal eller om en vandret eller lodret linje. Mulighederne for sjov og opdagelse er talrige. Forskellige størrelser rektangler kan studeres ved at klikke på M-by-N puslespil. For farve mønster eksperimenter, at Kadon puslespillet er bedst.

 

Referencer
JP D’Angelo og DB West, matematisk tankegang: problemløsning og Beviser, anden udgave, Prentice Hall, Upper Saddle River, NJ, 2000.
JM Ash og SW Golomb, “Fliselægning mangelfulde rektangler med trominoes,” Math. Mag., 77 (2004), 46-55. (Findes på math.depaul.edu/~mash/TileRec3b.pdf)
IP Chu og R. Johnsonbaugh, “Fliselægning mangelfulde brædder med trominoes,” Math. Mag., 59 (1986), 34-40.
IP Chu og R. Johnsonbaugh, “Fliselægning brædder med trominoes,” J. Rekreative Math., 18 (1985-1986), 188-193.
SS EPP, Diskret Matematik med Anvendelser, tredje udgave, Thomson, Belmont, CA, 2004.
M. Gardner, “Om den bemærkelsesværdige lighed mellem Icosian spil og Tower of Hanoi,” Scientific American, 196, (maj, 1957), 150-156. Denne kolonne primært helliget Hamilton kredsløb, men ender med et afsnit om skakternet flisebelægning problemer: Gardner, at kolonnens februar skakternet / domino problem “bedt Octave Levenspiel af Bucknell Universitet for at ringe til min opmærksomhed på en bemærkelsesværdig artikel af SW Golomb i American Mathematical Månedligt for december, 1954. ”
M. Gardner, “Mere om komplekse domino, plus svarene på sidste måneds puslespil,” Scientific American, 197, (december, 1957), 126-140. Dette Matematiske Spil kolonne starter ved at rapportere den eksplosive konsekvenser af maj kolonnens kort redegørelse for Golomb arbejde [6]: “I år, da dette afdeling blev indviet, har det fået flere bogstaver omkring en matematisk rekreation end nogen anden … den” pentomino ‘ problem … Hundredvis af korrespondenter sendes i vidt forskellige løsninger. Mange vidnede på problemet mærkelige fascination …. ”
M. Gardner, The Scientific American Book of Mathematical Puslespil & Diversions, Simon og Schuster, New York, 1959. (Gengivet og opdateret som Hexaflexagons og andre Matematisk Diversions, University of Chicago Press, 1988.) [kapitel 13 i denne første sådan indsamling kombinerer flisebelægning materiale [6] og [7], og hedder “Polyominoes.”]
SW Golomb, “Checker Boards og Polyominoes,” Amer. Math. Månedligt, 61 (1954), 675-682.
SW Golomb, “The General Theory of Polyominoes Del I – Domino, Pentominoes og Skaktern,” Rekreative Math. Mag., Issue No. 4 (august 1961), 3-12.
SW Golomb, Polyominoes, Scribner s, New York, 1965. (Anden udgave: Polyominoes, Puslespil, Mønstre, problemer og Pakninger, Princeton University Press, Princeton, 1994.)
J. Herman, R. Kučera og J. SIMSA, tælle og konfigurationer: Problemer i Kombinatorik, Aritmetik og Geometri (Karl Dilcher, oversætter), Springer-Verlag, New York, 2003.
R. Honsberger, Matematisk Gems II, Matematisk Association of America, Washington, DC, 1976.
R. Johnsonbaugh, Diskret matematik, sjette udgave, Pearson Prentice Hall, Upper Saddle River, NJ, 2005.
D. Klarner, Box-Pakning gåder. Multilithed noter, University of Waterloo, Ontario, 1973-74. 42 sider + titelbladet. (Dele af dette er sammenfattet i kapitel 8 i Honsberger [13].)
GE Martin, Polyominoes, En guide til gåder og problemer i fliser, matematiske Association of America, Washington, DC, 1991.
GE Martin, gennemgang af S. Golomb s Polyominoes (1994 edition), Matematiske anmeldelser og MR1291821 (95k: 00006), 1995.
I. Mizniks, “Computer Analyse af 3 Color Problem for V-Shapes”, Acta societatis Mathematicae Latviensis, Abstracts af den 5. lettiske Matematisk Conference, April 6-7, 2004 Daugavpils, Letland. (Findes på http://www.de.dau.lv/matematika/lmb5/tezes/Mizniks.pdf)
RB Nelsen, Beviser uden ord II, Flere Øvelser i Visual Thinking, Matematisk Association of America, Washington, DC, 2000.
KH Rosen, Diskret Matematik og dens anvendelsesmuligheder, Femte udgave, McGraw-Hill, New York, 2003. (For at fremstå som eksempel 13, afsnit 4.1, i den sjette udgave, 2007.)
JN Silva (red.) Rekreative Matematik kollokvium I (Conference Proceedings, April 29 – Maj 2, 2009. University of Évora), Associação Ludus, Lisboa, 2010.
D. Singmaster, gennemgang af GE Martins Polyominoes, Matematiske anmeldelser og MR1140005 (93D: 00006), 1993.
A. Soifer, Geometri Etudes i Kombinatoriske matematik, anden udgave, Springer, New York, 2010.
N. Starr, “Tromino Fliselægning Mangelfulde Cubes af Side Længde 2n”, Geombinatorics XVIII (2) (2008), 72-87.
N. Starr, “Tromino Fliselægning Mangelfulde Cubes af eventuelle sidelængde”, http://arxiv.org/abs/0806.0524, 3. juni, 2008.
DJ Velleman, hvordan at bevise det: en struktureret tilgang, anden udgave, Cambridge University Press, New York 2006

Comments are closed.