Pelataan yksinkertaista pasianssia tavallisella 13x4 korttipakalla. Ässä on 1 ja kuningas 13. Sanotaan numeroita järjestyksessä yhdestä kolmeentoista (neljä kertaa). Jokaisen numeron jälkeen otetaan yksi kortti pois pakasta. Jos kortin numero on sama kuin sanottu numero, peli päättyy. Tavoitteena on käydä läpi kaikki 52 korttia.
Pelataan ohjelmalla ensimmäiset 13 korttia kaikilla mahdollisilla erilailaisilla korttipakan kombinaatioilla. Montako pelin pelaamisen jatkamisen kannalta aidosti erilaista 13 pois otetun kortin kombinaatiota voi olla? Ajatelkaa asiaa ihan tyhmän ohjelman kannalta.
Montako 26 pois otetun kortin kombinaatiota ja montako 39 pois otetun 39 kortin kombinaatiota?
Laskenta onnistuu myös ihan kynällä ja ruutupaperilla. Riittää hallita pienten (5 järjestelmän) numeroiden yhteenlasku.
Kun todellisten kombinaatioiden äärimmäisen vähäinen määrä on selvillä, niin on helppo tehdä ohjelma, joka laskee muutamassa minuutissa voitollisten pelien tarkan määrän kaikilla mahdollisilla erilailaisilla (52!/4x3x2x1)^13 kpl ) korttipakan kombinaatioilla .
Pelataan ohjelmalla ensimmäiset 13 korttia kaikilla mahdollisilla erilailaisilla korttipakan kombinaatioilla. Montako pelin pelaamisen jatkamisen kannalta aidosti erilaista 13 pois otetun kortin kombinaatiota voi olla? Ajatelkaa asiaa ihan tyhmän ohjelman kannalta.
Montako 26 pois otetun kortin kombinaatiota ja montako 39 pois otetun 39 kortin kombinaatiota?
Laskenta onnistuu myös ihan kynällä ja ruutupaperilla. Riittää hallita pienten (5 järjestelmän) numeroiden yhteenlasku.
Kun todellisten kombinaatioiden äärimmäisen vähäinen määrä on selvillä, niin on helppo tehdä ohjelma, joka laskee muutamassa minuutissa voitollisten pelien tarkan määrän kaikilla mahdollisilla erilailaisilla (52!/4x3x2x1)^13 kpl ) korttipakan kombinaatioilla .
Vastaukset 37
Vanhimmat
13 (ja 39) 39 kpl. 26 korttia 104 kpl.
Pelattu 13 korttia:
[0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 4, 4, 4] 2860
[0, 0, 0, 0, 0, 0, 0, 0, 0, 2, 3, 4, 4] 8580
[0, 0, 0, 0, 0, 0, 0, 0, 0, 3, 3, 3, 4] 2860
[0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 3, 4, 4] 38610
[0, 0, 0, 0, 0, 0, 0, 0, 1, 2, 2, 4, 4] 38610
[0, 0, 0, 0, 0, 0, 0, 0, 1, 2, 3, 3, 4] 77220
[0, 0, 0, 0, 0, 0, 0, 0, 1, 3, 3, 3, 3] 6435
[0, 0, 0, 0, 0, 0, 0, 0, 2, 2, 2, 3, 4] 25740
[0, 0, 0, 0, 0, 0, 0, 0, 2, 2, 3, 3, 3] 12870
[0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 2, 4, 4] 102960
[0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 3, 3, 4] 102960
[0, 0, 0, 0, 0, 0, 0, 1, 1, 2, 2, 3, 4] 308880
[0, 0, 0, 0, 0, 0, 0, 1, 1, 2, 3, 3, 3] 102960
[0, 0, 0, 0, 0, 0, 0, 1, 2, 2, 2, 2, 4] 51480
[0, 0, 0, 0, 0, 0, 0, 1, 2, 2, 2, 3, 3] 102960
[0, 0, 0, 0, 0, 0, 0, 2, 2, 2, 2, 2, 3] 10296
[0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 4, 4] 36036
[0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 2, 3, 4] 360360
[0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 3, 3, 3] 60060
[0, 0, 0, 0, 0, 0, 1, 1, 1, 2, 2, 2, 4] 240240
[0, 0, 0, 0, 0, 0, 1, 1, 1, 2, 2, 3, 3] 360360
[0, 0, 0, 0, 0, 0, 1, 1, 2, 2, 2, 2, 3] 180180
[0, 0, 0, 0, 0, 0, 1, 2, 2, 2, 2, 2, 2] 12012
[0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 3, 4] 72072
[0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 2, 2, 4] 216216
[0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 2, 3, 3] 216216
[0, 0, 0, 0, 0, 1, 1, 1, 1, 2, 2, 2, 3] 360360
[0, 0, 0, 0, 0, 1, 1, 1, 2, 2, 2, 2, 2] 72072
[0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 2, 4] 51480
[0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 3, 3] 25740
[0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 2, 2, 3] 180180
[0, 0, 0, 0, 1, 1, 1, 1, 1, 2, 2, 2, 2] 90090
[0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 4] 2860
[0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 2, 3] 25740
[0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 2, 2, 2] 34320
[0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 3] 858
[0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 2] 4290
[0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2] 156
[1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] 1
Oikeanpuolenen numero on kertoo monessako eri järjestyksessä eri numeroisten korttien määrät voivat esiintyä. Järjestyksellä ei mitään merkitystä pelaamisen kannalta.
Kaikkien voittopelien määrän laskenta 9x4 pakalla sujui tyhmällä ohjelmalla hetkessä. Isompien pakkojen laskenta vaatii paljon optimointia muistin käytön ja suorituskyvyn suhteen.
Kaikki 13x4 korttipakan erilaiset kombinaatiot läpikäymällä voittoja tulee
1493804444499093354916284290188948031229880469556 kpl. Huomioimalla kaikki helposti havaittavat symmetriset tilanteet, säästöä näyttäsi tulleen ainakin triljoona triljoonaa kertainen määrä.
Alla olevassa taulukosssa on kaikki vielä läpikäytävät korttien määrien kombinaatiot ja niiden esintymiskerrat 39 kortin jälkeen. Tuon taulukon listojen läpikäymiseen menee aikaa enää sekunnin murto-osa. Python ohjelma kannattaa ajaa uusimmalla (V6) Pypy:llä. Yli 10 kertainen nopeutus. Ja korttien määrät osoitavat listat kannattaa lajitella reverse=True (suurimmat vasemmalle). Moninkertainen nopeutus. C-kielisellä ohjelmalla todennäköisti suoritusjan saisi putoamaan reiluun minuuttiin. Kokeilkaa. Nyt hiukan yli 5 min yhdellä prosessilla. Muistia tarvittiin vain n. 3 Gtavua. Yksi iso Python-lista.
[[4,4,4,4,4,4,4,4,4,3,0,0,0],162619168241049638202921555131212800],
[[4,4,4,4,4,4,4,4,4,2,1,0,0],1469615458183538590217433684954009600],
[[4,4,4,4,4,4,4,4,3,3,1,0,0],8837602611034901092926520364475494400],
[[4,4,4,4,4,4,4,4,3,2,2,0,0],13284566627137577977610769442151673600],
[[4,4,4,4,4,4,4,3,3,3,2,0,0],47340725176190039821024603102461964800],
[[4,4,4,4,4,4,3,3,3,3,3,0,0],22142263587657674776044303102545016000],
[[4,4,4,4,4,4,4,4,4,1,1,1,0],981705321742978993450928551731417600],
[[4,4,4,4,4,4,4,4,3,2,1,1,0],53244716511724893370462672258100467200],
[[4,4,4,4,4,4,4,3,3,3,1,1,0],94871173261677386736024138245326156800],
[[4,4,4,4,4,4,4,4,2,2,2,1,0],26678943633497360265849844207497945600],
[[4,4,4,4,4,4,4,3,3,2,2,1,0],427827944360611606442537244161772748800],
[[4,4,4,4,4,4,3,3,3,3,2,1,0],667014835670455220035573696950320380800],
[[4,4,4,4,4,3,3,3,3,3,3,1,0],178272899967974066454548595303681624000],
[[4,4,4,4,4,4,4,3,2,2,2,2,0],107184442115926406174704176557562220800],
[[4,4,4,4,4,4,3,3,3,2,2,2,0],668433713261461370798735011184292960000],
[[4,4,4,4,4,3,3,3,3,3,2,2,0],803935030222979908001416414742750314560],
[[4,4,4,4,3,3,3,3,3,3,3,2,0],255794996027687291008004817341309053440],
[[4,4,4,3,3,3,3,3,3,3,3,3,0],18990666459228062603880263441050483200],
[[4,4,4,4,4,4,4,4,3,1,1,1,1],8891900559604637150032016475470755200],
[[4,4,4,4,4,4,4,4,2,2,1,1,1],26732413445480975592677038025188684800],
[[4,4,4,4,4,4,4,3,3,2,1,1,1],285790417068091481523521244097011014400],
[[4,4,4,4,4,4,3,3,3,3,1,1,1],222784127595485295243719636315078884800],
[[4,4,4,4,4,4,4,3,2,2,2,1,1],429597483130863650478877685314735104000],
[[4,4,4,4,4,4,3,3,3,2,2,1,1],2009323297629392596520945061178183190400],
[[4,4,4,4,4,3,3,3,3,3,2,1,1],1611095934966412158968893988892701287680],
[[4,4,4,4,3,3,3,3,3,3,3,1,1],256308336699877281906966600402806741760],
[[4,4,4,4,4,4,4,2,2,2,2,2,1],64576726694983064394809860237218184320],
[[4,4,4,4,4,4,3,3,2,2,2,2,1],1510199704279490138699578611781529966400],
[[4,4,4,4,4,3,3,3,3,2,2,2,1],4036314202888694278116864924214609219200],
[[4,4,4,4,3,3,3,3,3,3,2,2,1],2696968320511901261712141316841157137760],
[[4,4,4,3,3,3,3,3,3,3,3,2,1],514871633373255828360143702822982380400],
[[4,4,3,3,3,3,3,3,3,3,3,3,1],22935021753906645064841222204814608364],
[[4,4,4,4,4,4,3,2,2,2,2,2,2],151341457489240501693285247400311603520],
[[4,4,4,4,4,3,3,3,2,2,2,2,2],1213472699755560096638869521794783306880],
[[4,4,4,4,3,3,3,3,3,2,2,2,2],2027034574103322266839025770662740418240],
[[4,4,4,3,3,3,3,3,3,3,2,2,2],1031937197397516267339547131827113061280],
[[4,4,3,3,3,3,3,3,3,3,3,2,2],172379249397952806094162635448799897760],
[[4,3,3,3,3,3,3,3,3,3,3,3,2],8376725473832445454591610717446248204],
[[3,3,3,3,3,3,3,3,3,3,3,3,3],71758270419238519410206261793581136]
1493804444499093354916284290188948031229880469556
Laskemasi voittomäärä on oikea. Kaikki mahdottomina pidetyt laskut muuttuvat ajan myötä helpoiksi kotitehtäviksi! Aloitin itse ratkomaan ongelmaa aluksi ihan vaan 3x2 pakalla. Kasvattamalla pakkaa laskentaa muuttui nopeasti mahdottomaksi. Aina löytyi kuitenkin yksinkertaisia tapoja nopeuttaa laskemista. Alussa 13x2 pakkaan kuli yli vuorokausi ja 6x4 pakkaan tunteja.
13x4 pakan laskenta-ajan saisi Python ohjelmalla helposti viidesosaan 8 ytimisellä 32 Gtavuisella kotikoneellakin ajamalla noita listoja rinnakkain. Ei kannattane, sillä laskentaan löytyy myös valmis vaikeahko kaava. Pitää joskus yrittää soveltaa kaavaa Python ohjelmassa. Ehkä oppii taas jotain uutta.
Täysin mahdoton lasku, jos ei huomaa yhdistää varmasti samanlaisia vaihtoehtoja. Jos lähdetään ihan alusta, niin ensimmäinen kortti voi olla 2...13. Voi olettaa sen olevan 2. Muista tulee tietysti ihan sama tulos. Kerroin 12. Toinen kortti voi olla 1 tai 3...13. Riittää laskea ykkösellä erikseen ja sitten vain kolmosella. Lopuista 11 tulee sama tulos. Kokonaiskerroin jälkimmäisessä tapauksessa jo 131. Näin voi jatkaa joka kortin kohdalla koko ensimmäisen 13 kortin kierroksen. Kertoimet kasvavat mieletömiksi ja homma sujuu hetkessä.
Samaa menetelmää voi soveltaa samalla tavalla kolmella muullakin 13 kortin kerroksella. Pitää pitää kirjaa koko ajan erinumeroisten korttien lukumääristä. Jos aidosti peräkkäiset lukumäärät ovat samoja, riittää laskea vain se eka tapaus. Helppo todeta parilla vertailulauseella.
Koodia kannattaa optimoida siten, että viimeisessä silmukassa on vain yksi käsky. Ja sen viimeiseen silmukan voi tietysti vielä poistaa ja laittaa sen 12 käskyä peräkkäin ja purkaa hitaita indeksointeja. Tästä ajasta suurin osa on turhia listojen indeksointien ylä- ja alarajojen tarkistusia yms. Varsinaista hyötytyötä vain kymmenisen prosenttia.
Aikaa kuluu hiukan yli 3 minuuttia python ohjelmalla. Ei voine enää kovin montaa minuuttia nopeuttaa!
Netistä löytyy helposti luvut nx4 korttipakoille vain n:n arvoille 12 asti. Esim.;
https://oeis.org/A059074
Jos n on 13, oikea tarkka todennäköisyys löytyy useista paikoista sievennetyssä muodossa ja siitä on helppo laskea oikea luku.
Löytyykö jostakin taulukko, jossa oli mukana 14x4 pakka? (Kaikki jokerit mukana.) Laskentaan menee reilusti alle 30 min ja tulee iso luku, mutta ...
Kokeilin hakea Bingillä lukua 1493804444499093354916284290188948031229880469556
Löytyi yksi osuma http://www.talkstats.com/threads/probabilty-of-picking-a-card-in-a-deck.50865/
Sen lopussa joku kertoi laskeneensa tuon luvun wolfram alpha:lla "yksinkertaisella" kaavalla.
Ymmärtääkseni kaavassa riittää muuttaa luku 13 halutuksi (nx4 pakoilla). Kannattanee ensin kokeilla pienillää n:n arvoja. Itse en (vielä) osaa muuttaa kaavaa wolfram alphan (tai jonkun muun laskimen) ymmärtämään muotoon. Kokeneemmat kokeilkaa. Oikeat luvut löytyvät sieltä oeis.org sivulta.
14x4+pakalle+ohjelmalta+menee++aikaa+hiukan+päälle+20+min.+Ohjelman+muuttamiseen+meni+pari+tuntia,+sillä+aina+unohtui+jotain+ja+tulos+ei+ollut+oikeaa+suuruusluokkaa.+Voittojen+lukumäärä+lienee
Kyllä, WolframAlpha antaa saman tuloksen "talkstatsin kaavalla":
Kaavan voi kirjoittaa WA:aan näin:
\int_0^{\infty}(1/24(x^4−16x^3 72x^2−96x 24) )^14e^(-x)dx
linkki (katkeaa varmaan täällä, mutta kopioi kokonaan):
https://www.wolframalpha.com/input/?i=\int_0^{\infty}(1/24(x^4−16x^3 72x^2−96x 24) )^14e^(-x)dx
Kiitoksia! Oikea kaavamuoto toimii hienosti ja supernopeasti. Tulos tuleekin heti sinne alkuun, joten ei meinannut millään löytyä!
Tietääkö joku, kauanko tehokkaalla tavallisella kotikoneella menisi tuon laskun suorittamiseen jollakin ilmaisella laskimella? Onko sellaisia? Wolfram alpha kait hydyntää joidenkin muiden aikaisemmin tekemiä tekemiä laskuja. Pakkohan tuossa on suorittaa valtavasti hankalaa numeerista laskentaa tarkan tuloksen saamiseksi.
Kahden maan tapauksista löytyy tarinaa ja teoriaa https://oeis.org/A000459
ja taulukko 100:lle n:n arvolle https://oeis.org/A000459/b000459.txt
Tuossahan taitaa muuten käydä niin, että kun korttien määrä kasvaa rajatta, niin todennäköisyys lähestyy lukua 1/e^4.
Niinkuin "yksinkertaisten" derangementtien (eli toisin sanoen olisi vain yksi maa tässä pelissä) tapauksessa lähestytään 1/e:tä, niin olisiko se yleisemmin silleen, että kun on k maata, niin lähestytään 1/e^k:ta, kun korttien määrää Nk kasvaa rajatta?
Ainakin myös k=2 näyttäisi toimivan: kun WolframAlphaan syöttää
\int_0^{\infty}(1/2(x^2−4x 2) )^2018*e^(-x)dx / ((2018*2)!/(2!)^2018)
niin sieltä tulee liki 1/e^2. Tässä on siis L_2 eli toinen Laguerren polynomi, niinkuin Wikipediassa sanotaan että se menee ja tulisi inclusion-exclusionista (se yhden maan tapaushan on helpohko nähdä, mutta en ainakaan suorilta käsin näitä useamman osaa itse perustella)
(Näyttää jotain virhettä tulevan myös WA:n laskuissa suuremmilla arvoilla, mutta Decimal approximation- kohta näyttäisi olevan "oikein".)
Paperista http://nyjm.albany.edu/j/2004/10-7.pdf löytyy tietoutta (Thm 1.1 ja asymptoottinen Thm 1.2).
Todennäköisyydelle saadaan asymptoottinen kaava
e^(-4) * (1 - 3/2 * N^(-1) O(N^(-2))).
missä N = korttia per maa. Arvolle N=13 se (kun siis unohdetaan O(N^(-2))-termi) antaa 0,016202265 eli kymmenestuhannesosan tarkkuudella oikein.
Tässä X = {"Pata", "Risti", "Hertta", "Ruutu"} ja merkkasin N:llä mitä tuolla on merkitty n:llä. Momentit (ks. kaava juuri ennen Thm. 1.2:ta) ovat nyy(r) = 4^r, sillä kaikki X:n alkiot samaistetaan (niinkuin paperissa olevassa "Couples mixing" -esimerkissäkin, joka siis vastaa tätä peliä, kun maita on kaksi).
Jos tuota pasianssia (13x4) pelaa vain 13 ensimmäistä korttia, millä todennäköisyydellä voitttaa (eli voisi vielä jatkaa)? Saatteko laskettua millään kaavalla.
En osaa laskea oikein (millään permutaatiokaavalla?) miten monella eri tavalla 13 ensimmäistä korttia voi valita. Tyhmästi 13 tasoisella loopilla lukemaksi tule 294818964039600. Onko oikein? Google ei tunnista.
Voittopelien lukumäärä näkyy ohjelmasta suoraan ja saan oikeahkon ison prosenttiluvun.
Laskin+ohjelmalla,+kuinka+monella+tavalla+n+ensimmäistä+korttia+voidaan+valita+nx4+pakasta:
Tuo+nopea+simulointini+ei+ole+oikealla+tavalla+täysin+satunnainen.+Kokeilin+perinteisellä+oikealla+tavalla,+jossa+oikeasti+valitaan+koko+jäljellä+olevasta+pakasta+satunnainen+kortti.+Aluksi+tehdään+52+pituinen+lista,+jossa+on+peräkkäin+neljään+kertaan+luvut+0...12.+Tämä+lista+kopioidaan+joka+kerta+työkopioksi+laskentaa+varten.+Ensiksi+arvotaan+satunnaisluku+väliltä+0...51,+ja+poistetaan+valittu+kortti+listasta.+Sitten+arvotaan+satunnaisluku+väliltä+0...50,+ja+poistetaan+valittu+kortti+listasta.+Jne.
Luulen,+että+simulointituloksesi+35,693%+on+oikein,+sillä+minä+sain+tämän+laskemalla+inkluusio-ekluusiolla+seuraavasti+(tämä+missä+tutkitaan+vain+13+ekaa+korttia+on+hieman+helpompi+tehdä,+sillä+siinä+päällekkäisyydet+eivät+tule+sotkemaan)
Oletatko laskuissasi pakassa olevan 52 erilaista korttia? Eikös tässä pasianssissa erilaisia kortteja ole vain 13? Suurin luku mikä voi esiintyä on 52!/(4*3*2*1)^13. Yksinkertaistuisivatko laskusi näillä olettamilla huomattavasti? Vai menisikö kaikki vaan hankalammaksi?
Ohjelman mukaan ensimmäisellä 13 kortin kierroksella voittoja on 104311654627608 kpl. On varmasti oikein, kosa lopputulos on OK. Kortit eri järjestyksessä. Saatko tuon luvun jotenkin isoja lukuja sieventämällä?
Tarkkaa kertoimesi arvoa käyttäen erilaisia pelejä voi olla ekalla kierroksella 292242671829192 kpl. Onko oikein? Tuo luku kiinnostaa, sillä erillisellä virheellisellä ohjelmapätkälä saan luvuksi hiukan liian suuren luvun. Jotenkin symmetriaan perustuvien kertoimien laskenta ei toimikaan ihan samalla tavalla ja ilman niitä ohjelman ajo kestää pari päivää.
Viimeinen lukusi 1411407822148941643776 on käsittämättömän suuri. On monia kertalukuja suurempi kuin 13^13 (302875106592253). Luvunhan on oltava pienempi kuin 0,356935*13^13.
Tulostin voittomärät eri kierrosten jälkeen. Tuollaisia lukuja pitäisi käsittääkseni saada kaikilla mahdollisilla eri laskutavoilla, jos ja kun viimeinen luku on varmasti todistettavasti oikein. Sama ohjelma laskee kaikki nuo luvut aina pohjautuen edellisen kierroksen tuloksiin. Luvut ovat kymmenien aidosti erilaisiin korttimääräkombinaatiohin päättyvien voittopelien summia, eikä näitä summia käytetä ohjelmassa erikseen missään. Jostain syystä google ei ole vielä oppinut niitä tunnisamaan. Numeroiden välille kirjoitetut välit, pilkut tai pisteen häirinnevät tunnistamista. Oppinee yhtenäisinä kirjoitetut luvut parissa päivässä!
1. kierros 104311654627608
2. kierros 5718165798747030058212302664
3. kierros 21697471641928694249094119387113590420504
4. kierros 1493804444499093354916284290188948031229880469556
Joo, minä oletan jokaisen kortin olevan erilainen. Tällöin erilaisia ekan 13 kortin jonoja on 52*51*...*40. Kyllä se taitaisi mennä tuossa minun laskutavassani hankalemmaksi, jos maita ei erotella. Silloinhan pakka olisi multijoukko. Wikipediassa oli jotain yleisemmästä Inkluusio-eksluusiosta yleistettynä multijoukoille siellä kohdassa missä myös Möbius-inversiosta puhuttiin, mutta siitä en saanut ihan vielä ainakaan ymmärrystä :D.
Huomasinkin tämän eroavaisuuden, kun olin viestin lähettänyt, että nämä meidän luvut ei täsmää. En tiedä miten saisi laskettua ne voitokkaiden ekojen kierrosten määrät jos samastetaan saman arvoiset kortit. Todennäköisyydenhän tuosta saa saman (jos nyt oletetaan että laskuni meni oikein, hyvinhän se simulaation kanssa on sopiva).
Niin, en tosiaan tiedä voiko tuosta luvusta mitenkään helposti "sieventää" sitä samaistettujen määrää, kun siellähän on täysin sekavat (?) määrät minkä verran mitäkin arvoa on.
"Tarkkaa kertoimesi arvoa käyttäen erilaisia pelejä voi olla ekalla kierroksella 292242671829192 kpl. Onko oikein?"
Luvun pitäisi ymmärtääkseni olla jaollinen kolmellatoista. Eli ei voi olla oikein. Vaikka luvun laskisi äärimmäisen tarkasti suoraan niistä isoista luvuista ensin niitä sieventäen, ei tulos miksikään muutu. Ei mene edes tasan, joten jossakin joku luku on hiukan väärin.
Simuloin myös pienempiä korttipakkoja ja laskin ohjelmallisesti saaduilla arvoilla. Aina sama virhe. Simuloinnin oikea lukema on aina selvästi suurempi.
Syynä on se, että nx4 pakan ensimmäisten n kortin eri kombinaatioilla on eri esiintymistiheys. En ymmärtänyt enkä osannut huomioida tätä. Laskuissasi teet sen kait automaattisesti ja oikeaoppisesti.
Pieni 4x4 pakka voi olla 63063000 eri järjestyksessä. Nuo käy hetkessä läpi. Korttien numeroarvoiksi kannattaa valita 0,1,2 ja 3. Neljällä ensimmäisellä on yhteensä 256 eri kombinaatiota. Niistä on helppo muodostaa lukuja 0..255, joita voi käytää pienen 256-paikkaisen taulukon indekseinä. Kävin läpi kaikki korttipakan 63063000 kombinaatiota ja kasvatin joka kerta neljää ekaa korttia vastaavaa muistipaikkaa. Lopuksi tulostin taulukon. Tuossa alku siitä:
[0, 0, 0, 0] 34650
[0, 0, 0, 1] 138600
[0, 0, 0, 2] 138600
[0, 0, 0, 3] 138600
[0, 0, 1, 0] 138600
[0, 0, 1, 1] 207900
[0, 0, 1, 2] 277200
[0, 0, 1, 3] 277200
[0, 0, 2, 0] 138600
[0, 0, 2, 1] 277200
[0, 0, 2, 2] 207900
[0, 0, 2, 3] 277200
[0, 0, 3, 0] 138600
[0, 0, 3, 1] 277200
[0, 0, 3, 2] 277200
[0, 0, 3, 3] 207900
[0, 1, 0, 0] 138600
[0, 1, 0, 1] 207900
[0, 1, 0, 2] 277200
[0, 1, 0, 3] 277200
[0, 1, 1, 0] 207900
[0, 1, 1, 1] 138600
[0, 1, 1, 2] 277200
[0, 1, 1, 3] 277200
[0, 1, 2, 0] 277200
[0, 1, 2, 1] 277200
[0, 1, 2, 2] 277200
[0, 1, 2, 3] 369600
[0, 1, 3, 0] 277200
[0, 1, 3, 1] 277200
[0, 1, 3, 2] 369600
Jatkuu samantapaisena ja kääntyy puolivälissä ympäri eli viimeinen luku on sama kuin ensimmäinen. Neljän ensimmäisen kortin kombinaatiota 0,0,0,0 on esiintynyt vain 34650 kertaa. Samoin 1,1,1,1 ja 2,2,2,2 ja 3,3,3,3. Joitakin kombinaatioita esiintyy 369600 kertaa. Syyn tuohon varman keksii pienellä miettimisellä. Ihan samanlainen taulukko tulee vaikka valitsisin 4 viimeistä korttia tai niitä edeltävät 4 korttia.
Taitaa ola parasta siirtyä pelaamaan vain 3x3 pakan pasianssia ja yrittää ymmärtää sen matemaattiset ihmeellisyydet. Vain 1680 erilaista pakkaa. Kolmen ekan kortin (0, 1 ja 2) kombinaatioiden esiintymismäärät:
[0, 0, 0] 20
[0, 0, 1] 60
[0, 0, 2] 60
[0, 1, 0] 60
[0, 1, 1] 60
[0, 1, 2] 90
[0, 2, 0] 60
[0, 2, 1] 90
[0, 2, 2] 60
[1, 0, 0] 60
[1, 0, 1] 60
[1, 0, 2] 90
[1, 1, 0] 60
[1, 1, 1] 20
[1, 1, 2] 60
[1, 2, 0] 90
[1, 2, 1] 60
[1, 2, 2] 60
[2, 0, 0] 60
[2, 0, 1] 90
[2, 0, 2] 60
[2, 1, 0] 90
[2, 1, 1] 60
[2, 1, 2] 60
[2, 2, 0] 60
[2, 2, 1] 60
[2, 2, 2] 20
Vaikeaksi menee. Ei ollut mitään ongelmia laskea koko ison pakan läpikäynnin lukumääriä ja todennäköisyyksiä. Ja vielä täysin oikein ilman mitään pohdintoja.
Voittoon johtavien kolmen ensimmäisen kortin (0,1 ja 2) kombinaatiot on merkitty ok:lla. Niiden yhteenlaskettu määrä on 540. Sen kun jakaa 1680:lla tulee tasan tarkkaan oikea todennäköisyys 0,32142857142857. Jos laskee yksinkertaisesti 8/27 menee vähän pieleen. Näin juuri tein 13x4 pakalla. Luvut olivat kyllä oikeita, mutta ...
[0, 0, 0] 20
[0, 0, 1] 60
[0, 0, 2] 60
[0, 1, 0] 60
[0, 1, 1] 60
[0, 1, 2] 90
[0, 2, 0] 60
[0, 2, 1] 90
[0, 2, 2] 60
[1, 0, 0] 60 ok -> [2, 1, 0] -> [0, 1, 2]
[1, 0, 1] 60 ok -> [1, 2, 0] -> [0, 1, 2]
[1, 0, 2] 90
[1, 1, 0] 60
[1, 1, 1] 20
[1, 1, 2] 60
[1, 2, 0] 90 ok -> [1, 1, 1] -> [1, 1, 1]
[1, 2, 1] 60 ok -> [0, 2, 1] -> [0, 1, 2]
[1, 2, 2] 60
[2, 0, 0] 60 ok -> [2, 0, 1] -> [0, 1, 2]
[2, 0, 1] 90 ok -> [1, 1, 1] -> [1, 1, 1]
[2, 0, 2] 60
[2, 1, 0] 90
[2, 1, 1] 60
[2, 1, 2] 60
[2, 2, 0] 60 ok -> [1, 0, 2] -> [0, 1, 2]
[2, 2, 1] 60 ok -> [0, 1, 2] -> [0, 1, 2]
[2, 2, 2] 20
(3, 1680, 0, 540, 540)
Noiden kertoimien (20,60,90) laskeminen menee erittäin vaikeaksi huomattavasti isommilla pakoilla, ellei hallitse jotain erikoismatematiikkaa.
Taulukossa ok:n jälkeiset luvut kuvaavat eri numeroiden määriä ja jälkimmäisessä nämä määrä on vielä lajiteltu "suuruusjärjestykseen". Huomataan että erilaisia tapauksa on vain kaksi [0,1,2] ja [1,1,1]. Ekassa jotain on nolla kertaa, 1 kerta ja kaksi kertaa ja toisessa kaikkia on yksi kerta. Summa aina kolme. Ohjelma käsittelee ainostaan noita lukumäärien lajiteltuja kombinaatiota. Niitä on isoissa pakoissa tuhansia tai miljoonia kertoa vähemmän kuin lukujen kombinaatioita. Toisen kierroksen jälkeen lukumäärien summa on aina 6 ja lopuksi tietysi 9.
Kertoimesi on absoluuttisen oikea. Ja ennimmäisellä kierroksella ohjelman laskema voittojen määrä on 294818964039600 olikin alusta alkaen ihan. Tätä lukua ei voi kuitenkaan käyttää yhtikäs mihikään, sillä on 39 osatapauksen summa. Jokaisella oma esiintymistiheys.
Laskin ensimmäisen kierroksen normaalisti ja jatkoin kolme seuraava kierrosta siten, ettei peliä hylätä, jos eka korti on 1, toka on 2 jne. Helppo muutos. Näin ekan kieroksen todennäköisyys jää voimaan. Sain voittojen määräksi
32846678114487755017366772424415729395763200000000 kpl.
Tuon kun jakaa kaikkien pelien määrällä 52!/24^13) saan ihan saman kertoimen kuin sinäkin muutaman sadan desimaalin tarkkuudella. Lukuisi ovat tarkalleen 24^13 kertaa suurempia kuin ohjelmalla saadut luvut. Eli erittäin hyvin ja tarkasti laskettu! Samalla periaatteella saa laskettua voittotodennäköisyyden, jos pelia pelaa vain 26 korttia. Tarvitaan vain yksi pitkän listan copy-paste! Voittojen määrä
11724286958989348877417188738544652542240640000000
ja todennäköisyys 0,1274043303682. Onko oikein? Lähes sama simuloimalla.
Kyllä, saman todennäköisyyden saan, mutta mulla on tuo lukuarvo sitten tietysti taas kaikkien koko pakan permutaatioiden lkm:
10276200796375637224456418122851024737102417783549492314767360000000
prob = 0.127404330368
Laskin inkluusio-ekluusiolla taas samoin merkinnöin, mutta nyt lasketaan A_j:itten unioni 2n:ään asti. Ja tosiaan, ne {1,2,..., 2n}:n osajoukot J on nyt indeksoitava kolmella parametrilla m0, m1 ja m2, jotka merkitsevät samaa kuin linkissä https://arxiv.org/pdf/math/0703900.pdf
"Specifically, we associate to a set S of cards the parameters m0, m1, m2, m3, m4,
where m0 tells how many ranks are not represented at all in the set S, m1
tells how many ranks are represented in the set S by a single card, and so on.
" (minun merkinnässä siis S=J).
Tuolta linkistä katsoin neuvoa, siellähän se on laskettu kokonaan. Yksi juttu mikä pitää muistaa muuttaa, kun käydään vain joukot A_1, ..., A_{2n} läpi on se kuinka monta joukkoa kutakin parametri-tyyppiä on. Mitkä tuolla koko höskän kaavalle ovat luvut 1, 4, 6, 4, 1 pitää nyt olla 1, 2, 1. Laskin tämän kaavan jo eilen, mutta tuo virhe sinne silloin jäi, niin en saanut oikeaa vastausta.
Kahden kierroksen läpäiseville pakan permutaatioiden määrälle saadaan kaava
\sum_{m1=0}^n \sum_{m2=0}^{n-m1} ( (-1)^m1 * multinomial(n-m1-m_2, m1, m2) * (2k)^m1 * (k(k-1))^m2 * (nk-m1-2m2)! )
Täällä kaava derangTwoRounds(k, n) Pythonilla koodattuna: http://tpcg.io/qP2VWK
Muuten, tuo tn:n arvohan on about neliöjuuri koko pelin läpäisyn tn:stä 0,016232727. Johtunee siitä, että läpäistäkseen koko pelin on läpäistävä kaksi puolikasta jotka ovat melkein riippumattomia.
No eihän se oikea pythonkaavalinkki sinne sitten suostunut tulemaan, kokeillaanpas uudestaan:
http://tpcg.io/VQTvnz
Hienosti toimii ohjelma ja nopeasti!
Saatko laskettua kaavoilla tai onko joku jo aikaisemmin laskenut niiden tapausten lukumäärän, joissa ensimmäisen kierroksen jälkeen kaikkia erinumeroisia kortteja on 1 kpl, toisen kierroksen jälkeen 2 kpl, kolmannen kierroksen jälkeen 3 kpl ja lopuksi tietysti 4 kpl?
Ohjelmallisesti tyhmästi 13 tasoisella silmukkaketjulla tuo on kaikkein nopein (sekunnin murto-osa) , helpoin ja muistia vain täysin olemattomasti kuluttava erikoistapaus. Kaikki tapaukset päättyvät nopeasti yhteen ja samaan etukäteen tunettuun tilaan ja siitä on helppo jatkaa. Ei tarvita yhtikäs mitään pitkien listojen jälkikäsittelyä lajitteluinen ja yhdistämisineen. Tulokset eri kierrosten jälkeen:
1. 2290792932
2. 5247732257301156624
3. 12021467964053894989684181568
4. 27538693844319092709438736048179077376
Tuo eka numero on mielenkiintoinen, sillä se esiintyy monissa eri yhteyksissä (esim. oeis.org) ja jossakin jopa n:n arvolla 13.
Tuo on itseasiassa melko helppo, sillä jokainen kierros on tuolloin erillinen peli yhdellä maalla eli vastaus on ekalle kierrokselle tavalliset derangementit, jotka saadaan kaavalla:
13! * \sum_{m=0}^13 {(-1)^m/m!}
jälkimmäiset tulee tämän potensseina:
5247732257301156624 = 2290792932^2
jne.
(Mutta tämä onkin tosiaan hyvin erityinen erityistapaus :D, eihän ne kortit "ikinä" menisi noin, jos koko pakan sekoittaisi.)
Niin, mutta siis tosiaan tuo eka luku on 13 objektin derangmenttien eli kiintöpisteettömien permutaatoiden lukumäärä. (Mikäköhän "derangemenet" olisi suomeksi, ei ole wikipedia sivuakaan suomeksi, sanakirjan tarjoama "häiriintyneisyys" ei kuulosta oikealta :D)
miten helekutissa tämä pasianssi voi kiinnostaa näin paljon?
Jos vielä palataan integraalikaavaan, joka mm. http://www.talkstats.com/threads/probabilty-of-picking-a-card-in-a-deck.50865/ :ssa esitettiin. Senhän voi "laskea auki" näin (kuvalinkki, kun täällä kaavat olisi liian sotkuisia):
https://aijaa.com/eJ2ZTt
eli päädytään tosiaan samaan kaavaan kuin Doyle, Grinstead, Snell -paperissa.
Mutta mitenköhän se on alunperin ymmärretty kääntää tuosta "multi-summasta" integraaliksi, jossa on e^{-x} mukana? Onkohan siihen jotain yleisempää teoriaa?
Esim. "yhden kierroksen kaava", voidaan (nyt kun sen tempun tietää) puljauttaa integraaliksi:
\int_0^\infty (x^4-8x^3 12x^2)^13 e^{-x} dx
Eli siinä on polynomi x^4-8x^3 12x^2 Laguerren polynomin tilalla. Liittyykö jokaiseen tälläiseen "jollain tavalla rajoitettujen permutaatioiden laskemisongelmaan" jokin polynomi, jolla se voidaan noin laskea?
Ai niin, yleisille k, n tuo yhden kierroksen kaava on
\int_0^\infty (x^4-2kx^3 k(k-1)x^2)^n e^{-x} dx
Ja tuo kysymys "liittykö jokin polynomi..." on tietysti vähän hölmö, kun siihenhän voidaan laittaa vaikka vakiopolynomi, joka kertoo sen määrän (koska int_0^\infty e^{-x}dx = 1), mutta tajusitte varmaan mitä tarkoitin, eli jokin sellainen parametristä riippuva polynomi, joka toimii kaikilla k, n niinkuin nyt tässäkin tehtävässä.
PS. kuvalinkissä painovirhe: 24:sta jäi 2 pois.
Potensseihin unohtui laittaa k:t eli
\int_0^\infty (x^k-2kx^{k-1} k(k-1)x^{k-2})^n e^{-x} dx
Keksit varmaan sopivan polynomin helpolle hyvin rajoitetulle erikoistapaukselle. Millä todennäköisyydella jokaisella kierroksella saadaan aina pienimmät mahdolliset kortit? Eli ekalla kierroksella pikkukortit ja yksi nelonen ja viimeisellä yksi kymppi ja kaikki kuvakortit.
Derangement on (ison paperisanakirjan mukaan) epäjärjestys. Ei kuitenkaan kannattane käyttää missään ainakaan ilman lainausmerkkejä.
En tiedä saako noita jotenkin saman integraalin alle mutta tuossahan on kaksi palasta, joihin puree L_4(x)^3 * L_1(x) ja kaksi, joihin L_4(x)^2*L_3(x)*L_2(x). Sitten pitää vielä kertoa sillä kuinka nelos-, seiska- ja kymppi-kortit voi valita eri osiin, se on luvulla 4*6*4.
Koko lasku:
(\int_0^\infty (x^4-16x^3 72x^2-96x 24)^3 (x-1) e^{-x}dx)^2
(\int_0^\infty (x^4-16x^3 72x^2-96x 24)^2 (x^3-9x^2 18x-6)(x^2-4x 2) e^{-x}dx)^2
=
82612224^2 * 122370048^2
Kerrotaan 4*6*4:llä ja saadaan
9810928749103579149307624380432384
Todennäköisyys on
9810928749103579149307624380432384 / 52!
= 134951900164 / 1109474371024679788256032031272569985107421875
= 1.2163588784783 × 10^-34
Meniköhän oikein?
Oikeellisuudesta en tiedä, sillä sain eri tuloksen.
Muutin ohjelmaa siten, se valitsee joka kierrokselle lähtötiedoksi erilaisen kiinteän jo pelattujen korttien määrälistan. Jokainen kierros on tavallaan loppukierros. Ekalla kierroksella 1, 2 ja 3 kortteja on jäljellä 4 kpl ja nelosia 1 kpl. Listan jälkeinen luku kertoo voittojen määrän sillä kierroksella ja isompi luku koko voittokertymän.
1. [0, 0, 0, 3, 4, 4, 4, 4, 4, 4, 4, 4, 4] 145530, 145530
2. [4, 4, 4, 1, 0, 0, 2, 4, 4, 4, 4, 4, 4] 295890, 43060871700
3. [4, 4, 4, 4, 4, 4, 2, 0, 0, 1, 4, 4, 4] 295890, 12741281327313000
4. [4, 4, 4, 4, 4, 4, 4, 4, 4, 3, 0, 0, 0] 145530, 1854238671563860890000
1854238671563860890000
1854238671563860890000*24^13/52! = 2,0149458736362360519610^-29
Ekalla kierroksella voittopelien lukumäärä (145530) on aika pieni, muttei vähää määrää kortteja tuon enempää pysty millään kombinoimaan pelin ehdoilla. Monta rajoitetta. Oltava todella paljon pienempi kuin 4^13 ja ja käytännössä paljon pienempi kuin 3^13.
Ei kun joo, mä ajattelin ihan väärin! Eihän silloin niitä mitkä ei saa sattua ole kuin niissä kohdin mitä sillä kierroksella on mahdollista tulla. Kokeillaas uudestaan:
Määritellään joukot
A1 = {σ∈S(13) | σ(1) ∈ {1,2,3,4} }
A2 = {σ∈S(13) | σ(2) ∈ {5,6,7,8} }
A3 = {σ∈S(13) | σ(3) ∈ {9,10,11,12} }
A4 = {σ∈S(13) | σ(4) ∈ {13} }
Näiden unionin komplementtia siis kysytään ekan kierroksen laskemiseksi (ja vika kierros on symmetrinen). Se saadaan
\sum_{m=0}^3 binomial(3,m)(-4)^m (13-m)! - \sum_{m=0}^3 binomial(3,m)(-4)^m (12-m)!
= 2011806720
Sitten toka kierros: joukot
B4 = {σ∈S(13) | σ(4) ∈ {1,2,3} }
B5 = {σ∈S(13) | σ(5) ∈ {4,5,6,7} }
B6 = {σ∈S(13) | σ(6) ∈ {8,9,10,11} }
B7 = {σ∈S(13) | σ(7) ∈ {12,13} }
en jaksanut kehitellä kaavaa, vaan laskin Pythonilla sen inkluusio-eksluusio -summan kaikkien joukkojen J yli, siitä tulee
2045191680
Kolmos kierros on symmetrinen. Muistetaan kertoa vielä sillä 4*6*4:llä:
2011806720**2*2045191680**2*4*6*4
= 1625218572357220765714909800809103360000
1625218572357220765714909800809103360000.0/factorial(52)
= 2.014945873636236e-29
Jos+joskus+laiskottaa+vähän+enemmän+ja++kaavat+ovat+unohtuneet,+niin+saat+laskettua+ne+molemmat+luvut+suoraan+tyhmällä+python-ohjelmalla++poistamalla+kaikista+mahdollisista+(4**13,+eli+13+numeroiset+nelijärjestelmän+luvut)+tapauksista+väärät+kombinaatiot.+(Ohjelmallinen+inkluusio-eksluusio!)+Alla+tyhmä+ja+tarkoituksellisen+hidas+ohjelmapätkä.