Egy urnában 25 piros,25 fehér és 50 zöld golyó van. Hányféle sorrendben vehetjük ki az urnából a benne lévő 100 golyót, ha mindig legalább annyi piros golyónak kell az urnában lennie, mint fehérnek, és a zöld golyók sosem kerülhetnek többségbe?

A zöld eleve relatív többségben van, tehát csak az lehet a feladatban a második feltétel, hogy a zöld nem lehet abszolút többségben.

Hosszas próbálkozások után keresgéltem kicsit a Google-vel, és megtaláltam ugyanezt a feladatot egy Rényis feladatsorban (megoldás nélkül). Szerencsére oda volt írva, hogy a témakör a Catalan számok. Kedves kérdező, igazán te is odaírhattad volna a kérdéshez a témakört. Nem hallottam még ezelőtt a Catalan számokról, de akkor eleve azzal kezdtem volna...

A megoldás C(25)·C(50), ahol C(n) jelöli az n-edik Catalan számot:

C(n) = (2n alatt n) / (n+1)

Levezetés:

A kihúzott golyóknál azt kell figyelembe venni, hogy ha z,f,p-vel jelöljük a már kihúzott zöld, fehér és piros golyók számát, akkor minden pillanatban igaz kell legyen ez a két egyenlőtlenség:

z ≥ f+p

f ≥ p

Ezekből egyébként következnek ilyen dolgok:

- elsőre zöldet kell húzni, illetve zöldet bármikor húzhatunk, amíg el nem fogy

- fehéret akkor húzhatunk ki, ha ki van már húzva elegendő zöld (z > f+p)

- pirosat akkor húzhatunk, ha fehéret is húzhatnánk, és ki van már húzva elég sok fehér (f > p)

Ha csak 25-öd annyi golyó lenne (vagyis egy garnitúra: 2 zöld és 1-1 fehér és piros golyó), akkor ilyen sorrendben húzhatnánk:

ZFZP

vagy

ZZFP

n·4 = 100 golyó esetén is végül az a feladat, hogy írjunk fel a Z,F,P betűkből egy olyan karakterláncot (stringet), aminek tetszőleges kezdeti rész-stringjére teljesülnek a fenti feltételek.

A feladat rokon a Dyck szavak generálásával. A 2n hosszú Dyck szavak n darab X és n darab Y betűből állnak, és annyi szabály van, hogy a szó bármely kezdeti stringjében x ≥ y igaz kell legyen, ahol x és y az X és Y betűk száma a rész-stringben. Ilyen szavakat C(n) féleképpen lehet generálni (ennek a bizonyítása bizonyára nem része a feladatnak).

Ha most a mi zöldjeinket X-nek, a fehéret és a pirosat meg mindkettőt Y-nak nevezzük el, vagyis kezdetben nem akarjuk őket megkülönböztetni, akkor a mi feltételeink pont a Dyck szó feltételévé alakulnak (hisz f≥p nem lesz érdekes, z≥f+p pedig egyszerűen x ≥ y lesz).

A 100 = 2·50 golyóból pedig C(50) féleképpen tudunk Dyck szavakat generálni.

Na most ha X,Y-ról vissza akarunk térni a Z,F,P-re, akkor egy ilyen Dyck szóban van 50 Z, az 50 Y-ból pedig 25 F-et és 25 P-t kell csinálni úgy, hogy a feltételeink fennálljanak. A feltétel pedig egyszerűen az, hogy f ≥ p. Az pedig megint csak egy Dyck feltétel n=25-tel, ami C(25) féle stringet eredményez.

Kész.

Ja, még egy érdekesség:

A Catalan számokat egy XIX századi belga matematikusról, Eugène Catalan-ról nevezték el. Ő maga az írásaiban ugyanezeket a számokat viszont Segner számoknak nevezte. Segner az a Segner, akiről a Segner kereket elnevezték a fizikában, és egyébként egy XVIII századi magyar természettudós (orvos, matematikus, fizikus, kémikus, csillagász) volt: Segner János András.

bongolo: Gratulálok!

És ha jól látom, annak a valószínűsége, hogy bekövetkezik, éppen P = (1/26) * (1/51)

Vagyis, a kedvező esetek száma az összesnek 1/(26*51)-ed része.

C(n) képlete miatt: /(n+1)

Jól látod, tényleg annyi a valószínűség! Jó egyszerűre adódott :)

És a Dyck szó valószínűsége is egyszerűen 1/(n+1)