Kezdőlap


Feladat:	B.3933	Korcsoport: 18-	Nehézségi fok: átlagos
Megoldó(k):	Paripás Viktor , Szalkai Balázs
Füzet:	2008/február, 92 - 93. oldal		PDF \| MathML
Témakör(ök):	Rekurzív sorozatok, Feladat
Hivatkozás(ok):	Feladatok: 2006/október: B.3933

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.

I. megoldás.

\begin{matrix} a_{2006} & = & a_{1003} = 1 - a_{501} = 1 - (1 - a_{250}) = a_{125} = 1 - a_{62} = 1 - a_{31} = \\ = & 1 - (1 - a_{15}) = a_{15} = 1 - a_{7} = 1 - (1 - a_{3}) = a_{3} = 1 - a_{1} = 0. \end{matrix}

II. megoldás. Megmutatjuk, hogy az

a_{n}

sorozat egyenlő a következő szabállyal értelmezett

b_{n}

sorozattal:

\begin{matrix} b_{n} = {\begin{matrix} 1, & han2-es számrendszerbeli felírásában páratlan sok 1-es van; \\ 0, & egyébként. \end{matrix} \end{matrix}

Nyilván

b_{1} = 1

, hiszen az 1 felírásához egyetlen 1-es szükséges. Az

n

szám 2-es számrendszerbeli alakjából a

2 n

felírását úgy kaphatjuk, hogy a számjegysor végére egy nullát illesztünk; az 1-esek száma ezzel nem változik, így

b_{2 n} = b_{n}

. Végül

(2 n + 1)

-nek a 2-es számrendszerbeli alakja a

2 n

-ből az 1 hozzáadásával nyerhető; az utóbbi ‐ mint láttuk ‐ nullára végződik, tehát 1-et hozzáadva az utolsó nulla számjegy 1-esre változik, ezzel az 1-esek száma eggyel nő, az 1-esek számának paritása éppen az ellenkező lesz. Így

b_{2 n + 1} = 1 - b_{2 n} = 1 - b_{n}

. A

b_{n}

sorozat ugyanannak a rekurziónak és kezdeti feltételnek tesz eleget, mint az

a_{n}

sorozat, ezért

a_{n} = b_{n}

, minden

n

-re. A 2006 felírása a 2-es számrendszerben 11111010110, így

a_{2006} = b_{2006} = 0