Problem B. 5338. (October 2023)
B. 5338. There are 10 numbered seats in a particular row of an auditorium. The seats are accessible from each end of the row. The 10 spectators holding tickets for that row arrive in a random order and they take their seats. Since the spectators do not like passing others already seated, they will approach their seats from the direction where that can be avoided, if possible. Determine the probability that at least one of the 10 ticket holders will not be able to access their seat without passing a seated spectator.
Proposed by L. Koncz, Budapest
(5 pont)
Deadline expired on November 10, 2023.
Sorry, the solution is available only in Hungarian. Google translation
I. megoldás. Határozzuk meg a komplementer esemény valószínűségét, vagyis azt, hogy mekkora eséllyel jut be mindenki a helyére átmászás nélkül.
Az elsőként érkező néző legyen a \(\displaystyle k\)-adik széken ülő, ő biztosan gond nélkül eljut a helyére. Ezután viszont csak akkor kerülhetők el az átmászások, ha a tőle balra ülők egymás közötti sorrendje is épp megfelelő (először a tőle közvetlenül balra ülő jön meg, utána a másodszomszédja, és így tovább, végül a sor bal szélén ülő) és a tőle jobbra ülők egymás közötti sorrendje is épp megfelelő.
Mivel az első néző érkezése után a tőle balra ülők balról, a jobbra ülők pedig jobbról közelítik meg a helyüket, az ő egymáshoz viszonyított sorrendjük nem számít. Így a 2.-ként, 3.-ként, ..., 10.-ként érkező 9 néző közül bármelyik \(\displaystyle k-1\) lehet a tőle balra ülő \(\displaystyle k-1\), viszont innen már csak egyféle jó sorrend van (a fentiek szerinti). Tehát a megfelelő sorrendek száma \(\displaystyle \binom{9}{k-1}\). Így összességében a megfelelő sorrendek száma \(\displaystyle \sum\limits_{k=1}^{10} \binom{9}{k-1}=2^9\), hiszen a Pascal-háromszög 9-edik sorában a binomiális együtthatók összege \(\displaystyle 2^9\). Mivel összesen \(\displaystyle 10!\)-féle sorrendben érkezhetnek, így annak a valószínűsége, hogy nincs átmászás, \(\displaystyle \frac{2^9}{10!}\).
Annak a valószínűsége pedig, hogy lesz legalább egy néző, aki nem tudja átmászás nélkül elfoglalni a helyét:
\(\displaystyle 1-\frac{2^9}{10!}=\frac{3628288}{3628800}=\frac{14173}{14175}\approx 0,999859.\)
II. megoldás. Számoljuk meg ismét, hogy hányféle sorrend esetén nincs átmászás, de most fordított sorrendben tekintsük a nézőket. Képzeljük azt, hogy az előadás végén épp fordított sorrendben távoznak (tehát az utolsóként érkező megy el először, és így tovább), ez pontosan akkor oldható meg átmászás nélkül, ha az érkezés megoldható volt. Először csak a sor bal szélén vagy a jobb szélén ülő néző tudja elhagyni helyét, ami 2 lehetőség. Ezután 9 szomszédos helyen ülnek a nézők, ismét csak a leginkább balra, vagy leginkább jobbra ülő tud távozni, ami szintén 2 lehetőség. Ezt így folytatva kapjuk, hogy mindig a bal vagy jobb szélső távozhat, egészen a 9. nézőig (mindig 2-2 lehetőség), majd végül a 10. (aki eredetileg elsőként érkezett) is távozik. Ez összesen \(\displaystyle 2^9\) féle lehetőség, innen a komplementer valószínűség az 1. megoldáshoz hasonlóan számolható.
Statistics:
127 students sent a solution. 5 points: 97 students. 4 points: 11 students. 3 points: 5 students. 2 points: 1 student. 1 point: 2 students. 0 point: 2 students. Not shown because of missing birth date or parental permission: 3 solutions.
Problems in Mathematics of KöMaL, October 2023