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. Bebizonyítjuk, hogy ha a sorozat mindegyik elemének legfeljebb osztója van, akkor létezik a kívánt részsorozat. Teljes indukciót alkalmazunk. Ha , akkor mindegyik elem , és a teljes sorozat megfelelő. Tegyük fel, hogy állításunk igaz esetén, és tekintsünk egy olyan pozitív egészekből álló , , sorozatot, amelyben mindegyik elemnek legfeljebb osztója van. Két esetet fogunk vizsgálni: 1. eset: Létezik olyan prímszám, amely végtelen sok elemnek osztója. Legyenek ezek az elemek , , és tekintsük az , , sorozatot. Ebben mindegyik elemnek legfeljebb osztója van, ezért az indukciós feltevés szerint kiválasztható belőle egy olyan , , részsorozat, amelyben bármelyik két elem legnagyobb közös osztója ugyanaz a szám. Ekkor viszont az , , sorozatban bármely két elem legnagyobb közös osztója . Létezik tehát a feltételeknek megfelelő részsorozat. 2. eset: Bármelyik prímszám a sorozat elemei közül csak véges soknak osztója. Ebben az esetben rekurzívan definiálunk egy olyan részsorozatot, amelyben bármely két elem relatív prím. Legyen . Ha már definiáltuk , , , -et, akkor legyen az első olyan pozitív egész, amely nagyobb -nél, és amelyre relatív prím az , , elemek mindegyikéhez. Ilyen elem létezik, mert az , , elemeknek külön-külön és együttesen is csak véges sok prímosztója van, és ez a véges sok prímosztó a sorozat elemei közül összesen csak véges soknak osztója.
Megjegyzés. A feladat valójában a halmazelmélet kategóriájába tartozik. Lényegében ugyanezzel a módszerrel bizonyítható be, hogy ha a , , halmazsorozat legfeljebb elemű halmazokból áll, akkor kiválasztható egy olyan részsorozata, amelyben bármelyik két halmaz metszetének elemszáma ugyanaz.
|