Kezdőlap


Feladat:	F.2253	Korcsoport: 18-	Nehézségi fok: nehéz
Megoldó(k):	Bohus G. , Bölcsföldi L. , Feledi Gy. , Fodor L. , Hátsági Zs. , Horváth I. , Kiss Gy. , Korányi L. , Kuruzsa Á. , Maloveczky Gy. , Ódor T. , Simonyi G. , Somogyi H. , Szegedy P. , Szirmay L.
Füzet:	1981/május, 193 - 195. oldal		PDF \| MathML
Témakör(ök):	Egész együtthatós polinomok, Természetes számok, Teljes indukció módszere, Feladat
Hivatkozás(ok):	Feladatok: 1980/április: F.2253

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.

Bizonyítsuk be, hogy az első 1024 pozitív egész számot szét lehet osztani két, egyenként 512 elemet tartalmazó ( $x_{1}$ , $x_{2}$ , $...$ , $x_{512}$ ) és ( $y_{1}$ , $y_{2}$ , $...$ , $y_{512}$ ) részre úgy, hogy minden $j < 10$ természetes számra fennálljon a következő egyenlőség:

\begin{matrix} x_{1}^{j} + x_{2}^{j} + ... + x_{512}^{j} = y_{1}^{j} + y_{2}^{j} + ... + y_{512}^{j} . \end{matrix}

(1)

I. megoldás. Kényelmesebb lesz az első

1024

nem negatív egész számra bizonyítani a feladat állítását. Ebből következni fog az eredeti állítás, hiszen ha valamilyen

(x_{i}, y_{i}, i = 1,2, ...,512)

számokra minden

j < 10

mellett fennáll (1), akkor az

\begin{matrix} {\bar{x}}_{i} = x_{i} + 1, {\bar{y}}_{i} = y_{i} + 1, i = 1,2, ...,512 \end{matrix}

(2)

számokra is érvényes (1) minden

j < 10

mellett. Az

{\bar{x}}_{i}^{j}

{\bar{y}}_{i}^{j}

hatványok közül ugyanis az első például a

j

tényezős

\begin{matrix} (x_{i} + 1) (x_{i} + 1) ... (x_{i} + 1) \end{matrix}

szorzattal egyenlő. Ha ebben minden tagot minden taggal megszorzunk, összesen

2^{j}

szorzatot kapunk, hiszen mindegyik tényezőben két tag között választhatunk: vagy az

x_{i}

-t választjuk, vagy az

1

-et. A kapott szorzatok mindegyike

x_{i}^{k}

alakú, ahol

k

azoknak a tényezőknek a száma, amelyekben az

x_{i}

-t választottuk. Így tehát

k ≦ j < 10

, és emiatt a kapott szorzatok mindegyikére külön-külön alkalmazva (1)-et,

j

helyett a

k

kitevőre azt kapjuk, hogy (1) az

x_{i}

-k,

y_{i}

-k helyett az

{\bar{x}}_{i}

{\bar{y}}_{i}

számokra is teljesül.
Írjuk fel az első

1024

nem negatív egészet a kettes alapú számrendszerben, és aszerint osszuk őket két részre, hogy ebben az alakjukban a számjegyek összege páros-e vagy páratlan. Mivel

1024

2

-nek éppen

10

-edik hatványa, a számaink mind

\begin{matrix} 2^{9} e_{9} + 2^{8} e_{8} + ... + e_{0} \end{matrix}

(3)

alakúak, ahol az

e_{k}

számjegyek mindegyike

0

vagy

1

. Megfordítva, minden ilyen alakú szám megtalálható a két rész valamelyikében aszerint, hogy az

\begin{matrix} e_{9} + e_{8} + ... + e_{0} \end{matrix}

összeg páros-e vagy sem.
Ha egy (3) alakú számnak ki akarjuk számolni a

j

-edik hatványát, most

j

tényezős szorzatot kell kiszámítanunk, de a

\begin{matrix} (2^{9} e_{9} + 2^{8} e_{8} + ... + e_{0}) \cdot (2^{9} e_{9} + 2^{8} e_{8} + ... + e_{0}) ... (2^{9} e_{9} + 2^{8} e_{8} + ... + e_{0}) \end{matrix}

(4)

szorzatban a kifejtés után már

10^{j}

részeredmény van, hiszen most mindegyik tényezőben

10

lehetőség közül választhatunk. Mindegyik részeredményben a

10

számjegy közül néhány szerepel, mégpedig

j < 10

miatt biztosan

10

-nél kevesebb. Minden konkrét számra egy adott típusú részeredmény akkor és csakis akkor lesz

0

-tól különböző, ha az érintett számjegyek egyike sem

0

. Mivel pedig a nem érintett számjegyek ezekkel együtt pontosan ugyanannyiszor adnak páros összeget, mint páratlant, pontosan ugyanannyiszor kapunk mindkét részben

0

-tól különböző részeredményt. Végül amiatt, hogy ezek értéke független a számjegyek összegének paritásától, a mondott felosztásra (1) valóban teljesül.

II. megoldás. Legyen

n

tetszőleges pozitív egész, és legyen

m = 2^{n}

. Az

n

számra vonatkozó teljes indukcióval bizonyítjuk, hogy a következő állítás

n

-nek minden szóba jövő értékére teljesül:
Az első

2^{n + 1} (= 2 m)

pozitív egész számot szét lehet osztani két, egyenként

m

elemet tartalmazó

(x_{1}, x_{2}, ..., x_{m})

és

(y_{1}, y_{2}, ..., y_{m})

csoportba úgy, hogy minden, legfeljebb

n

-edfokú

p (x)

polinomra fennálljon a

\begin{matrix} p (x_{1}) + p (x_{2}) + ... + p (x_{m}) = p (y_{1}) + p (y_{2}) + ... + p (y_{m}) \end{matrix}

egyenlőség.
Ha ezt az állítást bizonyítottuk, ebből a feladat állítása már azonnal következik. Válasszuk ugyanis

n

-et kilencnek, a

p (x)

polinom helyére pedig tegyük az

1, x, x^{2}, ..., x^{9}

polinomokat ; az így kapott egyenlőségek adják a feladat állítását.
Most rátérünk az általunk kimondott tétel bizonyítására. Elsőként az

n = 1

esettel foglalkozunk. Állítjuk, hogy az

1,2,3,4

számoknak az

x_{1} = 1

x_{2} = 4

y_{1} = 2

y_{2} = 3

felosztása megfelel. Valóban, minden, legfeljebb elsőfokú polinom

p (x) = a x + b

alakú (ahol

a = 0

is lehetséges), és ekkor

\begin{matrix} p (1) + p (4) = 5 a + 2 b = p (2) + p (3) \end{matrix}

ahogyan kívántuk.
Másodszor tegyük fel, hogy

n ≧ 1

-re az

1,2, ...,2 m

számoknak az

(x_{1}, x_{2}, ..., x_{m})

és

(y_{1}, y_{2}, ..., y_{m})

felosztása megfelelő. Osszuk fel az első

4 m

pozitív egész számot a következő módon :

\begin{matrix} (x_{1}, x_{2}, ..., x_{m}, y_{1} + 2 m, y_{2} + 2 m, ..., y_{m} + 2 m), \end{matrix}

illetve

\begin{matrix} (y_{1}, y_{2}, ..., y_{m}, x_{1} + 2 m, x_{2} + 2 m, ..., x_{m} + 2 m), \end{matrix}

Állítjuk, hogy ez a felosztás jó lesz

(n + 1)

-re. Legyen

p (x)

egy tetszőleges, legfeljebb

(n + 1)

-edfokú polinom. A

q (x) = p (x + 2 m) - p (x)

polinom legfeljebb

n

-edfokú, hiszen a jobb oldalon a legmagasabb fokú tag együtthatója

0

. Így alkalmazhatjuk indukciós feltevésünket a

q (x)

polinomra, tehát a következő egyenlőség fennáll:

\begin{matrix} q (x_{1}) + q (x_{2}) + ... + q (x_{m}) = q (y_{1}) + q (y_{2}) + ... + q (y_{m}) . \end{matrix}

Ebből

q (x_{i}) = p (x_{i} + 2 m) - p (x_{i})

és

q (y_{i}) = p (y_{i} + 2 m) - p (y_{i})

alapján átrendezéssel azt kapjuk, hogy

\begin{matrix} p (x_{1}) + ... + p (x_{m}) + p (y_{1} + 2 m) + ... + p (y_{m} + 2 m) = \\ = p (y_{1}) + ... + p (y_{m}) + p (x_{1} + 2 m) + ... + p (x_{m} + 2 m) . \end{matrix}

Mivel

p

tetszőleges, legfeljebb

(n + 1)

-edfokú polinom volt, ez éppen tételünk érvényességét bizonyítja

(n + 1)

-re.
A teljes indukció elve alapján tehát a tétel minden

n

-re érvényes, ezzel a bizonyítást befejeztük.