Mathematical and Physical Journal
for High Schools
Issued by the MATFUND Foundation
Already signed up?
New to KöMaL?

Problem B. 4011. (May 2007)

B. 4011. Assoc City has 2007 inhabitants. They like joining clubs. The following two resolutions are passed to regulate club life: (1) every club must have exactly 101 members, and (2) no two clubs may have exactly the same set of members. In the senate of the city, each club is represented by a member, and it is against the law for two clubs to have the same representative. The committee of law are planning to impose a limitation on the number of clubs, so that however they are formed according to the rules above, it should always be possible to delegate representatives. What is the maximum number of clubs that may be allowed by the committee?

(5 pont)

Deadline expired on June 15, 2007.


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

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.


Statistics:

45 students sent a solution.
5 points: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 points:Cseh Ágnes, Énekes Péter, Szőke Nóra.
3 points:4 students.
2 points:4 students.
1 point:1 student.
0 point:11 students.
Unfair, not evaluated:2 solutionss.

Problems in Mathematics of KöMaL, May 2007