Feladat: N.27 Korcsoport: 18- Nehézségi fok: nehéz
Megoldó(k):  Braun Gábor ,  Csörnyei Marianna ,  Elek Péter ,  Futó Gábor ,  Gyarmati Katalin ,  Megyesi Zoltán ,  Pap Gyula ,  Pete Gábor ,  Szeidl Ádám 
Füzet: 1995/január, 37 - 38. oldal  PDF  |  MathML 
Témakör(ök): Halmazelmélet, Konstruktív megoldási módszer, Lefedések, Nehéz feladat
Hivatkozás(ok):Feladatok: 1994/március: N.27

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 egyszerűség kedvéért feltesszük, hogy a feladatban és a megoldásban szereplő intervallumok zártak ‐ ez nem megy az általánosság rovására.
a) Egy intervallum ,,dagasztásán'' értsük azt a műveletet, hogy az intervallumot bal végpontjából a kétszeresére nagyítjuk. Könnyen látható, hogy a dagasztás monoton abban az értelemben, hogy megőrzi a tartalmazás kapcsolatot. Tekintsük a feladatbeli Ij-k bal oldali felei által lefedett területet. Ez a terület előáll páronként diszjunkt intervallumok, ún. komponensek egyesítéseként. (A komponensekre bontás valójában egyértelmű, de erre nem lesz szükségünk.) Egy ilyen komponens a megoldás elején tett megállapodás folytán vagy teljesen tartalmazza egy Ij bal oldali felét, vagy diszjunkt tőle. Ezért, és a monotonitás miatt a komponens dagasztott képe magába foglalja mindazokat az Ij-ket, amelyek bal oldali felei őt alkotják. A dagasztott komponensek tehát összességében lefedik az I-t, hiszen egyesítésük az összes Ij-t tartalmazza (az egyesítés valójában meg is egyezik az I-vel). Ebből az is következik, hogy a dagasztott komponensek összhossza legalább akkora, mint az I intervallumé ‐ ami éppen a bizonyítandó állítás, hiszen a dagasztás minden intervallum hosszát megkétszerezi.
b) Hasonlóképpen járunk el, mint az a) esetben, csak most egy intervallum dagasztásának azt a műveletet nevezzük, hogy az intervallumot középpontjából a háromszorosára nagyítjuk. A dagasztás most is monoton, és az Ij-kből kiválaszott bal és jobb felek olyan komponenseket határoznak meg (egyértelműen), amelyeket feldagasztva egy I-t fedő intervallum-rendszert kapunk (ellenben most nem igaz általában, hogy a rendszer egyesítése éppen az I). A dagasztott komponensek összhossza tehát legalább akkora, mint az I intervallumé ‐ és ezt kellett igazolnunk, hiszen a dagasztás az intervallumok hosszát most megháromszorozza.

 Pap Gyula (Debrecen, Fazekas M. Gimn., I. o.t.) és
 
 Futó Gábor (Fazekas M. Főv. Gyak. Gimn., IV. o.t.) dolgozata alapján

 
Megjegyzés. A feladatbeli állítások élesek, és a megoldásból az is kiolvasható, hogy mely rendszerekre nem javíthatók a becslések.