Problem A. 519. (November 2010)

A. 519. Let n $\ge$ 3 and k be positive integers. We place n coins on the table with the heads sides up. Then the following operation is performed k times: we choose one of the n coins randomly, with equal probabilities, and flip that coin. Prove that the probability that the procedure results in all the n coins lying with tails up is less than $\frac{1}{2^{n-1}}$ .

(Suggested by L. Rónyai and G. Kós)

(5 pont)

Deadline expired on December 10, 2010.

Sorry, the solution is available only in Hungarian. Google translation

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}}$ .

Statistics:

12 students sent a solution.

5 points: Á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 points: Frankl Nóra.

2 points: 1 student.

1 point: 1 student.

0 point: 1 student.

Problems in Mathematics of KöMaL, November 2010

12 students sent a solution.
5 points:	Á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 points:	Frankl Nóra.
2 points:	1 student.
1 point:	1 student.
0 point:	1 student.

Already signed up?
New to KöMaL?