Kezdőlap


Feladat:	1988. évi Nemzetközi Matematika Diákolimpia 23. feladata	Korcsoport: 16-17	Nehézségi fok: nehéz
Megoldó(k):	Bíró András , Emanuel Atanaszov
Füzet:	1988/október, 296 - 299. oldal		PDF \| MathML
Témakör(ök):	Végtelen leszállás módszere, Indirekt bizonyítási mód, Maradékos osztás, Gyökök és együtthatók közötti összefüggések, Nemzetközi Matematikai Diákolimpia
Hivatkozás(ok):	Feladatok: 1988/szeptember: 1988. évi Nemzetközi Matematika Diákolimpia 23. 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.

I. megoldás. A következő megoldást sajnos nem a versenyen, hanem utána, este találtam. Ekkor már tudtam azt, hogy a végtelen leszállás elvével kijön a feladat. Erre a módszerre igazság szerint magamtól is gondolhattam volna, hiszen két hazai válogatóversenyen szükség volt rá.
Tegyük fel, hogy a $a ≦ b$ . Osszuk el $b$ -t maradékosan $a$ -val: $b = q a + r$ ( $q$ , $r$ egész; $0 ≦ r < a$ ). Ekkor

\begin{matrix} a b + 1 = q a^{2} + r a + 1, és \\ a^{2} + b^{2} = a^{2} + q^{2} a^{2} + 2 a r + r^{2} . \end{matrix}

A feltétel szerint

a b + 1 | a^{2} + b^{2}

. Legyen a hányados

k

, azaz

\begin{matrix} k (q a^{2} + r a + 1) = a^{2} + q^{2} a^{2} + 2 q a r + r^{2} . \end{matrix}

Másrészt:

\begin{matrix} q (q a^{2} + r a + 1) = q^{2} a^{2} + q a r + q . \end{matrix}

A felső egyenletből az alsót kivonva:

\begin{matrix} (k - q) (q a^{2} + r a + 1) = a^{2} + q r a + r^{2} - q . \end{matrix}

(1)

Most két esetet különböztetünk meg:
I.

r = 0

(azaz

a | b

),
II.

r \neq 0

(azaz

a ∤ b

).
Mind a két esetben (1) jobb oldalát fogjuk alulról és felülről úgy megbecsülni, hogy ennek, mint

(q a^{2} + r a + 1)

többszörösének, már csak egy lehetséges értéke marad.
I. eset.

r = 0

. (1) most így alakul:

\begin{matrix} (k - q) (q a^{2} + 1) = a^{2} - q . \end{matrix}

Könnyen látható, hogy:

\begin{matrix} - (q a^{2} + 1) < a^{2} - q < q a^{2} + 1, \end{matrix}

tehát

\begin{matrix} a^{2} - q = 0, és k - q = 0. \end{matrix}

Ez utóbbiakból:

k = a^{2}

, azaz valóban négyzetszám.
Látható az is, hogy az

a ∣ b

esetben csak a

b = a^{3}

lehetséges, és az

a

a^{3}

számpár kielégíti a feltételt.
II. eset.

r \neq 0

. Megmutatjuk, hogy ekkor:

\begin{matrix} 0 < a^{2} + q r a + r^{2} - q < 2 (q a^{2} + r a + 1) . \end{matrix}

A bal oldali egyenlőtlenség abból következik, hogy

a^{2} + r^{2} > 0

, és

q r a - q ≧ 0

. (Itt használjuk ki, hogy

r > 0

.) A jobb oldali céljára:

\begin{matrix} 2 q a^{2} > a^{2} + q r a, (r < a) \\ 2 r a > r^{2}, \\ 2 > - q, \end{matrix}

ezeket összegezve megkapjuk a jobb oldali egyenlőtlenséget, és így (1)-ben csak

\begin{matrix} q a^{2} + r a + 1 = a^{2} + q r a + r^{2} - q és k - q = 1 \end{matrix}

lehetséges. Átrendezve:

\begin{matrix} a^{2} + {(a - r)}^{2} = (q + 1) (a (a - r) + 1) . \end{matrix}

(2)

r < a

miatt

a - r > 0

, így

a

és

(a - r)

is pozitív egész. Az

a

b

számokból kiindulva találtunk egy másik számpárt,

a

-t és

(a - r)

-et, amelyre

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

és ebben az új számpárban a számok minimuma,

(a - r)

kisebb, mint az eredeti számpárban

(a)

. Ha most

a - r | a

, akkor az I. eset szerint

k

négyzetszám. Ha pedig

a - r ∤ a

, akkor a II. eset szerint tovább tudjuk csökkenteni a minimumot. Az eljárást folytatva előbb-utóbb az I. esethez kell eljutnunk, ha előbb nem, akkor, amikor a két szám minimuma

1

lesz.
Ezzel beláttuk, hogy

k

csak négyzetszám lehet.
Nézzük még meg, milyen számpárok elégítik ki a feladat feltételeit! Figyelembe véve, hogy a II. pont eljárásával előbb-utóbb minden megoldásból egy

(a, a^{3})

típusú megoldáshoz jutunk, az eljárást (a II. esetbelit) megfordítva kapjuk, hogy a megoldások az

\begin{matrix} a_{1} = a, a_{2} = a^{3}, a_{n + 2} = a^{2} a_{n + 1} - a_{n} \end{matrix}

típusú sorozatok szomszédos elemeiből álló számpárok.

Bíró András (Budapest, Fazekas M. Gyak. Gimn., III. o.t.)

A 6. feladat több szempotból is a legnehezebbnek bizonyult a versenyen. A magyar csapat például mindössze egyetlen pontot szerzett ezen a feladaton. Ennél talán többet mond, hogy az olimpiai bizottság tagjai közül ‐ ez a bizottság hat kiválló ausztrál matematikusból állt, és ők választották ki a részt vevő országok javaslataiból azt a 31 feladatot, amelyik a nemzetközi zsűri elé került ‐ senki sem tudta megoldani.
Hosszas vita után végül kitűzték. Sokan fogadtak arra, hogy nem, vagy alig lesz jó megoldás, és majd mindenki veszített. Végül 11 (!) versenyző oldotta meg helyesen a feladatot. A szerzők mindegyike így vagy úgy a végtelen leszállás módszerével jutott el a megoldáshoz. Az alábbiakban a bolgár Emanuel Atanaszov különdíjas megoldását ismertetjük, aki talán a legelegánsabban nyúlt a problémához.

II. megoldás. Jelöljük a hányados értékét

K

-val és rendezzük át a feltételt. Így az

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

(1)

összefüggéshez jutunk. Tegyük fel, hogy az állítás nem igaz, a

K

nem négyzetszám, és tekintsük az

\begin{matrix} x^{2} - K x y + y^{2} = K \end{matrix}

(2)

kétismeretlenes diofantoszi egyenletet, amelynek feltételünk szerint létezik pozitív egész

(a; b)

számokból álló megoldása.
Vegyük észre, hogy (2)-nek nem lehetnek ellenkező előjelű megoldásai, hiszen ekkor a bal oldalon

\begin{matrix} - K x y > K és x^{2} - y^{2} > 0. \end{matrix}

Olyan megoldása sincs a (2) egyenletnek, ahol az egyik szám

0

volna, hisz ekkor a bal oldal értéke négyzetszám. (Lényegében itt használjuk fel az indirekt föltevést!)
Tekintsük most a (2) egyenletnek azt a pozitív

(A, B)

megoldását, amelyre a két szám közül a nem nagyobb ‐ legyen ez

B

‐ minimális. Ilyen létezik és az előbbiek szerint

A ≧ B > 0

.
A (2)-ben

y

helyére

B

-t helyettesítve az immár egyismeretlenes

\begin{matrix} x^{2} - K B x + B^{2} - K = 0 \end{matrix}

(3)

egyenletet kapjuk, amelynek tehát az

A

megoldása. A másodfokú (3) egyenlet másik,

A'

gyökére

\begin{matrix} A + A' = K B, \end{matrix}

tehát

A'

is egész.
Az

(A', B)

számpár is megoldása (2)-nek, a

B

pozitív, így az

A'

is az. A gyökök és együtthatók közti másik összefüggésben a gyökök szorzata pozitív:

A' A = B^{2} - K > 0

, ahonnan

0 < A' A < B^{2}

, vagyis

A ≧ B

miatt

A' < B

!
Abból a feltevésből kiindulva, hogy a

K

nem négyzetszám, találtunk a (2) egyenletre egy másik megoldást, az

(A' B)

számpárt, ahol

0 < A' < B,

ellentétben az

(A, B)

megoldásra előírt kikötésünkkel. Ez azt jelenti, hogy a

K

valóban négyzetszám.