Invariandid

Invariant on suurus, mida ükski lubatud käik ei muuda. Nihuta nupumängu, lõika laualt ruute või lisa Königsbergi sildu – leht hoiab invarianti pidevalt nähtaval. Selleks on kas inversioonide arvu paarsus, mustade ja valgete ruutude vahe või paaritu arvu sildadega maamassiivide hulk. Kui invariant on alg- ja lõppseisus erinev, ei vii eesmärgini ükski käikude jada.

Näidisarvutus — Invariandid

Inversioonid	1
Invariant: inversioonid mod 2	paaritu
Käike lahenduseni	saavutamatu

Need on väärtused, mida kalkulaator lehe avamisel näitab. Muuda ülal mõnda sisendit, et need ümber arvutada.

Interaktiivse simulatsiooni laadimine...

Õppetund

Teooria — Invariandid

Invariant on suurus, mida ükski lubatud käik ei muuda. Kui selle väärtus on alguses üks ja lõpus teine, ei saa eesmärgini kuidagi jõuda. Selle teadmiseks ei pea ühtki lahenduskäiku läbi proovima.

Mida iga sümbol tähendab

I: invariant: siin inversioonide arvu paarsus, mustade ja valgete ruutude arvu vahe või paaritu arvu sildadega maamassiivide hulk
d(v): maamassiivi v aste: mitu silda sinna viib

Kust valem tuleb

Miks nupu nihutamine säilitab paarsuse? Loe kaheksa nuppu reastikku üle, jättes tühimiku vahele. Rõhtne lüke ei muuda seda lugemisjärjekorda üldse. Püstine lüke liigutab üht nuppu jadas kolme koha võrra, möödudes kahest nupust vana ja uue ruudu vahel. Mõlemad paarid kas saavad juurde ühe inversiooni või kaotavad selle. Seega muutub inversioonide arv −2, 0 või +2 võrra, aga mitte iial paaritu arvu võrra. Lahendatud seisus on see arv 0. Paaritut arvu inversioone andvasse seisu pole seega võimalik jõuda. Raskem osa on tõestada, et igasse paarisarvuga seisu saab alati jõuda. 8-mängu puhul näitab meie lehe otsing seda vahetult.
Miks doomino säilitab ruutude vahe? Malelaual on iga ruudu naabrid teist värvi. Seetõttu katab kahele naaberruudule paigutatud doomino alati ühe musta ja ühe valge ruudu. Kivi asetamine ei muuda seega kunagi katmata mustade ja valgete ruutude arvu vahet. Lõpetatud katmine ei jäta ühtki ruutu vabaks, mis tähendab, et vahe on 0. Järelikult peab see vahe olema 0 juba alguses: üht värvi ruute peab olema täpselt sama palju kui teist värvi ruute.
Miks on ülimalt kaks paaritut maamassiivi? Jälgi teekonda. Iga kord, kui see maamassiivi läbib, saabutakse ühe ja lahkutakse teise silla kaudu. Sildu kasutatakse paaridena kõikjal, välja arvatud alguses, kus üht silda kasutatakse vaid lahkumiseks, ja lõpus, kus üht silda kasutatakse vaid saabumiseks. Kui teekond lõpeb samas kohas, kus algas, on igal maamassiivil paarisarv sildu. Vastasel juhul on paaritu arv sildu täpselt alguses ja lõpus. Vastupidine väide kehtib samuti, kui sillad ühendavad kõike omavahel, ja meie leht leiab selle teekonna, ehitades selle kinnistest ringidest ja need omavahel kokku liites.

3 × 3 liugmõistatuse pooli seise pole kunagi võimalik saavutada ja sa saad ilma otsimata öelda, milliseid 🖖

Vajuta nupule 7 ja 8 vahetatud ja proovi mäng lahendada. Loe reastikku üle vales järjekorras olevad nupupaarid. Siin on neid üks, sest 8 asub 7 ees. Rõhtne lüke jätab selle arvu samaks. Püstine lüke viib ühe nupu kahest teisest mööda, mis muudab inversioonide arvu 0 või 2 võrra. Nii jääbki paaritu arv alatiseks paarituks, kuid lahendatud seisus on see 0. Leht otsis läbi kõik lahendatud seisust tulenevad positsioonid. 362 880 paigutusest on saavutatavad 181 440 – täpselt need, mille inversioonide arv on paaris. Kaks kõige kaugemat seisu vajavad 31 käiku. 15-mäng vallutas 1880. aastal Ameerika. 1890. aastatel pakkus Sam Loyd 1000 dollarit sellele, kes suudab 14 ja 15 tagasi õigesse järjekorda viia. Seda auhinda ei saanud mitte keegi kunagi võita.

Lõika malelaualt kaks vastasnurka ja doominotega katmine muutub võimatuks 🖖

Vajuta nupule Vastasnurgad. Tervet lauda saab 32 doominokiviga katta 12 988 816 viisil. Lõika kaks vastasnurka välja ja lauda ei saa enam üldse katta. Mõlemad nurgad on sama värvi, mis jätab üht värvi ruute järele 30 ja teist 32, ent iga doomino katab ühe mõlemast. Lõika selle asemel välja ühe serva kaks nurka, mis on eri värvi, ja laua katmiseks on 2 436 304 viisi. Nüüd vajuta nupule Eraldatud nurk. Värvid on ideaalses tasakaalus, 30 ja 30, aga lahendusi ikka pole, sest nurgaruudul puudub naaber. Värvide loendamine suudab tõestada, et katmine on võimatu. See ei suuda aga iial tõestada vastupidist.

Königsbergi teekonna võimatust saab tõestada peastarvutusega 🖖

Vajuta nupule Königsberg. Saarel on 5 silda ning kolmel ülejäänud maamassiivil igal ühel 3. Teekond, mis läbib igat silda täpselt korra, saabub maamassiivile ja lahkub sealt, kasutades sildu paaridena. Üle jääda saab sild vaid seal, kus teekond algab ja kus see lõpeb. Järelikult tohib paaritu arv sildu olla ülimalt kahel maamassiivil, kuid siin on see kõigil neljal. Euler tõestas selle oma 1735. aastal kirjutatud artiklis. Lisa B–C kõrval oleva + nupuga kahe kalda vahele üks sild. Järele jääb kaks paaritu arvuga maamassiivi ja leht leiab teekonna punktist A punkti D. Nende nelja arvu summa on alati sildade arvust kaks korda suurem, mistõttu esinevad paaritud arvud alati paaridena.

Ülesanne täielikult lahendatud

Kas keegi sai võita Sam Loydi 1000 dollarit? 4 sammu
Vaheta 4 × 4 laual ainult 14 ja 15 ning jäta tühimik nurka. Sam Loyd pakkus 1000 dollarit igaühele, kes suudab selle tagasi algseisu nihutada. Kas see on võimalik?

Ava see ülesanne tööriistas
1. Selle lehe 3 × 3 laual oli invariandiks inversioonide arvu paarsus:
  
  $3 wide: a vertical slide passes 2 tiles \Rightarrow Δ I \in {- 2, 0, + 2}$
2. Nelja ruudu laiusel laual viib püstine lüke ühe nupu kolmest teisest mööda. Nii muutub inversioonide arv paaritu arvu võrra ja tühimik vahetab rida:
  
  $4 wide: a vertical slide passes 3 tiles \Rightarrow Δ I \in {- 3, - 1, + 1, + 3}, Δ row = \pm 1$
3. Iga lüke pöörab ümber mõlemad paarsused või ei pööra kumbagi. Nende summa, võetuna mod 2, ei muutu kunagi:
  
  $I + row of the blank (mod 2) never changes$
4. Võrdle neid kaht seisu, kus tühimik on mõlemas 4. reas:
  
  $solved: 0 + 4 = 4 (even), 14 \leftrightarrow 15 : 1 + 4 = 5 (odd)$
Vastus

Keegi ei saanud seda võita: see nupuvahetus jääb invariandi valele poolele. Lahendatud seisust on võimalik jõuda täpselt pooltesse 16! paigutusest ehk 10 461 394 944 000 seisuni. Vajuta nupule 7 ja 8 vahetatud, et näha sama lõksu 3 × 3 laual.

$unreachable; \frac{16 !}{2} = 10, 461, 394, 944, 000 arrangements can be reached$

Õpitee

Tõestusmeetodid

Allikad (3)

The parity argument for the 15-puzzle, the history (made in upstate New York in the 1870s, a craze in early 1880, analysed in the American Journal of Mathematics that year) and Sam Loyd's later $1,000 prize for a swap that cannot be done: K. Conrad, "The 15-Puzzle (and Rubik's Cube)", expository notes, University of Connecticut.
Euler's paper on the seven bridges of Königsberg, which reduced the walk to the number of bridges at each land mass: L. Euler, "Solutio problematis ad geometriam situs pertinentis", Commentarii academiae scientiarum Petropolitanae 8, 128–140 (written 1735, published 1741); Eneström number E53, The Euler Archive.
The number of domino tilings of square boards, with 12,988,816 for the 8 × 8 chessboard: OEIS Foundation, "A004003: Number of domino tilings (or dimer coverings) of a 2n X 2n square", The On-Line Encyclopedia of Integer Sequences.

42Mathi meeskond · Kontrollitud avaldatud allikate põhjal. Parandused on teretulnud.