A C. 1862. feladat (2025. május)

C. 1862. \(\displaystyle n \ (> 2)\) gyerek hintázni szeretne a játszótér két hintájával, amelyeket nem különböztetünk meg. Kitalálták, hogy párosával fognak hintázni úgy, hogy mindenki mindegyik társával együtt hintázik egyszer, két percet. Minden hintázás után a hintázóknak le kell szállniuk, és átadni a hintákat egy olyan párosnak, akik még nem hintáztak együtt. (Olyan gyerek, aki most szállt ki a hintából, nem lehet az új párban.) Végrehajtható-e ez a terv?

Németh László, ötlete alapján

(5 pont)

A beküldési határidő 2025. június 10-én LEJÁRT.

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.

Statisztika:

17 dolgozat érkezett.
5 pontot kapott:	Budai Máté, Iván Máté Domonkos, Molnár Lili.
4 pontot kapott:	Hetyei Dániel.
3 pontot kapott:	2 versenyző.
1 pontot kapott:	6 versenyző.
0 pontot kapott:	3 versenyző.

A KöMaL 2025. májusi matematika feladatai