Középiskolai Matematikai és Fizikai Lapok
Informatika rovattal
Kiadja a MATFUND Alapítvány
Már regisztráltál?
Új vendég vagy?

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).

  1. 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).
  2. 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).
  3. 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