|
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ó (, , , ) és (, , , ) részre úgy, hogy minden természetes számra fennálljon a következő egyenlőség: | | (1) |
I. megoldás. Kényelmesebb lesz az első 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 számokra minden mellett fennáll (1), akkor az | | (2) | számokra is érvényes (1) minden mellett. Az , hatványok közül ugyanis az első például a tényezős szorzattal egyenlő. Ha ebben minden tagot minden taggal megszorzunk, összesen szorzatot kapunk, hiszen mindegyik tényezőben két tag között választhatunk: vagy az -t választjuk, vagy az -et. A kapott szorzatok mindegyike alakú, ahol azoknak a tényezőknek a száma, amelyekben az -t választottuk. Így tehát , és emiatt a kapott szorzatok mindegyikére külön-külön alkalmazva (1)-et, helyett a kitevőre azt kapjuk, hogy (1) az -k, -k helyett az , számokra is teljesül. Írjuk fel az első 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 a -nek éppen -edik hatványa, a számaink mind alakúak, ahol az számjegyek mindegyike vagy . Megfordítva, minden ilyen alakú szám megtalálható a két rész valamelyikében aszerint, hogy az összeg páros-e vagy sem. Ha egy (3) alakú számnak ki akarjuk számolni a -edik hatványát, most tényezős szorzatot kell kiszámítanunk, de a | | (4) | szorzatban a kifejtés után már részeredmény van, hiszen most mindegyik tényezőben lehetőség közül választhatunk. Mindegyik részeredményben a számjegy közül néhány szerepel, mégpedig miatt biztosan -nél kevesebb. Minden konkrét számra egy adott típusú részeredmény akkor és csakis akkor lesz -tól különböző, ha az érintett számjegyek egyike sem . 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 -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 tetszőleges pozitív egész, és legyen . Az számra vonatkozó teljes indukcióval bizonyítjuk, hogy a következő állítás -nek minden szóba jövő értékére teljesül: Az első pozitív egész számot szét lehet osztani két, egyenként elemet tartalmazó és csoportba úgy, hogy minden, legfeljebb -edfokú polinomra fennálljon a | | 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 -et kilencnek, a polinom helyére pedig tegyük az 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 esettel foglalkozunk. Állítjuk, hogy az számoknak az , , , felosztása megfelel. Valóban, minden, legfeljebb elsőfokú polinom alakú (ahol is lehetséges), és ekkor | | ahogyan kívántuk. Másodszor tegyük fel, hogy -re az számoknak az és felosztása megfelelő. Osszuk fel az első pozitív egész számot a következő módon : | | illetve | | Állítjuk, hogy ez a felosztás jó lesz -re. Legyen egy tetszőleges, legfeljebb -edfokú polinom. A polinom legfeljebb -edfokú, hiszen a jobb oldalon a legmagasabb fokú tag együtthatója . Így alkalmazhatjuk indukciós feltevésünket a polinomra, tehát a következő egyenlőség fennáll: | | Ebből és alapján átrendezéssel azt kapjuk, hogy
Mivel tetszőleges, legfeljebb -edfokú polinom volt, ez éppen tételünk érvényességét bizonyítja -re. A teljes indukció elve alapján tehát a tétel minden -re érvényes, ezzel a bizonyítást befejeztük. |
|