Tässä olisi pieni pelikorttitehtävä ratkottavaksi.
Herra Kusti Ritonen ”sekoittaa” tavallisen 52 kortin pakan uudeksi pakaksi laittamalla joka toisen kortin alkuperäisestä pakasta pakan päälle ja joka toisen taas pakan alle. Näin saadussa sekoitetussa pakassa on siis alkuperäisen pakan ensimmäinen kortti 27., toinen kortti 26., kolmas kortti 28., neljäs kortti 25.,…, toiseksi viimeinen kortti viimeisenä ja viimeinen kortti ensimmäisenä. Montako kertaa Kustin pitää tällä tavalla sekoittaa pakka, jotta se olisi taas alkuperäisessä järjestyksessä? Entä pääseekö hänen tyttöystävänsä Kata Pakkonen samasta tehtävästä helpommalla, kun hänen korttipakastaan puuttuu kaksi korttia?
Herra Kusti Ritonen ”sekoittaa” tavallisen 52 kortin pakan uudeksi pakaksi laittamalla joka toisen kortin alkuperäisestä pakasta pakan päälle ja joka toisen taas pakan alle. Näin saadussa sekoitetussa pakassa on siis alkuperäisen pakan ensimmäinen kortti 27., toinen kortti 26., kolmas kortti 28., neljäs kortti 25.,…, toiseksi viimeinen kortti viimeisenä ja viimeinen kortti ensimmäisenä. Montako kertaa Kustin pitää tällä tavalla sekoittaa pakka, jotta se olisi taas alkuperäisessä järjestyksessä? Entä pääseekö hänen tyttöystävänsä Kata Pakkonen samasta tehtävästä helpommalla, kun hänen korttipakastaan puuttuu kaksi korttia?
Vastaukset 4
Vanhimmat
Korttien sekoittaminen voidaan kuvata diskreettiaikaisena dynaamisena järjestelmänä
x(i 1)=Ax(i),
jossa x(i) on (pysty)vektori, joka sisältää korttien järjestyksen i:n sekoituskerran jälkeen, A on matriisi, joka kuvaa sekoituksen vaikutuksen pakkaan (jokaisella rivillä ja sarakkeessa on tasan yksi ykkönen, muut alkiot ovat nollia). Alkutilassa x(0) voisi olla esimerkiksi [1 2 3 ... 52]. Kortit on siis numeroitu (älkää yrittäkö tätä ammattipelurien kanssa :) ja kortin k sijainti pakassa nähdään sen sijainnista vektorissa x.
esim. kolmen kortin pakka:
x(0)=[1 2 3]
A=
|0 1 0| -> toinen kortti päätyy pakan päälle
|1 0 0| -> ensimmäinen kortti keskelle
|0 0 1| -> kolmas kortti pysyy pohjalla
x(1)=Ax(0)=[2 1 3]
x(2)=Ax(1)=AAx(0)=[1 2 3]
Siis kolmen kortin pakalle riittää kaksi sekoituskertaa, jotta se palaa alkuperäiseen järjestykseen.
Yleisemmin jos matriisi A korotetaan n:teen potenssiin ja tuloksena on yksikkömatriisi, palaa pakka alkuperäiseen järjestykseen n:llä sekoituskerralla.
Tarvittavien sekoituskertojen määrä saadaan siis ratkaisemalla seuraava tehtävä.
"Etsi pienin nollaa suurempi n,
jolla A^n on yksikkömatriisi."
Mutta mites tuo ratkaistaan analyyttisesti? Kompuutterillahan homma menee helposti numeerisesti kokeilemalla eri n:n arvoja (kerrotaan A:ta itsellään kunnes tulee yksikkömatriisi vastaan). Tai jos ei jaksa viritellä tuota matriisia, sekoitusrutiini mielivaltaisen määrän kortteja sisältävälle pakalle on helppo koodata melkein millä tahansa ohjelmointikielellä.
Kusti ottaa korttien sekoitukseen avuksi kolikon ja ryhtyy sekoittamaan pakkaa siten, että jokaisen kortin kohdalla suoritetaan arvonta laitetaanko se pakan päälle vaiko pakan alle. Todennäköisyydet 0,5 molemmille vaihtoehdoille. Eli alkuperäisen pakan ensimmäinen kortti päätyy uuteen pakkaan paikkaan p, toinen kortti päätyy joko paikkaan p-1 tai p 1 ... viimeinen kortti päätyy joko uuden pakan alle tai päälle. Edellä oleva p:n arvo siis riippuu siitä miten myöhemmin siirrettävät kortit jakautuvat "päälle" ja "alle".
Mikä on odotusarvo sekoituskertojen lukumäärälle, jolla pakka palaa alkuperäiseen järjestykseen?
Itse olen tutkinut ilmiön tuloksia lähinnä tietokoneen avulla tekemällä sekoitusta simuloivan ohjelman Exceliin. Tuloksista olen havainnut, että korttien sekoituskertojen määrä a riippuu korttien määrästä n seuraavasti: (lg n/lg 2) 1
Kun kortteja on 10, sekoitusmatriisi on
|0 0 0 0 0 0 0 0 0 1|
|0 0 0 0 0 0 0 1 0 0|
|0 0 0 0 0 1 0 0 0 0|
|0 0 0 1 0 0 0 0 0 0|
|0 1 0 0 0 0 0 0 0 0|
|1 0 0 0 0 0 0 0 0 0|
|0 0 1 0 0 0 0 0 0 0|
|0 0 0 0 1 0 0 0 0 0|
|0 0 0 0 0 0 1 0 0 0|
|0 0 0 0 0 0 0 0 1 0|
Matriisilla on varsin säännöllinen rakenne: ykkösiä nauhoina vasemman reunan puolesta välistä oikean reunan nurkkiin. Sekoitussäännön mukaisesti ykköset ovat (oikealle päin liikuttaessa) vuorotellen matriisin ylä- ja alapuoliskoissa.
Lisäksi kasaamalla matriisi parittomalle määrälle kortteja huomataan, että oikeaan alanurkkaan tulee aina ykkönen, jolloin pakan alimmainen kortti pysyy aina alimmaisena eikä siis "sekoitu" ollenkaan. Muiden korttien sekoittumiseen tämä ylimääräinen kortti ei vaikuta. Voidaan siis tarkastella ainoastaan parillisia korttimääriä.
Nyt ensimmäisen sekoituksen jälkeen päälimmäinen kortti päätyy paikkaan n/2 1. Eli suunnilleen pakan keskelle. Matriisin rakenteesta huomataan, että pakan keskeltä kortti siirtyy puolta lähemmäksi pakan reunaa (pohjaa tai huippua). Ja vastaavasti etäisyys reunaan puolittuu jokaisella sekoituksella.
Alkuperäisen pakan päälimmäinen kortti palaa siis pakan päälimmäiseksi aikaisintaan log_2 n (2-kantainen logaritmi) sekoituskerralla ensimmäinen sekoitus. Tämähän oli se havaitsemasi alaraja sekoituskertojen määrälle.
Jos ykköskortti ei osukaan ihan pakan päälle (vaan esim pohjalle tai toiseksi) palaa se takaisin pakan keskikohdan tuntumaan ja aloittaa uuden lähestymisen.
Tässä nyt tarkasteltiin vain yhtä korttia, joten kaikkien muidenkin korttien pitää vielä osua oikeille paikoilleen samalla sekoituskertojen määrällä. Mutta jonkinlainen alaraja-analyysi se sekoituskertojen määrälle kuitenkin on.
Se miten todistetaan, miksi sekoituskertoja tarvitaan korkeintaan n jää pohdinnan alle.
Jos log_2 n ei ole kokonaisluku, voidaanko desimaaliosasta, tai määrästä, jolla n ylittää lähimmän n:ää pienemmän kahden potenssin jotenkin päätellä montako kertaa päälimmäinen kortti palaa pakan keskiosan tuntumaan?
Jos pakan ensimmäinen kortti on palannut alkuperäiselle paikalleen, voivatko muut kortit olla väärillä paikoilla? Vai riittääkö tarkastella yhden kortin liikkeitä pakassa.
Tämä oli aika heuristista heittelyä, mutta ehkä noilta linjoilta pääsee vielä eteenpäin.