Feladat: 1097. matematika feladat Korcsoport: 16-17 Nehézségi fok: nehéz
Megoldó(k):  Benczúr András ,  Gagyi Pálffy A. ,  Gálfi László ,  Huber T. ,  Juhász István ,  Kéry G. ,  Kiss Ildikó ,  Kóta J. ,  Krámli András ,  Máté A. ,  Máté E. ,  Molnár Emil ,  Náray-Szabó G. ,  Nováky Béla ,  Opálény M. ,  Pór A. ,  Simonovits Miklós ,  Szegő Károly ,  Székely Jenő ,  Vesztergombi György ,  Zalán P. 
Füzet: 1962/január, 23. oldal  PDF  |  MathML 
Témakör(ök): Gráfok összefüggősége, Leghosszabb út módszere, Feladat
Hivatkozás(ok):Feladatok: 1961/március: 1097. 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) Ültessünk le tetszés szerint egy F1 fiút az asztalhoz, mellé egy F2 ismerősét, amellé F2-nek egy F3 ismerősét, és ezt folytassuk, amíg meg nem akadunk. Ha Fm az utolsó, akit leültethettünk, akkor kell, hogy Fm összes ismerősei, tehát legalább n fiú, már előbb az asztalnál üljenek, különben folytathatnánk az asztalhoz ültetést.
Legyen Fm ismerősei közül Fi az első, akit asztalhoz ültettünk, akkor most felállítjuk az előtte leültetetteket, a maradók megfelelnek a feltételeknek, hiszen Fm ismeri Fi-t és Fm-en kívül minden ismerőse is ‐ tehát legalább még n fiú ‐ az asztalnál ül.
b) Ha a táborozásnak csak n+1 tagja van ‐ és így mindenki mindenkit ismer ‐, akkor valóban csak n+1 fiút ültethetünk le a kívánt módon. Hasonlóan akkor is, ha a résztvevők olyan n+1 tagú csoportokba rendezhetők, amelyeken belül bármelyik két fiú ismeri egymást, de senki sem ismer más csoportbelit. ‐ Ha viszont n=2, a fiúk j száma legalább 4, és a fiúk olyan F1,F2,...,Fj sorozatba rendezhetők, melyben mindenki csak a két szomszédját ismeri, továbbá F1 és Fj egymást, akkor a kívánt elhelyezés csak valamennyi fiú leültetésével valósul meg, tehát n+1=3-nál többen ülnek az asztalnál.

 
 Szegő Károly (Bp., Apáczai Csere J. Gyak. Gimn., IV. o. t.)