Problem C. 1487. (May 2018)

C. 1487. Nine actors take part of acting exercises each involving three characters. With what minimum number of exercises is it possible to make sure that every pair of actors play together at least once?

(5 pont)

Deadline expired on June 11, 2018.

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

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.

Statistics:

111 students sent a solution.
5 points:	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 points:	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 points:	9 students.
2 points:	5 students.
1 point:	13 students.
0 point:	32 students.
Unfair, not evaluated:	2 solutionss.

Problems in Mathematics of KöMaL, May 2018