 |
A B. 5141. feladat (2020. december) |
B. 5141. Bizonyítsuk be, hogy
\(\displaystyle \sum_{i=0}^n\, \sum_{j=i}^n \binom{n}{i} \binom{n+1}{j+1} = 2^{2n}. \)
Javasolta: Nagy Dávid (Cambridge)
(6 pont)
A beküldési határidő 2021. január 11-én LEJÁRT.
1. megoldás: algebrázós. A \(\displaystyle \sum_{i=0}^n \sum_{j=i}^n \binom{n}{i}\binom{n+1}{j+1}\) összegben a belső szumma tekintetében \(\displaystyle \binom{n}{i}\) egy konstans szorzónak számít, tehát kiemelhető belőle:
\(\displaystyle \sum_{i=0}^n \sum_{j=i}^n \binom{n}{i} \binom{n+1}{j+1} = \sum_{i=0}^n \left( \binom{n}{i} \sum_{j=i}^n \binom{n+1}{j+1} \right). \)
Közismert, hogy \(\displaystyle \binom{k}{\ell} = \binom{k}{k-\ell}\) (tetszőleges \(\displaystyle k,\ell\) egészek esetén), így:
\(\displaystyle \sum_{i=0}^n \left( \binom{n}{i} \sum_{j=i}^n \binom{n+1}{j+1} \right) = \sum_{i=0}^n \left( \binom{n}{n-i} \sum_{j=i}^n \binom{n+1}{n-j} \right). \)
Nézzük meg a belső szummát közelebbről:
\(\displaystyle S(i) = \sum_{j=i}^n \binom{n+1}{n-j} = \binom{n+1}{n-i} + \binom{n+1}{n-i-1} + \ldots + \binom{n+1}{1} + \binom{n+1}{0} = \sum_{j=0}^{n-i} \binom{n+1}{j} = S'(i). \)
Ekkor persze:
\(\displaystyle \sum_{i=0}^n \left( \binom{n}{n-i} \sum_{j=i}^n \binom{n+1}{n-j} \right) = \sum_{i=0}^n \binom{n}{n-i} S(i) = \sum_{i=0}^n \binom{n}{i} S(n-i) = \sum_{i=0}^n \binom{n}{i} S'(n-i) = \sum_{i=0}^n \left( \binom{n}{i} \sum_{j=0}^{i} \binom{n+1}{j} \right). \)
Következésképpen:
$$\begin{eqnarray*} 2 \cdot \sum_{i=0}^n \sum_{j=i}^n \binom{n}{i} \binom{n+1}{j+1} &=& \sum_{i=0}^n \left( \binom{n}{i} \sum_{j=i}^n \binom{n+1}{j+1} \right) + \sum_{i=0}^n \left( \binom{n}{n-i} \sum_{j=i}^n \binom{n+1}{n-j} \right) = \\ &=& \sum_{i=0}^n \left( \binom{n}{i} \sum_{j=i+1}^{n+1} \binom{n+1}{j} \right) + \sum_{i=0}^n \left( \binom{n}{i} \sum_{j=0}^{i} \binom{n+1}{j} \right) = \\ &=& \sum_{i=0}^n \left( \binom{n}{i} \sum_{j=i+1}^{n+1} \binom{n+1}{j} + \binom{n}{i} \sum_{j=0}^i \binom{n+1}{j} \right) = \\ &=& \sum_{i=0}^n \left( \binom{n}{i} \sum_{j=0}^{n+1} \binom{n+1}{j} \right) = \sum_{i=0}^n \left( \binom{n}{i} 2^{n+1} \right) = 2^{n+1} \sum_{i=0}^n \binom{n}{i} = 2^{n+1} \cdot 2^n = 2^{2n+1}. \end{eqnarray*}$$Ez éppen a bizonyítandó egyenlet kétszerese.
2. megoldás: valszámos. Nevezzük Segédfeladatnak a következő kérdést:
Anna \(\displaystyle n\)-szer, Balázs \(\displaystyle n+1\)-szer dob fel egy (szabályos) pénzérmét. Mennyi az esélye, hogy Balázs többször dobott fejet, mint Anna? (ez egy ismert feladat, ld. pl. https://matkonyv.fazekas.hu/cache/pdf/vol_valszam_ii.pdf 11.15 feladat)
Annak az esélye, hogy Anna éppen \(\displaystyle i\) fejet dob.
\(\displaystyle \frac{\binom{n}{i}}{2^n}. \)
Annak az esélye, hogy Balázs \(\displaystyle i\)-nél több fejet dob:
\(\displaystyle \frac{\sum_{j=i+1}^{n+1} \binom{n+1}{j}}{2^{n+1}} = \frac{\sum_{j=i}^n \binom{n+1}{j+1}}{2^{n+1}}. \)
Tehát annak az esélye, hogy Anna pontosan \(\displaystyle i\) fejet dob, míg Balázs ennél több fejet dob:
\(\displaystyle \frac{\binom{n}{i}}{2^n} \cdot \frac{\sum_{j=i}^n \binom{n+1}{j+1}}{2^n} = \frac{\sum_{j=i}^n \binom{n}{i} \binom{n+1}{j+1}}{2^{2n+1}}. \)
Így annak az esélye, hogy Annánál Balázs több fejet dob:
\(\displaystyle \frac{\sum_{i=0}^n \sum_{j=i}^n \binom{n}{i}\binom{n+1}{j+1}}{2^{2n+1}}. \)
Ez tehát a segédfeladat kérdésére a válasz; egyben a bizonyítandó egyenlet bal oldalának \(\displaystyle \frac1{2^{2n+1}}\) része.
Elegendő tehát belátnunk, hogy a segédfeladatunkra a válasz \(\displaystyle \frac12\). Erre mutatunk egy szép indoklást. Tegyük fel, hogy Anna és Balázs egyidőben dobálják fel a pénzérméiket, és számolják a fejeket. Állítsuk meg a játékot egy pillanatra akkor, amikor mindketten az \(\displaystyle n\)-edik dobásuk után járnak (Anna ekkor már befejezte, Balázsnak még van egy utolsó dobása).
- Ha Balázsnak már eddig is több fej dobása van, akkor biztosan több lesz neki a végén is (hiszen Anna már nem dob).
- Ha ebben a pillanatban Annának több feje van, akkor biztosan nem lehet Balázsnak több a végén (hisz már csak egy dobása van).
- Ha a vizsgált pillanatban döntetlen az állás, akkor Balázs utolsó dobásától függően, \(\displaystyle 1/2\) eséllyel fog teljesülni, hogy ő fejet dob.
Ha az egyes esetek valószínűségét \(\displaystyle P_1,P_2,P_3\)-mal jelöljük, akkor tehát annak az esélye, hogy Balázs több fejet dob, éppen \(\displaystyle P_1 + \frac12P_3\). Mivel a szimmetria okán \(\displaystyle P_1 = P_2\), illetve nyilván \(\displaystyle 1 = P_1+P_2+P_3\), így a keresett valószínűség tényleg \(\displaystyle \frac12\).
Statisztika:
71 dolgozat érkezett. 6 pontot kapott: 64 versenyző. 5 pontot kapott: 2 versenyző. 4 pontot kapott: 2 versenyző. 2 pontot kapott: 1 versenyző. 1 pontot kapott: 1 versenyző. 0 pontot kapott: 1 versenyző.
A KöMaL 2020. decemberi matematika feladatai