Problem C. 1862. (May 2025)

C. 1862. \(\displaystyle n\) (\(\displaystyle {>2}\)) children want to play on the two undistinguishable swings of the playground. They have decided that everybody will play together with two other children for two minutes. After each round, the two children have to hand over the swings to another pair who have not yet played on the swings together. (A child handing over the swing to the next pair cannot be in the next pair.) Is the plan of the children feasible?

Based on the idea of László Németh, Fonyód

(5 pont)

Deadline expired on June 10, 2025.

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

Megoldás. \(\displaystyle n=3\)-ra és \(\displaystyle n=4\)-re könnyen látható, hogy nem végrehajtható a terv.

\(\displaystyle n \geq 5\) esetén jelölje a gyerekeket \(\displaystyle A_1, A_2, \ldots, A_n\). \(\displaystyle n=5\)-re az \(\displaystyle A_1A_2, A_3A_4, A_5A_1, A_2A_3, A_4A_5, A_1A_3, A_2A_4, A_5A_1, A_1A_4, A_2A_5\) egy lehetséges hintáztatási sor. Ezt \(\displaystyle n=6\)-ra könnyű kibővíteni: az új párosokat az előző sor elemei közé szúrjuk be mohó módon, azaz \(\displaystyle A_6\) legkisebb sorszámú párjával közös hintázását a legelső olyan helyre illesztjük be, ahova lehet:

\(\displaystyle \mathbf{A_6 A_3}, A_1A_2, \mathbf{A_6 A_5}, A_3A_4, \mathbf{A_6 A_2}, A_5A_1, \mathbf{A_6 A_4}, A_2A_3, \mathbf{A_6 A_1}, A_4A_5, A_1A_3, A_2A_4, A_5A_1, A_1A_4, A_2A_5\).

Teljes indukcióval bizonyítjuk, hogy \(\displaystyle n \geq 7\) esetén is végrehajtható a terv, ugyanis az eggyel kisebb számú eset hintáztatási sorába beilleszthetők az új párok hintázásai.

Tehát tegyük fel, hogy valamely \(\displaystyle n \geq 7\)-re végrehajtható a terv, és adott egy lehetséges hintáztatási sor. Ekkor az \(\displaystyle n\) új párt szúrjuk be a már meglévő sor párjai közé egyesével, mohó módon úgy, hogy ne rontsuk el (azaz továbbra is teljesüljenek a feladat feltételei). Akkor nem tudnánk egy új párost beilleszteni, ha az \(\displaystyle \binom{n}{2}+1\) helyből minden lehetségeset (azaz a feltételek által nem tiltottat) felhasználtunk volna már az új párosok számára. De legfeljebb \(\displaystyle n-1\) helyet használtunk el, és egy új páros számára pontosan \(\displaystyle 2(n-1)\) tiltott hely van, tehát ekkor \(\displaystyle \binom{n}{2}-(n-1)-2(n-1) \leq 0\) lenne. De \(\displaystyle n \geq 7\), azaz minden új páros számára fogunk helyet találni.

Statistics:

17 students sent a solution.
5 points:	Budai Máté, Iván Máté Domonkos, Molnár Lili.
4 points:	Hetyei Dániel.
3 points:	2 students.
1 point:	6 students.
0 point:	3 students.

Problems in Mathematics of KöMaL, May 2025