|
Feladat: |
1356. matematika feladat |
Korcsoport: 14-15 |
Nehézségi fok: átlagos |
Megoldó(k): |
Babai László , Balla Katalin , Bárány I. , Bozóky-Szeszich Á. , Csajka P. , Cserháti Zsuzsa , Csirmaz László , Darvas György , Domokos László , Domokos Zsuzsanna , Eff L. , Ferenczi M. , Ferenczy György , Fodor Magdolna , Forgács Péter , Halász Sylvia , Herényi István , Huhn András , Höss Rozália , Kotsis Erzsébet Kinga , Kövesdi Gy. , Laczkovich M. , Lehótzky L. , Lévai Ferenc , Lukács G. , Major Pál , Malina János , Márki László , Mérő László , Nagy Klára , Pintér J. , Racskó P. , Simig György , Sipos L. , Sólyom Irén , Steiner György , Surányi László , Sükösd Csaba , Szász András , Székely Gábor , Szörényi M. , Tényi G. , Tóth Teréz , Vesztergombi Katalin |
Füzet: |
1965/október,
72 - 73. oldal |
PDF | MathML |
Témakör(ök): |
Teljesgráfok, Kombinatorikai leszámolási problémák, Kombinációk, Feladat |
Hivatkozás(ok): | Feladatok: 1964/december: 1356. matematika feladat |
|
A szöveg csak Firefox böngészőben jelenik meg helyesen. Használja a fenti PDF file-ra mutató link-et a letöltésre. a) A bizottság bármelyik két tagja a többi három távollétében nem nyithatja ki a szekrényt; ezért bármelyik tag-párhoz található legalább egy olyan zár, amelyhez egyiküknek sincs kulcsa; nevezzük az ilyen zárakat az illető tag-pár részére nyithatatlan zárnak. Két különböző tag-pár részére nem lehet közös nyithatatlan zár, mert különben a közös nyithatatlan zárt akkor sem lehetne kinyitni, ha a két tag-pár ‐ és csak ezek ‐ lennének jelen együttesen, márpedig két tag-pár legalább három tagját tartalmazza a bizottságnak. Eszerint egyrészt legalább annyi zárnak kell lennie a szekrényen, ahány különböző pár választható a bizottság tagjai közül, vagyis 10. Másrészt mindegyik bizottsági tagot legalább annyi kulccsal kell ellátni, ahány különböző tag-pár képezhető a többi négy tagból ‐ vagyis legalább 6 kulccsal ‐, mert bármelyik tagnál kell kulcsnak lennie a többi négyből képezhető 6 párhoz tartozó 6 különböző nyithatatlan zár mindegyikéhez. b) Megmutatjuk, hogy 10 zár elég a feltétel teljesítéséhez. Így minden pár részére csak egy nyithatatlan zárt írhatunk elő. A bizottság bármelyik tagja a többi négy mindegyikével egy-egy párt alkot, ezért a megfelelő pár számára nyithatatlan négy zárhoz nem kap kulcsot, a többi 6-hoz kap. A zárak szempontjából nézve pedig bármelyik zárhoz csak az a két tag nem kap kulcsot, akikből álló pár részére az illető zár nyithatatlan, a többi három kap, ennélfogva a bizottság bármelyik három tagjának jelenlétében minden zárnak legalább egy kulcsa rendelkezésre áll.
Az ábrán és a táblázaton , , , , a bizottság tagjait, 1, 2, , 10 a zárakat, ill. kulcsaikat jelöli. Az ábrán az , , , , pontpárokat összekötő szakasz melletti szám a pár részére nyithatatlan zárt adja meg. A táblázaton egy ,,‐'' jel azt jelöli, hogy a jel sorához tartozó személynek nincs kulcsa a jel oszlopához tartozó zár nyitására. Minden oszlopban három jelöletlen mező van. Sólyom Irén (Budapest, Veres Pálné g. III. o. t.) |
|