Den Tromino Pussel av Norton Starr

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

Om Pussel – Fysiska och Virtuella

v-21 pussel De grundläggande pussel består av 21 rätt vinkel formade bitar (“plattor”) av den typ som visas, som består av tre rutor, en ytterligare enda kvadrat kakel, och en plan, 8x8 kvadratiska rutnät vars rutor har samma storlek som de som plattor. Brickorna upptar totalt 3x21 + 1 = 63 + 1 = 64 torg, samma antal rutor på ett schackbräde. I vad som följer kommer vi kallar dessa vinklade bitar trominoes, som den enklaste av flera namn som används för dem, som innehåller L-trominoes, L-triominoes, och V-trominoes.
för Att spela en fysisk version av detta pussel, med hjälp av 21 faktiska tromino plattor, en enkel fyrkantig bit, och en 8x8 checkerboard-som bas, först placera den inre kvadrat kakel på någon av de 64 kvadrat lägen på basen. Fyll sedan i den resterande 63 rutor med trominoes så att de inte överlappar varandra och ingen ofylld kvadrat. En sådan lösning är att det pussel som kallas för en plattsättning 8x8 kvadrat. Alternativt, börja med att successivt placera trominoes i den schackrutiga bas (varje bricka upptar endast tre rutor i rutnätet mönster), och när alla 21 som är placerade, placera enda kvadratiska plattor i en position som är tillgänglig.

Här är bakgrunden till den kommersiella versionen av detta pussel, som marknadsförs av Kadon Företag. I januari 2000 årliga mötet för den Matematiska Association of America, Arthur Benjamin fick Haimo utmärkelse för framstående college undervisning. I sitt tacktal att han skissat sin favorit bevis med induktion. Detta resonemang innebär att en 2n×2n encelliga square (dvs en generaliserad rutmönster med 2n rutor längs varje sida) med en cell ockuperade, kan alltid vara kakel-av trominoes. Tre år efter att ha hört Benjamin kommentarer jag höll en föreläsning om induktion och återkallade hans favorit bevis. Komplettera mina förberedda exempel, jag ad-libbed detta klassiska argumentet, på grund av att Salomo Golomb. Att tro att en verklig pussel av detta slag skulle lägga till ett element av verkligheten och kan väcka intresse för metoden för induktion, jag skickade en not till Kadon, en ledande pussel tekokare, för att se om de hade något jag skulle kunna köpa. De visste inte, så jag frågade om de skulle göra några till mina specifikationer. En serie av e-post med Kate Jones, Ordförande för Kadon, ledde till ett pussel av den typ som illustreras ovan till vänster. Hon föreslog att använda flera olika färger för tromino plattor, vilket gör detta till en mer intressant pussel än vad jag ursprungligen hade tänkt. Jag valde svalare, genomskinliga plattor snarare än fet, ogenomskinlig och kära, och valde blå, turkos och ametist för trominoes.

Kate frågade om jag skulle låta Kadon lägga pussel för att urval av objekt de säljer och jag gick lätt – jag ville bara ha lite för mitt eget bruk. Till min förvåning, hon förklarade att jag skulle få royalties. Det var aldrig mitt mål, och alla mina royalties är donerade till Amherst College och Matematisk Association of America.

Kadon förde ut pusslet under namnet “Vee-21”, se www.gamepuzzles.com/polycub2.htm#V21. Denna kommersiella version, i tre levande, genomskinlig akryl färger, kommer med en fyrtio sidig broschyr som erbjuder ett antal förbättringar till den grundläggande pussel. Kate bidragit med några tillägg av pussel, en del två-person strategi spel, och förslag på färg krav på åtskillnad för tilings man kan försöka. Hon upptäckte också att den estetiska möjligheter i att göra symmetriska mönster. Kate inbjudna Oriel Maximé för att bidra till några av hans labyrint-liknande utmaningar för plattsättning med trominoes, och broschyren innehåller en mängd olika rektangulära mallar med strategiskt valda linjer av nät mörklagt för att fungera som hinder över som trominoes får inte släppas ut.

Två interaktiva dator pussel av denna typ finns här. Den 8-av-8 pussel har utvecklats av två av mina elever, samtidigt som en flytt kollega bidragit M-med-N puzzle. M-av-N-pussel (spelar på de flesta system, men kan vara långsamma att ladda) är något mer flexibla, vilket gör att valet av valfritt antal rader och kolumner mellan 2 och 32, inkluderande. Den 8-av-8 pussel (spelar bäst med Internet Explorer på en PC) har en annan mus åtgärder och är med fördel begränsas till tre färger av tromino. Anvisningar ges med varandra. Online och Kadon-versioner som båda har en ovanlig bredd av överklagande, spännande för fyra-åringar och rutinerade puzzlers.


Historia
Visa att för varje positivt heltal n, 2nx2n kvadrat med en cell som upptas (en “bristfällig” square) kan alltid vara kakel-av trominoes är på grund av att Salomo Golomb. Han publicerade den i sin 1954 artikel [9] i American Mathematical Monthly. Som nämnts ovan, var det för att illustrera Golomb argument för 2nx2n bristfällig rutor att pusslet var beställd. Hans samma artikel som infördes i print termen tromino och dess generalisering, polyomino. En polyomino är en sammanhängande rad av identiska rutor med den egendom som någon två rutor som antingen inte röra eller annat möta längs hela, gemensam kant. De enda två tromino former finns tre rutor i rad och L-form i detta pusselspel, och här “tromino” bara hänvisar till den senare.

Golomb är ett bevis är ett förstklassigt exempel på matematisk induktion. Utöver ren elegans av argument, det är ett sällsynt exempel på en nonnumerical tillämpning av metoden. Detta står i kontrast till de exempel och övningar som ofta finns i läroboken behandlingar av induktion, som normalt består av en mängd olika formler för ändliga summor, orättvisor och liknande. Beviset första framträdande i ett populärt medium var i Joseph Madachy Fritids Matematik Tidningen RMM), där Golomb ingår det i den första av fyra delar serie av artiklar om polyominoes publiceras i RMM, [10]. I Martin Gardner sädes Maj 1957 Scientific American kolumnen införa polyominoes till allmänheten anmärkte han att “en styrelse med en ruta som saknas på alla punkt, kan vara som omfattas av 21 rätt trominoes” [6, s. 154]. För sin första bok av insamlade Matematisk Spel kolumner, Gardner som utarbetats genom att påpeka att “en genial induktion argument visar att 21 rätt trominoes och en monomino kommer att omfatta 8-av-8 styrelsens oberoende av var monomino placeras” [8, s. 126].

Den tromino plattsättning argument för bristfällig checkerboards och allmänt 2n×2n sats har medverkat i en rad böcker sedan varje Månad och RMM artiklar. Det förklarades i Golomb klassiska Polyominoes, [11, 1965, s. 21-22] och i den andra upplagan av denna bok [11, 1994, s. 5]. Den andra upplagan ger en rik historia och en omfattande undersökning av detta spännande ämne, och är fylld med bilder och pussel. 22 sidor referenser, med hänvisning till både böcker och artiklar, är en extra bonus. Index namn listor 81 personer, en hel del avses mer än en gång i kroppen av boken. Många av dessa kommer att redovisas av spel aficionados och amatör matematiker samt av personal i antingen område. En beskrivning av boken ges i granskningen [17] av George Martin. I 1976, Ross Honsberger gav en tydlig, detaljerad tillämpning av Golomb argument till checker board i hans Matematisk Pärlor II, [13, s. 61]. Den grundläggande idén av bevis är också nämns i George E. Martins bok ägnas åt polyomino tilings [16, s. 27-28]. David Singmaster: s genomgång [22] i detta sistnämnda boken är särskilt intressant, för det ger en vacker skiss av ämnet och dess historia.

Detta ämne är också allt vanligare biljettpriset för texter och problem böcker. Till exempel, det dyker upp i diskret matematik texter av Susanna Epp [5, s. 234], Richard Johnsonbaugh (som nämner tromino tilings av rektanglar som uppstår i VLSI layout) [14, s. 58-59], och Kenneth Rosen [20, s. 247-8]. Tromino plattsättning är även behandlas i Daniel Velleman bok om att konstruera bevis [26, s 271-275] och problemet böcker av John P. D ‘ Angelo & Douglas B. West [1, s. 75] och av Jiří Herman, Radan Kučera & Jaromír Šimša [12, s. 271]. De kristallina illustration av Golomb argument är Roger Nelsen är extra “bevis utan ord,” med tanke på hans andra bok som titeln [19, s. 123].

Detta område av fritids matematik har dragit nytta av en fortsatt ström av utredning och föreslog problem. Under 1985 och 1986 I-Ping Chu och Richard Johnsonbaugh studerat frågan om plattsättning bristfällig n×n styrelser, där n behöver inte längre vara en effekt av 2, och, mer allmänt, brister och icke-brist rektangulär styrelser [3, 4]. George Martins bok ingår ett helt kapitel ägnas åt tromino tilings [16, s. 23-37]. Färg problem för tromino plattsättning behandlas av Ilvars Mizniks, som erkänner Kadon Vee-21 färgval sida som inspiration för sin [18]. 2004 artikeln [2] av J. Marshall Aska och Salomo Golomb, om tromino plattsättning av bristfällig rektanglar, innehåller flera nya och grundläggande resultat, som svar på en gammal fråga Chu och Johnsonbaugh. Aska och Golomb avslutas med en öppen problem om 2-bristfällig rektanglar (rektanglar med två celler avlägsnas).

Internet är en bra källa av plattsättning och visar information. Till exempel, en sökning på “tromino” och “kakel” dyker upp applets som de av Alexander Bogomolny på www.cut-the-knot.org/Curriculum/Games/TrominoPuzzle.shtml och Christopher Mawata på www.utc.edu/Faculty/Christopher-Mawata/trominos/som illustrera tromino pussel i flera storlekar.


Variationer
Här är några förlängningar av tromino pussel som läsare kan överväga. Den första var på förslag av min bror Raymond (Pete), som frågade hur man kan ordna trominoes i 8×8 rutnätet så att maximera antal obemannat rutor. Detta kan utarbetas på: en väg skulle förutsätta plattor och nätet är velcroed så de stannar på plats, samtidigt som alternativt kan man låta brickor för att glida så att det blir möjligt att klämma in så många brickor som möjligt (alltid inom grid lines). Pete var inte medvetna om att kardborreband version är en variant på Golomb är pentomino positionering pussel som beskrivs av Gardner [7, sid. 128] och [8, s. 133]. Golomb utökad detta pussel för att en två-person pentomino spel [7, sid. 128] och [8, s. 133-135], regler som kan tillämpas för att den tromino pussel. David Klarner rapporterade om en två-person pentomino spel, Pan-Kāi (utvecklat av Alex Randolph och som har utfärdats i 1961 av Phillips Förlag), som ingår följande begränsning: “den viktigaste regeln är att det är förbjudet att spela en bit inne i ett stängt regionen av styrelsen, om färre än 5 celler skulle sedan vara lediga, såvida inte flytta exakt fyller i regionen.” [15, s. 8] (Se [21, s. 75] för mer information om Randolph och Pan-Kāi.)En annan riktning är tredimensionell. Överväga en kub med sidan längd 2n, som innehåller 23n enhet celler, av vilka den ena är upptagen (enda brist.) Kan de återstående cellerna kaklade med tre dimensionell trominoes (tre tärningar i en L-form, med två av dem mötes-och den tredje på två intilliggande ytor av de senare)? Det nödvändiga villkoret att 2n = 3k + 1 visar sig vara tillräckliga. [23 Kapitel 6: Norton Starr är 3-Dimensionell Tromino Plattsättning], [24, s. 72-87] och [25] fallet med en 4×4×4 kub presenterar några små utmaningar som kan roa unga puzzlers.

Enklare problem lätt tyder på sig själva och har behandlats av flera andra. Till exempel kan hela 3×3 och 6×6 kvadratiska matriser kaklade med trominoes? Kan varje bristfällig 5×5 och 7×7 kvadratmeter array kaklade? Dessa två sistnämnda pussel är mer utmanande än hela 3×3, 6×6, och bristfällig 8×8 fall. Går vidare, får läsarna anser tilings av olika rektangulära matriser, se referenser nedan. När du använder en version med mer än en färg av tromino, såsom Kadon Vee-21, överväga olika färg begränsningar. Till exempel, prova att ordna brickorna så att inte två av samma färg för att dela en kant. I motsatt riktning, försöka samla så många brickor av samma färg tillsammans som möjligt. För båda dessa mönster typer, prova ytterligare för att göra plattsättning visas symmetrisk om en diagonal eller om en horisontell eller vertikal linje. Möjligheterna till roligt och discovery är många. Olika storlek rektanglar kan studeras genom att klicka på M-med-N pussel. För färg mönster experiment, Kadon pussel som är bäst.


> Referenser

  1. J. P. D ‘ Angelo och D. B. West, Matematiskt Tänkande: att Lösa Problem och Korrektur, Andra upplagan, Prentice Hall, Upper Saddle River, NJ, 2000.
  2. J. M. Aska och S. W. Golomb, “Plattsättning bristfällig rektanglar med trominoes,” Math. Mag – ., 77 (2004), 46-55. (Tillgänglig på math.depaul.edu/~mash/TileRec3b.pdf)
  3. I. P. Chu och R. Johnsonbaugh, “Plattsättning bristfällig styrelser med trominoes,” Math. Mag – ., 59 (1986), 34-40.
  4. I. P. Chu och R. Johnsonbaugh, “Plattsättning styrelser med trominoes,” J. Fritids Matematik., 18 (1985-86), 188-193.
  5. S. S. Epp, Diskret Matematik med Tillämpningar, Tredje upplagan, Thomson, Belmont, CA, 2004.
  6. M. Gardner, “Om den märkliga likheter mellan Icosian Spel och Tower of Hanoi,” Scientific American, 196, (Kan, 1957), 150-156. Denna kolumn var i första hand åt att Hamilton kretsar, men avslutas med ett avsnitt om schackrutigt kakel problem: Gardner säger att februari kolumnen schackrutiga/domino problem “uppmanas Oktav Levenspiel av Bucknell University för att kalla på min uppmärksamhet till en märklig artikel av S. W. Golomb i American Mathematical Monthly för December, 1954.”
  7. M. Gardner, “Mer om komplexa domino, plus svaren på förra månadens pussel,” Scientific American, 197, (December 1957), 126-140. Detta Matematisk Spel kolumn börjar genom att rapportera den explosiva effekten av den Kan kolumn kort redogörelse av Golomb arbete [6]: “I det år då denna avdelning invigdes, det har fått flera brev om en matematisk rekreation än någon annan… “pentomino” problem… Hundratals kontaktpersoner skickas inom mycket varierande lösningar. Många vittnade om att problemet är konstigt fascination… .”
  8. M. Gardner, Det Vetenskapliga Bok av Matematiska Pussel & Omläggningar, Simon and Schuster, New York, 1959. (Omtryckt och uppdaterad som Hexaflexagons och Andra Matematiska Omläggningar, University of Chicago Press, 1988.) [Kapitel 13 i denna första samling kombinerar plattsättning material [6] och [7] och har titeln “Polyominoes.”]
  9. S. W. Golomb, “Checker Styrelser och Polyominoes,” Amer. Matten. Varje månad, 61 (1954), 675-682.
  10. S. W. Golomb, “The General Theory of Polyominoes Del i – Domino, pentominoes. passa siffrorna i elnätet och Checkerboards,” Fritids Matematik. Mag – ., Fråga Nr 4 (Augusti 1961), 3-12.
  11. S. W. Golomb, Polyominoes, Scribner ‘ s, New York, 1965. (Andra upplagan: Polyominoes, Pussel, Mönster, Problem och Förpackningar med en nettovikt av, Princeton University Press, Princeton, 1994.)
  12. J. Herman, R. Kučera och J. Šimša, , Räkna och Konfigurationer: Problem i Kombinatorik, Aritmetik och Geometri (Karl Dilcher, översättare), Springer-Verlag, New York, 2003.
  13. R. Honsberger, Matematisk Pärlor II, Matematiska Association of America, Washington, DC, 1976.
  14. R. Johnsonbaugh, Diskret Matematik, Sixth edition, Pearson Prentice Hall, Upper Saddle River, NJ, 2005.
  15. D. Klarner, Box-Förpackning Pussel. Multilithed anteckningar, University of Waterloo, Ontario, 1973-74. 42 sidor + titelsida. (Delar av denna sammanfattas i Kapitel 8 av Honsberger [13].)
  16. G. E. Martin, Polyominoes, En Guide till Pussel och Problem i Kakel, Matematiska Association of America, Washington, DC, 1991.
  17. G. E. Martin, översyn av S. Golomb Polyominoes (1994 års utgåva), Matematisk Recensioner, MR1291821 (95k:00006), 1995.
  18. I. Mizniks, “Computer Analys av 3 Färg Problemet för V-Former”, , Acta Societatis Mathematicae Latviensis, Sammanfattningar av 5 lettiska Matematiska Konferens, 6-7 April, 2004, Daugavpils, Lettland. (Tillgänglig på http://www.de.dau.lv/matematika/lmb5/tezes/Mizniks.pdf)
  19. R. B. Nelsen, Bevis Utan Ord II, Mer Övningar i Visuellt Tänkande, Matematiska Association of America, Washington, DC, 2000.
  20. K. H. Rosen, , Diskret Matematik och Dess Tillämpningar, Femte upplagan, McGraw-Hill, New York, 2003. (Visas som Exempel 13, Avsnitt 4.1 i sjätte upplagan, 2007.)<namn=”sjung”>
  21. J. N. Silva (Ed.) Fritids Matematik Symposiet jag (Conference Proceedings, Apr. 29-Maj 2, 2009. Universitetet i Évora), Associação Ludus, Lisboa, 2010.
  22. D. Singmaster, översyn av G. E. Martin Polyominoes, Matematiska Recensioner, MR1140005 (93d:00006), 1993.
  23. A. Soifer Geometriska Etudes i Kombinatorisk Matematik, Second Edition, Springer, New York, 2010.
  24. N. Starr, “Tromino Plattsättning Bristfällig Kuber av Sidan Längd 2n“, Geombinatorics XVIII(2) (2008), 72-87.
  25. N. Starr, “Tromino Plattsättning Bristfällig Kuber av Några Biverkningar Längd”, http://arxiv.org/abs/0806.0524 , juni 3, 2008.
  26. D. J. Velleman, Hur kan man Bevisa Det: En Strukturerad Metod, Andra upplagan, Cambridge University Press, New York, 2006

Leave a Reply

Your email address will not be published. Required fields are marked *