![]() |
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