Kaikki tuntevat pelin, missä siirrellään neliön muotoisella pelialustalla laattoja liu'uttamalla yrittäen saada laatat numerojärjestykseen. Pelilauta on siis esim
123
456
78T
missä T on tyhjä ruutu mihin voi siirtää kutosen tai kasin. En nyt muista pelin nimeä, mutta sillä ei ole väliä.
Kysymys kuuluu, että ratkeaako x*x kokoinen peli kaikista mahdollisista alkuasetelmista? Jos ei, niin kuinka monesta ratkeaa ja kuinka monta erilaista alkuasetelmaa voi siinä mielessä olla, että mistään ei voi järjestää palikoita toiseen?
Tehtävä on yksinkertainen kun sen hoksaa, joten tietävämmiltä hieman malttia :)
123
456
78T
missä T on tyhjä ruutu mihin voi siirtää kutosen tai kasin. En nyt muista pelin nimeä, mutta sillä ei ole väliä.
Kysymys kuuluu, että ratkeaako x*x kokoinen peli kaikista mahdollisista alkuasetelmista? Jos ei, niin kuinka monesta ratkeaa ja kuinka monta erilaista alkuasetelmaa voi siinä mielessä olla, että mistään ei voi järjestää palikoita toiseen?
Tehtävä on yksinkertainen kun sen hoksaa, joten tietävämmiltä hieman malttia :)
Vastaukset 8
Vanhimmat
Et kerro, mitä tarkoitat pelin ratkeamisella.
Ajattelin tuon olevan tuttu, mutta joo.
Peli ratkeaa jos nappulat voi järjestellä ennalta sovittuun järjestykseen laudalla. Yleensä tämä järjestys on suuruusjärjestys riveittäin, eli esimerkkini on ratkenneessa tilassa.
Peli ratkeaa arvotusta alkuasetelmasta 50% todennäköisyydellä. Toinen 50% johtaa lopputilanteeseen:
123
456
87T
Alkuasetelmien määrä voidaan laskea hyvin yksinkertaisesti: 9!. Ratkaistavissa olevien alkuasetelmien määrä / kaikki on siis:
181440 / 362880.
Olenko oikeassa? ;-)
Kyseessä oli yleisesti n*n pelilaudasta, mutta 3*3 laudalla tosiaan alkutiloja on 9!.
En ymmärrä mitä olet laskenut ja miten? Millä perustein 50% johtaa mainitsemaasi lopputilanteeseen?
Luin tosiaan kysymyksen vähän turhan nopeasti. Alkuasetelmien määrä n*n pelilaudalla on tietysti siis (n*n)! kpl.
Siitä en ole varma, voiko yleisellä n*n laudalla kaikki alkuasetelmat ratketa, mutta sen olen itse havainnut 3*3 laudalla, että asetelmasta
123
456
87T
ei voi järjestää numeroita järjestykseen
123
456
78T
Tämä aiheutuu siitä, että numeroiden järjestelyssä _parillinen_ määrä numeroita vaihtaa paikkaansa. Siis jos alimman rivin järjestää, myös keskimmäiseltä riviltä siirtyy yksi numero toiseen paikkaan (7/8 ja 5/6)
123 - 123
456 - 465
87T - 78T
Todistukseni on siis vielä puutteellinen, mutta jos joku osaa todistaa sen, että yleisellä n*n laudalla numeroiden järjestelyssä siirtyy aina _parillinen_ määrä numeroita uussiin paikkoihin, niin silloin todistus on täydellinen.
Jos taas voidaan osoittaa, että n*n laudalla _pariton_ määrä numeroita voi vaihtaa paikkoja keskenään, niin silloin kaikki alkuasetelmat voidaan järjestää lopulta oikeaan järjestykseen.
Vastaus on oikea, mutta vaatisi vähän lisää perusteluita kuten itsekin totesit. Ajattele pelilautaa suorana lukuja ja mieti miten yhden laatan liikkeellä voit numeroiden paikkoja vaihdella. Vinkkinä voisin sanoa permutaatiot ja niiden parillisuuden.
Entä sitten, jos n yli k:n on n yli n-k:n.
Jos ajatellaan 3x3 pelilautaa, niin se voidaan esittää jonona 1,2,3,4,5,6,7,8,0 missä 0 kuvaa tyhjää paikkaa ja nyt tuo jono on "ratkaistussa" tilassa (ylärivi vasemmalta 1, 2 ja 3, keskirivi vasemmalta 4, 5 ja 6 ja alarivi samoin 7, 8 ja tyhjä). Jos siirrämme kasia vaikka oikealle, niin jono tulee muotoon (A) 1,2,3,4,5,6,7,0,8 ja vitsi on siinä, että tämä on jonolle 1,2,3,4,5,6,7,8 sama permutaatio kuin tuo aiempikin, kun nollaa ei huomioida.
Jos olisimme siirtäneet muodosta (A) viitosen alas saisimme jonon 1,2,3,4,0,6,7,5,8 joka vastaisi tilannetta, jossa on ensin vaihdettu ensin 5 ja 6, sitten 5 ja 7, eli tarkastaeltaessa pelkästään alkioita, joissa nolla ei ole mukana, niin huomataan siirron vastaavan aina sen jonon parillista permutaatiota, eli tasaa puolta mahdollisista tapauksista. Käymällä eri vaihtoehdot läpi yleisellä laudalla tuosta pitäisi tulla suht helposti todistus.