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 -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 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 -ket, amelyek bal oldali felei őt alkotják. A dagasztott komponensek tehát összességében lefedik az -t, hiszen egyesítésük az összes -t tartalmazza (az egyesítés valójában meg is egyezik az -vel). Ebből az is következik, hogy a dagasztott komponensek összhossza legalább akkora, mint az 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 -kből kiválaszott bal és jobb felek olyan komponenseket határoznak meg (egyértelműen), amelyeket feldagasztva egy -t fedő intervallum-rendszert kapunk (ellenben most nem igaz általában, hogy a rendszer egyesítése éppen az ). A dagasztott komponensek összhossza tehát legalább akkora, mint az 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.
|