Feladat: 1988. évi Nemzetközi Matematika Diákolimpia 13. feladata Korcsoport: 16-17 Nehézségi fok: nehéz
Megoldó(k):  Csirik János 
Füzet: 1988/október, 292 - 293. oldal  PDF  |  MathML 
Témakör(ök): Függvényegyenletek, Teljes indukció módszere, Kettes alapú számrendszer, Nemzetközi Matematikai Diákolimpia
Hivatkozás(ok):Feladatok: 1988/szeptember: 1988. évi Nemzetközi Matematika Diákolimpia 13. feladata

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.

Vegyük észre, hogy ha n kettes számrendszerbeli jegyeit visszafele olvassuk (jobbról balra), akkor f(n)-et kapjuk! Ezt az állítást n szerinti teljes indukcióval bizonyítjuk. Nyilván:

f(1)=1,f(2)=1,f(3)=3,f(4)=1.
Tegyük fel, hogy az állítás (n-1)-ig igaz, és bizonyítsuk n-re.

a) n=2k esetén legyen f(k)=z.
f(n)=f(2k)=f(k)=z.

b) Ha n=4k+1, legyen 2t-1≦k<2t, és f(k)=z,
f(n)=2f(2k+1)-f(k)=2⋅(2t+1+z)-z=2t+2+z.

c) Ha n=4k+3, legyen 2t-1≦k<2t, és f(k)=z,
f(n)=3f(2k+1)-2f(k)=3⋅(2t+1+z)-2z=3⋅2t+1+z.

A feladat megoldásait tehát azok az 1 és 1988 közé eső számok adják, melyeket ha kettes számrendszerben írunk fel, visszafele olvasva ugyanazt kapjuk. Ezeket hívjuk palindrom számoknak. Számoljuk össze őket.
A kettes számrendszerben 2n jegyű palindrom 2n-1 van, mert az első számjegy 1, a másodiktól az n-edik helyig állhat 0 vagy 1, ez 2n-1 lehetőség, és az utolsó n jegy egyértelműen meghatározott.
Hasonló okból 2n+1 jegyű palindrom 2n db van.
1988 a kettes számrendszerben: 11111000100 (11 jegyű). Ennél a legfeljebb 10 jegyű palindromok mind kisebbek. Ezek száma 62. Az 1988 a 11 jegyű palindromok közül az 1967=11110101111 és 2015=11111011111 közé esik, ezért az 1988-nál kisebb 11 jegyű palindromok száma 30.
Összesen tehát a feladatnak 92 db megoldása van.
Csirik János (Szeged, JATE Ságvári E. Gyak. Gimn., II. o. t.)