KöMaL - Középiskolai Matematikai és Fizikai Lapok
English Információ A lap Pontverseny Cikkekről Távoktatás Hírek Fórum Internetes Tesztverseny
Versenykiírás
Tudnivalók
Nevezési lap
Feladatok
A verseny állása
Korábbi évek
Arcképcsarnok
Munkafüzet

 

Rendelje meg a KöMaL-t!

Támogatóink:

Ericsson

Google

Emberi Erőforrások Minisztériuma

Emberi Erőforrás Támogatáskezelő

Oktatáskutató és Fejlesztő Intézet

ELTE

Reklám:

VersenyVizsga portál

Kísérletek.hu

Matematika oktatási portál

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ő LEJÁRT.


Megoldás: Mivel {103\choose 101}>103, 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\le103, 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 A_1,A_2,\ldots,A_n (n\le103) 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 \ell lakossal, ha \ell 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.


A B. 4011. feladat statisztikája
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

  • Támogatóink:   Ericsson   Google   Szerencsejáték Zrt.   Emberi Erőforrások Minisztériuma   Emberi Erőforrás Támogatáskezelő   Oktatáskutató és Fejlesztő Intézet   ELTE   Nemzeti Tehetség Program   Nemzeti
Kulturális Alap