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 file
Témakör(ök): Rekurzív sorozatok, Teljes indukció módszere, Gyakorlat
Hivatkozás(ok):Feladatok: 1998/január: Gy.3176

Az (ai) sorozatot a következőképpen definiáljuk: a1=0, a2=2, a3=3, an=max1<d<n{adan-d} (n=4, 5, 6, ...). Határozzuk meg a1998 értékét.

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:

a4=max{22}=4,a5=max{23,32}=6,a6=max{24,33,42}=9,a7=max{26,34,43,62}=12,a8=max{29,36,44,63,92}=18,
... és így tovább. Ezek az eredmények azt sugallják, hogy n>1 esetében an+3=3an teljesül.*
Ezt n-re vonatkozó teljes indukcióval bizonyítjuk. n{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 an+3 az
An+3={a2an+1,a3an,...,an-2a5,an-1a4,ana3,an+1a2}
halmazba eső számok maximuma. Az An+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 adan+3-d=3(adan-d) teljesül. Ezek a szorzatok pontosan az
An={a2an-2,a3an-3,...,an-2a2}
halmazba eső szorzatok háromszorosai.
A fennmaradó három szorzat: {an-1a4,ana3,an+1a2}. 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 {an-4a4,an-3a3,an-2a2} szorzatok háromszorosai. Ezek a szorzatok viszont már szerepelnek An-ben (hiszen n>5). Ezért az An+3-ba eső szorzatok pontosan az An-be eső szorzatok háromszorosai, azaz an+3=3an valóban igaz.
Mivel 1998=3665+3, azért a1998=36653=366657910210312.
 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 an-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 a8 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é.