Kezdőlap


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 \| MathML
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

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 \leq (n - 2)! - 1$ pozitív egészre van olyan $l < k$ és $l ∣ k$ , 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 < i \leq 2 k$ esetén

\begin{matrix} \begin{matrix} a_{i + 2 k} & = a_{i} + (n - 1)! \\ a_{i + 2 \cdot 2 k} & = a_{i} + 2 \cdot (n - 1)! \\ ⋮ \\ a_{i + (n - 1) \cdot 2 k} & = a_{i} + (n - 1) (n - 1)!, \end{matrix} \end{matrix}

így

k_{2} = n \cdot 2 k

-ra szintén teljesül:

*	‐szerepel minden $(n! - 1)$ -nél nem nagyobb szám.

*	‐minden $m \leq ((n - 1)! - 1)$ -hez létezik $l < k_{2}$ , $l ∣ k_{2}$ , hogy $a_{i} = a_{i + l} (mod m)$ 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.)