Feladat: N.155 Korcsoport: 18- Nehézségi fok: nehéz
Megoldó(k):  Bérczi Gergely ,  Devecsery András ,  Gerbicz Róbert ,  Gueth Krisztián ,  Gyenes Zoltán ,  Horváth Gábor ,  Juhász András ,  Kun Gábor ,  Lippner Gábor ,  Lukács László ,  Máthé András ,  Mecz Balázs ,  Pap Júlia ,  Székelyhidi Gábor ,  Terpai Tamás ,  Végh A. László ,  Zábrádi Gergely 
Füzet: 1998/április, 229 - 230. oldal  PDF file
Témakör(ök): Osztók száma, Legnagyobb közös osztó, Teljes indukció módszere, Halmazelmélet, Nehéz feladat
Hivatkozás(ok):Feladatok: 1997/december: N.155

Bizonyítsuk be, hogy ha egy pozitív egészekből álló végtelen sorozatban mindegyik elemnek ugyanannyi osztója van, akkor létezik olyan végtelen részsorozata, amelyben bármelyik két elem legnagyobb közös osztója ugyanaz.

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 n osztója van, akkor létezik a kívánt részsorozat.
Teljes indukciót alkalmazunk. Ha n=1, akkor mindegyik elem 1, és a teljes sorozat megfelelő.
Tegyük fel, hogy állításunk igaz n=k esetén, és tekintsünk egy olyan pozitív egészekből álló a1, a2, ... sorozatot, amelyben mindegyik elemnek legfeljebb k+1 osztója van.
Két esetet fogunk vizsgálni:
1. eset: Létezik olyan p prímszám, amely végtelen sok elemnek osztója. Legyenek ezek az elemek ai1, ai2, ... és tekintsük az ai1p, ai2p, ... sorozatot. Ebben mindegyik elemnek legfeljebb k osztója van, ezért az indukciós feltevés szerint kiválasztható belőle egy olyan aj1p, aj2p, ... részsorozat, amelyben bármelyik két elem legnagyobb közös osztója ugyanaz a d szám. Ekkor viszont az aj1, aj2, ... sorozatban bármely két elem legnagyobb közös osztója pd. 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 i1=1. Ha már definiáltuk i1, i2, ..., im-et, akkor legyen im+1 az első olyan pozitív egész, amely nagyobb im-nél, és amelyre aim+1 relatív prím az ai1, ..., aim elemek mindegyikéhez. Ilyen elem létezik, mert az ai1, ..., aim 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 H1, H2, ... halmazsorozat legfeljebb n elemű halmazokból áll, akkor kiválasztható egy olyan részsorozata, amelyben bármelyik két halmaz metszetének elemszáma ugyanaz.