Kezdőlap


Feladat:	C.410	Korcsoport: 16-17	Nehézségi fok: nehéz
Füzet:	1996/április, 204 - 206. oldal		PDF \| MathML
Témakör(ök):	Elsőfokú diofantikus egyenletek, Egész számok összege, C gyakorlat
Hivatkozás(ok):	Feladatok: 1995/november: C.410

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.

Tudjuk, hogy az első $n$ természetes szám összege $S_{n} = \frac{n (n + 1)}{2}$ . A feladat követelménye szerint azt a legkisebb $n$ természetes számot keressük, amelyre

\begin{matrix} \frac{n (n + 1)}{2} = k \cdot 10^{4}, \end{matrix}

illetve átalakítva:

\begin{matrix} n (n + 1) = k \cdot 2 \cdot 2^{4} \cdot 5^{4} = k \cdot 2^{5} \cdot 5^{4} = k \cdot 32 \cdot 625, \end{matrix}

alkalmas

k

természetes számmal.

n

és

n + 1

két egymást követő egész szám, ezért nem lehet 1-nél nagyobb közös osztójuk. Így csak egyikük lehet páros; amelyik egyszersmind

32

-vel is osztható kell, hogy legyen. Hasonlóképpen csak egyikük lehet osztható

5

-tel; amelyik tehát

625

-tel is osztható.
Elképzelhető, hogy ugyanaz osztható

32

-vel is és

625

-tel is, amiből

n = 32 \cdot 625 = 20000

, illetve

n + 1 = 32 \cdot 625

, tehát

n = 19999

adódik. Lehetséges azonban az, hogy

n

és

n + 1

egyike osztható

32

-vel, másikuk

625

-tel. Ez két esetet jelent, attól függően, hogy

n

vagy

n + 1

osztható

32

-vel.
Legyen először

n = 32 x

és

n + 1 = 625 y

, alkalmas

x

és

y

egész számokkal. Eszerint

625 y = 32 x + 1

, vagy szokásos alakba írva:

\begin{matrix} 625 y - 32 x = 1. \end{matrix}

Ez egy úgynevezett kétváltozós elsőfokú diofantoszi egyenlet. Általános alakja

a \cdot x + b \cdot y = c

, ahol

a

b

c

adott egész számok; és attól lesz az egyenlet diofantoszi, hogy az

(x, y)

megoldásokat az egész számok körében keressük. Ismeretes, hogy az ilyen típusú egyenleteknek pontosan akkor van megoldásuk, ha

a

és

b

legnagyobb közös osztója osztja

c

-t is. Jelen esetben ez természetesen teljesül. Most az egyenlet megoldásának általános módszerét ebben a konkrét esetben végezzük el. Tekintjük az ismeretlenek együtthatói közül a kisebbiket, ez most 32, és megkeressük a

625

-höz legközelebbi

32

-vel osztható számot, ez

640

. A kiinduló egyenletet

640 y - 15 y - 32 x = 1

alakba írva, kiemeljük a

32

-t.

32 (20 y - x) - 15 = 1

, és bevezetjük az

u = 20 y - x

új ismeretlent, ahol

u

is egész; kapjuk, hogy

\begin{matrix} 32 u - 15 y = 1. \end{matrix}

(1)

u

-ra és

x

-re egy diofantoszi egyenlet. Az előzőhöz hasonló eljárással ezt

15 (2 u - y) + 2 u = 1

alakba írva azt kapjuk, hogy:

\begin{matrix} 15 v + 2 u = 1, ahol v = 2 u - y egész szám . \end{matrix}

(2)

Még egy lépést kell tennünk: az egyenletet

2 (7 v + u) + v = 1

alakba írjuk, azaz:

\begin{matrix} 2 w + v = 1, ahol w = 7 v + u egész szám . \end{matrix}

(3)

Most már

v

-t is ki tudjuk fejezni

w

-vel:

v = 1 - 2 w

. Ezután rendre kifejezhetjük a (3), a (2) és az (1) alatti összefüggés felhasználásával

u

y

és

x

mindegyikét

w

-vel:

\begin{matrix} \begin{matrix} u & = w - 7 v = w - 7 (1 - 2 w) = 15 w - 7, \\ y & = 2 u - v = 2 (15 w - 7) - (1 - 2 w) = 32 w - 15, \\ x & = 20 y - u = 20 (32 w - 15) - (15 w - 7) = 625 w - 293. \end{matrix} \end{matrix}

Az eljárásból következik, hogy

x

és

y

csak ilyen alakú lehet, ahol

w

egész szám. Fordítva is igaz, ha

w

egész szám, akkor az

x

-re és

y

-ra kapott értékeket a kiindulási egyenletbe behelyettesítve, azt e számpár kielégíti. Mivel

n

pozitív, ezért

x

és

y

is pozitív, ami csak úgy lehet, ha

w

is pozitív. Emellett akkor kapjuk a legkisebb

n

értéket, ha

x

(és

y

) minimális. Ez akkor történik meg, ha

w = 1

, azaz

x = 332

és

y = 17

. Ebből az

n = 332 \cdot 32 = 10624

érték adódik. (Hasonlóan

n + 1 = 17 \cdot 625 = 10625

.)
Nem felejtkezhetünk meg a másik esetről, amikor

n = 625 y

és

n + 1 = 32 x

. Ez a

625 y - 32 x = - 1

egyenlethez vezet. Itt elvégezve az eljárást az

\begin{matrix} y = 32 w + 15 és x = 625 w + 293 \end{matrix}

eredményhez jutunk. Most

n

‐ és így

x

valamint

y

‐ pozitivitásához elég az is, ha

w \geq 0

; és nyilván

w = 0

adja a minimális lehetőséget. Azt kapjuk, hogy:

\begin{matrix} n = 625 \cdot y = 625 \cdot 15 = 9375; \end{matrix}

ami valóban a megoldást szolgáltatja, hiszen

9375 < 10624 < 19999 < 20000

.
Megjegyzések. 1. Azok is megkapták a maximális 5 pontot, akik próbálgatással keresték meg az egyenlet megoldását, feltéve, ha az összes megfelelő értéket megtalálták.
2. Azok, akik azt állították, hogy

n

legkisebb értéke a

20000

, dolgozataikra nem kaptak pontot.