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. Megjegyzés. A feladat zárójeles toldaléka felesleges akkor, ha egytagú összeget is lehetségesnek tartunk, ha tehát bármely számot a saját összegének is mondunk. Ez a felfogás megkönnyíti a szövegezést, a megoldásainkban szereplő összegek is így értendők.
I. megoldás. A feladat állításán túlmenően azt bizonyítjuk, hogy ha , akkor az természetes szám felírható a véges sorozatból kiválasztott számok összegeként. Ezt az állítást -ra vonatkozó teljes indukcióval bizonyítjuk be. Ha , akkor állításunk miatt helyes, hiszen ebben az esetben csak lehetséges. Legyen tehát , és tegyük fel, hogy állításunk helyes, ha benne helyén áll. Ha , akkor indukciós feltevésünk szerint felírható a kívánt alakban, ti. már is elegendő az összegül -et adó számok kiválasztásához. Legyen tehát | | Minthogy a baloldali összeg a feladat feltevése szerint legalább , egyenlőtlenségeinkből következik. Eszerint vagy , vagy pedig az indukciós feltevés szerint felírható az sorozatból kiválasztott számok összegeként. Így tehát vagy , vagy pedig -t a kiválasztott számokhoz csatolva összegül adódik.
II. megoldás. Ismét azt bizonyítjuk, hogy ha , akkor felírható az sorozatból kiválasztott számok összegeként, de most -re vonatkozó teljes indukciót alkalmazunk. Ha , akkor miatt helyes az állítás, akármekkora is értéke. Legyen tehát , és tegyük fel, hogy állításunk helyes, ha benne helyén nála kisebb szám áll. A rögzített mellett olyan értékeket kell tekintenünk, amelyekre teljesül. Elég, ha közülük csak a legkisebbel foglalkozunk, tehát azzal a értékkel, amelyre | | hiszen növelésekor az összegül -et adó számok kiválasztásához rendelkezésre álló választék csak növekszik. Egyenlőtlenségeinkből az értékre adódik. Így tehát a feladat feltevését is alkalmazva | | Ha tehát az érdektelen (azaz ) esetet figyelmen kívül hagyjuk, akkor Indukciós feltevésünk szerint ez éppen azt biztosítja, hogy előállítható az sorozatból kiválasztott számok összegeként. Ha tehát ezeket ebből a sorozatból elhagyjuk, akkor a megmaradóknak az összege.
Megjegyzések. 1. Felvethető a kérdés, hogy feladatunk feltevésének teljesülnie kell-e, ha állítása teljesül. Ez nincs így. Ha pl. minden esetben , viszont , akkor a feltevés a esetben nem teljesül: , viszont bármely természetes szám mégis előállítható az 1, 3, 1, 1, 1, sorozatból kiválasztott számok összegeként. Elmondhatjuk, hogy negatív tapasztalatunk nem meglepetés, mert a végtelen sorozat elemeinek permutálása a természetes számok előállíthatóságának mit sem árt, viszont megszüntetheti a feladat feltevésének teljesülését. Előző példánk is úgy keletkezik, hogy a feltevést is kielégítő 1, 1, 3, 1, 1, 1, sorozat két elemét felcseréljük. 2. Feladatunk feltételének szükségességét mégiscsak bebizonyítjuk, de a következő formában: Ha minden természetes szám felírható egy természetes számokból alakuló végtelen sorozatból kiválasztott számok összegeként, akkor ez a sorozat átrendezhető alakba úgy, hogy minden értékre teljesüljön. Abból indulunk ki, hogy lehetséges választás, hiszen -nek szerepelnie kell a sorozatban, mert is előállítható általa. A további értékek megválasztását a következőképpen szabályozzuk: Minthogy előállítható, a sorozatban elhagyása után is szerepelnie kell legalább egy -nél nem nagyobb elemnek (ti. -nek vagy -nek). Azt választjuk közülük -nek, amelyiknek a sorozatban a legkisebb az indexe. megválasztása után van egy legkisebb természetes szám (ti. vagy ), amely nem írható fel a véges , sorozatból kiválasztott számok összegeként. Szerepelnie kell ezért a sorozatban , és elhagyása után is legalább egy -nál nem nagyobb számnak. Azt választjuk közülük -nak, amelyiknek az indexe a sorozatban a legkisebb. Így folytatjuk ezt az eljárást. Ha már megválasztottuk az , sorozatelemeket, akkor van egy legkisebb természetes szám, amely nem írható fel a véges sorozatból kiválasztott számok összegeként. Szerepelnie kell ezért a sorozatban a már kiválasztott elemek elhagyása után legalább egy -nál nem nagyobb számnak. Ezek közül azt választjuk -nak, amelyiknek az indexe a sorozatban a legkisebb. A következő lépésben fellépő nagyobb -nál, hiszen maga már bizonyosan felírható az sorozatból kiválasztott számok összegeként vagy azért, mert , vagy pedig azért, mert mellé az sorozatból összeget adó számokat választhatunk ki, hiszen volt a legkisebb így elő nem állítható szám. Ha tehát eljárásunkat minden határon túl folytatjuk, akkor miatt a sorozat bármely eleme előbb-utóbb kiválasztásra kerül, mert ha pl. a -adik lépésben már akkor ettől a lépéstől kezdve csak vagy nála kisebb indexű elem kerülhet kiválasztásra, márpedig a véges sok elem előbb-utóbb elfogy. Ezek szerint az általunk képezett sorozatban a sorozat minden eleme előfordul, tehát az utóbbi sorozatot valóban átrendeztük. definíciójából következik, hogy értéke legfeljebb hiszen ez a szám biztosan nem állítható elő az sorozatból kiválasztott számok összegeként. Minthogy pedig , bebizonyítottuk, hogy feladatunk feltevésének teljesülnie kell az átrendezéssel származtatott sorozatra. 3. Ha az feltételnek eleget tevő monoton sorozatokra szorítkozunk, akkor kizártuk azt, hogy a sorozat elemeit permutálhassuk, hogy tehát a feladat feltevésének teljesülése ettől a permutálástól függjön. Az ilyen monoton sorozat esetében a feladat feltevésének (minden permutálás nélkül) teljesülnie kell, ha az állítása teljesül. Ha ugyanis , akkor nem írható fel az sorozatból kiválasztott számok összegeként, hiszen ebben a végtelen sorozatban csak az elemek nem nagyobbak -nél, és mindezeknek az összege még mindig kisebb nála. 4. Utolsóként azt a kérdést vetjük fel, hogy hogyan kell a feladat feltevését kielégítő sorozatot megválasztani, ha azt akarjuk, hogy elemei a lehető legnagyobbak legyenek. Megmutatjuk, hogy 1, 2, 4, 8, ez az optimális sorozat. Akárhogyan választjuk meg ugyanis a feltevést kielégítő sorozatot, ebben minden értékre teljesül az egyenlőtlenség. Ezt -ra vonatkozó teljes indukcióval bizonyítjuk be. A esetben helyes az állítás, mert a feltevés szerint . Legyen tehát , és tegyük fel, hogy az állítás teljesül, ha benne helyén nála kisebb szám áll. Ekkor | | ami állításunk helyességét bizonyítja. Az utolsó egyenlőség, éppen feladatunk állítására hivatkozva, azt a jól ismert tényt bizonyítja, hogy minden természetes szám felírható különböző hatványainak összegeként. Beláttuk tehát, hogy a vizsgált tulajdonságú sorozatok közül hatványsorozatának az elemei a legnagyobbak. |