 |
A B. 5231. feladat (2022. március) |
B. 5231. Bizonyítsuk be, hogy minden \(\displaystyle n\) pozitív egészre teljesül, hogy
\(\displaystyle \sum_{k=1}^n k \cdot 2^{k-1} = \sum_{k=1}^n 2^{n-k} \cdot (2^k-1). \)
(4 pont)
A beküldési határidő 2022. április 11-én LEJÁRT.
Megoldás. Tekintsük az alábbi, \(\displaystyle n \times n\)-es táblázatot (a táblázat \(\displaystyle i.\) sorának \(\displaystyle j.\) eleme \(\displaystyle 2^{j-1}\), ha \(\displaystyle i \leq j\), egyébként 0).
\(\displaystyle \begin{matrix} 1 & 2 & 2^2 & 2^3 & \ldots & 2^{n-3} & 2^{n-2} & 2^{n-1} \\ 0 & 2 & 2^2 & 2^3 & \ldots & 2^{n-3} & 2^{n-2} & 2^{n-1} \\ 0 & 0 & 2^2 & 2^3 & \ldots & 2^{n-3} & 2^{n-2} & 2^{n-1} \\ 0 & 0 & 0 & 2^3 & \ldots & 2^{n-3} & 2^{n-2} & 2^{n-1} \\ \vdots & \vdots & \vdots & \vdots & \ddots & \vdots & \vdots & \vdots \\ 0 & 0 & 0 & 0 & \ldots & 2^{n-3} & 2^{n-2} & 2^{n-1} \\ 0 & 0 & 0 & 0 & \ldots & 0 & 2^{n-2} & 2^{n-1} \\ 0 & 0 & 0 & 0 & \ldots & 0 & 0 & 2^{n-1} \end{matrix} \)
A bizonyítandó egyenlet mindkét oldalán a táblázatban szereplő számok összege áll:
- A \(\displaystyle \displaystyle \sum_{k=1}^n k \cdot 2^{k-1}\) összegben oszloponként adjuk össze a számokat, a \(\displaystyle k\)-adik oszlopban éppen \(\displaystyle k \cdot 2^{k-1}\) a számok összege.
- A \(\displaystyle \displaystyle \sum_{k=1}^n 2^{n-k} \cdot (2^k-1)\) összegben soronként adjuk össze a számokat, hiszen az \(\displaystyle (n-k+1)\)-edik, azaz alulról \(\displaystyle k\)-adik sorban a számok összege éppen
\(\displaystyle 2^{n-k} + \ldots + 2^{n-1} = 2^{n-k} \cdot \left(1 + \ldots + 2^{k-1} \right) = 2^{n-k} \cdot (2^k-1). \)
Megjegyzés. Érdemes elmesélni, hogy miként született ez a feladat.
Képzeljük el, hogy \(\displaystyle 2^n\) különböző magasságú embert szeretnénk tornasorba állítani kevés összehasonlítással (egy összehasonlítással két embert tudunk összehasonlítani).
Egy lehetőség, hogy egyenként ,,illesztjük be'' az embereket a tornasorba. Ha \(\displaystyle t-1\) embert már sorba rendeztünk, akkor a \(\displaystyle t\). ember helyét bináris kereséssel meg tudjuk találni a tornasorban \(\displaystyle \lceil \log_2(t) \rceil\) összehasonlítással, a legszerencsétlenebb esetben is. Ezzel a módszerrel a legszerencsétlenebb esetben éppen \(\displaystyle \displaystyle \sum_{k=1}^n k \cdot 2^{k-1}\) összehasonlításra lesz szükségünk a \(\displaystyle 2^n\) ember tornasorának felállításához (hiszen éppen \(\displaystyle 2^{k-1}\) különböző olyan \(\displaystyle t\) érték van, amelyre \(\displaystyle \lceil \log_2(t) \rceil = k\)).
Egy másik lehetőség, hogy először \(\displaystyle 2^{n-1}\) diszjunkt párt összehasonlítunk, aztán két-két párt összefésülünk egy-egy négyes tornasorrá, majd két-két négyest egy-egy nyolcas tornasorrá, és így tovább. Így \(\displaystyle 2^{n-k}\) alkalommal fogunk két \(\displaystyle 2^{k-1}\) méretű tornasort összefésülni. Könnyen meggondolható, hogy két \(\displaystyle s\) tagú tornasor összefésüléséhez – a legrosszabb esetben – \(\displaystyle 2s-1\) összehasonlítás szükséges. Tehát ezzel a módszerrel a legszerencsételenebb esetben \(\displaystyle \displaystyle \sum_{k=1}^n 2^{n-k} \cdot (2^k-1)\) összehasonlításra lesz szükségünk.
A feladat kitűzóje rendezési algoritmusokat tanított matekórán, amikor kíváncsiságból összehasonlította \(\displaystyle n=7\) esetén a két módszer lépésszámát. Meglepve tapasztalta, hogy mindkét esetben éppen \(\displaystyle 769\)-et kapott eredményül – jobban belegondolva kiderült, hogy ez nem egy véletlen egybeesés.
Statisztika:
91 dolgozat érkezett. 4 pontot kapott: 90 versenyző. 3 pontot kapott: 1 versenyző.
A KöMaL 2022. márciusi matematika feladatai