A C. 1487. feladat (2018. május)

C. 1487. Kilenc színész háromfős helyzetgyakorlatokat játszik. Legkevesebb hány gyakorlatra van szükség ahhoz, hogy bármely két színész szerepeljen közösen?

(5 pont)

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

Megoldás. Szemléltessük a feladatot egy kilencpontú gráffal, melynek csúcsai az egyes színészek. Ha két színész együtt szerepel, akkor a pontok össze vannak kötve egy éllel. A háromfős helyzetgyakorlatokat egy-egy háromszög szemlélteti a gráfban.

Mivel bármely két színésznek szerepelnie kell közösen, ezért teljes gráfról van szó. A kilencpontú teljes gráf összes éleinek száma $\displaystyle \frac{9\cdot8}{2}=36$.

Ha a $\displaystyle 36$ élből ki tudunk alakítani $\displaystyle 12$ olyan háromszöget, melyeknek nincs közös oldala, akkor a legkevesebb gyakorlattal oldottuk meg, hogy bármely két színész szerepeljen közösen.

Ha egy csúcs része egy háromszögnek, akkor a csúcsból induló két éllel kapcsolódik a háromszöghöz. Minden csúcsból $\displaystyle 8$ él indul, tehát minden csúcs $\displaystyle 4$ háromszöghöz fog kapcsolódni. Vagyis minden színész $\displaystyle 4$ gyakorlatban fog részt venni és ezekben $\displaystyle 4\cdot2=8$ különböző színésszel játszik együtt, tehát minden színésszel szerepel közösen. A háromszögek egy lehetséges kialakítását a lenti ábrák mutatják.

Tehát legkevesebb $\displaystyle 12$ gyakorlatra van szükség.

Megjegyzés. Sokan csak a végeredményt közölték, ők – a Versenykiírás szerint ("A puszta eredményközlést nem értékeljük. A kimondott állításokat matematikából bizonyítani kell...") – 0 pontot kaptak.

Statisztika:

111 dolgozat érkezett.
5 pontot kapott:	Agócs Katinka, Ajtai Boglárka, Almási Adél Csilla, Andó Viola, Biró 424 Ádám, Böcskei Bálint Attila, Bukor Benedek, Debreczeni Tibor, Dékány Barnabás, Fodor Marcel, Fonyi Máté Sándor, Gárdonyi Csilla Dóra, Görcs András, Hordós Adél Zita, Jankovits András, Kerekes Boldizsár, Kiszelovics Dorina, Koleszár Domonkos, Kovács 161 Márton Soma, Kovács 526 Tamás, Lajkó Áron, Markó Gábor, Molnár 410 István, Németh Csilla Márta, Nyitrai Boglárka, Országh Júlia, Pipis Panna, Purzsa Aletta, Schenk Anna, Shuborno Das, Surján Anett, Szalontai Kinga Sára, Szécsi Adél Lilla, Tóth 529 Petra, Veres Kata, Williams Hajna.
4 pontot kapott:	Ajtai Janka, Csóti Kristóf, Debreczeni Dorina, Gém Viktória, Hámori Janka, Imreh Júlia, Kis 194 Károly, Kiss 014 Dávid, Nagy 202 Eszter , Pinke Andrea, Székelyhidi Klára, Szőnyi Laura, Varga 269 Viktor, Vlaszov Artúr.
3 pontot kapott:	9 versenyző.
2 pontot kapott:	5 versenyző.
1 pontot kapott:	13 versenyző.
0 pontot kapott:	32 versenyző.
Nem versenyszerű:	2 dolgozat.

A KöMaL 2018. májusi matematika feladatai