Kezdőlap


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 \| MathML
Témakör(ök):	Irányított gráfok, Logikai feladatok, Feladat
Hivatkozás(ok):	Feladatok: 1992/december: F.2934

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 $V_{1}$ ), amelyre végtelen sokszor alkalmazzák. Legyen $V_{2}$ a $V_{1}$ egyik szomszédja. Mielőtt $V_{1}$ -re alkalmazzák C)-t, a két város közötti szakasz $V_{1}$ -ből vezet $V_{2}$ -be. Ahhoz, hogy $V_{1}$ -re ismét alkalmazzák C)-t, az utat vissza kell fordítani. Ez viszont csak úgy lehetséges, ha közben valamikor $V_{2}$ -re is alkalmazzák. Tehát, ha C)-t már kétszer hajtják végre $V_{1}$ -ben, a kettő között $V_{2}$ -ben is végre kell hajtani. Ebből pedig következik, hogy C)-t $V_{2}$ -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

V_{1}, V_{2}, ..., V_{n}

, és jelölje

h_{i}

azt a legkisebb számot, ahányszor a menetiránnyal szemben kell haladni, ha hétközben a fővárosból

V_{i}

-be utazunk. Tekintsük az

S = \sum_{i = 1}^{n} h_{i}

ö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

V_{1}

-ben hajtják végre. Ekkor

h_{1}

1-gyel csökken, mivel a

V_{1}

-be vezető utak utolsó darabja a jó irányba (befelé) fordul. A többi

h_{i}

(i = 2, ..., n)

nem változik, mert egy

V_{i}

-be vezető út irányaiban csak akkor történik változás, ha az út

V_{1}

-en keresztül vezet; ilyenkor viszont egy jó útszakaszt (a

V_{1}

-ből kifelé vezetőt) cserélünk rosszra, és egy rossz útszakaszt (a

V_{1}

-be befelé vezetőt) cserélünk jóra. Ezzel megmutattuk, hogy

S

értéke

1

-gyel csökken.
Mivel

S ⩾ 0

é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.)