Az A. 519. feladat (2010. november)

A. 519. Legyen n $\ge$ 3 és k pozitív egész szám. Az asztalon úgy helyezünk el n érmét, hogy mindegyiken a fej legyen felül. Ezután összesen k-szor végrehajtjuk a következő operációt: véletlenszerűen -- egyenlő valószínűséggel --, kiválasztunk egy érmét, és a kiválasztott érmét megfordítjuk.

Bizonyítsuk be, hogy annak valószínűsége, hogy az eljárás végén mindegyik érmén az írás lesz felül, kisebb, mint $\frac{1}{2^{n-1}}$ .

Javasolta: Rónyai Lajos és Kós Géza

(5 pont)

A beküldési határidő 2010. december 10-én LEJÁRT.

Megoldás. Legyen S={1,2,...,n}^k az olyan k hosszúságú sorozatok halmaza, amelyek minden tagja az 1,2,...,n számok közül való. Az (a₁,a₂,...,a_k) $\in$ S sorozatot megfeleltethetjük annak az esetnek, amikor sorban az a₁-edik, utána az a₂-edik, ..., végül az a_k-adik érmét fordítjuk meg. Az (a₁,a₂,...,a_k) sorozatot nevezzünk jónak, ha a sorozatban az 1,2,...,n-1 számok mindegyike páratlan sokszor szerepel; ez azt jelenti, hogy a k-adik lépés után az első n-1 érme mindegyikén az írás lesz felül.

Legyen G a jó sorozatok halmaza. Azt igazoljuk, hogy a jó sorozatok gyakorisága kisebb, mint $\dfrac{1}{2^{n-1}}$ , azaz $\dfrac{|G|}{|S|}<\dfrac1{2^{n-1}}$ .

Minden u=1,2,...,(n-1)-re legyen R_u a következő operáció. Az (a₁,...,a_n) sorozatban megkeressük az első olyan elemet, ami egyenlő u-val vagy n-nel. Ha ez az elem u, akkor n-re cseréljük; ha pedig n, akkor u-ra cseréljük. A operáció csak azokon a sorozatokon értelmes, amikben szerepel az u vagy az n.

Bármely A=(a₁,a₂,...,a_n) jó sorozatra és $U=\{u_1<\dots<u_\ell\}\subset\{1,2,\dots,n-1\}$ indexhalmazra legyen $R^UA=R_{u_\ell}\dots R_{u_1}A$ . Azaz, ha 1 $\in$ U, akkor az A sorozaton végrehajtjuk az R₁ operációt. Ezután, ha 2 $\in$ U, akkor végrehajtjuk az R₂ operációt, és ezt folytatjuk (n-1)-ig. Mivel A jó sorozat, az operáció minden esetben értelmes lesz.

Ha U nem üres, akkor az R^UA sorozat rossz lesz: U minden eleme páros sokszor fog szerepelni R^UA-ban. Megfordítva, ha ismerünk egy B sorozatot, ami előáll R^UA alakban, akkor B-ből le tudjuk olvasni az U halmazt, majd a operációkat fordított sorrendben végrehajtva rekonstruálhatjuk az A sorozatot.

Ha n $\ge$ 3, akkor nem minden sorozat áll elő R^UA alakban: például ilyenek azok a sorozatok, amelyekben nem szerepel sem az n, sem az n-1. Tehát,

$|S| > \big|\big\{R^UA:\, A\in G,\, U\subset\{1,\dots,n-1\}\big\}\Big| = |G| \cdot 2^{n-1},$

vagyis

$\frac{|G|}{|S|} < \frac1{2^{n-1}}.$

Ezzel bebizonyítottuk, hogy annak valószínűsége, hogy a k lépés után az első n-1 érmén az írás lesz felül, kisebb, mint $\frac1{2^{n-1}}$ .

Statisztika:

12 dolgozat érkezett.

5 pontot kapott: Ágoston Tamás, Backhausz Tibor, Janzer Olivér, Mester Márton, Nagy 235 János, Nagy 648 Donát, Szabó 928 Attila, Weisz Ágoston.

4 pontot kapott: Frankl Nóra.

2 pontot kapott: 1 versenyző.

1 pontot kapott: 1 versenyző.

0 pontot kapott: 1 versenyző.

A KöMaL 2010. novemberi matematika feladatai

12 dolgozat érkezett.
5 pontot kapott:	Ágoston Tamás, Backhausz Tibor, Janzer Olivér, Mester Márton, Nagy 235 János, Nagy 648 Donát, Szabó 928 Attila, Weisz Ágoston.
4 pontot kapott:	Frankl Nóra.
2 pontot kapott:	1 versenyző.
1 pontot kapott:	1 versenyző.
0 pontot kapott:	1 versenyző.

Már regisztráltál?
Új vendég vagy?