 |
A B. 4011. feladat (2007. május) |
B. 4011. A 2007 lakosú Egyesületfalva lakói nagyon szeretnek klubokat alakítani. A település polgármestere a következő szabályokat hozza:
(1) minden klubnak pontosan 101 taggal kell rendelkeznie, és
(2) két különböző klubnak nem lehet azonos a tagsága.
A város szenátusában mindegyik klubot az egyik tagja képviseli, és a törvény szerint semelyik két klubnak nem lehet ugyanaz a személy a képviselője. A jogi bizottság úgy szeretné korlátozni a klubok számát, hogy azok bárhogyan is alakuljanak a szabályok betartásával, mindig lehessen törvényesen képviselőket találni. Legfeljebb hány klub megalakítását engedélyezheti a bizottság?
(5 pont)
A beküldési határidő 2007. június 15-én LEJÁRT.
Megoldás: Mivel , 103 ember tud 103-nál több klubot alakítani a szabályok betartásával, ekkor azonban nem tudja mindegyik klubot más személy képviselni. A klubok számát tehát nem lehet több, mint 103-ban maximálni. 103 klub megalakítását viszont már engedélyezheti a bizottság, ugyanis igaz a következő: ha k
103, akkor a szabályok betartása mellett k klubnak összesen legalább k tagja lesz. Ez azért igaz, mert 101 ember legfeljebb 1, 102 ember pedig legfeljebb 102 klubot tud alakítani a szabályok betartásával.
Ha az (n
103) klubokat a szabályok betartásával hozták létre, akkor tényleg mindegyik klub tud más képviselőt delegálni a szenátusba. Készítsünk ugyanis egy páros gráfot. Az egyik osztály csúcsai legyenek ezek a klubok, a másik osztály csúcsai pedig a falu lakói, az Ai klubot pedig pontosan akkor kösse össze egy él az 
lakossal, ha tagja Ai-nek. Azt kell megmutatnunk, hogy ebben a gráfban létezik n független élből álló párosítás, amely tehát az első osztály mindegyik csúcsát összeköti a második osztály egy-egy csúcsával. Mivel fenti észrevételünk értelmében az Ai csúcsokat tartalmazó osztály bármely k elemű részhalmazának együttesen legalább k szomszédja van, az állítás azonnal következik Hall teljes párosítások létezésére vonatkozó nevezetes tételéből.
Statisztika:
45 dolgozat érkezett. 5 pontot kapott: Almási 270 Gábor András, Aujeszky Tamás, Blázsik Zoltán, Bodor Bertalan, Dibuz Dániel, Grósz Dániel, Honner Balázs, Kiss 243 Réka, Kiss 902 Melinda Flóra, Kunos Ádám, Kunovszki Péter, Mihálykó Ágnes, Nagy 648 Donát, Sümegi Károly, Szalóki Dávid, Szűcs Gergely, Tossenberger Anna, Tóth 666 László Márton, Varga 171 László, Wolosz János. 4 pontot kapott: Cseh Ágnes, Énekes Péter, Szőke Nóra. 3 pontot kapott: 4 versenyző. 2 pontot kapott: 4 versenyző. 1 pontot kapott: 1 versenyző. 0 pontot kapott: 11 versenyző. Nem versenyszerű: 2 dolgozat.
A KöMaL 2007. májusi matematika feladatai