Kezdőlap


Feladat:	B.4864	Korcsoport: 16-17	Nehézségi fok: nehéz
Megoldó(k):	Busa Máté , Döbröntei Dávid Bence , Gáspár Attila , Kovács Benedek , Nagy Nándor
Füzet:	2017/szeptember, 347 - 350. oldal		PDF \| MathML
Témakör(ök):	Feladat, Várható érték
Hivatkozás(ok):	Feladatok: 2017/március: B.4864

A szöveg csak Firefox böngészőben jelenik meg helyesen. Használja a fenti PDF file-ra mutató link-et a letöltésre.

I. megoldás. Minden húzás után írjuk fel, hogy milyen golyót húztunk. Ha kéket, azt

K

-val, ha pirosat, azt

P

-vel jelöljük. A 100-adik piros után írjunk le annyi kéket, amennyi a zsákban maradt. Így egy olyan 200 hosszú

P

‐

K

sorozathoz jutunk, melyben 100 db

P

és 100 db

K

van.
Összesen

(\binom{200}{100})

ilyen sorozatot tudunk felírni.
Számoljuk össze azokat a lehetőségeket, amikor

k

darab golyó marad a zsákban. Vagyis az utolsó

k

db betű

K

és előttük

P

van. A többi golyót tetszőlegesen húzhatjuk ki, azaz az első

200 - k - 1

helyre 99 db

P

-t és

100 - k

K

-t írhatunk az összes lehetséges elrendezésben. Ezt

(\binom{199 - k}{99})

-féleképpen tehetjük meg (kiválasztjuk, hogy melyik helyre kerüljön piros (

P

) golyó.) Így annak a valószínűsége, hogy

k

darab golyó marad a zsákban:

\begin{matrix} \frac{(\binom{199 - k}{99})}{(\binom{200}{100})} . \end{matrix}

Ekkor a keresett várható érték az alábbi formában írható:

\begin{matrix} E = \sum_{i = 0}^{100} \frac{(\binom{199 - i}{99})}{(\binom{200}{100})} \cdot i = [1 \cdot (\binom{198}{99}) + 2 \cdot (\binom{197}{99}) + ... + 100 \cdot (\binom{99}{99})] \cdot \frac{1}{(\binom{200}{100})} . \end{matrix}

Célunk a szögletes zárójelben lévő kifejezés egyszerűbb alakra hozása. Ehhez az alábbi azonosságot fogjuk felhasználni:

\begin{matrix} (\binom{n}{k}) + (\binom{n - 1}{k}) + ... + (\binom{k}{k}) = (\binom{n + 1}{k + 1}) . \end{matrix}

(Ennek, az ún. zokni-szabálynak a bizonyítása: cseréljük ki az összegben a

(\binom{k}{k})

tagot

(\binom{k + 1}{k + 1})

-re, majd jobbról balra haladva mindig az utolsó két tagot helyettesítsük az

(\binom{l}{m}) + (\binom{l}{m + 1}) = (\binom{l + 1}{m + 1})

azonosság alapján a megfelelő taggal.)
Ez alapján az

\begin{matrix} (\binom{198}{99}) + (\binom{197}{99}) + (\binom{196}{99}) + ... + (\binom{99}{99}) & = (\binom{199}{100}), \\ (\binom{197}{99}) + (\binom{196}{99}) + ... + (\binom{99}{99}) & = (\binom{198}{100}), \\ (\binom{196}{99}) + ... + (\binom{99}{99}) & = (\binom{197}{100}), \\ ⋮ \\ (\binom{100}{99}) + (\binom{99}{99}) & = (\binom{101}{100}), \\ (\binom{99}{99}) & = (\binom{100}{100}) \end{matrix}

egyenletekhez jutunk. Ezeket összeadva kapjuk, hogy a bal oldal épp a szögletes zárójelben álló kifejezés, míg a jobb oldalt átalakíthatjuk (ismét az a zokni-szabályt felhasználva):

\begin{matrix} (\binom{199}{100}) + (\binom{198}{100}) + ... + (\binom{101}{100}) + (\binom{100}{100}) = (\binom{200}{101}) = (\binom{200}{99}) . \end{matrix}

A keresett várható érték tehát:

\begin{matrix} E = \frac{(\binom{200}{99})}{(\binom{200}{100})} = \frac{\frac{200!}{99! \cdot 101!}}{\frac{200!}{100! \cdot 100!}} = \frac{100}{101} . \end{matrix}

Megjegyzés. A feladat állítása

n

kék és

n

piros golyóra is megfogalmazható, ekkor a várható érték

\frac{n}{n + 1}

Megjegyzés. Azt, hogy a kérdéses összeg

(\binom{200}{101})

-gyel egyenlő, Busa Máté (Nagykanizsa, Batthyány Lajos Gimn., 11. évf.) a következőképpen bizonyította: Vegyük az első 200 pozitív egész számot. Ezek közül szeretnénk kiválasztani 101 db számot. Ezt megtehetjük

(\binom{200}{101})

-féleképpen. Máshogy összeszámolva: Legyen a kiválasztott számok közül növekvő sorrendben a 100. szám egy

x

szám, ahol

x

nyilván legalább 100 és legfeljebb 199. Ilyen esetből, ahol a 100. legkisebb szám az

x

, pontosan

(200 - x) \cdot (\binom{x - 1}{99})

van, hiszen a legnagyobb kiválasztott szám

(200 - x)

-féle lehet, az

x

-nél kisebb 99 darab számot pedig

(\binom{x - 1}{99})

-féleképpen lehet kiválasztani. Ha összeadjuk a lehetőségeket a lehetséges

x

-ekre, akkor megkapjuk, hogy

\begin{matrix} (\binom{200}{101}) = \sum_{x = 100}^{199} (200 - x) \cdot (\binom{x - 1}{99}) = 100 \cdot (\binom{99}{99}) + 99 \cdot (\binom{100}{99}) + ... + 1 \cdot (\binom{198}{99}) . \end{matrix}

II. megoldás. Feltételezhetjük, hogy az utolsó piros golyó kihúzása után a zsákban maradt golyókat is egyenként kihúzzuk. Így a 200 golyónak

(\binom{200}{100})

féle sorrendje lehet, minden eset ugyanolyan valószínű. Feltételezhetjük, hogy a golyókat fordított sorrendben húztuk ki, ekkor az első piros golyó előtt kihúzott kék golyók számának várható értékét keressük.

Állítás. Ha összesen

100

piros és

n

kék golyónk van, akkor az első piros golyó előtt kihúzott kék golyók számának várható értéke

\frac{n}{101}

Bizonyítsunk teljes indukcióval. Ha

n = 0

, akkor az állítás triviális.
Ha

n \geq 1

, akkor az első golyó

\frac{100}{100 + n}

valószínűséggel piros, ekkor a kék golyók száma 0. Az első golyó

\frac{n}{100 + n}

valószínűséggel kék. Az indukciós feltevés miatt ezután még átlagosan

\frac{n - 1}{101}

kék golyót húzunk ki, így a kék golyók számának várható értéke:

\begin{matrix} E = \frac{n}{100 + n} \cdot (1 + \frac{n - 1}{101}) = \frac{n}{100 + n} \cdot \frac{100 + n}{101} = \frac{n}{101} . \end{matrix}

Ezzel az állítást igazoltuk. Ha

n = 100

, akkor a várható érték

\frac{100}{101}

III. megoldás. A feladatban leírt folyamatot kibővíthetjük úgy, hogy a végén a zsákban maradt golyókat is kihúzzuk, ilyen módon mindig kihúzásra kerül mind a 200 golyó.
Ekkor azon kék golyók számának várható értékét kell meghatároznunk, melyek a kihúzottak sorában az utolsó piros golyó után következnek.
Legyen

p_{1}

annak a valószínűsége, hogy egy adott kék golyó az utolsó piros golyó után kerül kihúzásra. Ha csak ezt a kék golyót és a 100 piros golyót tekintjük, ezen 101 golyó közül mindegyik ugyanannyi eséllyel lesz utolsóként kihúzva. Vagyis a kék golyó

p_{1} = \frac{1}{101}

eséllyel lesz az utolsó piros után kihúzva.
Ugyanígy, mind a 100 kék golyóról egyenként elmondható, hogy az

\frac{1}{101}

valószínűséggel lesz az utolsó piros golyó után kihúzva. Ha a 100 kék golyóhoz egyenként valószínűségi változókat rendelünk, melyek értéke 1, ha a golyó az utolsó piros után kerül kihúzásra, és 0, ha nem, akkor a keresett várható érték a 100 valószínűségi változó összegének várható értéke. Változók összegének várható értéke pedig egyenlő a változók várható értékeinek összegével. Mivel minden golyóhoz tartozó változó

\frac{1}{101}

eséllyel lesz 1, és a maradék eséllyel 0, minden változóhoz

\frac{1}{101}

várható érték tartozik. Így a 100 kék golyóhoz tartozó változók várható értékeinek összege

100 \cdot \frac{1}{101} = \frac{100}{101}

, vagyis az utolsó piros után húzott kék golyók számának is

\frac{100}{101}

a várható értéke.
A keresett várható érték tehát

\frac{100}{101}

IV. megoldás. Egy véletlenszerű, viszatevés nélküli kihúzást úgy is elképzelhetünk, mint 200 db golyót sorrendben, melyből 100 piros, 100 pedig kék színű. Ez azért igaz, mert amikor az utolsó piros golyót kihúzzuk, utána már csak kék marad a zsákban, azok kihúzása pedig egyféleképpen történhet meg.
Tekintsük a 100 piros golyót, amelyek 101 helyet határoznak meg (előttük és utánuk is van egy-egy hely). Ezen 101 helyre fogunk 100 db kék golyót elhelyezni. Jelölje

d_{i}

i

-edik helyen lévő golyók számát, a részeket értelemszerűen számozzuk.
Be fogjuk bizonyítani, hogy tetszőleges

1 < i \leq 100

esetén

E (d_{i}) = E (d_{i + 1})

. Ehhez vegyük az összes lehetséges kihúzást. Ezek egyértelműen összepárosíthatók, hiszen az

i

-edik helyen levő golyókat megcserélve az

(i + 1)

-edik helyen lévőkkel, egyértelműen megkapjuk az adott kihúzás párját (ami akár önmaga is lehet). A párosítás lehetősége miatt igazoltuk, hogy

E (d_{i}) = E (d_{i + 1})

. Ebből az egyenlőség tranzitivitása miatt

E (d_{i}) = E (d_{j})

tetszőleges

1 < i, j \leq 100

esetén. Azt is tudjuk, hogy

\begin{matrix} \sum_{i = 1}^{101} E (d_{i}) = 100 = {a kék golyók száma} . \end{matrix}

Ezért

\begin{matrix} E (d_{i}) = \frac{100}{101}, \end{matrix}

így ez a végén zsákban maradó golyók számának várható értéke.