Kezdőlap


Feladat:	N.182	Korcsoport: 18-	Nehézségi fok: nehéz
Megoldó(k):	Csirmaz Előd , Dancsó Zsuzsanna , Dezső Balázs , Gerbicz Róbert , Gyenes Zoltán , Harangi Viktor , Horváth Gábor , Iván Szabolcs , Juhász András , Keszegh Balázs , Kiss Gergely , Kunszenti-Kovács Dávid , Lukács László , Mansur Boase , Máthé András , Mecz Balázs , Naszódi Gergely , Pálvölgyi Dömötör , Pataki Péter , Szakács László , Székelyhidi Gábor , Terpai Tamás , Tran Thanh Long , Végh A. László , Zábrádi Gergely
Füzet:	1999/március, 164 - 166. oldal		PDF \| MathML
Témakör(ök):	Rekurzív sorozatok, Természetes számok, Oszthatósági feladatok, Nehéz feladat
Hivatkozás(ok):	Feladatok: 1998/szeptember: N.182

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.

Az $a$ és $b$ egymáshoz relatív prímek, hiszen pl. az $a$ osztója a $b$ -hez relatív prím $(b^{2} + b + 1)$ -nek. Így az egyetlen olyan megoldás, amelyre $a = b$ , az $a = b = 1$ . Tegyük fel ezután, hogy $a < b$ , és $a b^{+} = b^{2} + b + 1$ , $b a^{-} = a^{2} + a + 1$ .
Ekkor $b b^{+} > a b^{+} = b^{2} + b + 1 > b (b + 1)$ miatt $b^{+} > b$ , hasonlóan $(a + 1) a^{-} \leq b a^{-} = a^{2} + a + 1 < (a + 1) (a + 1)$ szerint $a^{-} \leq a$ , és így ‐ mivel $a^{-}$ osztója az $a$ -hoz relatív prím $(a^{2} + a + 1)$ -nek ‐ $a^{-} < a$ vagy $a^{-} = a = 1$ .
Megmutatjuk, hogy $a$ , $b$ -hez hasonlóan az $a^{-}$ , $a$ és a $b$ , $b^{+}$ párok is eleget tesznek a feladat feltételeinek. Nyilván $a^{-} ∣ b a^{-} = a^{2} + a + 1$ és $b^{+} ∣ a b^{+} = b^{2} + b + 1$ . Mivel $a$ és $b$ egymáshoz relatív prímek, elég igazolni, hogy

\begin{matrix} a ∣ b^{2} {(a^{-})}^{2} + a^{-} + 1) és b ∣ a^{2} ({(b^{+})}^{2} + b^{+} + 1) . \end{matrix}

Az első oszthatóság igazolásához használjuk

b a^{-} = a^{2} + a + 1

-et:

\begin{matrix} b^{2} ({(a^{-})}^{2} + a^{-} + 1) = {(a^{2} + a + 1)}^{2} + b (a^{2} + a + 1) + b^{2} = a x + (1 + b + b^{2}), \end{matrix}

és ez valóban osztható

a

-val; hasonlóan láthatjuk be a második oszthatóság teljesülését is.
Tehát az

a < b

megoldásból ,,lefelé'' és ,,felfelé'' is tovább lépve megkaphatjuk az

a^{-} \leq a < b < b^{+}

sorozatot, amelynek bármely két szomszédos eleme megoldás, és ezt ugyanígy folytathatjuk tovább, mindkét irányban. Észrevehetjük, hogy a sorozatot bármelyik két szomszédos eleme már meghatározza, hiszen

b^{+} = \frac{b^{2} + b + 1}{a}

-hoz hasonlóan például

b = \frac{a^{2} + a + 1}{b^{-}}

.
Vizsgáljuk meg, hová jutunk, ha

a < b

-ből indulva a sorozatot ,,lefelé'' folytatjuk, ameddig csak lehetséges. Legyen

a_{- 1} = a^{-} = \frac{a^{2} + a + a}{b}

a_{- 2} = \frac{a_{- 1}^{2} + a_{- 1} + 1}{a}

s.í.t. A sorozat ebben az irányban akkor ér véget, amikor

a_{- (n + 1)} = a_{- n}

, azaz

a_{- (n + 1)} = a_{- n} = 1

. Ekkor

a_{- (n - 1)} = \frac{a_{- n}^{2} + a_{- n 1} + 1}{a_{- (n + 1)}} = 3

a_{- (n - 2)} = \frac{a_{- (n - 1)}^{2} + a_{- (n - 1)} + 1}{a_{- n}} = 13

stb.; az

a

b

pár tehát két szomszédos eleme annak az

x_{1} < x_{2} < ...

sorozatnak, amelyet az

x_{1} = 1

x_{2} = 3

x_{i + 1} = \frac{x_{i}^{2} + x_{i} + 1}{x_{i - 1}}

rekurzió definiál. Ennek a sorozatnak bármely két szomszédos eleme valóban megoldást ad, hiszen az

(1, 3)

pár megoldás.

Megjegyzések. 1. A megoldás ötlete a következő gondolatból származik.
Ha az

(a, b)

számpár megoldás, akkor az

a^{2} + a + (b^{2} + b + 1) = (a^{2} + a + 1) + b^{2} + b

szám osztható

a

-val és

b

-val. Mivel

a

és

b

relatív prímek,

a b

-vel is osztható, vagyis egy megfelelő

K

pozitív egésszel

\begin{matrix} a^{2} + b^{2} + a + b + 1 = K a b . \end{matrix}

(1)

Ennek a megfordítása is igaz, ha az

a

b

K

pozitív egészekre (1) teljesül, akkor

a^{2} + a + 1

osztható

b

-vel és

b^{2} + b + 1

osztható

a

-val.
Tekintsük most a

\begin{matrix} t^{2} - (K b - 1) t + (b^{2} + b + 1) = 0 \end{matrix}

másodfokú egyenletet. Ennek egyik gyöke

t_{1} = a

. A másik gyöke a Vita-formulák alapján

\begin{matrix} t_{2} = (K b - 1) - a = \frac{b^{2} + b + 1}{a} . \end{matrix}

Az első felírásból látszik, hogy

t_{2}

egész szám, a másodikból pedig, hogy pozitív.
2. Az előbbi lépés többszöri megismétlésével az (1) egyenlet tetszőleges

(a, b, K)

megoldásából további megoldásokat állíthatunk elő. Könnyű meggondolni, hogy kellő számú lépést megtéve eljuthatunk az

(1, 1, K)

megoldáshoz. Ebből következik, hogy csak

K = 5

lehetséges, és az

(x_{n})

sorozatot az

\begin{matrix} x_{0} = x_{1} = 1, x_{n + 1} = 5 x_{n} - x_{n - 1} - 1 \end{matrix}

(2)

rekurzióval is definiálhatjuk.
3. A (2) a rekurzióból

x_{n}

explicit alakban is felírható:

\begin{matrix} x_{n} = \frac{1}{3} + \frac{7 - \sqrt[]{21}}{21} {(\frac{5 + \sqrt[]{21}}{2})}^{n} + \frac{7 + \sqrt[]{21}}{21} {(\frac{5 - \sqrt[]{21}}{2})}^{n} . \end{matrix}