Egy matek feladat, amit régen hallottam, de azóta se tudom a megoldását. Hogyan lehet ezt megcsináni? Nehéz feladat!

tegnapelőtt 23:35-re válaszolva:

Természetesen ha igaz az állítás --- és annak tűnik --- akkor azokra a konkáv poliéderekre is igaz, amelyek konvexszé "pofozhatók". A "topológiailag gömb" meghatározásod annyira találó, hogy tényleg az tűnik a leginkább járható útnak, hogy ha a poliédert kivetíted egy gömbre, és ott kapsz egy "térképet", amin hasonlóan meg tudod fogalmazni a feladatot.

Az is könnyen látható (csak nem tudom, hogy előre visz-e), hogy a magasabb fokú csúcsok széthúzásával olyan térképre vezethetjük vissza a feladatot, ahol minden csúcs foka 3.

Első válaszoló vagyok, írom a MEGOLDÁST. Ha még szeretnél gondolkozni rajta, ne olvassd el az alábbiakat!

Euler-tétel: e = l + c - 2 (e: élek; l: lapok; c: csúcsok száma).

Vegyünk egy olyan pillanatot, amikor egyik hangya sincs csúcsban (a legtöbb pillanat ilyen). Ha két hangya ugyanazon az élen van, akkor rövidesen találkozni fognak, vagy nemrég találkozttak. Ezért feltehetjük, hogy l különböző élen van éppen egy-egy hangya. Jelöljük sárgával azokat az éleket, amelyeken nincs hangya (a többi szürke), és tekintsük a poliéder csúcsaiból, illetve a sárga élekből álló gráfot. Ennek a gráfnak c-2 éle van, ezért a gráf nem összefüggő és van legalább egy körmentes komponense. Vegyünk egy ilyen komponenst. Ez egy sárga fa (szélsőséges esetben akár izolált pont is lehet), amiből indulnak ki legalább 3 szürke él. Ha az összes ilyen szürke élen befelé megy a hangya, akkor elengedhetetlenül találkozni fognak; ha mindegyiken kifelé, akkor meg nemrég találkozniuk kellett. Ha viszont vegyes, akkor a sárga fát az óramutató járásával ellentétes irányban körüljárva kell lennie két egymás melletti szürke élnek, ahol előbbin befelé jön egy hangya, utóbbin kifelé. Ez egyetlen hangyának az útvonala, így csak abban az esetben fordulhat elő, ha ez a sárga fa két csúcsát összekötő él (úgyhogy szürke él nincs közben. Ekkor viszont erről az élről elfeledkezve. A többi szürke élen végigvihewtjük az előző gondolatot. (Ha mind befelé megy, akkor találkoznak; ha mind kifelé, akkor találkoztak; ha meg vegyes, akkor a váltásnál lennie kell egy ilyen élnek). Ezt addig ismételgethetjük, míg el nem fogynak a sárga fához csatlakozó szürke élek, viszont mivel vannak olyan szürke élek, amelyek más komponensek felé mutatnak, a folyamat nem az élek elfogyásával fog véget érni, hanem egy olyan állapottal, amikor mindegyiken kifelé vagy mindegyiken befelé mennek a hangyák.