Globe Views
500 things that everyone should know ...
Home | About Us

Den Tromino Puslespill

av norton Starr

Om Puzzle - Fysisk og virtuell

v-21 puzzle

Den grunnleggende puslespill består av 21 rettvinklede formet stykker ("flisene") av den typen som vises, sammensatt av tre kvadrater, en ekstra enkelt kvadrat flis, og et fly, 8 × 8 kvadrat grid som rutene er samme størrelse som de av flisene. Flisene okkupere totalt 3 × 21 + 1 = 63 + 1 = 64 kvadrater, samme antall av kvadrater som på en sjakkbrett. I det følgende kaller vi disse vinklede stykker trominoes, som den enkleste av flere navn som brukes for dem, som inkluderer L-trominoes, L-triominoes, og V-trominoes.

Å spille en fysisk versjon av denne oppgave, ved hjelp av 21 faktiske tromino fliser, en enkelt kvadrat stykke, og en 8 x 8 dambrett-lignende base, første posisjon den enkelt kvadrat flis på ett av de 64 firkantede steder på basen. Deretter fyller de resterende 63 kvadrater med trominoes slik at det ikke er noen overlapping og ingen ufylt square. En slik løsning på gåten kalles en flislegging av 8 x 8 kvadrat. Alternativt, starte med suksessivt plassere trominoes inn dambrett base (hver slik flis opptar bare tre kvadrater av rutenett mønster), og når alle 21 er plassert, plasseres enkelt kvadrat flisen i en posisjon som forblir tilgjengelig.

Her er bakgrunnen for den kommersielle versjonen av dette puslespillet, markedsført av Kadon Enterprises. På januar 2000 årlige møtet i Mathematical Association of America, fikk Arthur Benjamin Haimo prisen for fremragende college undervisning. I sin takketale skissert han sin favoritt bevis ved induksjon. Dette resonnementet sikrer at en 2n × 2n avbrutt square (dvs. en generalisert dambrett med 2n ruter langs hver side) med én celle okkupert, kan alltid være flislagt med trominoes. Tre år etter å ha hørt Benjamins bemerkninger ble jeg holde et foredrag på induksjon og mintes sin favoritt bevis. Supplere mine forberedt eksempler, jeg annonsen libbed denne klassiske argumentet, på grunn av Solomon Golomb. Tenker at en faktisk puslespill av denne typen ville legge til et element av virkeligheten og kan vekke interesse i metoden for induksjon, sendte jeg et notat til Kadon, en ledende puslespill maker, for å se om de hadde noen jeg kunne kjøpe. De gjorde ikke, så jeg spurte om de ville gjøre noen til min spesifikasjoner. En rekke e-poster med Kate Jones, president i Kadon, førte til et puslespill av den typen illustrert ovenfor venstre. Hun foreslo å bruke flere forskjellige farger for de tromino fliser, noe som gjør dette til en mer interessant puslespill enn jeg hadde opprinnelig tenkt. Jeg har valgt for kjøligere, gjennomskinnelige fliser i stedet for fet, ugjennomsiktig seg, og valgte blå, aqua og ametyst for trominoes. Kate spurte om jeg ville la Kadon legge puslespillet til en rekke elementer de selger, og jeg lett enige om - jeg bare ønsket noen for min egen bruk. Til min overraskelse, erklærte hun at jeg skulle motta royalties. Det var aldri mitt mål, og alle mine royalties er donert til Amherst College og Mathematical Association of America. Kadon brakt ut av puslespillet under navnet "Vee-21", se www.gamepuzzles.com/polycub2.htm # V21. Dette kommersielle versjonen, i tre levende, gjennomskinnelig akryl farger, kommer med en førti siders brosjyre som tilbyr en rekke forbedringer til de grunnleggende puslespill. Kate bidro noen utvidelser i puslespillet, noen to personer strategi spill, og forslag fra fargeseparasjon krav til tilings man kan forsøke. Hun oppdaget også de estetiske mulighetene i å gjøre symmetriske mønstre. Kate inviterte Oriel Maxime å bidra noen av hans labyrint-lignende utfordringer for flislegging med trominoes, og brosjyren inneholder en rekke rektangulære maler med strategisk valgt linjer tavlene formørket å tjene som barrierer over som trominoes ikke kan plasseres. To interaktive datamaskin puslespill av denne typen er gitt her. Den 8-by-8 puslespillet ble utviklet av to av mine studenter, mens en avdelingsleder kollega bidro M-by-N puslespillet. Den M-by-N puslespill (spiller på de fleste systemer, men kan være treg å laste) er noe mer fleksibelt, slik at valget av hvilket som helst antall rader og kolonner mellom 2 og 32, inklusive. Den 8-by-8 puslespill (spiller best med Internet Explorer på en PC) har en annen mus handling og fordel begrenses til tre farger tromino. Retninger er gitt med hver. Nett og Kadon versjoner både har uvanlig bredde appell, spennende for fire åringer så vel som erfarne puzzlers. Historie Beviset på at for noe positivt heltall n, en 2n × 2n firkant med én celle okkupert (en "mangelfull" firkant) kan alltid være flislagt med trominoes skyldes Solomon Golomb. Han publiserte den i sin 1954 artikkel [9] i American Mathematical Monthly. Som nevnt ovenfor, var det for å illustrere Golomb argument for 2n × 2n mangelfull firkanter som puslespillet ble bestilt. Hans samme artikkelen innført i skrive begrepet tromino og generalisering, Polyomino. En Polyomino er en tilkoblet rekke identiske kvadrater som har den egenskapen at to firkanter enten ikke berøre eller annet møte langs en hel, felles kant. De eneste to tromino figurer er tre ruter på rad og L-form i dette puslespillet, og her "tromino" bare refererer til sistnevnte. Golomb er bevis er et første-rate eksempel på matematisk induksjon. Utover ren eleganse av argumentet, er det en sjelden forekomst av en nonnumerical bruk av metoden. Dette står i kontrast til de eksempler og øvelser ofte finnes i lærebok behandlinger av induksjon, som typisk består av en rekke av formler for endelige summer, ulikheter, og lignende. Beviset første opptreden i et populært medium var i Joseph Madachy sin Recreational Matematikk Magazine (RMM), hvor Golomb tatt det i den første av hans fire deler serie artikler om polyominoes publisert i RMM [10]. I Martin Gardner banebrytende mai 1957 Scientific American kolonne innføre polyominoes til det brede publikum, bemerket han at "et styre med en firkant mangler på noe punkt, kan dekkes av 21 riktige trominoes" [6, s.. 154]. For sin første bok av innsamlede matematiske spill kolonner, Gardner utarbeidet av bemerket at "en genial induksjon argument viser at 21 rette trominoes og en monomino vil dekke 8-by-8 bord uavhengig av hvor monomino settes" [8, s.. 126]. Den tromino flislegging argument for mangelfulle Sjakkbrett og den generelle 2n × 2n teorem har dukket opp i en rekke bøker siden Månedlig og RMM artikler. Det ble forklart i Golomb klassiske Polyominoes [11, 1965, s. 21-22] og i den andre utgaven av boken [11, 1994, s.. 5]. Den andre utgaven gir en rik historie og en omfattende undersøkelse av denne spennende emne, og er fylt med bilder og oppgaver. Sine 22 sider av referanser, siterer både bøker og artikler, er en ekstra bonus. Indeksen av navnene lister 81 individer, ganske mange nevnt mer enn én gang i kroppen av boken. Mange av disse vil bli gjenkjent av spillet aficionados og amatører matematikere samt av fagfolk i enten området. En beskrivelse av boken er gitt i anmeldelsen [17] av George Martin. I 1976 ga Ross Honsberger en klar og detaljert anvendelse av Golomb argument til kontrolløren styret i sin Mathematical Gems II [13, s.. 61]. Den grunnleggende ideen om bevis er også nevnt i George E. Martin bok viet til Polyomino tilings [16, s. 27-28]. David Singmaster gjennomgang [22] i denne siste boken er spesielt interessant, for det gir en flott skisse av faget og dets historie. Dette emnet er også stadig mer vanlig takst for tekster og problemområder bøker. For eksempel vises det i de diskrete matematikk tekster av Susanna Epp [5, p. 234], Richard Johnsonbaugh (som nevner tromino tilings av rektangler som oppstår i VLSI layout design) [14, s. 58-59], og Kenneth Rosen [20, s. 247-8]. Tromino flislegging er også behandlet i Daniel Velleman bok om bygging bevis [26, s. 271-275], og problemet bøker av John P. D'Angelo & Douglas B. West [1, s.. 75] og ved Jiří Herman, Radan Kucera & Jaromír Simsa [12, s.. 271]. Den mest krystallinsk illustrasjon av Golomb argumentet er Roger Nelsen er ekstra "bevis uten ord," gitt i sin andre bok den tittelen [19, s.. 123]. Dette området av fritidsaktiviteter matematikk har dratt nytte av en vedvarende strøm av etterforskning og foreslo problemer. I 1985 og 1986 studerte jeg-Ping Chu og Richard Johnsonbaugh spørsmålet flislegging mangelfull n × n boards, der n ikke lenger trenger være en effekt på 2, og mer generelt, mangelfull og ikke-mangelfull platens [3, 4 ]. George Martin bok inkludert et helt kapittel viet til tromino tilings [16, s. 23-37]. Coloration problemer for tromino flislegging er behandlet av Ilvars Mizniks, som erkjenner Kadon Vee-21 fargevalg side som inspirasjon for sin forskning [18]. 2004 artikkelen [2] av J. Marshall Ash og Solomon Golomb, om tromino flislegging av mangelfulle rektangler, inneholder flere nye og grunnleggende resultater, hvorav svarer på en gammel spørsmålet Chu og Johnsonbaugh. Aske og Golomb ende med et åpent problem om to-mangelfull rektangler (rektangler med to cellene fjernes). Internett er en god kilde til flislegging skjermer og informasjon. For eksempel slår et søk på "tromino" og "flislegging" opp applets for eksempel av 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 oppgaver i flere størrelser. Variasjoner Her er noen utvidelser av tromino puslespill som leserne kan vurdere. Den første ble foreslått av min bror Raymond (Pete), som spurte hvordan man kan arrangere trominoes i 8 × 8 rutenett, slik som å maksimere antall ledige plasser. Dette kan utdypet: en rute ville anta fliser og rutenettet blir velcroed slik at de holder seg på plass, mens alternativt kunne tillate fliser å skyve for å tillate klemme så mange brikker som mulig (alltid innenfor rutenettet linjer). Pete var ikke klar over at borrelås versjonen er en variant av Golomb er pentomino posisjonering puslespill som beskrevet av Gardner [7, s.. 128] og [8, s.. 133]. Golomb utvidet dette puslespillet til en to-person pentomino spillet [7, s.. 128] og [8, s. 133-135], regler for som kan brukes til tromino puslespill også. David Klarner rapportert på en to-person pentomino spillet, Pan-Kai (utviklet av Alex Randolph og utgitt i 1961 av Phillips Publishers), som inkluderte følgende begrensning: "den viktigste regelen er at det er forbudt å spille et stykke inne i en avsluttet regionen av styret hvis færre enn 5 celler vil da forbli ledig, hvis ikke farten nøyaktig fyller regionen. "[15, s.. 8] (Se [21, s.. 75] for mer informasjon om Randolph og Pan-Kai.) En annen retning er tredimensjonalt. Vurdere en kube av sidelengde 2n, inneholder 23N enhet celler, hvorav den ene er okkupert (enkelt mangel.) Kan de gjenværende cellene være flislagt med tredimensjonale trominoes (tre kuber i en L-form, med to av dem møte den tredje på to tilstøtende ansikter sistnevnte)? Den nødvendige betingelse at 2n = 3K + 1 viser seg å være tilstrekkelig så vel. [23, kapittel 6: Norton Starr er 3-dimensjonal Tromino Flislegging], [24, s. 72-87] og [25] The case of a 4 × 4 × 4 kube presenterer noen beskjedne utfordringer som kan underholde unge puzzlers. Enklere problemer lett foreslår seg selv og har vært ansett av mange andre. For eksempel kan hele 3 × 3 og 6 × 6 kvadrat matriser være flislagt med trominoes? Kan hver mangelfull 5 × 5 og 7 × 7 kvadrat matrise flislegges? Disse to sistnevnte oppgaver er mer utfordrende enn full 3 × 3, 6 × 6, og mangelfull 8 × 8 tilfeller. Går videre, kan leserne vurdere tilings av ulike rektangulære arrays - se referansene nedenfor. Når du bruker en versjon med mer enn én farge av tromino, som Kadon Vee-21, vurdere ulike farger begrensninger. Prøv for eksempel å arrangere flisene slik at ingen to av samme farge deler en kant. I motsatt retning, kan du prøve å gruppere så mange brikker av samme farge sammen som mulig. For begge disse mønster typene, prøv videre for å gjøre flislegging vises symmetrisk om en diagonal eller om en horisontal eller vertikal linje. Mulighetene for moro og funn er mange. Ulik størrelse rektangler kan studeres ved å klikke på M-by-N puslespillet. For fargemønsteret eksperimenter, er Kadon puslespillet beste. Referanser
  1. JP D'Angelo og DB West, matematisk tenkning: Problemløsning og Proofs, Second Edition, Prentice Hall, Upper Saddle River, NJ, 2000.
  2. JM Ash og SW Golomb, "Flislegging mangelfull rektangler med trominoes," Math. Mag., 77 (2004), 46-55. (Tilgjengelig på math.depaul.edu / ~ mash/TileRec3b.pdf)
  3. IP Chu og R. Johnsonbaugh, "Flislegging mangelfull boards med trominoes," Math. Mag., 59 (1986), 34-40.
  4. IP Chu og R. Johnsonbaugh, "teglstein styrene med trominoes," J. Recreational Math., 18 (1985-86), 188-193.
  5. SS Epp, Diskret matematikk med applikasjoner, tredje utgave, Thomson, Belmont, CA, 2004.
  6. M. Gardner, "Om slående likhet mellom Icosian spill og Tower of Hanoi," Scientific American, 196, (mai 1957), 150-156. Denne kolonnen ble i hovedsak viet til Hamilton kretser, men ender med et avsnitt om sjakkbrett flislegging problemer: Gardner sier at i februar kolonnen dambrett / domino problem "bedt Octave Levenspiel av Bucknell University for å ringe min oppmerksomhet til en bemerkelsesverdig artikkel av SW Golomb i American Mathematical månedlig for desember 1954. "
  7. M. Gardner, "Mer om komplekse dominobrikker, pluss svar på forrige måneds puslespill," Scientific American, 197, (desember 1957), 126-140. Dette Mathematical Games kolonnen starter ved å rapportere den eksplosive effekten av mai kolonnens kort redegjørelse for Golomb arbeid [6]: "I år siden denne avdelingen ble innviet, har den fått flere brev om en matematisk rekreasjon enn noen andre ... den" pentomino ' problem ... Hundrevis av korrespondenter sendt i svært varierende løsninger. Mange vitnet til problemet er rart fascinasjon .... "
  8. M. Gardner, The Scientific American Book of Mathematical Puzzles og avsporing, Simon og Schuster, New York, 1959. (Gjengitt og oppdatert som Hexaflexagons og andre matematiske avsporing, University of Chicago Press, 1988.) [Kapittel 13 i denne første slik innsamling kombinerer flislegging materialet [6] og [7] og har tittelen "Polyominoes."]
  9. SW Golomb, "Checker Boards og Polyominoes," Amer. Matematikk. Månedlig, 61 (1954), 675-682.
  10. SW Golomb, "The General Theory of Polyominoes Del I - Dominoes, Pentominoes og Sjakkbrett," Recreational Math. Mag., 4. utgave nr. (august 1961), 3-12.
  11. SW Golomb, Polyominoes, Scribner for, New York, 1965. (Andre utgave: Polyominoes, Puslespill, mønstre, problemer og emballasje Princeton University Press, Princeton, 1994.)
  12. J. Herman, R. Kucera og J. Simsa, Counting og konfigurasjoner: Problemer i Kombinatorikk, regning, og geometri (Karl Dilcher, oversetter), Springer-Verlag, New York, 2003.
  13. R. Honsberger, Matematisk Gems II, Mathematical Association of America, Washington, DC, 1976.
  14. R. Johnsonbaugh, Diskret matematikk, sjette utgave, Pearson Prentice Hall, Upper Saddle River, NJ, 2005.
  15. D. Klarner, Box-Emballasje Puzzles. Multilithed notater, University of Waterloo, Ontario, 1973-1974. 42 sider + tittel siden. (Deler av denne er oppsummert i kapittel 8 Honsberger [13].)
  16. GE Martin, Polyominoes, A Guide to puslespill og problemer i Tiling, Mathematical Association of America, Washington, DC, 1991.
  17. GE Martin, gjennomgang av S. Golomb er Polyominoes (1994-utgaven), Mathematical Reviews, MR1291821 (95k: 00006), 1995.
  18. I. Mizniks, "Computer Analyse av tre Color Problem for V-Shapes", Acta Societatis Mathematicae Latviensis, Abstracts av 5. latviske Mathematical Conference, 6 til 7 april 2004, Daugavpils, Latvia. (Tilgjengelig på http://www.de.dau.lv/matematika/lmb5/tezes/Mizniks.pdf)
  19. RB Nelsen, Proofs uten ord II, flere øvelser i Visual Thinking, Mathematical Association of America, Washington, DC, 2000.
  20. KH Rosen, Diskret matematikk og dens applikasjoner, Fifth Edition, McGraw-Hill, New York, 2003. (Hvis du vil vises som eksempel 13, § 4.1, i den sjette utgaven, 2007.)
  21. JN Silva (red.) Recreational Matematikk Colloquium I (Konferansemateriell, 29 april til 2 mai 2009. Universitetet i Evora), Associação Ludus, Lisboa, 2010.
  22. D. Singmaster, gjennomgang av GE Martins Polyominoes, Mathematical Reviews, MR1140005 (93d: 00006), 1993.
  23. A. Soifer, Geometriske Etudes i kombinatorisk matematikk, Second Edition, Springer, New York, 2010.
  24. N. Starr, "Tromino Flislegging Mangelfull Cubes av sidelengde 2n", Geombinatorics XVIII (2) (2008), 72-87.
  25. N. Starr, "Tromino Flislegging Mangelfull Cubes av noen side Lengde", http://arxiv.org/abs/0806.0524, 3. juni 2008.
  26. DJ Velleman, How To Prove It: en strukturert tilnærming, Second edition, Cambridge University Press, New York, 2006

Oversatt s http://www3.amherst.edu/~nstarr/trom/intro.html Hjemmeside
Globe Views

Copyright™ 2014: «QRATOR Creative Technologies»