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. Legyen a feltételnek megfelelő módon megadott intervallumok jobb végpontjainak legkisebbike ; hagyjuk el az intervallumok közül mindazokat ‐ a feltétel szerint legfeljebb hármat ‐, amelyek -et tartalmazzák. A megmaradó intervallumok egyike sem tartalmazza -et, rájuk a fenti eljárást megismételve a végpontot kapjuk, és ismét legfeljebb három újabb intervallumot hagyhatunk el. További intervallumunk viszont már egyáltalán nem maradhat, hiszen egy ilyennek sem a , sem pedig a végpontúval nem lehet közös pontja, e kettőnek pedig egymással szintén nincsen. Azt kaptuk, hogy legfeljebb intervallum adható meg az előírt módon. Ez viszont lehetséges is, ha közülük hármat-hármat ,,egymásba skatulyázunk''.
Megjegyzés. A megoldás során lényegében azt láttuk be, hogy ha intervallumok egy rendszerében bármely három között van két metsző, akkor létezik legfeljebb két pont ‐ ezek voltak és ‐ amelyek valamennyi intervallumot ,,lefogják'', azaz mindegyik intervallum tartalmaz a pontok közül legalább egyet. Ez általában is igaz. Intervallumok bármely rendszerében az intervallumrendszert lefogó pontok számának a minimuma egyenlő a páronként közös pontok nélkül megadható intervallumok számának a maximumával. Ennél kevesebb pont nyilván nem elegendő valamennyi intervallum lefogásához, hiszen diszjunkt intervallumok lefogásához különböző pontokra van szükség. Az pedig, hogy ennyi ponttal megvalósítható valamennyi intervallum lefogása, éppen a megoldás gondolatmenetével igazolható, hiszen a kiválasztott végpontok egy diszjunkt intervallumrendszer végpontjai. |