Feladat: Gy.2480 Korcsoport: 16-17 Nehézségi fok: átlagos
Füzet: 1988/november, 388 - 389. oldal  PDF  |  MathML 
Témakör(ök): Ponthalmazok, Halmazalgebra, Halmazok számossága, Gyakorlat
Hivatkozás(ok):Feladatok: 1988/április: Gy.2480

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 J1; hagyjuk el az intervallumok közül mindazokat ‐ a feltétel szerint legfeljebb hármat ‐, amelyek J1-et tartalmazzák. A megmaradó intervallumok egyike sem tartalmazza J1-et, rájuk a fenti eljárást megismételve a J2 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 J1, sem pedig a J2 végpontúval nem lehet közös pontja, e kettőnek pedig egymással szintén nincsen.
Azt kaptuk, hogy legfeljebb 6 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 J1 és J2 ‐ 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 J1,J2,...Jk végpontok egy diszjunkt intervallumrendszer végpontjai.