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 file
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

Bizonyítsuk be, hogy az első 1024 pozitív egész számot szét lehet osztani két, egyenként 512 elemet tartalmazó (x1, x2, ... , x512) és (y1, y2, ... , y512) részre úgy, hogy minden j<10 természetes számra fennálljon a következő egyenlőség:
x1j+x2j+...+x512j=y1j+y2j+...+y512j.

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ó (x1, x2, ... , x512) és (y1, y2, ... , y512) részre úgy, hogy minden j<10 természetes számra fennálljon a következő egyenlőség:

x1j+x2j+...+x512j=y1j+y2j+...+y512j.(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 (xi,yi,i=1,2,...,512) számokra minden j<10 mellett fennáll (1), akkor az
x¯i=xi+1,y¯i=yi+1,i=1,2,...,512(2)
számokra is érvényes (1) minden j<10 mellett. Az x¯ij, y¯ij hatványok közül ugyanis az első például a j tényezős
(xi+1)(xi+1)...(xi+1)
szorzattal egyenlő. Ha ebben minden tagot minden taggal megszorzunk, összesen 2j szorzatot kapunk, hiszen mindegyik tényezőben két tag között választhatunk: vagy az xi-t választjuk, vagy az 1-et. A kapott szorzatok mindegyike xik alakú, ahol k azoknak a tényezőknek a száma, amelyekben az xi-t választottuk. Így tehát kj<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 xi-k, yi-k helyett az x¯i, 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 a 2-nek éppen 10-edik hatványa, a számaink mind
29e9+28e8+...+e0(3)
alakúak, ahol az ek 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
e9+e8+...+e0
ö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
(29e9+28e8+...+e0)(29e9+28e8+...+e0)...(29e9+28e8+...+e0)(4)
szorzatban a kifejtés után már 10j 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=2n. 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ő 2n+1(=2m) pozitív egész számot szét lehet osztani két, egyenként m elemet tartalmazó (x1,x2,...,xm) és (y1,y2,...,ym) csoportba úgy, hogy minden, legfeljebb n-edfokú p(x) polinomra fennálljon a
p(x1)+p(x2)+...+p(xm)=p(y1)+p(y2)+...+p(ym)
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,x2,...,x9 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 x1=1, x2=4, y1=2, y2=3 felosztása megfelel. Valóban, minden, legfeljebb elsőfokú polinom p(x)=ax+b alakú (ahol a=0 is lehetséges), és ekkor
p(1)+p(4)=5a+2b=p(2)+p(3)
ahogyan kívántuk.
Másodszor tegyük fel, hogy n1-re az 1,2,...,2m számoknak az (x1,x2,...,xm) és (y1,y2,...,ym) felosztása megfelelő. Osszuk fel az első 4m pozitív egész számot a következő módon :
(x1,x2,...,xm,y1+2m,y2+2m,...,ym+2m),
illetve
(y1,y2,...,ym,x1+2m,x2+2m,...,xm+2m),
Á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+2m)-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:
q(x1)+q(x2)+...+q(xm)=q(y1)+q(y2)+...+q(ym).
Ebből q(xi)=p(xi+2m)-p(xi) és q(yi)=p(yi+2m)-p(yi) alapján átrendezéssel azt kapjuk, hogy
p(x1)+...+p(xm)+p(y1+2m)+...+p(ym+2m)==p(y1)+...+p(ym)+p(x1+2m)+...+p(xm+2m).
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.