Mathematical and Physical Journal
for High Schools
Issued by the MATFUND Foundation
Already signed up?
New to KöMaL?

Problem B. 5115. (September 2020)

B. 5115. Ali has \(\displaystyle n\) coins in his purse, and Baba has \(\displaystyle n-1\) purses, initially all empty. Baba is playing the following game: he divides the coins (all in the same purse at start) into two purses, with \(\displaystyle a_1\) coins in one of them and \(\displaystyle b_1\) coins in the other (\(\displaystyle a_1,b_1>0\)), and then he writes the product \(\displaystyle a_1b_1\) on a blackboard. Then he continues in the same way: in the \(\displaystyle k\)th move (\(\displaystyle k=2,3,\ldots\)) he selects a purse containing at least two coins, divides them between two empty purses, with \(\displaystyle a_k\) coins in one of them and \(\displaystyle b_k\) in the other (\(\displaystyle a_k,b_k>0\)), and writes the product \(\displaystyle a_kb_k\) on the board.

The game terminates when there is 1 coin in each purse. Then Ali gives as many coins to Baba as the sum of all the products \(\displaystyle a_k b_k\) on the board.

What is the maximum number of coins that Baba may get?

(5 pont)

Deadline expired on October 12, 2020.


Sorry, the solution is available only in Hungarian. Google translation

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.


Statistics:

101 students sent a solution.
5 points:85 students.
4 points:2 students.
3 points:2 students.
2 points:1 student.
1 point:2 students.
0 point:6 students.
Unfair, not evaluated:2 solutionss.
Not shown because of missing birth date or parental permission:1 solutions.

Problems in Mathematics of KöMaL, September 2020