KöMaL - Középiskolai Matematikai és Fizikai Lapok
 English
Információ
A lap
Pontverseny
Cikkek
Hírek
Fórum

Rendelje meg a KöMaL-t!

VersenyVizsga portál

Kísérletek.hu

Matematika oktatási portál

A. 519. Let n\ge3 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 points)

Deadline expired on 10 December 2010.


Google Translation (Sorry, the solution is published in Hungarian only.)

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 (a1,a2,...,ak)\inS sorozatot megfeleltethetjük annak az esetnek, amikor sorban az a1-edik, utána az a2-edik, ..., végül az ak-adik érmét fordítjuk meg. Az (a1,a2,...,ak) 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 Ru a következő operáció. Az (a1,...,an) 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=(a1,a2,...,an) 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\inU, akkor az A sorozaton végrehajtjuk az R1 operációt. Ezután, ha 2\inU, akkor végrehajtjuk az R2 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 RUA sorozat rossz lesz: U minden eleme páros sokszor fog szerepelni RUA-ban. Megfordítva, ha ismerünk egy B sorozatot, ami előáll RUA 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\ge3, akkor nem minden sorozat áll elő RUA 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 on problem A. 519.
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

  • Támogatóink:   Ericsson   Cognex   Emberi Erőforrás Támogatáskezelő   Emberi Erőforrások Minisztériuma   Nemzeti Tehetség Program    
    MTA Energiatudományi Kutatóközpont   MTA Wigner Fizikai Kutatóközpont     Nemzeti
Kulturális Alap   ELTE   Morgan Stanley