Feladat: 1960. évi Kürschák matematikaverseny 2. feladata Korcsoport: 18- Nehézségi fok: nehéz
Megoldó(k):  Bollobás Béla ,  Máté Attila ,  Mezei Ferenc 
Füzet: 1961/március, 100 - 103. oldal  PDF  |  MathML 
Témakör(ök): Természetes számok, Maradékos osztás, Kombinatorikai leszámolási problémák, Permutációk, Számsorozatok, Egyenlőtlenségek, Teljes indukció módszere, Kürschák József (korábban Eötvös Loránd)
Hivatkozás(ok):Feladatok: 1961/március: 1960. évi Kürschák matematikaverseny 2. feladata

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 0<n≤a1+a2+...+ak, akkor az n természetes szám felírható a véges a1,a2,...,ak sorozatból kiválasztott számok összegeként. Ezt az állítást k-ra vonatkozó teljes indukcióval bizonyítjuk be.
Ha k=1, akkor állításunk a=1 miatt helyes, hiszen ebben az esetben csak n=1 lehetséges. Legyen tehát k>1, és tegyük fel, hogy állításunk helyes, ha benne k helyén k-1 áll.
Ha 0<n≤a1+a2+...+ak-1, akkor indukciós feltevésünk szerint n felírható a kívánt alakban, ti. már a1,a2,...,ak-1 is elegendő az összegül n-et adó számok kiválasztásához. Legyen tehát
1+a1+a2+...+ak-1≤n≤a1+a2+...+ak.
Minthogy a baloldali összeg a feladat feltevése szerint legalább ak, egyenlőtlenségeinkből
0≤n-ak≤a1+a2+...+ak-1
következik. Eszerint n-ak vagy 0, vagy pedig az indukciós feltevés szerint felírható az a1,a2,...,ak-1 sorozatból kiválasztott számok összegeként. Így tehát vagy n=ak, vagy pedig ak-t a kiválasztott számokhoz csatolva összegül n adódik.
 
II. megoldás. Ismét azt bizonyítjuk, hogy ha 0<n≤a1+a2+...+ak, akkor n felírható az a1,a2,...,ak sorozatból kiválasztott számok összegeként, de most n-re vonatkozó teljes indukciót alkalmazunk.
Ha n=1, akkor a1=1 miatt helyes az állítás, akármekkora is k értéke. Legyen tehát n>1, és tegyük fel, hogy állításunk helyes, ha benne n helyén nála kisebb m szám áll.
A rögzített n>1 mellett olyan k értékeket kell tekintenünk, amelyekre n≤a1+a2+...+ak teljesül. Elég, ha közülük csak a legkisebbel foglalkozunk, tehát azzal a k értékkel, amelyre
a1+a2+...+ak-1<n≤a1+a2+...+ak,
hiszen k növelésekor az összegül n-et adó számok kiválasztásához rendelkezésre álló választék csak növekszik.
Egyenlőtlenségeinkből az m=a1+a2+...+ak-n értékre 0≤m<ak adódik. Így tehát a feladat feltevését is alkalmazva
0≤m≤ak-1≤a1+a2+...+ak-1<n.
Ha tehát az érdektelen m=0 (azaz n=a1+a2+...+ak) esetet figyelmen kívül hagyjuk, akkor
0<m<n≤a1+a2+...+ak.
Indukciós feltevésünk szerint ez éppen azt biztosítja, hogy m előállítható az a1,a2,...,ak sorozatból kiválasztott számok összegeként. Ha tehát ezeket ebből a sorozatból elhagyjuk, akkor a megmaradóknak n 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 i≠2 esetben a1=1, viszont a2=3, akkor a feltevés a k=2 esetben nem teljesül: 3>1+1, 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ó c1,c2,c3,... végtelen sorozatból kiválasztott számok összegeként, akkor ez a sorozat átrendezhető a1=1,a2,a3,... alakba úgy, hogy
ak≤1+a1+a2+...+ak-1
minden k>1 értékre teljesüljön.
Abból indulunk ki, hogy a1=1 lehetséges választás, hiszen 1-nek szerepelnie kell a c1,c2,c3,... sorozatban, mert 1 is előállítható általa. A további a1 értékek megválasztását a következőképpen szabályozzuk:
Minthogy N2=2 előállítható, a c1,c2,c3,... sorozatban a1 elhagyása után is szerepelnie kell legalább egy N2-nél nem nagyobb elemnek (ti. 1-nek vagy 2-nek). Azt választjuk közülük a2-nek, amelyiknek a c1,c2,c3,... sorozatban a legkisebb az indexe.
a2 megválasztása után van egy legkisebb N3 természetes szám (ti. 3 vagy 4), amely nem írható fel a véges a1, a2 sorozatból kiválasztott számok összegeként. Szerepelnie kell ezért a c1,c2,c3,... sorozatban a1, és a2 elhagyása után is legalább egy N3-nál nem nagyobb számnak. Azt választjuk közülük a3-nak, amelyiknek az indexe a c1,c2,c3,... sorozatban a legkisebb.
Így folytatjuk ezt az eljárást. Ha már megválasztottuk az a1,a2,...,ak-1, sorozatelemeket, akkor van egy legkisebb Nk természetes szám, amely nem írható fel a véges a1,a2,...,ak-1 sorozatból kiválasztott számok összegeként. Szerepelnie kell ezért a c1,c2,c3,... sorozatban a már kiválasztott elemek elhagyása után legalább egy Nk-nál nem nagyobb számnak. Ezek közül azt választjuk ak-nak, amelyiknek az indexe a c1,c2,c3,... sorozatban a legkisebb.
A következő lépésben fellépő Nk+1 nagyobb Nk-nál, hiszen Nk maga már bizonyosan felírható az a1,a2,...,ak sorozatból kiválasztott számok összegeként vagy azért, mert ak=Nk, vagy pedig azért, mert ak mellé az a1,a2,...,ak-1 sorozatból Nk-ak összeget adó számokat választhatunk ki, hiszen Nk volt a legkisebb így elő nem állítható szám.
Ha tehát eljárásunkat minden határon túl folytatjuk, akkor N2<N3<N4<... miatt a c1,c2,c3,... sorozat bármely ci eleme előbb-utóbb kiválasztásra kerül, mert ha pl. a k-adik lépésben már Nk≥ci akkor ettől a lépéstől kezdve csak ci vagy nála kisebb indexű elem kerülhet kiválasztásra, márpedig a véges sok c1,c,...,ci-1 elem előbb-utóbb elfogy. Ezek szerint az általunk képezett a1,a2,a3,... sorozatban a c1,c2,c3,... sorozat minden eleme előfordul, tehát az utóbbi sorozatot valóban átrendeztük.
Nk definíciójából következik, hogy értéke legfeljebb 1+a1+a2+...+ak-1 hiszen ez a szám biztosan nem állítható elő az a1,a2,...,ak-1 sorozatból kiválasztott számok összegeként. Minthogy pedig ak≤Nk, bebizonyítottuk, hogy feladatunk feltevésének teljesülnie kell az átrendezéssel származtatott a1,a2,a3,... sorozatra.
3. Ha az a1≤a2≤a3≤... 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 ak>1+a1+a2+...+ak-1=n, akkor n nem írható fel az a1,a2,a3,... sorozatból kiválasztott számok összegeként, hiszen ebben a végtelen sorozatban csak az a1,a2,...,ak-1 elemek nem nagyobbak n-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 k>1 értékre teljesül az
ak≤2k-1
egyenlőtlenség. Ezt k-ra vonatkozó teljes indukcióval bizonyítjuk be. A k=2 esetben helyes az állítás, mert a feltevés szerint a2≤1+a1=21. Legyen tehát k>2, és tegyük fel, hogy az állítás teljesül, ha benne k helyén nála kisebb szám áll. Ekkor
ak≤1+a1+a2+...+ak-1≤1+20+21+...+2k-2=2k-1,
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ó 2 különböző hatványainak összegeként. Beláttuk tehát, hogy a vizsgált tulajdonságú sorozatok közül 2 hatványsorozatának az elemei a legnagyobbak.