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