Tavallinen 4x13 korttipakka jaetaan neljälle pelaajalle. Jokainen saa siis 13 korttia. Ässä on 1 ja kuningas 13.
Kysymys 2:
Millä todennäköisyydellä kaikkien neljän pelaajan korttien numeroiden summa on alkuluku?
Kysymys 2:
Millä todennäköisyydellä kaikkien neljän pelaajan korttien numeroiden summa on alkuluku?
Vastaukset 20
Vanhimmat
Suurin mahdollinen yhden pelaajan saama korttien summa on 4*13+4*12+4*11+10=114 ja pienin mahdollinen summa on 4*1+4*2+4*3+4=28
Alkuluvut joiden suuruinen korttien summa voi olla ovat siten
29, 31, 37, 41, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113
Monte Carlo - simuloinnissa laskettaisiin sekoitetun korttipakan 13 ensimmäisen kortin summa, 13 seuraavan kortin summa jne. ja sitten tarkistettaisiin että löytyykö joku noista summauksista yllä olevasta luettelosta.
Kaikkien pelaajien korttien yhteissumma on neljällä jaollinen joten se ei ole alkuluku.
Tuossa yllä kylläkin summan maksimimäärä on 154 eli mahdolliset alkuluvut ovat
29, 31, 37, 41, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151
Simuloinnista (N=10 miljoonaa) tulos 60.959% +- 0.025%
Alkuluvuille ei ole mitään kivaa kaavaa joten jos tuota yrittäisi laskea tarkasti olisi käytävä lävitse jokaiseen luettelon alkulukuun liittyvät mahdolliset korttiyhdistelmät.
Laske kuinka monella eri tavalla 13 korttia voidaan valita 4x13 kortin pakasta, jos maalla ei ole mitään merkitystä?
Ei tule ihan suoraan yhdestä peruskaavasta. Joku helppo summakaava kuitenkin varmasti löytyy jostakin.
Esim. 3x5 pakasta voidaan valita 5 korttia 101 eri tavalla,
3x6 pakasta voidaan valita 6 korttia 336 eri tavalla,
3x7 pakasta voidaan valita 7 korttia 1128 eri tavalla,
3x8 pakasta voidaan valita 8 korttia 3823 eri tavalla,
3x9 pakasta voidaan valita 9 korttia 13051 eri tavalla,
4x8 pakasta voidaan valita 8 korttia 5475 eri tavalla ja
4x9 pakasta voidaan valita 9 korttia 19855 eri tavalla.
Helppo ja nopea laskea pelkät määrät. Jokaista erinumeroista korttia voi olla 0, 1, 2, 3 tai 4 kpl. Yhteensä saa olla vain 13 (tai joku pienempi valittu määrä). Rajoittaa tehokkaasti yksinkertaista silmukkaketjua.
10: 72403
11: 265233
12: 975338
13: 3598180
Hakemalla noita oeis.org:sta löytyy:
https://oeis.org/A187925
En ihan nyt heti keksi, mitä tuossa oikein tehdään binomikertoimilla ja miten ne liittyvät korttipakkaan.
Tapoja valita r korttia kxn pakasta on x^r:n kerroin polynomissa (1+x+x^2+...+x^k)^n eli r=n=13, k=4, niin:
https://www.wolframalpha.com/input?i=coefficient+of+x^13+in+(1+x+x^2+x^3+x^4)^13
3598180
Senhän voi multinomikaavalla avata.
Olikos tuo käänteiselle eli että jonkun summa on alkuluku? Minä saan simulaatiolla tämmöisen tuloksen: https://www.desmos.com/calculator/jcfuyiwisz
Eli n=13:lle 0,39. Jännästi heilahtelee tuo kuvaaja.
Viimeinen 4xn pakka, jolle sain tarkasti laskettua on n=5. Tulos 620054/2909907 = 0,213084. Vei 12 sekuntia. Tai saattaisi vielä n=6:kin mennä, laitetaanpas pyörimään.
Ehkä inkluusio-eksluusio käänteistapauksen laskentaan voisi olla tehokkaampi. Kakkoskysymyshän on yksi osa sitä.
No menihän se, vähän päälle 7 minuuttia
n=6: 1125719611/4008235231 = 0.280852
Nuo luvut kertovat vain erilaisten tapausten määrän. Jokaisen eri tapauksen painotuskerroin pitää myös laskea. Pienimmillään 4 ja suurimmillaan (kaikki kortit erisuuria) 4^13.
n=7: 163717674428160*7!^4/28! = 0.346478978592309
Lajittelin Itertoolsin combinations:illa saadut 7-pituiset kädet ja laskin samanlaisten määrät painokertoimiksi. Erilaisia käsiä on vain 1520.
Poistin ekan pelaajan kortit pakasta ja tein saman tempun toisen pelaajan käsille. Niille kaikille tuli toinen painokerroin.
Kolmannen pelaajan kädet otin suoraan ilman (sisäsilmukassa hidasta) painokertoimien laskua. Neljännen pelaajan käden summan saa aina pelkkänä vähennyslaskuna pakan korttien kokonaissummasta.
Aikaa kului alle 2 min. Tai vajaa 3 min, jos laski samalla myös toisen kysymyksen tapauksen. (3428905780992 kpl, 0.007256661669774). Laskureita kasvatetaan aina kahden ison painokertoimen tulolla. Valtava nopeutus.
Painokertoimet voi laskea myös suoraan käden ykkösten, kakkosten, kolmosten ja nelosten määristä ihan vaan kertolaskulla. Jos jotain samanarvoista korttia oli pakassa jäljellä 4 kpl:
1: 4
2: 6
3: 4
4: 1
Jos jotain samanarvoista korttia oli pakassa jäljellä 3 kpl:
1: 3
2: 3
3: 1
Ei pitäisi olla mitään ongelmaa laskea ainakin n=10, jos kaikki erilaiset kädet (72403 kpl) muodostaa ilman tyhmää itertoolsin combinations:ia ja muistia kuluttavaa listojen lajittelua ja laskee painokertoimet suoraan käden korteista.
n=8: 32028061915537368*8!^4/32! = 0.321692552052864
Menee tyhmällä tavalla vielä vähän alle tunnissa.
Kysymys 2 kannattaa laskea erikseen, sillä käden korttien summa on vain noin joka viides kerta alkuluku. Tehokas karsinta jokaisessa kolmessa vaiheessa. Aika meni alle 11 min.
n=8: 742898320587264*8!^4/32! = 0.007461733316731
n=9: 7149002354325551040*9!^4/36! = 0.333244064239134
Meni täysin uudella optimoidulla putkikoodilla 1 h 45 minuutissa yhdellä ytimellä.
Kaikki laskenta perustuu vain samanarvoisten korttien määrät ilmoittaviin listoihin. Pituus <= n:
Koko pakka on aluksi [4,4,4,4,4,4,4,4,4]. Neljä ykköstä jne... Samalla tavalla näytetään jokainen käsi. Esim. [0,2,0,3,1,0,3] on kakkospari, kolme nelosta, viitonen ja kolme seiskaa. Loppunollia ei tarvitse laittaa. Käteen jaettujen korttien poisto pakasta on nopea vähennyslasku
Jäljellä olevan pakan listaa käytetään kortin numerolla (-1) indeksoituna kaikkien mahdollisten jakojen muodostamassa n-tasoisessa silmukkaketjussa for range lausekkeisssa.
Kaikille kolmelle jaolle lasketaan eri tapausten painokertoimet. Niiden yhteistulot kasvavat parhaimmillaan yli miljardiksi. Painokertoimien kertoimet saadaan pakassa vielä olleiden samanarvoisten korttien ja kädessä olevin korttien määrillä indeksoituina taulukosta: pkl = [[1], [1,1], [1,2,1], [1,3,3,1], [1,4,6,4,1]]. Onko tuttu lista?
Ei kulu juuri lainkaan muistia eikä tarvita mitään kirjasto-ohjelmia.
n=10 menisi varmasti alle vuorokaudessa, jos sen jakaisi viidelle ytimelle. Helppoa, sillä ihan alussa eka pelaaja saa 0, 1, 2, 3, tai 4 ykköstä. Ehkä joskus talvella.
👍
Veisikö sinun koodilla miten paljon vähemmän aikaa laskea tapaukset
-ensimmäisen pelaajan käden summa alkuluku (ja muut mitä vaan)
- ensimmäisen ja toisen käsien summat alkuluvut
- eka, toka ja kolmas (mutta ei välttämättä neljäs)
- kaikki
Kun näistähän vastauksen saa inkluusio-eksluusiolla. Raskainhan näistä on tuo kolmas tapaus. Minulla muistaakseni tämä toi parannusta: n=6 vei jotain 2 min vs. entinen 7min.
Minä koitin vielä sellaista taktiikkaa, että pidetään mukana puuta, johon aluksi tallennettu kaikki mahdolliset yhden pelaajan kädet, joiden summa alkuluku ja haarotaan sen mukaan kuinka monta ykköstä, kakkosta,... käytetään. Sitten kun käsien jakoa muodostetaan, niin voidaan rajoittua näihin määriin. Mutta tuo ei tuonut mielestäni mitään hyötyä. Taitaa olla niin paljon rajoittavampi ehto se että mitä pakassa on jäljellä. Niitä alkuluku käsiä kun kuitenkin on sen verran paljon, että tuo ei paljon rajoita.
Jos käsien summien pitää olla alkulukuja, niin laskenta nopeutuu, sillä joka vaiheessa tapausten määrä putoa neljäs tai viides osaan ja aika tietysti samassa suhteessa.
n=13: ensimmäisen pelaajan käden summa alkuluku menee sekunnissa. Ehkä puolet ajasta kuluu 768541 painokertoimen laskentaan.
n=13: 133563451484*13!*(52-13)!/52! = 0.210331652710113
Tärkeintähän on saada muodostettua kaikki mahdolliset tapaukset mahdollisimman nopeasti ja laskea niiden määrät (painokertoimiksi). En ole keksinyt nopeampaa tapaa kuin n-1 pituinen silmukkaketju. Viimeisten korttien määrän saa ihan vaan vähennyslaskuna. Silmukkaketju sylkee joka vaiheesta alkuluvuttomia tai alkuluvullisia käsiä. Taulukkotarkistus. Ei voi tulla enää uutta samassa silmukassa, joten heti perään aina break. Tarvitaan paljon vähemän kuin 5^(n-1) "laskua".
Kaikki aika kuluu todellakin vain kolmannessa jaossa, joten vain sitä pitää optimoida. Ehkä mahdotonta. Yritin jopa taulukoida suurimman osan kolmannen vaiheen laskennasta. Hidastui!
Yksinkertaisella putkikoodilla n=6 menee 1 sekunnissa, jos mikään käsi ei saa olla alkuluku. Ja n=8 menee alle 2 minuutissa.
Ensimmäisen käden summa alkuluku:
n=14: 1227563780512*14!*(56-14)!/56! = 0.211476393426509; 2689637 kpl
n=15: 9630521129468*15!*(60-15)!/60! = 0.181044948332079; 9295027 kpl
n=16: 87231517665392*16!*(64-16)!/64! = 0.178560302502177; 33807762 kpl
Viimeiseen tapaukseen meni 16 s. Vain n. 1 s 33807762 painokertoimen laskentaan.
pkl0 = [1,4,6,4,1]
k0 = 1
for i in range(0,len(a0)): k0 = k0*pkl0[a0[i]]
Painokertoimien keskiarvo on n=16:ssa 87231517665392/33807762 = 2580222.
Jos ei valmista lainkaan käsiä (listoja) seuraavan jaon laskentaa varten, aikaa kuluu n=16:ssa vain n. 3 s.
Painokertoimet saa laskettua helposti silmukkaketjussa muiden hommien ohessa. Kaikki painokertoimien kertoimet ovat koko ajan suoraan käytetävissä ketjun edetessä kohti täyttä (n kortin) kättä. Sitten vaan s += pk.
Tästä syntyikin aivan uusi helppo kaikkien laskettavissa oleva korttipakan puolittamiseen liittyvä tehtävä.
Montako enkeliä mahtuu seisomaan nuppineulan pään päällä?
Ensimmäisen kysymyksen osalta, korttien numeroiden summa ei voi olla alkuluku, jos se on jaollinen kahdella. Koska jokainen pelaaja saa 13 korttia ja korttien numeroiden summa on 1+2+3+...+13=91, niin jokaisen pelaajan korttien numeroiden summa on 91, joka ei ole alkuluku. Täten todennäköisyys, että korttien numeroiden summa ei ole alkuluku yhdelläkään pelaajalla, on 100%.
Toisen kysymyksen osalta, jokaisen pelaajan korttien numeroiden summa voidaan laskea olevan alkuluku vain, jos korttien numerot ovat sellaiset, että niiden summa on itsessään alkuluku. Koska korttipakassa on numerot 1-13 ja näiden numeroiden summa on 91 (ei alkuluku), yksikään pelaajan korttien numeroiden summa ei ole alkuluku. Täten todennäköisyys, että kaikkien neljän pelaajan korttien numeroiden summa on alkuluku, on 0%.
Millä todennäköisyydella yksikään käsi ei ole jaollinen millään luvulla?