Kezdőlap


Feladat:	F.2722	Korcsoport: 18-	Nehézségi fok: átlagos
Megoldó(k):	Antos A. , Balogh 171 J. , Benczúr P. , Benkő D. , Gutai Zs. , Harcos G. , Hídvégi Z. , Kocsor A. , Kovács 271 Ágnes , Lois L. , Mezei J. , Mohai Zsuzsanna , Nagy 124 G. , Nagy G. P. , Peták A. , Podoski Károly. , Sustik M. , Tokodi T. , Tóth 702 P. , Tuba I.
Füzet:	1989/november, 374 - 375. oldal		PDF \| MathML
Témakör(ök):	Algebrai átalakítások, Maradékos osztás, Oszthatósági feladatok, Számsorozatok, Teljes indukció módszere, Feladat
Hivatkozás(ok):	Feladatok: 1989/január: F.2722

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.

Először megmutatjuk, hogy $n$ osztható nyolccal. Ismeretes, hogy egy páratlan négyzetszám nyolccal osztva $1$ -et ad maradékul. Miután $2 n + 1$ a feltétel szerint négyzetszám és nyilván páratlan, ezért $2 n$ osztható nyolccal, tehát $n$ páros. Ebből viszont következik, hogy $3 n + 1$ is páratlan. A feltétel szerint négyzetszám is, így nyolccal osztva $1$ maradékot ad. Tehát $3 n$ osztható nyolccal, így $n$ is osztható nyolccal.
Most megmutatjuk, hogy $n$ osztható öttel is. Ha $n$ öttel osztva $1$ maradékot ad, akkor $2 n + 1$ , ha $n$ öttel osztva $4$ maradékot ad, akkor pedig $3 n + 1$ ad öttel osztva $3$ maradékot, tehát $3$ -ra, vagy $8$ -ra végződik, s így nem lehet négyzetszám. Hasonlóan, ha $n$ öttel osztva $2$ vagy $3$ maradékot ad, akkor $3 n + 1$ , ill. $2 n = 1$ utolsó jegye vagy $7$ vagy $2$ . Tehát $2 n + 1$ és $3 n + 1$ csak úgy lehet egyszerre négyzetszám, ha $n$ osztható öttel is.
Beláttuk, hogy $n$ osztható öttel és nyolccal, így osztható negyvennel is.
Most rátérünk a feladat második részére. Tekintsük a következő $(A_{i})$ és $(B_{i})$ sorozatot: $A_{0} = B_{0} = 1$ , $A_{i + 1} = 5 A_{i} + 4 B_{i}$ , $B_{i + 1} = 6 A_{i} + 5 B_{i}$ ; $i = 0, 1, 2, ...$ . Azt állítjuk, hogy (a) $A_{i}$ páratlan,
(b) $\frac{1}{3} (B_{i}^{2} - 1) = \frac{1}{2} (A_{i}^{2} - 1)$ ,
(c) $n_{i} = \frac{1}{2} (A_{i}^{2} - 1)$ szigorúan monoton nő.

A (c) állítás világos, hiszen

A_{i}

és

B_{i}

pozitív, ezért

\begin{matrix} A_{i + 1} = 5 A_{i} + 4 B_{i} > 5 A_{i} > A_{i}, s így \frac{1}{2} (A_{i + 1}^{2} - 1) > \frac{1}{2} (A_{i}^{2} - 1) . \end{matrix}

Az (a) állítás is teljesül, hiszen

A_{0}

páratlan, és

A_{i + 1} - A_{i} = 4 (A_{i} + B_{i})

, tehát ha

A_{i}

páratlan, akkor

A_{i + 1}

is az. Ebből következik, hogy minden

A_{i}

páratlan.
Most belátjuk (b)-t is. Hattal szorozva és rendezve az igazolandó összefüggés a következő:

\begin{matrix} 3 A_{i}^{2} - 2 B_{i}^{2} = 1. \end{matrix}

(1)

Ezt teljes indukcióval bizonyítjuk.

i = 0

-ra

A_{0}^{2} = B_{0}^{2} = 1

, tehát (1) igaz. Tegyük fel; hogy

i = k

-ra teljesül, belátjuk, hogy akkor teljesül

i = k + 1

-re is

\begin{matrix} 3 A_{k + 1}^{2} - 2 B_{k + 1}^{2} = 3 {(5 A_{k} + 4 B_{k})}^{2} - 2 {(6 A_{k} + 5 B_{k})}^{2} = (75 - 72) A_{k}^{2} + \\ + (48 - 50) B_{k}^{2} + 120 A_{k} B_{k} - 120 A_{k} B_{k} = 3 A_{k}^{2} - 2 B_{k}^{2} = 1. \end{matrix}

Ezzel (b)-t is bebizonyítottuk.

n_{i} = \frac{1}{2} (A_{i}^{2} - 1)

számok (a) szerint egészek, (c) szerint pedig (minden

i

-re) különbözők, végül (b) szerint

2 n_{i} + 1 = A_{i}^{2}

és

3 n_{i} + 1 = B_{i}^{2}