Feladat: Pontversenyen kívüli P.83 Korcsoport: 16-17 Nehézségi fok: nehéz
Megoldó(k):  Bacsó G. ,  Bálint L. ,  Bartolits I. ,  Füredi Z. ,  Geréb M. ,  Katona E. ,  Less Gy. ,  Pásztor Miklós ,  Reviczky J. ,  Stachó B. 
Füzet: 1971/november, 150 - 151. oldal  PDF  |  MathML 
Témakör(ök): Kombinatorikus geometria térben, Teljes indukció módszere, Térgeometria alapjai, Pontversenyen kívüli probléma
Hivatkozás(ok):Feladatok: 1970/november: Pontversenyen kívüli P.83

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.

Az állítást teljes indukcióval bizonyítjuk. Két vagy három út esetén nyilvánvalóan megvalósítható a kívánt formájú kereszteződés-rendszer. Tegyük fel, hogy n út esetén is mindig kialakíthatók a kívánt kereszteződések, s bizonyítsuk az állítást (n+1)-re.
Tekintsünk (n+1) utat, és vegyünk ki közülük tetszőlegesen egyet, jelöljük e-vel. A maradó n út két szintes kereszteződése az indukciós feltevés értelmében megoldható a kívánt módon, és ezek közül a kereszteződések közül egy sem esik e-re, különben lenne olyan pont, amelyben 3 út találkozna.
Tekintsük az e által meghatározott két félsík egyikében levő kereszteződéseket és változtassuk őket az ellenkezőjükre, vagyis mindenütt az az út haladjon felül, amely eddig alul volt.
Kiválasztva most egy tetszőleges f utat az n út közül, alakítsuk ki e-nek és f-nek K kereszteződését úgy, hogy K-ban f akkor és csak akkor haladjon e fölött, ha f-en a K-val szomszédos kereszteződésekben f volt az alsó út. Az eddigiek biztosítják, hogy ha van f-en két, a K-val szomszédos kereszteződés, akkor ezek azonos típusúak f-re nézve, továbbá n≥2 folytán nem lehet, hogy f-en K legyen az egyetlen kereszteződés.
Az e-n levő összes kereszteződést így kialakítva, nyilvánvaló, hogy a követelmény az első n útra teljesül. Azt kell még bizonyítani, hogy e-n is váltakozva követik egymást a kereszteződések. Legyen A és B két szomszédos kereszteződés e-n, legyenek f és g az itt átmetsző utak, s legyen C az f és g kereszteződése. Azt kell megmutatnunk, hogy A és B ellentétes típusú pontok e szempontjából. Ez egyenértékű azzal, hogy A és B ellentétes pontok f, ill. g szempontjából (tehát ha A-nál f felül halad, akkor B-nél g alul van, vagy megfordítva).
Az AC és BC szakasz belsejében ugyanannyi kereszteződés van. Ugyanis ha egy egyenes egy háromszög egyik oldalszakaszát belső pontjában metszi, akkor metszi a háromszög valamelyik másik oldalszakaszát is.

 

 

Mivel pedig A és B szomszédosak az e-n, azért az AB szakaszt a rendszer egyik egyenese sem metszi, tehát minden olyan út, mely a belsejében metszi AC-t, metszi BC-t is, és BC-t csak ilyenek metszik. Eszerint f-en és g-n ugyanannyi szintváltás van C-től e-ig haladva. És mivel C eleve ellentétes típusú kereszteződés f és g szempontjából, azért A és B valóban ellentétes pontok f és g szempontjából is, tehát különböző szintű kereszteződések e-n. Ezzel a bizonyítást befejeztük.
 

Pásztor Miklós (Budapest, Ságvári E. Gyak. Gimn.)
 

Megjegyzések. 1. A bizonyítás csekély módosításával belátható, hogy az állítás akkor is igaz, ha az utak között párhuzamosak is szerepelhetnek.
2. Nem használtuk ki lényegesen, hogy az utak egyenesek. Valóban, elegendő lenne kikötni, hogy az útrendszernek megvan a következő 3 tulajdonsága: 1. bármely kereszteződésben két út találkozik. (Könnyű látni, hogy ez a feltétel nem hagyható el !) 2. Bármely két útnak legföljebb egy kereszteződése van; 3. Ha egy út metsz egy, a többiek által meghatározott zárt síkidomot, akkor azt kétszer is metszi.