Feladat: Gy.2593 Korcsoport: 18- Nehézségi fok: átlagos
Megoldó(k):  Bártfai Péter ,  Bártfai Tamás ,  Bodor András ,  Csorba Péter ,  Csörnyei Marianna ,  Dombi Gergely ,  Domokos Bálint ,  Farkas Zénó ,  Győry Máté ,  Hajnal József ,  Harcos Gergely ,  Imreh Csanád ,  Kallós Béla ,  Katz Sándor ,  Kiss István ,  Kórász Tamás ,  Magó Kálmán ,  Maróti Miklós ,  Megyesi Zoltán ,  Miklós György ,  Murvai István ,  Nagy Ádám ,  Nagy Benedek ,  Nagy Judit ,  Németh Sándor ,  Olaszi Zsolt ,  Pataki Gergely ,  Pintér Zoltán ,  Szabó Ágnes ,  Újváry-Menyhárt Zoltán ,  Wiener Gábor ,  Zámborszky Ferenc 
Füzet: 1990/november, 391 - 392. oldal  PDF  |  MathML 
Témakör(ök): Hamilton-út, -kör, Kombinatorikus geometria térben, Konstruktív megoldási módszer, Gyakorlat
Hivatkozás(ok):Feladatok: 1989/december: Gy.2593

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 kérdésre a válasz tagadó, megadunk olyan konvex poliédert, amelyen nem létezik a megadott tulajdonságú útvonal. Tekintsünk egy szabályos oktaédert, és ennek mind a nyolc lapjára illesszünk egy-egy tetraédert; ez nyilván megtehető úgy, hogy a kapott T test konvex maradjon,

 
A T-nek 14 csúcsa, 24 lapja és 36 éle van. Az állítjuk, hogy a csúcsai nem járhatók be a megadott módon. Tegyük fel, hogy ez mégis lehetséges, azaz létezik a csúcsoknak olyan C1, C2, ..., C14 felsorolása, ahol bármely két, e sorrendben szomszédos csúcsot él köt össze. Ha most erről az útvonalról bizonyos csúcsokat a belőlük kilépő valamennyi éllel együtt elhagyunk, akkor az útvonal megmaradt része biztosítja, hogy az élhálózat az elhagyott csúcsok számánál legfeljebb eggyel több részre eshet szét.
Hagyjuk el ezek szerint az eredeti oktaéder 6 csúcsát. A hálózatnak így egyetlen éle sem marad, a megmaradt 8 csúcs közül semelyik kettő között nem vezet él. A hálózat tehát 6 alkalmas csúcs törlésével 7-nél több részre esett szét, ezen a poliéderen tehát valóban nem létezik a kívánt típusú útvonal.
 
Megjegyzés. A megoldók egy része olyan típusú útvonalakra ‐ úgynevezett körökre ‐ gondolt, amelyek kezdő ‐ és végpontja egybeesik. A megadott példában természetesen ilyesfajta kör sem létezhet, hiszen ennek bármelyik élét törölve a megoldásban vizsgált útvonalhoz jutnánk. Az ilyen típusú út, illetve kör neve Hamilton-út, illetve Hamilton-kör.