Feladat: 2008. évi Kürschák matematikaverseny 3. feladata Korcsoport: 18- Nehézségi fok: nehéz
Füzet: 2009/február, 70 - 72. oldal  PDF  |  MathML 
Témakör(ök): Kürschák József (korábban Eötvös Loránd), Teljes indukció módszere, Gráfelmélet
Hivatkozás(ok):Feladatok: 2009/február: 2008. évi Kürschák matematikaverseny 3. feladata

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. Azt mondjuk, hogy az a városból elérhető a b város, ha csak vonaton vagy csak buszon el lehet jutni (esetleg átszállásokkal) a-ból b-be. A feladatot az országban található városok n száma szerinti indukcióval oldjuk meg. A feladat állítása n=1 esetén világos. Tegyük fel tehát, hogy n-nél kevesebb városra már igazoltuk az állítást, és tekintsünk egy n városból álló országot a leírt feltételekkel.
Legyen v az ország egy tetszőleges városa, és tekintsük a v-től különböző n-1 várost. Ezen n-1 város közül bármely kettőre igaz, hogy valamelyikükből (esetleg v-n is átutazva) elérhető a másik. Módosítsuk az n-1 városból álló hálózatot (gondolatban) úgy, hogy a létező járatok mellett odaképzeljük azokat is, amelyek csak v-n átutazva valósíthatóak meg. Az így kibővített, n-1 városból álló hálózatra alkalmazhatjuk az indukciós feltevést, tehát van egy olyan f(v) város az n-1 között, amelyből minden v-től különböző város elérhető. Ha v is elérhető f(v)-ből, akkor készen vagyunk, hiszen f(v) megfelel a kívánalmaknak.
Ha tehát v nem érhető el f(v)-ből, akkor a feltétel szerint f(v) elérhető v-ből, és az általánosság megszorítása nélkül az is feltehető, hogy ez busszal lehetséges. Legyen B, illetve V az f(v)-ből busszal, illetve vasúton elérhető, f(v)-től különböző városok halmaza. Tekintsük a városok V':=V∪{v} halmazát. Mivel f(v) nincs V'-ben, azért V' legfeljebb n-1 várost tartalmaz. Az is igaz, hogy V' bármely két városa közül egyikből elérhető a másik (esetleg V'-n kívüli városok érintésével). A korábban látott módon alkalmazhatjuk az indukciós feltevést V'-re, így van benne olyan v' város, amelyből minden V'-beli város elérhető.
Ha v'=v ez a város, akkor v megfelel a feladat kívánalmainak, hiszen v-ből minden V-beli város elérhető v' választása miatt, és azt is láttuk, hogy busszal v-ből f(v) és az összes B-beli város is elérhető.
Ha pedig v'≠v, akkor v'∈V, és ekkor v'-ből V minden városa és v is elérhető. Ha v vonattal érhető el v'-ból, akkor v elérhető lenne vonattal v'-n keresztül f(v)-ből is, amiről korábban feltettük, hogy lehetetlen. Ezek szerint v busszal érhető el v'-ből. Azonban ekkor v-n keresztül f(v) és így B minden városa is elérhető v'-ből busszal, ami éppen azt jelenti, hogy v' rendelkezik a feladatban megkövetelt tulajdonsággal.  □
A fenti bizonyításban az indukciós lépés ,,ravasz''. Az indukciót azonban a fenti megoldás első két bekezdése után máshogyan is befejezhetjük.

 
II. megoldás. Ha az ország valamelyik v városa elérhető f(v)-ből, akkor készen vagyunk, hisz ekkor f(v)-ből minden város elérhető. Tegyük fel tehát, hogy ez egyetlen v városra sem igaz, így a feladatbeli feltétel szerint bármelyik v városból elérhető f(v).
Legyen v egy tetszőleges város, és tekintsük a városok
v,f(v),f(f(v)),f(f(f(v))),...
sorozatát. Mivel véges sok város van, ezért a sorozatban előbb-utóbb felbukkan egy már korábban felsorolt város is. Találunk tehát egymástól különböző v1,v2,...,vk városokat úgy, hogy i=1,2,...,k-ra
f(vi)=vi+1 teljesül (ahol vk+1=v1). A v2,...,vk,vk+1 városok tehát rendelkeznek azzal a tulajdonsággal, hogy tetszőleges vi-ből vi-1 kivételével minden másik vj város elérhető. Ez azt is jelenti, hogy k≥3, hiszen v1-ből v2 elérhető, de vk nem.
Tegyük fel, hogy valamelyik vi-1-ből vi vonattal, míg vi-ből vi+1 busszal érhető el. Tudjuk, hogy vi+1-ből vi-1 elérhető. Ha ez busszal lehetséges, akkor vi-ből busszal vi+1-ben átszállva vi-1-be juthatunk, amiről feltettük, hogy nem lehetséges. Ha vi+1-ből vonattal lehet vi-1-be eljutni, akkor innen vonattal továbbutazhatunk vi-be, ami f(vi)=vi+1 miatt szintén nem lehetséges. Azt kaptuk tehát, hogy a vi-1-ből vi-be jutás eszközének azonosnak kell lennie a vi-ből vi+1-be jutás eszközével.
Ha tehát v1-ből busszal juthatunk v2-be, akkor v2-ből v3 is busszal érhető el, majd v3-ból v4-be is busszal juthatunk, és így tovább egészen vk-ig. Vagyis v1-ből vk elérhető, ami ellentmond annak a feltevésünknek, hogy egyetlen v város sem érhető el f(v)-ből. Kell lennie tehát olyan v városnak, ami f(v)-ből elérhető, ám ekkor f(v) rendelkezik a feladatban megkövetelt tulajdonsággal.  □
 
Megjegyzések. 1. Kettőnél több közlekedési eszköz esetén már nincs feltétlenül olyan város, ahonnan minden más város elérhető. Ez a helyzet, ha például A-ból B-be busz, B-ből C-be vonat és C-ből A-ba mondjuk kishajó közlekedik.
2. Ha nem tesszük fel, hogy bármely két város között van valamelyik irányba közlekedés, akkor nem mindig létezik olyan város, amelyikből minden másik elérhető. Igaz azonban, hogy található városoknak egy olyan V halmaza, hogy semelyik V-beli városból sem érhető el semelyik másik V-beli város, azonban bármelyik V-n kívüli város elérhető valamelyik V-beli városból. Nem látszik, hogy a fent közölt megoldások bármelyike kiterjeszthető-e az általánosabb állítás bizonyításává.
3. A közölt megoldások egyike sem algoritmikus, azaz egy kívánt tulajdonságú város megtalálására nem ad annál jobb módszert, mint hogy sorra ellenőrizzük az egyes városokat. Létezik olyan (n-től független) c konstans, hogy tetszőleges városról el tudjuk dönteni cn lépésben, hogy rendelkezik-e a kívánt tulajdonsággal (ahol n az ország városainak számát jelöli), így az egymás utáni ellenőrzéseket legfeljebb cn2 lépésben el tudjuk végezni. A 2. megjegyzésben jelzett V halmaz megtalálása a részhalmazok egyenkénti ellenőrzésével már sokkal több lépést igényelne. Létezik azonban olyan A algoritmus és C konstans, hogy bármely n városból álló országban az A algoritmus legfeljebb C⋅n2 lépés után megtalál egy, a 2. megjegyzésben leírt V városhalmazt.
4. A feladat bizonyos rokonságot mutat Gale és Shapley (sajnos nem eléggé) ismert ,,stabil házassági'' tételével. A részleteket egy remélhetőleg hamarosan megjelenő KöMaL cikk tartalmazza.