A B. 5115. feladat (2020. szeptember)

B. 5115. Ali erszényében $\displaystyle n$ darab érme lapul, Babának pedig van $\displaystyle n-1$ darab, kezdetben üres erszénye. Baba a következő játékot játssza: a kezdetben egy erszényben lévő érméket szétosztja két erszénybe, egyikbe $\displaystyle a_1$, másikba $\displaystyle b_1$ érmét téve ($\displaystyle a_1,b_1>0$), és a táblára felírja az $\displaystyle a_1b_1$ szorzatot. Majd innentől (az előzőhöz hasonlóan) a $\displaystyle k$-adik lépésben ($\displaystyle k=2,3,\ldots$) kiválaszt egy legalább két érmét tartalmazó erszényt, a benne lévő érméket szétosztja két üres erszénybe, egyikbe $\displaystyle a_k$, másikba $\displaystyle b_k$ érmét téve ($\displaystyle a_k,b_k>0$), és a táblára felírja az $\displaystyle a_kb_k$ szorzatot.

A játék akkor ér véget, ha minden erszénybe 1-1 érme került. Ekkor Ali kiszámolja a táblán lévő $\displaystyle a_k b_k$ szorzatok összegét és ennyi aranyat ad Babának.

Legfeljebb mennyi aranyat kaphat Baba?

(5 pont)

A beküldési határidő 2020. október 12-én LEJÁRT.

Megoldás. Megmutatjuk, hogy Baba akárhogyan próbálkozik mindig $\displaystyle \boxed{\: \dfrac{n(n-1)}{2} \:}$ a nyeresége.

1. megoldás: Teljes indukcióval.
(I) $\displaystyle n=1;2$ esetén triviális az állítás.
(II) T.F.H. egy $\displaystyle n=k$-ig minden nála kisebb, vagy egyenlő pozitív egészre igaz az állítás.
(III) Igaz-e $\displaystyle n=k+1$-re?
Osszuk a $\displaystyle k+1$ aranyat tetszőlegesen két $\displaystyle a_1=m>0$ és $\displaystyle b_1=k+1-m>0$ részre. A táblára kerülő első szorzat: $\displaystyle a_1 b_1 = m(k+1-m)$.
Innentől az indukciós feltevés miatt az $\displaystyle m$ érmés erszény miatt $\displaystyle \dfrac{m(m-1)}{2}$; a másik $\displaystyle k+1-m$ érmés erszény miatt $\displaystyle \dfrac{(k+1-m)(k-m)}{2}$ érme lesz Baba nyereménye.
Azaz Baba teljes nyereménye

$\displaystyle m(k+1-m)+\dfrac{m(m-1)}{2}+\dfrac{(k+1-m)(k-m)}{2}=\dfrac{m(m-1)}{2}+\dfrac{m(k+1-m)}{2}+\dfrac{m(k+1-m)}{2}+\dfrac{(k+1-m)(k-m)}{2}=$

$\displaystyle =\dfrac{m(m-1+k+1-m)}{2}+\dfrac{(k+1-m)(m+k-m)}{2}=\dfrac{mk}{2}+\dfrac{(k+1-m)k}{2}=\dfrac{k(m+k+1-m)}{2}=\dfrac{k(k+1)}{2}=\boxed{\: \dfrac{n(n-1)}{2} \:. }$

Ezzel az indukciós bizonyítási séma helyessége miatt megvagyunk.

2. megoldás. Ez egy ,,invariánst'' használó megoldás.
Rajzoljunk egy $\displaystyle n$ csúcsú (kezdetben) teljes gráfot. A gráf csúcsai az $\displaystyle n$ darab érmét jelentik, míg a gráf élei azt jelentik, hogy az adott két érme egy erszényben van-e.
Abban a lépésben (de csak akkor!), amikor két érme külön erszénybe kerül, töröljük le a megfelelő élt!
Gondoljuk végig mi történik, ha egy $\displaystyle a_k+b_k$ érméből álló erszényt két egyenként $\displaystyle a_k$ és $\displaystyle b_k$ érmés erszényre osztunk.
Az $\displaystyle a_k+b_k$ érmés erszénynek a gráfban megfelelő $\displaystyle a_k \cdot b_k$ élt le kell törölnünk.
Azaz a táblára írt $\displaystyle a_k b_k$ számok pontosan az adott lépés során a gráfban letörölt élek számával egyeznek meg.
Mivel a gráfban végül nincs egyetlen él sem (és minden élt pontosan egyszer töröltünk le); $\displaystyle \sum_{i} a_i b_i =\dfrac{n(n-1)}{2}$, azaz Baba nyereménye valóban bármely esetben $\displaystyle \dfrac{n(n-1)}{2}$ és pont ezt akartuk belátni.

Statisztika:

101 dolgozat érkezett.
5 pontot kapott:	85 versenyző.
4 pontot kapott:	2 versenyző.
3 pontot kapott:	2 versenyző.
2 pontot kapott:	1 versenyző.
1 pontot kapott:	2 versenyző.
0 pontot kapott:	6 versenyző.
Nem versenyszerű:	2 dolgozat.
Nem számítjuk a versenybe a születési dátum vagy a szülői nyilatkozat hiánya miatt:	1 dolgozat.

A KöMaL 2020. szeptemberi matematika feladatai