Feladat: 1972. évi Kürschák matematikaverseny 3. feladata Korcsoport: 18- Nehézségi fok: nehéz
Megoldó(k):  Prőhle Péter 
Füzet: 1973/február, 53 - 57. oldal  PDF  |  MathML 
Témakör(ök): Négyzetek, Kombinatorikus geometria síkban, Szélsőérték differenciálszámítással, Kürschák József (korábban Eötvös Loránd)
Hivatkozás(ok):Feladatok: 1973/január: 1972. é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. Fusson a két autóút a terület északi és déli oldalán, és jelöljük a megfigyelő állomásokat nyugatról keletre haladva A1, A2, A3, A4-gyel, a négyzet nyugati határától mért távolságukat a1, a2, a3, a4-gyel. Ezek között egyenlők is lehetnek, ez esetben az állomások jelölése tetszőleges. Eszerint a1≤a2≤a3≤a4.
Ha a3-a2≤5km, akkor építsünk egy bekötőutat autóúttól autóútig A2 és A3 között, illetőleg a kettőn keresztül, ha a2=a3, továbbá mindegyik állomástól eddig az útig egy nyugat‐keleti bekötőutat. Az előbbi út hossza 10km, az A1-től és A4-től épített utak összhossza a4-a1≤10km, az A2-től és A3-ból épített utaké a3-a2≥5km a feltétel szerint. Az egész úthálózat hossza tehát legfeljebb 25km.
Ha a3-a2≥5km, akkor építsünk egy‐egy észak‐déli bekötőutat A1 és A2 közt is, meg A3 és A4 között is, ill. a megfigyelőállomásokon át, ha a1=a2 vagy a3=a4, továbbá A1-ből és A2-ből az elsőig, A3-ból és A4-ből a másodikig nyugat‐keleti bekötőutakat. Ennek az útrendszernek a hossza

20+a2-a1+a4-a3=20+(a4-a1)-(a3-a2)≤20+10-5=25km,  
tehát ebben az esetben is van legfeljebb 25km-es úthálózat a kívánt tulajdonságokkal (1. ábra a) és b) része).
 
 

1. ábra
 

Megmutatjuk, hogy 25km-nél rövidebb úthálózattal nem oldható meg a feladat, ha pl. a megfigyelő állomások a terület határán vannak a délnyugati saroktól északra, az északnyugatitól keletre, az északkeletitől délre és a délkeletitől nyugatra 2,5-2,5km-re. Ebben a sorrendben jelöljük őket A1, A2, A4, A3-mal.
Egy legrövidebb úthálózat legfeljebb két egymással össze nem függő részből állhat, mert ha legalább háromból áll, akkor már az észak‐déli irányú útszakaszok legalább 30km-t tesznek ki. Ha két részből áll, akkor van legalább 20km-nyi észak‐déli szakasza. Ebben az esetben valamelyik rész legalább két állomást tartalmaz. Ha A1-ből A3-at vagy A4-et, vagy A4-ből A2-t el lehet érni, akkor a nyugat‐keleti irányú szakaszok összesen legalább 7,5km-t tesznek ki, ha pedig A1-ből A2-t, A3-ból A4-et lehet csak elérni, ehhez tegalább kétszer 2,5km-nyi nyugat‐keleti irányú útszakasz szükséges.
Ha végül mindegyik állomásról bármelyikre el lehet jutni bekötőutakon haladva, akkor tekintsük az úthálózatnak A1-ből A4-be vezető részét és azt a pontot, ahol ezt A2-ből, ill. A3-ból először érhetjük el. Ha A1-ből indulva előbb az A2 felé vezető elágazást érjük el, akkor van az úthálózatnak egy A1, A2 közti és egy A3, A4 közti része, amelyeknek nincs közös pontja; ezeknek legalább 7,5‐7,5 km-nyi észak‐déli szakasza van, az egész hálózat nyugat‐keleti szakaszai viszont legalább 10km-t tesznek ki. Ha viszont az A3-ba vezető elágazást érjük el előbb, vagy négyes útkereszteződés van, akkor A1, A3 és A2, A4 közt van olyan összeköttetés, amelyeknek legfeljebb egy közös pontja van, és egész hasonlóan látható, hogy ekkor legalább 15km-nyi nyugat‐keleti és 10km-nyi észak‐déli útszakasz van (2. ábra a) és b) része). ‐ Evvel a feladatot teljes egészében megoldottuk.
 
 

2. ábra
 

 
Megjegyzés. A megoldás első része mutatja, hogy 25km-nél rövidebb útrendszer is van, ha A1 és A4 nem a terület nyugati és keleti határvonalán van, és akkor is, ha a3-a2 nem éppen 5km. A megoldás ezen részében szereplő első útrendszerhez hasonló szerkeszthető az észak‐déli és nyugat‐keleti irány szerepének megcserélésével is, ami bizonyos feltételek mellett ismét 25km-nél nem hosszabb útrendszert szolgáltat. Ebből további szükséges feltételek lesznek leolvashatók.
Építsünk egy n nyugat‐keleti utat az egész területen át, amelyiktől két megfigyelő állomás északra van, kettő délre (esetleg két állomáson áthalad, a másik kettőt elválasztja, vagy legalább három állomáson áthalad). Ezután a legészakibb állomáson vagy az ilyenek egyikén át az északi autóúttól, a legdélibb állomáson vagy azok egyikén át a déli autóúttól n-ig észak‐déli bekötőutat építünk és a másik két állomástól n-ig szintén (3. ábra). Ha az utolsó két út hossza b3 és b4, akkor az egész útrendszeré 20+b3+b4, és ez kisebb, mint 25km, ha b3+b4<5km.
 
 

3. ábra
 

Ha az n-en keletkező északi elágazások és déli elágazások nem választják el egymást, akkor az úthálózat hossza 20km-re csökkenthető. Mozdítsuk el ugyanis n-nek a nyugati határtól a második elágazásig terjedő részét arra, amerre az elágazások vezetnek a közelebbi állomásig, és hasonlóan módosítsuk a harmadik elágazástól a terület határáig terjedő részét is. Az új útrendszer legföljebb 20km hosszú (4. ábra).
 
 

4. ábra
 

Azt kaptuk tehát, hogy csak akkor nem elegendő 25km-nél rövidebb úthálózat, ha a következő feltételek teljesülnek:
a) A terület nyugati és keleti határa mentén is legyen megfigyelőállomás;
b) a területet egy észak‐déli és egy kelet‐nyugati vonallal felosztva úgy, hogy két állomás a vonaltól ne feküdjék keletre, a másik kettő ne nyugatra és hasonlóan a másik vonaltól kettő ne feküdjék délre, a másik kettő ne északra, akkor a keletkező négy téglalap egyike se tartalmazzon a belsejében és határán egynél több állomást;
c) az említett kelet‐nyugati vonalhoz két oldalról legközelebb eső állomás e vonaltól vett távolságának összege éppen 5km legyen;
d) az észak‐déli vonal két oldalán a legközelebbi állomások távolságának összege legalább 5km legyen.
A fenti megoldás második részének gondolatmenetével belátható, hogy ha mind a négy feltétel teljesül, akkor szükség is van mindig 25km-es úthálózatra.
 
II. megoldás. Két úthálózatot tervezünk és utólag választjuk ki a kedvezőbbet. Az egyiknek két észak‐déli útszakasza lesz a terület két határán, a másiknak egy a terület középvonala mentén. (Az 5. ábrán az első úthálózat folytonos, a második pontozott vonallal van rajzolva.) Ezután minden megfigyelőállomástól kelet‐nyugati utat építünk a terület közelebbi határáig, ill. a középvonalig (a középvonalra eső esetleges állomástól tetszés szerint az egyik határig). Világos, hogy a pontozott útrendszeren is el lehet jutni minden állomástól bármelyik autóútig, a (két részből álló) folytonosan kihúzott útrendszer mentén is.
 
 

5. ábra
 

A két úthálózat együtt 30km észak‐déli és négyszer 5km kelet‐nyugati útszakaszból áll, tehát 50km hosszú, így legalább az egyik legfeljebb 25km-es. Ez (illetőleg bármelyik, ha a kettő egyenlő hosszú) kielégíti a feladat követelményeit.
Szükség van legalább 25km-nyi úthálózatra, ha pl. az A1 és A2 megfigyelő állomás a terület északnyugati és északkeleti sarkában van, A2 és A3 pedig a déli út mentén, a nyugati, ill. keleti határtól 2,5‐2,5 km-re.
Vizsgáljuk először egy, a feltételeket kielégítő bekötő-útrendszer észak‐déli útszakaszait. Ez összesen véges számú útszakasz, egy tetszés szerinti kelet‐nyugati egyenes ezeket véges számú pontban metszi; legalább egyben, mert ellenkező esetben volna olyan kelet‐nyugati egyenes, amelyen nem lehetne átjutni az északi úttól a déli felé.
Minden nyugat‐keleti egyenes első ilyen metszéspontját véve, ezek véges sok útszakaszt futnak be, amelyek összhossza 10km (6. ábra). Hasonlóan, ha minden nyugat‐keleti egyenes legalább két vagy három észak‐déli útszakaszt metsz, akkor a metszéspontok legalább 20, ill. 30km-nyi észak‐déli útszakaszon futnak végig.
 
 

6. ábra
 

Az olyan útrendszerek kedvezőtlenek, amelyeknél mindegyik egyenes legalább 3 metszéspontot szolgáltat. Ha mindegyik egyenesen van legalább 2 metszéspont, de több nem mindegyiken, akkor szemeljünk ki egy egyenest, amelyen két metszéspont van. Mindegyik megfigyelő állomástól el kell tudni jutni valamelyik metszésponthoz, hogy eljuthassunk a nyugat‐keleti vonal másik oldalán levő autóúthoz. Ha A1-ből és A3-ból vagy A2-böl és A4-ből ugyanahhoz a metszésponthoz lehet eljutni, akkor a megfelelő két állomás közt van egy olyan útrész, amelyiknek legalább 7,5km-nyi nyugat‐keleti szakasza van (7a ábra, szaggatott vonal); ha pedig A1 és A2-ből az egyik metszéspont érhető el, A3, és A4-ből a másik, akkor van kétszer 2,5km-nyi nyugat‐keleti útszakasz (7a. ábra, pontozott vonal), és mindkét esetben legalább 20km összhosszú észak‐déli útszakaszok, mint láttuk.
Ha végül van olyan nyugat‐keleti egyenes, amelyiken csak egy metszéspont van, akkor egy ilyen metszésponthoz mindegyik állomásról el lehet jutni (7b. ábra). Ekkor azonban az úthátózatnak az egyenestől északra eső része legalább 10km-nyi nyugat‐keleti útszakaszt tartalmaz, a déli része legalább 5km-nyit, ehhez járul legalább 10km-nyi észak‐ déli útszakasz. Mindig szükség van tehát legalább 25km-es úthálózatra.
 
 

7. ábra
 

 
Megjegyzések. 1. A megoldás első részének gondolatmenete Hangya László megoldása. Ez alkalmas sok további felmerülő kérdés megválaszolására is.
Ha pl. 4 helyett 5 vagy 6 megfigyelőállomás van a területen, akkor a fenti módon megszerkesztett két úthálózat összhossza 55, ill. 60km lesz, így legfeljebb 27,5, ill. 30km hosszú úthálózattal megoldható a feladat.
2. Ugyanesak 30km-t ad korlátul 6 pont esetén a gondolat következő módosított alkalmazása is. Osszuk a területet 4 észak‐déli úttal 3 egyenlő széles részre és mindegyik megfigyelő állomástól az őt közrefogó két útig építünk merőleges bekötőutat. Minden második észak‐déli út a rá merőleges, csatlakozó útszakaszokkal alkotja az egyik útrendszert, a kimaradók a másikat. A két útrendszer összhosszára így
4⋅10+6⋅103=60km  
adódik, mint az előbbi esetben is.
Nem nehéz belátni, hogy legalább 30km-nyi útra szükség is van, ha a megfigyelő állomások pl. a terület két útmenti oldalának közepén és két szélén vannak.
3. 5 állomás esetén van mindig 27,5km-nél rövidebb úthálózat is. A legjobb korlát megkeresését feladatul hagyom.
4. Hasonló okoskodással, alkalmasan választva azt is, hogy hány sávra osztjuk a területet, n pont esetén (2n+1)⋅5km, ill. annál kevéssel nagyobb felső korlát adódik a szükséges úthálózat hosszára.