Kezdőlap


Feladat:	Pontversenyen kívüli P.94	Korcsoport: 16-17	Nehézségi fok: nehéz
Megoldó(k):	Bacsó G. , Balog J. , Balogh Z. , Császár Gy. , Füredi Z. , Hermann P. , Katona E. , Komjáth P. , Komornik V. , Móri T. , Nemeskéri I. , Neumann L. , Petz D. , Reviczky J. , Szendrei Ágnes
Füzet:	1971/december, 219 - 220. oldal		PDF \| MathML
Témakör(ök):	Rekurzív eljárások, Permutációk, Fibonacci-sorozat, Pontversenyen kívüli probléma
Hivatkozás(ok):	Feladatok: 1971/február: Pontversenyen kívüli P.94

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.

1. Szemléletesen szólva az $1,2, ..., n$ számoknak csak az olyan permutációit tekintjük, amelyekben minden egyes szám vagy megmarad az alapsorrendbeli helyén, vagy pedig valamelyik szomszédjának a helyét foglalja el. Így a $2,3, ..., n - 1$ számok részére $3$ hely jön szóba, az $1$ és $n$ számok részére pedig csak $2$ hely.
Jelöljük az (1) tulajdonságú $n$ -elemű permutációk számát $p_{n}$ -nel. (1) szerint $i_{n}$ értéke vagy $n$ , vagy $(n - 1)$ . Az első esetben $(i_{1}, i_{2}, ..., i_{n - 1})$ az $1,2, ..., n - 1$ számok permutációja, melyre ugyancsak teljesül (1), ezek száma tehát $p_{n - 1} .$ A második esetben $n$ -nel csak $i_{n - 1}$ lehet egyenlő, tehát $(i_{1}, i_{2}, ..., i_{n - 2})$ az első $(n - 2)$ természetes szám (1) tulajdonságú permutációja. Ezeknek a száma $p_{n - 2}$ , tehát

\begin{matrix} p_{n} = p_{n - 1} + p_{n - 2} . \end{matrix}

(2)

Természetesen (2)-nek csak

n > 2

mellett van értelme, így a

p_{n}

számok meghatározásához szükségünk van az első két értékre, ami nyilván

p_{1} = 1

p_{2} = 2

. Ezek a kezdő értékek (2)-vel együtt már egyértelműen meghatározzák

p_{n}

értékét.
2. A továbbiakban explicit kifejezést keresünk

p_{n}

-re.
Általában az olyan sorozatokat, amelyekre teljesül (2), Fibonacci-féle sorozatoknak nevezzük. (2)-ből közvetlenül következik a Fibonacci-sorozatok következő három tulajdonsága:
a) Ha az

a_{n}

sorozat Fibonacci-sorozat, akkor ilyen típusú a

c_{n} = λ a_{n}

, sorozat is, ahol

λ

tetszőleges valós szám.
b) Ha az

a_{n}

b_{n}

sorozatok Fibonacci-sorozatok, akkor ilyen típusú a

c_{n} = a_{n} + b_{n}

, sorozat is.
c) Az

a_{n} = q^{n}

geometriai sorozat akkor és csakis akkor Fibonacci-sorozat ha

q

gyöke a

\begin{matrix} q^{2} = q + 1 \end{matrix}

egyenletnek, azaz ha

\begin{matrix} vagy q_{1} = \frac{1 + \sqrt[]{5}}{2}, vagy q_{2} = \frac{1 - \sqrt[]{5}}{2} . \end{matrix}

Elegendő tehát olyan

α

β

számokat keresnünk, melyekre a

c_{n} = α q_{1}^{n} + β q_{2}^{n}

sorozat első két tagja rendre megegyezik a fenti

p_{n}

sorozat első két tagjával, akkor minden

n

-re teljesül

p_{n} = c_{n}

. Ilyen számpár a

\begin{matrix} q_{1} α + q_{2} β = p_{1} = 1 q_{1}^{2} α + q_{2}^{2} β = p_{2} = 2 \end{matrix}

egyenletrendszerből:

\begin{matrix} α = \frac{\sqrt[]{5} + 1}{2 \sqrt[]{5}} azaz \frac{q_{1}}{\sqrt[]{5}}, β = \frac{\sqrt[]{5} - 1}{2 \sqrt[]{5}} azaz - \frac{q_{2}}{\sqrt[]{5}}, \end{matrix}

ennélfogva

\begin{matrix} p_{n} = \frac{1}{\sqrt[]{5}} (q_{1}^{n + 1} - q_{2}^{n + 1}) = \frac{1}{\sqrt[]{5}} {{(\frac{1 + \sqrt[]{5}}{2})}^{n + 1} - {(\frac{1 - \sqrt[]{5}}{2})}^{n + 1}} . \end{matrix}

Ezzel megkaptuk

p_{n}

kifejezését kizárólag az

n

indexszel kifejezve. (Könnyű belátni, hogy a kifejezés bármely

n

természetes szám esetén természetes számot ad

p_{n}

-ként.)