Kezdőlap


Feladat:	Gy.3176	Korcsoport: 16-17	Nehézségi fok: átlagos
Megoldó(k):	Babos Attila , Bajusz Csaba , Boros M. Mátyás , Buruzs Ádám , Csirmaz Előd , Deli Lajos , Gelencsér Gábor , Gerencsér Balázs , Győri Nikolett , Harangi Viktor , Kunszenti-Kovács Dávid , Lábó Eszter , Lábó Melinda , Lengyel Zoltán , Máthé András , Reviczky Ádám , Ritter Ádám , Schlanger Judit , Somlai Gábor , Taraza Busra , Tillinkó Zsanett , Ureczky Judit , Varga Szilvia , Varjú Péter , Vitéz Ildikó , Zábrádi Gergely , Zempléni Márton
Füzet:	1999/január, 24 - 26. oldal		PDF \| MathML
Témakör(ök):	Rekurzív sorozatok, Teljes indukció módszere, Gyakorlat
Hivatkozás(ok):	Feladatok: 1998/január: Gy.3176

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.

A definíció alapján számítsunk ki néhány további értéket:

\begin{matrix} \begin{matrix} a_{4} & = {max}_{}^{} {2 \cdot 2} = 4, \\ a_{5} & = {max}_{}^{} {2 \cdot 3, 3 \cdot 2} = 6, \\ a_{6} & = {max}_{}^{} {2 \cdot 4, 3 \cdot 3, 4 \cdot 2} = 9, \\ a_{7} & = {max}_{}^{} {2 \cdot 6, 3 \cdot 4, 4 \cdot 3, 6 \cdot 2} = 12, \\ a_{8} & = {max}_{}^{} {2 \cdot 9, 3 \cdot 6, 4 \cdot 4, 6 \cdot 3, 9 \cdot 2} = 18, \end{matrix} \end{matrix}

...

és így tovább. Ezek az eredmények azt sugallják, hogy

n > 1

esetében

a_{n + 3} = 3 \cdot a_{n}

teljesül.^*
Ezt

n

-re vonatkozó teljes indukcióval bizonyítjuk.

n \in {2, 3, 4, 5}

esetében a fenti számolások szerint igaz az állítás. Tegyük most fel, hogy az adott összefüggés igaz minden olyan

k < n

esetén, amelyre

k > 2

.
A sorozat definíciója szerint

a_{n + 3}

\begin{matrix} A_{n + 3} = {a_{2} \cdot a_{n + 1}, a_{3} \cdot a_{n}, ..., a_{n - 2} \cdot a_{5}, a_{n - 1} \cdot a_{4}, a_{n} \cdot a_{3}, a_{n + 1} \cdot a_{2}} \end{matrix}

halmazba eső számok maximuma. Az

A_{n + 3}

-ba eső első

n - 3

szorzat második tényezőjének

i

indexe rendre

n + 1

n

...

, 5. Ezek mindegyike eleget tesz a

4 < i < n + 3

kikötésnek. Az indukciós feltétel szerint ezekre a szorzatokra

a_{d} \cdot a_{n + 3 - d} = 3 \cdot (a_{d} \cdot a_{n - d})

teljesül. Ezek a szorzatok pontosan az

\begin{matrix} A_{n} = {a_{2} \cdot a_{n - 2}, a_{3} \cdot a_{n - 3}, ..., a_{n - 2} \cdot a_{2}} \end{matrix}

halmazba eső szorzatok háromszorosai.
A fennmaradó három szorzat:

{a_{n - 1} \cdot a_{4}, a_{n} \cdot a_{3}, a_{n + 1} \cdot a_{2}}

. Itt viszont az első tényezők mindegyikének az indexe legalább

6 - 1 = 5

. Ezekre alkalmazható az indukciós feltevés; vagyis ez nem más, mint az

{a_{n - 4} \cdot a_{4}, a_{n - 3} \cdot a_{3}, a_{n - 2} \cdot a_{2}}

szorzatok háromszorosai. Ezek a szorzatok viszont már szerepelnek

A_{n}

-ben (hiszen

n > 5

). Ezért az

A_{n + 3}

-ba eső szorzatok pontosan az

A_{n}

-be eső szorzatok háromszorosai, azaz

a_{n + 3} = 3 \cdot a_{n}

valóban igaz.
Mivel

1998 = 3 \cdot 665 + 3

, azért

a_{1998} = 3^{665} \cdot 3 = 3^{666} \approx 579 102 \cdot 10^{312}

Boros M. Mátyás (Budapest, Veres Péter Gimn., 9. o.t.) megoldása alapján

Megjegyzés. Ez a sorozat nem egy ,,kitalált'' képlet. Azok számára, akik valamit hallottak már csoportelméletről, elmondjuk, hogy

a_{n}

-re való rekurzió azt mondja meg, hogy miképpen határozhatjuk meg az

n

-elemű halmaz összes permutációjának csoportjában a maximális méretű kommutatív részcsoport elemszámát; amennyiben ezt kevesebb elemű halmazok esetében már tudjuk.

^* Az

a_{8}

kiszámítására azért volt külön szükség, mert 8 a legnagyobb index, amelyre a szorzatok között szerepel 3-mal nem osztható; ami a teljes indukciós bizonyításban esetszétválasztást tenne szükségessé.