Feladat: N.174 Korcsoport: 16-17 Nehézségi fok: nehéz
Füzet: 1998/április, 234. oldal  PDF  |  MathML 
Témakör(ök): Fagráfok, erdők, faváz, Nehéz 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 fagráf bejárásának nevezzük a következőt: egy bábu az élek mentén lépkedve eljut minden csúcshoz, és minden élen pontosan kétszer megy végig. Két bábu egyszerre járja be a fát, ha egyszerre indulnak, esetleg különböző csúcsokból, és időegységenként egyet-egyet lépnek. Két bábu akkor találkozik, ha egyszerre lépnek ugyanarra a csúcsra, vagy egyszerre tartózkodnak ugyanazon az élen. Jelöljük f(n)-nel azt a legnagyobb számot, amelyre létezik olyan n csúcsú fa, amit f(n) darab bábu egyszerre be tud járni úgy, hogy egyetlen találkozás sem történik. Bizonyítsuk be, hogy f(5k+1)=2k, ha k pozitív egész.