Domino juostos • Haydar Nurligareev • Populiariosios mokslinės užduotys "Elementai" • Matematika

Domino juostos

Užduotis

Pav. 1.

a) Kiek keliais būdais Ar galiu plyteles 2 × 10 juostelėmis su 2 × 1 domino? Plytelių plytelės, gautos viena nuo kitos per juostelės sukimąsi, laikomos skirtingomis; Pavyzdžiui, 1 paveiksle parodytos dvi skirtingos 2 × 3 plytelių juostos.
b) Tas pats klausimas 3 × 30 juostos atžvilgiu.


1 patarimas

a) Stenkitės ieškoti atsakymo į klausimą, pateiktą kaip ypatingas bendresnės problemos atvejis: kiek būdų galite domino 2 ×n už savavališką natūralų skaičių n? Nurodykite tokios juostos pakrovimų skaičių an – jis duos numerių seką. Kaip sekantis šios sekos elementas susijęs su ankstesniais?

b) Ar galime naudoti tuos pačius argumentus, kaip ir punkte a)?


2 patarimas

b) Veikti gana panaši į sąlygą a) Tai neveikia: domino kauliukus neįmanoma sudaryti iš nelyginio ląstelių skaičiaus. Todėl būtina apsvarstyti tik vienodo ilgio juostas. Leisk bn – 3 × 2 atraminių juostelių skaičiusn Domino. Kaip sekantis šios sekos elementas susijęs su ankstesniais?


Sprendimas

Pav. 2

a) Pirmiausia mes tai pažymi a1 = 1, a2 = 2 – atitinkami atramos yra parodytos fig. 2Kitas, tarkim, kai kurie natūralūs n visos vertės iš a1 iki an mes jau žinome. Kaip rasti an+1? Norėdami tai padaryti, mes atsižvelgiame į kairę viršutinę juostos juostelę 2 × (n + 1). Kiekvienoje plytelių dalyje jis yra padengtas tam tikru domino vertikaliu arba horizontaliu paviršiumi (3 pav.). Pirmuoju atveju mes galime nutraukti šį domino, kad likusį skaičių būtų 2 × juostosn. Tai reiškia, kad juostos išlyginimo skaičius yra 2 × (n + 1), kuriame kairysis viršutinis elementas yra padengtas vertikaliu domino skaičiumi, sutampa su juostos 2 ×n ir lygus an. Kalbant apie antrąjį atvejį, tiesa, kairysis apatinis elementas taip pat bus padengtas horizontaliu domino skaičiumi, o kartu šie domino formos bus 2 × 2 kvadratas, o jų nupjovimas duos 2 × juostelę (n – 1). Todėl juostos išlyginimo skaičius yra 2 × (n + 1), kuriame kairysis viršutinis elementas yra padengtas horizontaliu domino numeriu, sutampa su juostos plytelių skaičiumi 2 × (n – 1) ir lygus an−1.

Pav. 3

Apibendrinant rezultatus, gauname tokį pasikartojimo santykį: an+1 = an + an−1. Šiuo metu skaitytojas, susipažinęs su "Fibonacci" numeriais, nedelsdamas pateiks atsakymą.Tačiau net ir be tokių žinių, sunku rasti nuoseklų skaičiavimą a3 = 3, a4 = 5, a5 = 8, a6 = 13, a7 = 21, a8 = 34, a9 = 55, a10 = 89.

Atkreipkite dėmesį, kad gautas mūsų santykis taip pat galioja n = 1, jei mes manysime, kad a0 = 1: šiuo atveju lygybė an+1 = an + an−1 virsta 2 = 1 + 1. Šis svarstymas galioja elementui b)kad artimiausioje ateityje mums pavyks.

b) Panašus, nors ir šiek tiek gudrus argumentas taikomas 3 × 30 diapazonui. Pradedantiesiems tai pastebėsite b0 = a0 = 1, b1 = a3 = 3. Be to, tarkime, kad kai kuriems natūraliems n visos vertės iš b0 iki bn jau žinoma ir bandykite jas išreikšti bn+1. Norėdami tai padaryti, apsvarstykite domino, kuris apėmė kairę vidurinę langelį – tai yra trys galimi jos vietos nustatymai. Viename iš jų svarstomas dominas yra horizontalus, ir lengva pastebėti, kad tokių 3 × 2 juostelių (n + 1) sutampa su 3 × 2 plytelesnkuris yra lygus bn. Likusiose dviejose versijose domino yra vertikalus, ir kiekviena iš šių parinkčių natūraliai suskirstyta į du atvejus: viename iš jų sumaišymo skaičius yra bn, o kitame, pakartotinai galima suskirstyti į dvi sudėtines dalis ir pan.(4 pav.).

Pav. 4

Tęsdami argumentą tokiu būdu, darome išvadą, kad seka bn turi atitikti tokį santykį:

\ [b_ (n + 1) = b_n + (b_n + b_ (n-1) + \ ldots + b_1 + b_0) + (b_n + b_ (n-1) + \ ldots + b_1 + b_0). \]

Suderinus tokias sąlygas, mes sugalvojam kompaktiškesnę versiją:

\ [b_ (n + 1) = 3b_n + 2 (b_ (n-1) + \ ldots + b_1 + b_0). \]

Iš esmės gautas santykis jau yra tinkamas apskaičiuoti b15ypač jei šiuo tikslu naudojate kompiuterį. Tačiau jei norite rankiniu būdu apskaičiuoti pageidaujamą vertę, patogiau pirmiausia supaprastinti gautą išraišką. Norėdami tai padaryti, pakanka išskaidyti tą patį santykį iš abiejų paskutinės formulės dalių, tačiau išrašyta ne bn+1ir už bn. Tokiu būdu mes gauname

\ [b_ (n + 1) -b_n = (3b_n + 2b_ (n-1) + \ ldots + 2b_0) – (3b_ (n-1) + 2b_ (n-2) + \ ldots + 2b_0), \]

arba po akivaizdžių pokyčių:

\ [b_ (n +1) = 4b_n-b_ (n-1). \]

Paskutinė išraiška leidžia greitai gauti atsakymą net rankiniu būdu: b2 = 11, b3 = 41, b4 = 153, b5 = 571, b6 = 2131, b7 = 7953, b8 = 29 681, b9 = 110 771, b10 = 413 401, b11 = 1 542 841, b12 = 5 757 961, b13 = 21 489 003, b14 = 80 198 051, b15 = 299 303 201.


Po žodžio

Problemos užuominose buvo pasiūlyta apsvarstyti bendresnį klausimą: kaip dauguma būdų domino gali būti plytelių su domino 2 ×n ir 3 × 2n? Gali būti, kad skaitytojas pagrįstai pasiteiraus apie situaciją atsakydamas į jį. Pasirodo, kad jei seka atitinka linijinį pasikartojančią santykį, tai yra jo formulė nojo elemento, kurį galima rasti naudojant funkcijų generavimo metodą. Visų pirma, Fibonacci skaičiai an Bineto formulė galioja:

\ [a_n = \ dfrac (1) (\ sqrt (5)) \ cdot \ left (\ left (\ dfrac (1 + \ sqrt (5)) (2) \ right) ^ (n + 1) – \ left (\ dfrac (1- \ sqrt (5)) (2) \ right) ^ (n + 1) \ right) \]

ir elementai bn patenkinti santykį

\ [b_n = \ dfrac {(2+ \ sqrt3) ^ n} (3- \ sqrt3) + \ dfrac ((2- \ sqrt3) ^ n} (3+ \ sqrt3). \]

Parodykime pavyzdinę seka bnkaip veikia funkcijų generavimo metodas. Pirmiausia mes apibrėžiame šios sekos generuojančią funkciją – begalinę formalią formos sumą \ (B (x) = b_0 + b_1x + b_2x ^ 2 + b_3x ^ 3 + \ ldots \). Atkreipkite dėmesį, kad jei jūs padauginsite jį \ ((1-4x + x ^ 2) \) ir išplėskite skliaustus, tai dėl to, kad visi fiziniai n vykdomas santykis \ (b_ (n + 1) = 4b_n-b_ (n-1) \), beveik viskas bus sumažinta:

\ [\ hspace (-50mm) (1-4x + x ^ 2) B (x) \, = \, b_0 + \, b_1x \, + \, b_2x ^ 2 \, + \, b_3x ^ 3 \, + \ , \ ldots \\ hspace (5mm) -4b_0x-4b_1x ^ 2-4b_2x ^ 3- \ ldots \ \ hspace (68mm) + \, \, b_0x ^ 2 \, \, + \, \, b_1x ^ 3 \, + \, \ ldots = b_0 + (b_1-4b_0) x. \]

Taigi, dalijant \ ((1-4x + x ^ 2) \), atsižvelgiant į lygybes b0 = 1 ir b1 = 3 gauname išraišką B(x):

\ [B (x) = \ dfrac (b_0 + (b_1-4b_0) x) (1-4x + x ^ 2) = \ dfrac (1-x) (1-4x + x ^ 2). \]

Nes

\ (1-4x + x ^ 2 = (1- (2+ \ sqrt3) x) (1- (2- \ sqrt3) x) \),

mes galime suskaidyti šią frakciją į paprastesnę sumą:

\ [B (x) = \ dfrac (1) (3 \ sqrt3) \ cdot \ dfrac % (1- (2+ \ sqrt3) x) + \ dfrac (1) (3+ \ sqrt3) \ cdot \ dfrac (1) (1- (2- \ sqrt3) x}. \]

Tada du kartus naudojant geometrinės progresijos sumos formulę,

\ [\ dfrac (1) (1- (2+ \ sqrt3) x) = \ sum \ limits_ (n = 0) ^ (\ infty) (2+ \ sqrt3) ^ nx ^ n \ quad \ mbox (and} \ quad \ dfrac % (1- (2- \ sqrt3) x) = \ sum \ limits_ (n = 0) ^ (\ infty) (2- \ sqrt3) ^ nx ^ n, \]

įsitikinkite, kad generuojanti funkcija B(x) priima norimą formą:

\ [B (x) = \ sum \ limits_ (n = 0) ^ (\ infty) b_nx ^ n = \ sum \ limits_ (n = 0) ^ (\ infty) \ left (\ dfrac {(2+ \ sqrt3 ) ^ n) (3- \ sqrt3) + \ dfrac ((2- \ sqrt3) ^ n) (3 + \ sqrt3) \ teisė) x ^ n. \]

Pav. 5

Negalima apsiriboti klijavimo juostomis ir pabandyti pereiti prie dar daugiau bendrų problemų. Apsvarstykite kai kuriuos prijungtus regionus Γ ant raundo popieriaus. Natūralu būti įdomu, pirma, ar iš esmės galima padaryti Γ domino, ir, antra, jei tai įmanoma, tada kiek keliais būdais. Pirmas dalykas, į kurį reikia prisiminti, yra dažyti juodai baltu raižyto popieriaus, kaip tai atliekama su šachmatininku lentomis, ir apskaičiuoti, kiek ląstelių kokia spalva yra Γ regione. Kadangi kiekviena domino figūra apima dvi skirtingų spalvų ląsteles, mes gauname būtiną sąlygą: jei egzistuoja D domino sluoksnis, tada juodos ir baltos ląstelių skaičius viduje Γ sutampa. Tačiau ši sąlyga nepakankama; Pavyzdys, parodytas fig. 5

Nepaisant to, yra metodai, kurie ne tik atsako į pateiktus klausimus, bet ir tai atliekami polinomialiu laiku (tai reiškia, kad atsakymams į klausimą reikalingų operacijų skaičius priklauso nuo įvesties duomenų dydžio – γ domeno dydžio šiuo atveju – kaip polinomas) tai gana greitai. Mes apibūdinome požiūrį, kuris patenka į olandų fiziką Peterį Casteleyną (Pieter Kasteleyn).Tegul Γ yra domenas n juoda ir n balta ląstelių. Skaičius juos nuo 1 iki 2n kad juodos ląstelės eina pirmiausia ir tada baltas ląsteles, po to mes susiesime regionus Γ su matrica K = (Kuv) dydis 2n×2n pagal šią taisyklę (čia \ (i = \ sqrt (-1) \) yra įsivaizduojamas vienetas):

\ [K_ % = \ left \ (\ begin (array) % 1, \ mbox (jei $ u $ ir $ v $ yra horizontaliosios ląstelės), \ i, & \ mbox (if $ u $ ir $ v $ yra vertikaliai gretimos ląstelės}, \ 0, & \ mbox (priešingai). \ \ end % \ right. \]

Tada pasirodo sąžininga Castellino teorema, teigdamas, kad sumontavimas Γ pagal domino yra \ (\ sqrt (| \ det (K) |) \) (det yra matricos determinantas). Atsižvelgiant į tai, kad tik skirtingų spalvų ląstelės gali būti gretimos ląstelės, lengvai matyti, kad matrica K iš tikrųjų turi blokinį rodinį

\ [K = \ begin (pmatrix) 0 & A \ A ^ (T) & 0 \ end (pmatrix), \]

Pav. 6

kur A – matricos dydis n×nir AT jo perkelta matrica. Todėl tilings skaičius yra \ (\ sqrt (| \ det (A) ^ 2 |) \). Pavyzdžiui, jei Γ yra 2 × 3 stačiakampis, pavaizduotas fig. 6, tada matrica A turi išvaizdą

\ [A = \ begin (pmatrix) 1 & i & 0 \ i & 1 & i \ 0 & i & 1 \ end (pmatrix), \]

ir tilings skaičius yra \ (\ sqrt (| \ det (A) ^ 2 |) = \ det (A) = 3 \).

Plytelių domenų pjovimas į keteros popierių gali būti suprantamas kaip ypatingas atvejis, kai dar reikia daugiau bendros užduotys. Būtent apsvarstykite savavališką grafiką H. Puikus derinys (arba dimerinė pakuotėa) suskaičiuoti H vadinamas bet kokiu jo kraštų rinkiniu, kuriame kiekviena grafiko viršūnė būna lygiai vieną kartą. Akivaizdu, kad jei diagramos viršūnės H tam tikro regiono ląstelės centrai yra ant ramentuotojo popieriaus, o kraštai yra prijungti prie tų, kurių atitinkamos ląstelės yra gretimos, tada klausimas apie tobulų grafo atitikmenų skaičių H tiksliai paverčiamas domino skaičiumi Γ dalių skaičius. Pavyzdžiui, fig. 7 parodyta grafika, atitinkanti regioną Γ iš Fig. 6, taip pat jo tobulas atitikimas.

Pav. 7

Puikus derinimas yra glaudžiai susijęs su medžių spinduliu. Prisiminkite, kad medis vadinamas bet kokiu prijungtu grafiku be ciklų. Jei pateikiama prijungta grafika Gtada jo medis yra medis, kurio viršūnės sutampa su grafiko viršūnėmis G, o kiekvienas kraštas yra grafinis bruožas G. Sužinokite, kaip kiekvienas raktinio žiedo medis G atitiktų tobulą grafiko atitiktį H. Norėdami tai padaryti, darome prielaidą, kad grafikas G – plokščias, tai yra, jis gali būti išdėstytas plokštumoje taip, kad jo kraštai niekaip nesikirstų, išskyrus viršus. Tada plokštuma bus padalinta grafiko kraštais G apie vietoves, vadinamas aspektustarp kurių bus nepertraukiamo dydžio išorinis kraštas. Aptarsime grafiko viršūnių, kraštų ir paviršių rinkinį G raidėmis V, E ir F atitinkamai.

Sukurkite pagal diagramą G nauja, išplėstinė grafika H. Norėdami tai padaryti, pažymėkite viršūnių, kraštų vidurio taškus ir veidų centrus ("veido centras" gali būti laikomas bet kuriuo tašku viduje šio paviršiaus). Tai bus naujosios grafo viršūnės, o kraštai sujungs tokius viršūnių poras, kurių atveju nukrypsta atitinkami pirminio grafiko objektai (pav. 8)

Pav. 8 Korespondencija tarp medžio stulpelio G ir grafiko atitiktį H. Grafų viršūnės G pažymėtas juodi taškai, jo šonkaulių vidurys – balta, o veidų centrai – pilka. Atkreipkite dėmesį, kad patogumui yra išorinis grafiko paviršius G nėra pažymėtas tašku, bet išorinis kontūras

Atkreipkite dėmesį, kad diagramoje H yra tik dviejų tipų kraštai: \ ((\ bar (v), \ bar (e)) \) ir \ ((\ bar (f), \ bar (e)) \), kur \ (v \ in (V } \), \ (e \ in (E) \), \ (f \ in (F) \), ir su brūkšniu žymime atitinkamą grafiko viršūnę H. Viena vertus, iš to išplaukia, kad puikiai derina grafiką H nes garsiąją plokščiųjų grafų Eulerio formulę teigiama, kad \ (| V | – | E | + | F | = 2 \). Kita vertus, matome, kad jį lengva taisyti: pakanka pašalinti iš H dvi formos \ (\ bar (v) \) ir \ (\ bar (f) \) viršūnės kartu su iš jų išeinamais kraštais. Pavyzdžiui, pašalinus viršūnę, atitinkančią išorinį paviršių, taip pat vieną iš formos \ (\ bar (v) \) viršūnių, gauname grafiką H 'kuris jau turi matchings. Dabar, atsižvelgiant į nurodytą grafiką H ' Sukurkite raktą ant raktų G, pakanka pasiimti visus briaunos formos \ ((\ bar (v), \ bar (e)) \), įtrauktus į atitikimą, ir atkreipti juos atitinkančius kraštus e. Atkreipkite dėmesį, kad šis kartografavimas visada bus vienas su vienu, jei norint gauti diagramą H ' mes ištrinsime iš H viršūnių greta viena kitos pagal grafiką G.

Kalbant apie sumaišymo skaičių domino metodu, yra sudaryta sujungtos grafijos be kilpų medžių, kuriomis valdomas matricos determinantas, skaičiaus formulė. Tiksliau, tegul xuv žymi kraštų, jungiančių viršūnių skaičių tu ir v suskaičiuoti G, ir \ (\ deg (v) \) yra viršūnių laipsnis v, tai yra bendras iš jo kylančių kraštų skaičius. Mes apibrėžiame matricą Δ taip:

\ [\ Delta_ (uv) = \ left \ (\ begin (array) (cl) -x_ (uv), & \ mbox (if) \; \; u \ ne (v), \ deg (v), & \ mbox (if) \; \; u = v. \ \ end % \ right. \]

Akivaizdu, kad skaičių kiekvienoje matricos eilutėje Δ yra nulis, taigi ir \ (\ det \ Delta = 0 \). Tačiau paaiškėja, kad norint pasiekti tikslą, pakanka iš matricos pašalinti eilutę ir stulpelį,ir nesvarbu, kas. Būtent, jei mes išbraukti eilutę ir stulpelį, atitinkantį viršūnių tu ir v atitinkamai, o gaunama matrica vadinama \ (\ Delta ^ ((u, v)) \), tada skaičiuojamas medžių skersmuo G lygus \ (| \ det \ Delta ^ ((u, v)) | \). (Tiksliau, medžių skaičiavimas yra lygus bet kokiam matricos algebriniam komplementui Δ). Pavyzdžiui, jei diagramoje G susideda iš penkių viršūnių, sujungtų kraštais, kaip matėme fig. 8, tada jis atitinka matricą

\ [\ Delta = \ begin (pmatrix) 2 & -1 & -1 & 0 & 0 \ -1 & 3 & -1 & -1 & 0 \ -1 & -1 & 3 & 0 & -1 \ \ 0 & -1 & 0 & 2 & -1 \ 0 & 0 & -1 & -1 & 2 \ end (pmatrix), \]

ir pagal pirmiau apibūdintą formulę medžių skaičiavimas yra lygus, tarkim, \ (| \ det \ Delta ^ ((3,2)} | \):

\ [| \ det \ Delta ^ ((3,2)} | = – \ det \ begin (pmatrix) 2 & -1 & 0 & 0 \ -1 & -1 & -1 & 0 \ 0 & 0 & 2 & -1 \ 0 & -1 & -1 & 2 \ end (pmatrix) = 11. \]

Šiuo atveju diagramos skerspjūvių skaičius G lengva apskaičiuoti tiesiogiai. Iš tiesų, šią diagramą sudaro du ciklo ilgio trys ir keturi, atitinkamai. Norint gauti medį, reikia pašalinti iš kiekvieno ciklo vieną kraštą, tačiau pašalinti kraštai turi būti skirtingi. Todėl medžių skaičius yra 3,4 – 1 = 11.

Įdomu tai, kad iš pradžių šis rezultatas, veikiantis su matematinėmis grafikų ir medžių sklaidos koncepcijomis, buvo gautas Vokietijos fiziko Gustavui Kirchhoffui elektros grandinėms.Iš tiesų, elektros grandinę galima žiūrėti kaip grafiką, kurio viršūnės yra grandinės mazgai, o kraštai yra jo šakos. Dabar, jei kraštas jungia viršūnių tu ir v, priskiriamas atitinkamo filialo pasipriešinimas Ruv ir apsvarstykite matricą T = (Tuv) pateiktas

\ [T_ (uv) = \ left \ (\ begin (array) (cl) – \ dfrac (1) (R_ (uv)), & \ mbox (if) \; \; u \ ne (v), \ \ sum \ limits_ (w \ ne (v)) \ dfrac (1) (R_ (vw)}, & \ mbox (if) \; \; u = v, \ \ end % \ teisė. \]

tuomet iš Kirchhoffo įstatymų galima daryti išvadą, kad atsparumas tarp mazgų k ir l lygus \ (\ dfrac (\ det (T_ ((k, l)))) (\ det (T_ ((l))))), kur T(k, l) – matrica, susidaranti išbraukiant eilutes ir stulpelius, atitinkančius mazgus k ir lir T(l) – iš matavimo rezultatas T išbraukiant eilutę ir stulpelį, atitinkantį mazgą l.

Galiausiai pažymime du klasikinius rezultatus, susijusius su įvairių sričių domino domino. Pirma, mes turime pasakyti formulę, tiesiogiai susijusią su mūsų užduotimi, kurioje išreiškiamas dydžio stačiakampio plytelių skaičiaus skaičius. m×n:

\ [\ frac % %]} \ left (4) \ [\ frac % %]} {{\ frac % %]} \ prod \ limits_ (k = 1) \ cos ^ 2 \ frac (\ pi (j)} (m + 1) +4 \ cos ^ 2 \ frac (\ pi (k)) (n + 1) \ right). \]

Pav. 9

Atkreipkite dėmesį, kad jei abu skaičiai yra m ir n yra keista, teisingas atsakymas yra lygus nuliui. Labiausiai tipiškas šios formulės įrodymas yra paremtas pirmiau minėtu Castellino teoremu, tačiau, žinoma, tai neapsiribojama.Antra, neįmanoma paminėti aktekos deimanto užduoties. Azteco deimanto dydis n vadinamas figūra plokštumoje, kurią sudaro ląstelės, kurių centrai atitinka nelygybę \ (| x | + | y ​​| \ leqslant (n) \) (pavyzdžiui, 9 brėžinyje parodytas 4 dydžio aktekos deimantas). Pasirodo, bendras domino kiekis dominuoja Azteco deimantų deimantų n lygus \ (2 ^ (1 + 2 + \ ldots + n) = 2 ^ (n (n + 1) / 2) \). Tipiškos plytelės su dideliu elgesiu n: poliarinio rato teorema teigia, kad viduje apskritimo, užrašyto Azteco deimantų, yra chaotiškas. Tačiau beveik visi domino, esantys už šio rato ribų – deimantų kampuose, bus "užšaldyti": apatiniame ir viršutiniame kampe jie beveik visada bus horizontalūs, o kairėje ir dešinėje – vertikalūs.


Like this post? Please share to your friends:
Parašykite komentarą

;-) :| :x :twisted: :smile: :shock: :sad: :roll: :razz: :oops: :o :mrgreen: :lol: :idea: :grin: :evil: :cry: :cool: :arrow: :???: :?: :!: