Feladat: N.37 Korcsoport: 18- Nehézségi fok: nehéz
Megoldó(k):  Braun Gábor ,  Burcsi Péter ,  Gyarmati Katalin ,  Póczos Barnabás ,  Tóth Gábor Zsolt ,  Újváry-Menyhárt Mónika 
Füzet: 1995/március, 163. oldal  PDF file
Témakör(ök): Számhalmazok, Konstruktív megoldási módszer, Periodikus sorozatok, Rekurzív sorozatok, Maradékos osztás, kongruenciák, Nehéz feladat
Hivatkozás(ok):Feladatok: 1994/szeptember: N.37

Létezik-e természetes számoknak olyan sorozata, amely minden természetes számot végtelen sokszor tartalmaz, és amely minden pozitív egész m esetén periodikus mod m?

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.

Megmutatjuk, hogy a feladat kérdésére igenlő a válasz. Ehhez rekurzióval megadunk egy sorozatot, amely megfelel a kívánalmaknak. Kezdjük a sorozatot a 0, 1 számokkal. Tegyük fel, hogy eljutottunk a sorozatnak egy olyan részéig, amelyben k szám szerepel, és minden szám előfordul 0-tól (n-1)!-1-ig, továbbá minden m(n-2)!-1 pozitív egészre van olyan l<k és lk, hogy az i-edik és (i+l)-edik elem egyenlő (mod m). Ilyenkor a sorozat következő k eleme egyezzen meg az első k-val (ismételjük meg). Majd legyen 0<i2k esetén

ai+2k=ai+(n-1)!ai+22k=ai+2(n-1)!ai+(n-1)2k=ai+(n-1)(n-1)!,
így k2=n2k-ra szintén teljesül:
*‐szerepel minden (n!-1)-nél nem nagyobb szám.
*‐minden m((n-1)!-1)-hez létezik l<k2, lk2, hogy ai=ai+l(modm) minden i-re.
(Egy m számhoz valamelyik lépésben adódó periódus ‐ ugyanehhez az m-hez ‐ a későbbiekben is megfelelő lesz.) A konstrukciót folytatva előbb-utóbb eljutunk minden természetes számhoz. Azt, hogy minden szám végtelen sokszor fordul elő, az garantálja, hogy minden lépésben ,,megduplázzuk a sorozatot'', így ha egy szám szerepel legalább egyszer (de minden szám ilyen), akkor tetszőleges α-ra szerepelni fog 2α-szor is (α>0 egész), tehát végtelen sokszor.
Tehát konstruált sorozatunk a kívánt tulajdonságú.
 Burcsi Péter (Pápa, Türr I. Gimn., III. o.t.)