Aapo Rantalainen's blog

Experiences with Information Technology and Open source

Matematiikkaa todellisuudesta

Posted by Aapo Rantalainen on September 13, 2011

Edellinen matemaattinen postaus herätti mielenkiintoa, joten jatketaan. Tällä kertaa ei ansoja, vaan esimerkkitapaus kuinka todellisen maailman asioita voi todistaa matemaattisesti. Esimerkkinä toimii peli nimeltään “15”.

1 2 3 4
5 6 7 8
9 10 11 12
13 14 15 @

Ruudukossa on 16 paikkaa ja luvut 1…15, jotka pitäisi saada järjestykseen liikuttamalla niitä vuorollaan tyhjään kohtaan (tyhjää paikka esittää @) . Tapahtuipa viime kesänä, että seurueemme sai pelin käsiinsä, mutta kukaan ei onnistunut sitä ratkaisemaan. Mukana oli niin lapsia kuin aikuisiakin. Kaikki kuitenkin muistelivat, että peli ei ole kovin vaikea. Heräsi siis epäilys, onko pelissä alkutiloja joista peliä ei ole mahdollista ratkaista. Satuimme olemaan tiettömien taipaleiden takana, joten asiaa ei voinut suoriltaan tarkistaa.

Nyt sitten tein taustatyötä ja selvisi, että alunperin peli levisi vuonna 1870 Euroopassa juuri sen takia, että Sam Loyd asetti rahapalkinnon sille, joka ensinnä ratkaisee pelin eräästä hänen valitsemastaan alkutilasta. Jekku oli, että valitusta alkutilanteesta ei voi päästä ratkaisuun.

Kysymys: mistä tietää onko alkutilanne ratkeava vai ei?
(tai yleisemmin, onko olemassa alkutiloja, jotka eivät ole ratkeavia).

Ratkeava tarkoittaa siis alkutilasta sääntöjen mukaisia siirtoja tekemällä pääsyä ratkaistuun tilaan.

Ratkaisu: (Huomautetaan ensin, että nollakin on parillinen luku.)

Määritellään termi epäjärjestys. jonka voi laskea mille tahansa pelin tilalle  (tila on siis se miten laatat ja tyhjä kohta sijaitsevat).
Laske jokaiselle laatalle, kuinka monta sitä isompaa laattaa sen edellä on. Näiden summa on epäjärjestys.


Esimerkki:

3 2 1 4
6 5 7 8
9 10 11 12
13 14 15 @

Tämän tilan epäjärjestys on 4, koska laattaa
* ‘2’ edellä on yksi kpl  (‘3’) sitä isompia.    +1
* ‘1’ edellä on kaksi kpl (‘3’ ja ‘2’) sitä isompia.    +2
* ‘5’ edellä on yksi kpl (‘6’) sitä isompia.    +1
Yhteensä 4.

Esimerkki 2:

1 2 3 4
5 6 7 8
9 10 11 @
13 14 15 12

Tämän tilan epäjärjestys on 3, koska vain laatta ’12’ aiheuttaa epäjärjestystä, sitä edellä ruudukossa on sitä isompia ’13’,’14’ ja ’15’.


On vain yksi tila, jonka epäjärjestys on 0, nimittäin ratkaistu tila.

Kun laattaaa liikutetaan vasemmalle tai oikealle, epäjärjestys ei muutu.

Väite:
Kun tyhjä kohta on ylimmällä tai kolmannella rivillä, niin epäjärjestys on pariton.
Kun tyhjä kohta on tokalla tai neljännellä rivillä, niin epäjärjestys on parillinen.
(nimitetään tätä ominaisuudeksi)

Kun lähtee liikkeelle ratkaistusta tilasta ja siirtelee laattoja sääntöjen mukaan, huomaa että väite pitää koko ajan paikkansa. Tämän voi todistaa matemaattisesti, mutta se ei ole kovin lyhyt todistus, otetaan se siis annettuna.

Väitteestä seuraa: ratkaistusta tilanteesta laillisesti pelaamalla, et pääse tästä ominaisuudesta mitenkään eroon!
Josta seuraa: jos alkutilanteessa tämä ominaisuus ei ole voimassa et voi päästä ratkaistuun tilaan.

Esimerkki 3:

1 2 3 4
5 6 7 8
9 10 11 12
13 15 14 @

(Tämä on Loydsin $1000 ongelma ’15-14′)

Lasketaan epäjärjestys: vain ’14’ kasvattaa epäjärjestystä yhdellä, epäjärjestys on 1.
Tyhjä kohta on neljännellä rivillä. Väitteen mukaan epäjärjestyksen pitäisi olla parillinen.
-> Alkutilanne ei ole ratkeava.


Muita huomioita:
Tila on laillinen tai laitoin.
Mistä tahansa laittomasta tilasta pääsee mihin tahansa toiseen laittomaan tilaan.
Mistä tahansa laillisesta tilasta pääsee mihin tahansa toiseen lailliseen tilaan (joista yksi siis on ratkaistu tila).

Jonka jälkeen voidaankin kysyä minkälaisessa pelissä ja millä säännöillä voisikin olla kolme (tai useampia) tilojen ryhmiä, joiden välillä ei voisi liikkua laillisia sääntöjä tekemällä. Tai: kuinka monta tällaista ryhmää on Rubikin kuutiolla: ota ratkaistu kuutio, ruuvimeisseliä käyttäen irrota yksi kulmapalikka, käännä sitä pykälä vasta- tai myötäpäivään ja napsauta takaisin -> tällaista kuutiota ei voi mitenkään ratkaista laillisia siirtoja tekemällä. Intuitiolla sanoisin, että vasta- ja myötäpäivään käännetyistäkään ei pääse toisiinsa, joten Rubikin kuutiolla on ainakin 3 erillistä tilajoukkoa (jos irrotatkin kaksi kulmaa ja käännät toista myötäpäivään ja toista vastapäivään, niin kuutio on ratkaistavissa).

 

2 Responses to “Matematiikkaa todellisuudesta”

  1. Peliä voi pelata online: http://www.sunshine2k.de/stuff/Java/15puzzle/15Puzzle.html
    Peli näyttää ‘epäjärjestyksen’, kohdassa ‘Parity’, sellaisella erolla, että siihen on laskettu tyhjän kohdan rivin mukaan:

    ensimmäinen ja kolmas rivi +1
    toinen ja neljäs rivi +0

    Tällöin parityn parillisuus tarkoittaa ratkeavaa, ja parittomuus ratkeamatonta.

  2. Laskon said

    Olen nähnyt saman pelin mutta kuvan numeroiden sijasta

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

 
%d bloggers like this: