Szia!

Mi a valószínűsége annak, hogy N kockával dobva legalább M lesz az eredmény? Például 20 kockával dobva legalább 100. Van erre valami képlet vagy algoritmus?

A 20 kockával elérhető legalább 100 pontérték konkrét feladatát a következő módon oldottam meg. (Csak ezt a konkrét esetet programozva, más N és M esetén a dolog hasonlóan működik, már persze, ha N nem túl nagy és M nem túl kicsi.)

Mivel 20 kockával dobunk, ezért a legmagasabb pontszám 120 lehet (ekkor mind a 20 kockán 6-os jött ki), tehát a 20 kockán összesen legalább 100 pont úgy valósul meg, hogy a pontok összege 100 <= sum <= 120 lesz. Első lépésben előállítottam a 100, 101, ..., 120 számok összes partícióját, amely pontosan 20 elemből áll, és amelyben a legnagyobb szám nem nagyobb 6-nál.

A pontosan 20 elemből álló partíció, ahol minden szám egy kockadobás alkalmával lehetséges érték, a következőt jelenti: Legyen a1 >= a2 >= ... >= a20 pontosan 20 db számból álló rendezett (nem-növekvő) sorozat úgy, hogy minden aj (1 <= j <= 20) számra igaz: 1 <= aj <= 6, és a1 + a2 + ... + a20 = n. Ekkor {a1, a2, ..., a20} egy pontosan 20 elemből álló partíciója n-nek, ahol minden szám egy lehetséges érték a szabályos kockával való dobásnál. Itt 100 <= n <= 120 lesz. Még egyszer a feltételek: 1) nem-növekvő sorozat (tehát az egymás utáni elemek mindegyikére igaz: vagy kisebbek az őket megelőző elemektől, vagy egyenlő az előtte állóval), 2) minden elem legalább 1, de legfeljebb 6 lehet (ezek a kocka pontjai), 3) az összegük az az n szám, aminek a partícióit keressük (ne feledjük: 100 <= n <= 120).

n = 120-tól indultam, mert ilyen csak egy van: {6, 6, ..., 6} 20 db 6-osból álló sorozat. A 120-nak nincs több 20 elemből álló partíciója, ahol minden számra igaz az 1 <= aj <= 6 feltétel. Innentől rekurzióval visszafelé kiszámoltam az n = 119, majd ebből az n = 118 esetet, és így tovább n = 100-ig. Mikor egy konkrét n értékre kiszámoltam a lehetséges partíciókat, akkor ezekből úgy határoztam meg az n-1 partícióit, hogy n minden partíciójára végigjátszottam a következő rekurziót: Az utolsó elemet 1-el csökkentettem, ha az utolsó elem nem az 1 volt. Aztán, ha az utolsó elemet megelőző elem nagyobb volt, mint az utolsó, akkor az utolsót növeltem 1-gyel, és az utolsó előttit csökkentettem 1-gyel, amíg újabb partíciót nem kaptam. És így tovább az átalakítandó partíció minden elemére hátulról előre haladva, amíg lehetett. Ez sokkal egyszerűbb, mint így leírva. A lényeg, minden 100 és 120 közötti számhoz keressük a pontosan 20 db 1-től nem kisebb és 6-tól nem nagyobb elemekből álló partíciókat! Végül ez jött ki a partíciók darabszámára (kell minden partíció, nem csak a darabszámuk, ám itt most csak a darabszámokat írom ki):

120    1
119    1
118    2
117    3
116    5
115    7
114   10
113   13
112   18
111   23
110   30
109   37
108   47
107   57
106   70
105   84
104  101
103  119
102  141
101  164
100  192

Összesen tehát 1125 partíció. Van tehát 1125 db olyan 20 elemből álló rendezett (nem-növekvő) sorozat, ahol minden sorozat 1-től nem kisebb és 6-tól nem nagyobb elemekből áll, és az összege legalább 100, de legfeljebb 120. Egy ilyen például:

6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 5, 4, 4, 3, 2, 1

Ez a sorozat 1 db 1-est, 2-est, 3-ast, 5-öst, 2 db 4-est, és 14 db 6-os tartalmaz, és az összege 103.

Minden ilyen sorozathoz ki kell számolni, hogy az adott partíció összesen hányféle módon jöhet ki a 20 kockával való dobás során. Ez az ismétléses permutáció esete. A példa partíciót összesen 20!/(1!*1!*1!*2!*1!*14!) = 13953600 darab 20-as dobássorozat valósíthatja meg. Ezt mind az 1125 db partícióra ki kell számolni, és összegezni kell!

A végeredmény: 110597292630

Tehát ennyi 20 elemből álló (immár nem rendezett) sorozat lehetséges, ahol minden elemre igaz, hogy 1 <= aj <= 6, és a 20 elem összege legalább 100, de legfeljebb 120. Azaz 20 kockával dobva ennyi sorozat lehetséges, aminek az összege legalább 100, vagy ettől nagyobb.

Összesen 6^20 = 3656158440062976 sorozat lehetséges.

A keresett valószínűség ennek a kettőnek a hányadosa: 110597292630/3656158440062976 = 0,0000302495896835628. Vagyis kb. 0,003025% valószínűséggel lesz 20 dobás összege legalább 100.