Feladat: F.2934 Korcsoport: 18- Nehézségi fok: nehéz
Füzet: 1992/december, 461 - 462. oldal  PDF  |  MathML 
Témakör(ök): Irányított gráfok, Logikai feladatok, Feladat
Hivatkozás(ok):Feladatok megoldásai: 1993/október: 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.

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.