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