Feladat: 1097. matematika feladat Korcsoport: 16-17 Nehézségi fok: nehéz
Kitűző(k):  Bollobás Béla 
Füzet: 1961/március, 125. oldal  PDF  |  MathML 
Témakör(ök): Gráfok összefüggősége, Leghosszabb út módszere, Feladat
Hivatkozás(ok):Feladatok megoldásai: 1962/január: 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.

Egy fiú‐táborozás mindegyik résztvevője ismer legalább n másik résztvevőt (az ismeretség mindig kölcsönös; n legalább 2). Úgy akarunk leültetni fiúkat egy kerek asztal köré, hogy mindenki ismerje a két szomszédját. Bizonyítsuk be: legalább n+1 fiút leültethetünk ilyen módon, lehetséges azonban, hogy több nem ültethető le, viszont az is, hogy n+1-nél többnek kell az asztal körül ülnie.