Feladat: F.2934 Korcsoport: 18- Nehézségi fok: nehéz
Megoldó(k):  Csorba Péter ,  Csörnyei Marianna ,  Dienes Péter ,  Dőtsch András ,  Futó Gábor ,  Győrffy Werner ,  Horváth Gábor ,  K. L. ,  Kálmán Tamás ,  Kucsera Henrik ,  Marx Gábor ,  Megyesi Zoltán ,  Németh Ákos ,  Pete Gábor ,  Szeredi Tibor ,  Tichler Krisztián ,  Zsenei András 
Füzet: 1993/október, 303 - 305. oldal  PDF file
Témakör(ök): Irányított gráfok, Logikai feladatok, Feladat
Hivatkozás(ok):Feladatok: 1992/december: F.2934

Bolondóciában olyan az úthálózat, hogy bármely városba el lehet jutni az utakon; az útszakaszok nem keresztezik egymást (útszakasz: két várost összekötő útdarab, amely közben más várost nem érint). Az utak túlzsúfoltsága miatt az Utazásról Leszoktató Minisztérium (ULM) a következő intézkedéseket hozta:
A) minden útszakaszon egyirányú legyen a forgalom;
B) az útszakaszok irányítása olyan legyen, hogy egy adott időpontban ne létezzék olyan útvonal, amely egy városból kiindulva oda vissza is vezet.
Bolondócia lakosságának egy része bírálta az intézkedés következtében előállított helyzetet, mivel pl. a fővárosba csak bevezető út volt. Ezért az ULM a következőket rendelte el:
C) ha vannak olyan városok, amelyekből csak kivezető út van, akkor közülük az egyiknek a kivezető útszakaszait a következő hét kezdetekor ellentétes irányításúra kell változtatni; a többi útszakasz irányítása változatlan marad.
A Jövőkutató Intézet azonnal hozzálátott annak a vizsgálatához, hogy vajon eljön-e az a hét, amikor a fővárosból minden út kifelé fog vezetni.
Segítsünk nekik!
Olimpiai válogatóvereny 1987.

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.

I. megoldás. Először megmutatjuk, hogy C) végrehajtása után is teljesülni fog a B) feltétel (az A) természetesen mindig tejesülni fog). Legyen V az a város, amelynek kivezető útjait megfordítják, és tegyük fel, hogy ezzel kör keletkezett (olyan útvonal, amelyen egy adott városból kiindulva oda visszajutunk úgy, hogy mindig menetirány szerint haladunk). A kör nem tartalmazhatja V-t, mert C) végrehajtása után V-ből nem indul ki egyetlen kifelé vezető útszakasz sem. Ha viszont a kör nem tartalmazza V-t, akkor a kör útszakaszai a C) végrehajtása előtti állapotban maradtak. Ez pedig azt jelentené, hogy már C) végrehajtása előtt is létezett a kör (ami B) szerint nem lehet).
Másodszor azt bizonyítjuk, hogy ha A) és B) teljesül, akkor biztosan van olyan város, ahonnan minden út kifelé vezet. Tegyük föl, hogy nincs ilyen; megmutatjuk, hogy ekkor az úthálózat biztosan tartalmaz kört, ez pedig ellentmond B)-nek. Induljunk el egy tetszőleges városból, és haladjunk minden szakaszon a menetiránnyal szemben. Az indirekt feltevésünk szerint minden városba létezik bevezető útszakasz, ezért sohasem akadunk el.
Mivel véges sok város van, előbb-utóbb el kell jutnunk egy olyan városba, ahol már jártunk. Ez pedig azt jelenti, hogy tettünk egy körutazást, mindig a menetiránnyal szemben haladva. Ez az utazás visszafelé kört ad. Ezzel ellentmondásra jutottunk; mindig kell tehát léteznie olyan városnak, ahonnan minden út kifelé vezet.
Belátjuk, hogy mindegyik városra végtelen sokszor alkalmazzák a C) szabályt. Ez pedig azt is jelenti, hogy végtelen sok olyan hét lesz, amikor a fővárosból minden út kifelé vezet.
Mivel csak véges sok város van, és a C) intézkedést minden héten végrehajtják, lesz legalább egy olyan város (legyen ez V1), amelyre végtelen sokszor alkalmazzák. Legyen V2 a V1 egyik szomszédja. Mielőtt V1-re alkalmazzák C)-t, a két város közötti szakasz V1-ből vezet V2-be. Ahhoz, hogy V1-re ismét alkalmazzák C)-t, az utat vissza kell fordítani. Ez viszont csak úgy lehetséges, ha közben valamikor V2-re is alkalmazzák. Tehát, ha C)-t már kétszer hajtják végre V1-ben, a kettő között V2-ben is végre kell hajtani. Ebből pedig következik, hogy C)-t V2-re is végtelen sokszor alkalmazzák.
Azt kaptuk tehát, hogy ha egy városra végtelen sokszor alkalmazzák C)-t, akkor a város szomszédaira is végtelen sokszor hajtják végre. Mivel az utakon mindegyik városból mindegyikbe el lehet jutni, ebből az állításunk következik.

 

Megjegyzés. Mivel minden útdarab irányítása végtelen sokszor változik meg, elég sok idő elteltével bármelyik városból bármelyik városba el lehet úgy jutni, hogy mindig az éppen akkor érvényes irányban haladunk.
 

II. megoldás. 1.) Az előző megoldáshoz hasonlóan bizonyítjuk be, hogy A) és B) mindig érvényben marad, és C)-t minden héten végrehajtják.
2.) Legyenek a fővárostól különböző városok V1,V2,...,Vn, és jelölje hi azt a legkisebb számot, ahányszor a menetiránnyal szemben kell haladni, ha hétközben a fővárosból Vi-be utazunk. Tekintsük az S=i=1nhi összeget! Ez egy nemnegatív egész szám. Azt állítjuk, hogy ha C)-t nem a fővárosban hajtják végre, akkor S 1-gyel csökken.
Feltehetjük, hogy C)-t V1-ben hajtják végre. Ekkor h1 1-gyel csökken, mivel a V1-be vezető utak utolsó darabja a jó irányba (befelé) fordul. A többi hi (i=2,...,n) nem változik, mert egy Vi-be vezető út irányaiban csak akkor történik változás, ha az út V1-en keresztül vezet; ilyenkor viszont egy jó útszakaszt (a V1-ből kifelé vezetőt) cserélünk rosszra, és egy rossz útszakaszt (a V1-be befelé vezetőt) cserélünk jóra. Ezzel megmutattuk, hogy S értéke 1-gyel csökken.
Mivel S0 és 1-gyel csökken azokon a heteken, amikor C)-t nem a fővárosban hajtják végre, lehetetlen, hogy C)-t a fővárosban sohase hajtsák végre. (Amikor C)-t a fővárosban alkalmazzák, S értéke n-nel nő.)
Ha viszont C)-t a fővárosban alkalmazni lehet, akkor a fővárosból minden út kifelé vezet.
 

 Csörnyei Mariann (Fazekas M. Főv. Gyak. Gimn., III. o. t.)