Feladat: B.3696 Korcsoport: 16-17 Nehézségi fok: átlagos
Megoldó(k):  Bednay Dezső ,  Csajbók Bence ,  Filus Tamás ,  Gehér György ,  Hannák Gábor ,  Hubai Tamás ,  Kiss-Tóth Christián ,  Kőrizs Beatrix ,  Kovács Péter ,  Kunovszki Péter ,  Nagy Csaba ,  Nándori Péter ,  Nikházy László ,  Pálinkás Csaba ,  Stippinger Marcell ,  Strenner Balázs ,  Szabó Botond ,  Szabó Tamás ,  Szalóki Dávid ,  Szilágyi Dániel ,  Udvari Balázs ,  Ureczky Bálint 
Füzet: 2004/október, 415. oldal  PDF file
Témakör(ök): Síkbeli ponthalmazok távolsága, Indirekt bizonyítási mód, Feladat
Hivatkozás(ok):Feladatok: 2004/január: B.3696

Adott egy egyenesen néhány nyílt félegyenes; ezek végpontjai az egyenest részekre osztják. Igazoljuk, hogy a pontosan q számú félegyenes által lefedett részek száma legfeljebb q+1.

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.

Megoldás. Az egyszerűség kedvéért azonosítsuk az egyenest a számegyenessel. Ekkor mindegyik félegyenes vagy ,,jobbra végtelen'' (azaz a (+)-t tartalmazza), vagy ,,balra végtelen'' (azaz a (-)-t tartalmazza). A pontosan q számú félegyenes által lefedett részek (q+1)-félék lehetnek aszerint, hogy hány jobbra végtelen félegyenes tartalmazza őket (mert ezen félegyenesek száma legalább 0 és legfeljebb q).
Ezután indirekt módon bizonyítjuk állításunkat. Tegyük fel, hogy létezik a félegyeneseknek olyan elrendezése, amelyben legalább q+2 részt fed le pontosan q darab félegyenes. Ekkor a skatulya-elv miatt van legalább két egymástól különböző rész, amelyeket ugyanannyi jobbra végtelen félegyenes fed le, amiből persze az is következik, hogy a két részt lefedő balra végtelen félegyenesek száma is egyenlő.

 
 

Ha viszont a két rész I=]p,r[ és J=]s,t[, ahol a jelölést úgy választjuk, hogy rs, (lásd az ábrát), akkor minden I-t tartalmazó jobbra nyílt félegyenes J-t is tartalmazza, míg minden J-t tartalmazó balra nyílt félegyenes I-t is tartalmazza. Ezért nem lehet az adott félegyenesek közt olyan, amelynek kezdőpontja az [r,s] zárt intervallumba esik, mert ez a félegyenes I és J közül csak pontosan az egyiket tartalmazná. Tehát ellentmondásra jutottunk, s ezzel a bizonyítást befejeztük.