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.

 
 

1.2.3.4.5.6.7.8.9.10.ABCDE

 

Az ábrán és a táblázaton A, B, C, D, E a bizottság tagjait, 1, 2, ..., 10 a zárakat, ill. kulcsaikat jelöli. Az ábrán az A, B, C, D, E 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.)