Feladat: 1966. évi Kürschák matematikaverseny 3. feladata Korcsoport: 18- Nehézségi fok: nehéz
Megoldó(k):  Elekes György ,  Hoffmann György ,  Lovász László ,  Surányi László 
Füzet: 1967/május, 197 - 200. oldal  PDF  |  MathML 
Témakör(ök): Számhalmazok, Halmazok számossága, Tizes alapú számrendszer, Természetes számok, Kettes alapú számrendszer, "a" alapú számrendszer (a >1, egész szám), Prímszámok, Teljes indukció módszere, Oszthatóság, Kombinatorikai leszámolási problémák, Számsorok, Kürschák József (korábban Eötvös Loránd)
Hivatkozás(ok):Feladatok: 1967/április: 1966. évi Kürschák matematikaverseny 3. 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.

Megmutatjuk, hogy vannak kívánt tulajdonságú A, B számhalmazok, s ehhez elég egyetlenegy példát megadnunk.
Tartozzanak az A halmazhoz mindazok a nem-negatív egész számok, amelyeknek minden 0-tól különböző tizedesjegye (a szám végétől visszafelé számítva) páratlanadik helyen áll, B-hez pedig azok, amelyeknek minden 0-tól különböző jegye párosadik helyen helyezkedik el. A 0 eszerint mind a két halmazhoz hozzátartozik, hiszen nincs 0-tól különböző tizedesjegye.
Ha egy-egy A-hoz és B-hez tartozó számot összeadunk, akkor az összeg tizedesjegyei éppen a két szám megfelelő tizedesjegyei lesznek, hiszen ugyanazon a helyen mindig csak az egyikben állhat 0-tól különböző számjegy, s ez lesz az összeg tizedesjegye. Bármely nem-negatív egész szám páratlanadik jegyeiből egy A-hoz, párosadik jegyeiből egy B-hez tartozó számot alkothatunk, s ezek összege a fentiek szerint éppen az a szám lesz, amelyből kiindultunk. A két halmaz más számainak összege nem lehet ugyanez az érték, mert valahol más tizedesjegynek kell bennük szerepelnie, s akkor ezt összegük is tartalmazza.
Ha pl. 1967-ből indulunk ki, akkor ebből az A-hoz tartozó 907 és a B-hez tartozó 1060 adódik. Ezek összege valóban 1967.
Meg kell még állapítanunk, hogy az A, B halmazok mindegyike végtelen halmaz. Ez igaz, mert végtelen sok páratlanadik és végtelen sok párosadik tizedeshely van.

 
Megjegyzések. 1. A feladat megoldásaként csak egyetlenegy példát adtunk meg. Sok más példát is megadhattunk volna.
Eljárásunk változatlanul alkalmazható, ha nem tízes, hanem tetszőleges alapú számrendszert használunk. Legtetszetősebbnek talán a kettes számrendszer választásakor adódó példa mondható.
Megoldásunkban a (szám végétől visszafelé számlált) páratlanadik és párosadik tizedeshelyek szolgáltatták a két számhalmazt. Ehelyett a tizedeshelyeket akárhogyan is eloszthattuk volna két csoportba, mindenesetre azonban úgy, hogy mindkét csoport végtelen sok tizedeshelyet tartalmazzon. Így pl. sorolhatnók az egyikbe azokat a tizedeshelyeket, amelyeknek a szám végétől visszafelé számított sorszáma 3-mal osztható, s a másikba a többit. Vagy az egyikbe azokat, amelyeknek a sorszáma törzsszám, s a másikba a többit. Ilyen módon újabb példákhoz juthatunk természetesen akkor is, ha nem a tízes számrendszert használjuk.
További példákhoz jutunk, ha változó alapú számrendszerből indulunk ki. Ez a következőt jelenti: tetszőlegesen megválasztjuk az 1-nél nagyobb k1, k2,... alapszámokat; ezekkel minden nem-negatív egész számot kifejezhetünk
c1+c2k1+c3k1k2+c4k1k2k3+...
alakban, ahol a c1, c2,... számjegyek mindegyikére teljesül a 0≤ci<ki megszorítás, és természetesen minden szám kifejezésében csak véges sok számjegy szerepel. Egy szám számjegyeihez úgy juthatunk el, hogy azt k1-gyel osztva c1 lesz a maradék, a hányadost k2-vel osztva maradékként c2 adódik, majd a hányadosokat mindig tovább osztva a többi számjegyet is megkapjuk. Ilyen változó alapú számrendszerre változatlanul alkalmazhatjuk megoldásunk eredeti eljárását, s így a feladat kérdésére adott válasz helyességét bizonyító újabb példákat kapunk. Könnyen meggyőződhetünk arról, hogy minden korábban említett példa ennek a most ismertetett példának speciális esete.
2. Megmutatjuk, hogy a most megismert példa a legáltalánosabb, hogy tehát a feladat követelményét kielégítő bármely A, B halmazpárhoz el lehet jutni a változó alapú számrendszer alapszámainak megfelelő megválasztása után megoldásunk eredeti módszerével.
Legyen tehát A és B a feladat követelményét kielégítő két számhalmaz. Eszerint minden nem-negatív egész szám pontosan egyféleképpen állítható elő A és B egy-egy elemének összegeként. Ha a következőkben előállításról szólunk, mindig ilyen előállításra gondolunk. Jelölje a(n) és b(n) a két halmaznak azt az elemét, amelyek n előállításában fellépnek, amelyekre tehát n=a(n)+b(n).
A 0 mindkét halmaz eleme, mert különben 0 nem volna a két halmaz egy-egy elemének összegeként előállítható. A két halmaznak nincs más közös eleme, mert ha n ilyen volna, akkor n kétféleképpen is előállítható volna, ti. n+0 és 0+n alakban. Valamelyik halmaz elemei között 1 is szerepel, mert különben 1 nem volna előállítható. Legyen A ez a halmaz, s legyen k1 az a legkisebb természetes szám, amely A-nak nem eleme.
Azt állítjuk, hogy k1 szerepel B-ben. b(k1) nem lehet 0, mert ebből a(k1)=k1 következnék, pedig k1 nem tartozik A-hoz. Nem lehet b(k1) az 1, 2,...,k1-1 számok egyikével sem egyenlő, mert mindezek A elemei. Ezért szükségképpen b(k1)=k1, tehát k1 valóban eleme a B halmaznak.
A nem-negatív egész számokat k1 számból álló ,,szakaszokba'' osztjuk be. Egy ilyen szakasz a
tk1,tk1+1,...,tk1+(k1-1)(*)
számokból áll. Azt állítjuk, hogy egy-egy ilyen szakasz x számaira b(x) értéke azonos, s hogy ez az érték k1 többszöröse. Ez persze azt is jelenti, hogy a szakasz számaihoz tartozó a(x) értékek ugyancsak egy teljes szakaszt alkotnak.
Állításunkat t-re vonatkozó teljes indukcióval bizonyítjuk be. Az állítás a t=0 értékre teljesül, hiszen a kezdőszakasz minden elemére b(x)=0. Feltesszük, hogy állításunk a tk1 számot megelőző szakaszok mindegyikére helyes, bebizonyítjuk, hogy helyes a (*) szakaszra is.
Feltevésünkből következik, hogy az A halmaz tk1-nél kisebb elemei teljes szakaszokat alkotnak, hiszen A minden eleme fellép saját magának az előállításában, hozzá B-ből a 0 elemet adva, s akkor a tartalmazó szakasz minden elemére b(x)=0, a megfelelő a(x)=x értékek tehát valóban egy teljes szakaszt alkotnak. Feltevésünkből az is következik, hogy a B halmaz tk1-nél kisebb elemei mindannyian k1 többszörösei, hiszen mindegyik fellép a saját előállításában (A-ból a 0 elemet adva hozzá), s azért az indukciós feltevés reá is vonatkozik.
Tekintsük most már a (*) szakasz számainak előállítását. Ha e szakasz valamelyik x elemére a(x)<tk1 és b(x)<tk1, akkor utolsó megállapításunk szerint b(x) osztható k1-gyel, s így az a(x)+b(x) összegben a(x) helyébe az ezt az értéket tartalmazó és A-hoz tartozó szakasz elemeit írva a (*) szakasz minden elemének előállításához eljutunk. Ilyenkor tehát a bizonyítandó állítás teljesül.
Azt az esetet kell már csak vizsgálnunk, amikor (*) minden elemének előállításában szerepel tk1-nél nem kisebb szám is. Maga tk1 tehát vagy tk1+0, vagy 0+tk1 módon állítható elő. Az utóbbi esetben 0 helyébe az A-hoz tartozó 1, 2,...,k1-1 számokat írva ismét eljutunk (*) minden elemének olyan előállításához, amelyre állításunk teljesül.
Legyen tehát a(tk1)=tk1. Ekkor tk1 az A halmaz eleme. A (*) szakasz többi eleme sem tartozhatik B-hez, mert ha tk1+c1 odatartoznék, ahol 0<c1<k1, akkor
(k1-c1)+(tk1+c1)=tk1+k1
ugyanannak a számnak kétféle előállítása volna. Eszerint a (*) szakasz x elemére b(x)≥tk1 nem teljesülhet, s ezért a vizsgált eset tulajdonsága miatt szükségképpen a(x)≥tk1, amiből x<tk1+k1 miatt b(x)<k1 következik. Minthogy azonban B a k1-nél kisebb számok közül csak a 0-t tartalmazza, a b(x)=0 eredményhez jutunk (amiből az is következik, hogy a teljes (*) szakasz A-hoz tartozik). Eszerint a bizonyítandó állítás most is teljesül.
Indukciós okoskodásunk befejezése után megállapíthatjuk, hogy az A halmaz teljes ,,szakaszokból'' áll, s hogy B minden eleme k1 többszöröse. Mindkét halmaz teljes ismeretéhez elég eszerint azt tudnunk, hogy k1 többszörösei közül melyeket tartalmazzák.
Tekintsünk olyan változó alapú számrendszert, amelynek első alapszáma k1. Eredményünk szerint ebben a számrendszerben B minden elemének első jegye 0, viszont A bármely elemének első jegyét tetszőlegesen megváltoztatva megint A eleméhez jutunk.
Azt vizsgáljuk, hogy k1 többszörösei közül melyek tartoznak a két halmazhoz. Álljon az A1 halmaz azokból a nem-negatív n egész számokból, amelyekre nk1 az A halmaz eleme, B1 pedig azokból, amelyekre nk1 a B halmaz eleme. Az A1, B1 halmazok rendelkeznek az A, B halmazoknak a feladatban foglalt tulajdonságaival, hiszen k1 többszörösei is egyféleképpen állíthatók elő és előállításukban a fentiek szerint csak k1 többszörösei lépnek fel. Különbség van azonban A és B, valamint A1 és B1 szereposztásában, mert mintegy szerepet cserélnek. Azt a halmazt jelöltük A-val, amelynek 1 eleme, most viszont B1 játssza ezt a szerepet, hiszen 1 ennek eleme, mert k1 a B halmazhoz tartozik.
Az A1, B1 halmazokra elvégezhetjük ugyanazt az okoskodást, amelyet az A, B halmazokra már elvégeztünk. Ezt azzal kezdjük, hogy a legkisebb, B1 hez nem tartozó természetes számot k2-vel jelöljük. Így azt kapjuk, hogy A1 minden eleme k2 többszöröse, B1 pedig k2 számból álló teljes ,,szakaszokból'' áll. Ha k2-t választjuk számrendszerünk második alapszámául, akkor tehát elmondhatjuk, hogy A minden elemének második jegye 0, viszont B minden elemének második jegyét szabadon megváltoztathatjuk, s megint B eleméhez jutunk.
Ezt az eljárást minden határon túl folytathatjuk, hiszen végtelen halmazokból indultunk ki. Eljutunk tehát egy változó alapú számrendszer k1, k2... alapszámainak végtelen sorozatához. Minthogy a növekvő indexű halmazok állandóan szerepet cserélnek, ahhoz az eredményhez jutunk, hogy A elemeinek minden párosadik jegye 0, páratlanadik jegyeik pedig tetszőlegesek, a B halmaz elemeinél viszont fordítva, minden páratlanadik jegyük 0, és párosadik jegyeik tetszőlegesek. Megoldásunk eredeti módszere tehát valóban ehhez a két halmazhoz vezet el, ha az előírásunknak megfelelő változó alapú számrendszert használjuk.
3. A feladat két általánosítását említjük még meg. A részletek kidolgozását azonban már az olvasóra bízzuk.
A feladat kérdésére igennel kell felelni akkor is, ha nem két végtelen halmazról, hanem kettőnél többről van a feladatban szó. Ez első megjegyzésünknek ahhoz az észrevételéhez kapcsolódik, hogy a tizedeshelyeket akárhogyan beoszthatjuk két (végtelen sok tizedeshelyet tartalmazó) csoportba. Ha nem két, hanem kettőnél több csoportba osztjuk be őket, akkor a mondott általánosításhoz jutunk.
Igennel kell felelni a feladat kérdésére akkor is, ha benne nem-negatív egész számok helyett egész számokat mondunk. Ennek megvilágítása érdekében a végtelen
(1+x)(1+x2)(1+x4)(1+x8)...
szorzatot tekintjük. Ha itt a beszorzást formálisan elvégezzük, x minden nemnegatív egész kitevőjű hatványának összege adódik eredményül. Ha a szorzat tényezőit két csoportba szedve, pl. csak a páratlanadikokat, majd csak a párosadikokat szorozzuk össze, akkor az adódó két kifejezésben fellépő kitevők példát adnak olyan A, B halmazokra, amilyenekről a feladat szólt. Ha most a fenti szorzat helyett az
(1+x)(1+x-2)(1+x4)(1+x-8)...
szorzatot tekintjük, akkor a beszorzás x minden egész kitevőjű hatványának összegét adja, s a tényezők két csoportba szedésekor fellépő kitevőhalmazok az egész számok körében kimondott általánosítás helyességét támasztják alá.