Problem B. 5090. (March 2020)

B. 5090. The inscription on one side of a fair coin is \(\displaystyle +1\), and \(\displaystyle -1\) is on the other side. The coin is tossed \(\displaystyle n\) times in a row, and the \(\displaystyle n\) results are written down in a row. Then the product of every pair of consecutive items is written below them, resulting in a new list of numbers that only consists of \(\displaystyle (n-1)\) items. The procedure is repeated until a single number remains. What is the expected value of the sum of the \(\displaystyle \frac{n(n+1)}{2}\) numbers written down in the resulting triangular arrangement of numbers?

(3 pont)

Deadline expired on April 14, 2020.

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

1. megoldás.: Hívjuk a számháromszög felső sorát első sornak, az alatta lévőt másodiknak és így tovább. Az \(\displaystyle n\)-dik sorban lévő \(\displaystyle k\)-adik számot pedig jelöljük \(\displaystyle a_{n,k}\)-val. Nevezzük ,,\(\displaystyle a_{n,k}\)-csúcsú számháromszögnek'' a számháromszögünknek azon részét, mely az \(\displaystyle a_{n,k}; a_{n-1,k}, a_{n-1,k+1}; a_{n-2,k}, a_{n-2,k+1}, a_{n-2,k+2};...; a_{1,k}, a_{1,k+1}, ...,a_{1,n+k-1}\) számokból áll. (Azaz az első sorban lévő \(\displaystyle a_{1,k}\)-csúcsú háromszögek maguk az \(\displaystyle a_{1,k}\) számok; a második sorban lévő \(\displaystyle a_{2,k}\)-csúcsú háromszögek maguk a számok és a ,,felső két szomszédjuk'' és így tovább.)
Azt fogjuk megmutatni, hogy bármely \(\displaystyle n,k\) esetén annak az esélye, hogy \(\displaystyle a_{n,k}\) értéke +1, pontosan \(\displaystyle \dfrac{1}{2}\).
Ez az első sor bármely \(\displaystyle a_{1,k}\) elemére nyilván igaz.
Másfelől \(\displaystyle n>1\) esetén viszont, ha egy \(\displaystyle a_{n,k}\)-csúcsú számháromszög első sorában az \(\displaystyle a_{1,k+1}, a_{1,k+2}, ..., a_{1,k+n-1}\) elemeket változatlanul hagyom, az \(\displaystyle a_{1,k}\) elemet viszont ellentetjére változtatom, akkor ezzel az \(\displaystyle a_{n,k}\)-csúcsú számháromszögben pontosan az \(\displaystyle a_{2,k}, a_{3,k}, ..., a_{n,k}\) elemeket változatom csak meg, méghozzá mindegyiket az ellentettjére. Mivel \(\displaystyle a_{1,k}\) értéke \(\displaystyle \dfrac{1}{2}, \dfrac{1}{2}\) eséllyel +1, illetve -1, így \(\displaystyle a_{n,k}\) értéke is \(\displaystyle \dfrac{1}{2}, \dfrac{1}{2}\) eséllyel lesz +1, illetve -1.
Azaz ekkor \(\displaystyle a_{n,k}\) várható értéke \(\displaystyle \dfrac{1}{2} \cdot(-1) + \dfrac{1}{2} \cdot 1 = 0\).
A várható érték linearitása miatt pedig a táblázatban szereplő számok összegének a várható értéke megegyezik a táblázatban szereplő számok várható értékeinek az összegével, azaz \(\displaystyle \boxed{\: E(\text{összeg}) = 0 \:}\).

2. megoldás.: Hívjuk a számháromszög felső sorát első sornak, az alatta lévőt másodiknak és így tovább. Az \(\displaystyle n\)-dik sorban lévő \(\displaystyle k\)-adik számot pedig jelöljük \(\displaystyle a_{n,k}\)-val.
Nevezzük az \(\displaystyle m\)-dik sort ,,jónak'', ha tetszőleges, a sorban lévő \(\displaystyle a_{m,k}\) számra igaz, hogy annak az esélye, hogy a szám \(\displaystyle +1\) pontosan \(\displaystyle \dfrac{1}{2}\); illetve az \(\displaystyle a_{m,k}\) szám értékétől függetlenül az \(\displaystyle a_{m,k+1}\) számra is igaz, hogy annak az esélye, hogy a szám \(\displaystyle +1\) pontosan \(\displaystyle \dfrac{1}{2}\). Az első sor nyilván jó, hiszen szabályos érmével dobáltunk (és két szomszédos dobás egymástól nyilván független). Megmutatjuk, hogy tetszőleges további sor is jó.
Teljes indukcióval fogunk bizonyítani.
A bázis állítás igazságát (,,első sor jó'') már láttuk.
Tegyük fel, hogy az \(\displaystyle m\)-edik sor jó volt. Azt igazoljuk, hogy ekkor az \(\displaystyle (m+1)\)-edik sor is jó.
Vizsgáljuk az \(\displaystyle (m+1)\)-edik sor tetszőleges \(\displaystyle a_{m+1,k}\) elemét. Mivel \(\displaystyle a_{m+1,k}=a_{m,k} \cdot a_{m,k+1}\), ezért \(\displaystyle a_{m,k}, a_{m,k+1}\) lehetséges értékei alapján 4 aleset van:
\(\displaystyle a_{m,k}=-1, a_{m,k+1}=-1 \Rightarrow a_{m+1,k}=1\);
\(\displaystyle a_{m,k}=-1, a_{m,k+1}=1 \Rightarrow a_{m+1,k}=-1\);
\(\displaystyle a_{m,k}=1, a_{m,k+1}=-1 \Rightarrow a_{m+1,k}=-1\);
\(\displaystyle a_{m,k}=1, a_{m,k+1}=1 \Rightarrow a_{m+1,k}=1\).
Mivel az \(\displaystyle m\)-edik sor jó volt, ezért \(\displaystyle a_{m,k}\) és \(\displaystyle a_{m,k+1}\) is \(\displaystyle \dfrac{1}{2}-\dfrac{1}{2}\) eséllyel +1, illetve -1, azaz mind a 4 aleset valószínűsége \(\displaystyle \dfrac{1}{4}\); és innen annak az esélye, hogy \(\displaystyle a_{m+1,k}\) értéke +1 valóban \(\displaystyle \dfrac{1}{2}\).
Továbbá megmutatjuk, hogy a következő \(\displaystyle A,B\), illetve \(\displaystyle A',B'\) eseménypárok függetlenek (azaz \(\displaystyle P(A \cdot B) = P(A) \cdot P(B)\)). \(\displaystyle A: \; a_{m+1,k}=1\) és \(\displaystyle B: \; a_{m+1,k+1}=1\), illetve \(\displaystyle A': \; a_{m+1,k}=-1\) és \(\displaystyle B': \; a_{m+1,k+1}=-1\) (ennek a megmutatására azért van szükség, hogy a következő sorban is használhassuk a független események szorzási szabályát).
\(\displaystyle P(A \cdot B)=\dfrac{1}{4}\), hiszen az \(\displaystyle A \cdot B\) esemény pontosan akkor következik be, ha \(\displaystyle a_{m,k}=a_{m,k+1}=a_{m,k+2}=1\), vagy \(\displaystyle a_{m,k}=a_{m,k+1}=a_{m,k+2}=-1\), viszont ezen ,,tag-események'' valószínűsége \(\displaystyle \dfrac{1}{8}\); hiszen az \(\displaystyle m\)-edik sor jó volt, és a ,,tényező-valószínűségek'' mindegyike egymástól függetlenül \(\displaystyle \dfrac{1}{2}\). Mivel \(\displaystyle P(A)=P(B)=\dfrac{1}{2}\), ezért \(\displaystyle P(A) \cdot P(B)\) is \(\displaystyle \dfrac{1}{4}\), azaz \(\displaystyle A\) és \(\displaystyle B\) események függetlenek.
Hasonlóan \(\displaystyle P(A' \cdot B')=\dfrac{1}{4}\), hiszen \(\displaystyle A' \cdot B'\) esemény pontosan akkor következik be, ha \(\displaystyle (a_{m,k}=a_{m,k+2}=1; \text{ és } a_{m,k+1}=-1)\), vagy \(\displaystyle (a_{m,k}=a_{m,k+2}=-1; \text{ és } a_{m,k+1}=1)\), viszont ezen ,,tag-események'' valószínűsége is \(\displaystyle \dfrac{1}{8}\); hiszen az \(\displaystyle m\)-edik sor jó volt, és a ,,tényező-valószínűségek'' mindegyike egymástól függetlenül \(\displaystyle \dfrac{1}{2}\). Mivel \(\displaystyle P(A')=P(B')=\dfrac{1}{2}\), ezért \(\displaystyle P(A') \cdot P(B')\) is \(\displaystyle \dfrac{1}{4}\), azaz \(\displaystyle A'\) és \(\displaystyle B'\) események függetlenek. (Tehát a következő sorban is alkalmazható a független események szorzási szabálya.)
Ezzel (a teljes indukciós bizonyítási séma értelmében) megmutattuk, hogy a számháromszög valamennyi sora jó.
Ekkor a táblázat valamennyi \(\displaystyle a_{m,k}\) elemére ezen elem várható értéke: \(\displaystyle E(a_{m,k})=\dfrac{1}{2} \cdot 1 + \dfrac{1}{2} \cdot (-1)=0\).
A várható érték linearitása miatt pedig a táblázatban szereplő számok összegének a várható értéke megegyezik a táblázatban szereplő számok várható értékeinek az összegével, azaz \(\displaystyle \boxed{\: E(\text{összeg}) = 0 \:}\).

Statistics:

70 students sent a solution.
3 points:	Arató Zita, Argay Zsolt, Beinschroth Ninett, Biró 424 Ádám, Bognár 171 András Károly, Csizmadia Miklós, Fekete Richárd, Fleiner Zsigmond, Füredi Erik Benjámin, Hámori Janka, Jánosik Máté, Kercsó-Molnár Anita, Kerekes Boldizsár, Király Csaba Regő, Koleszár Domonkos, Kovács 129 Tamás, Lovas Márton, Mácsai Dániel, Metzger Ábris András, Mohay Lili Veronika, Molnár-Szabó Vilmos, Móra Márton Barnabás, Móricz Benjámin, Nádor Benedek, Nagy 551 Levente, Nagy Eszter Zsófia, Németh Márton, Nguyen Bich Diep, Nyárfádi Patrik, Országh Anna, Osztényi József, Reimann Kristóf, Sándor Péter, Somogyi Dalma, Szakács Ábel, Terjék András József, Tiderenczl Dániel, Tóth 057 Bálint, Török Mátyás, Vakaris Klyvis, Varga Boldizsár, Wiener Anna, Zempléni Lilla.
2 points:	13 students.
1 point:	9 students.
0 point:	5 students.

Problems in Mathematics of KöMaL, March 2020