Feladat: N.10 Korcsoport: 18- Nehézségi fok: nehéz
Megoldó(k):  Csörnyei Marianna ,  Futó Gábor ,  Szeidl Ádám 
Füzet: 1994/november, 442 - 444. oldal  PDF  |  MathML 
Témakör(ök): Számhalmazok, Halmazok számossága, Skatulyaelv, Nehéz feladat
Hivatkozás(ok):Feladatok: 1993/november: N.10

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.

Tetszőleges M és N pozitív egészekből álló halmaz esetén jelölje M+N az

M∪N∪{m+n:m∈M,n∈N}

halmazt, és definiáljuk sorra az A0,A1,... halmazokat az

A0=AAi+1=Ai+Ai(i=0,1,...)



rekurzióval. Nyilvánvaló, hogy Ai mindazokat a pozitív egészeket tartalmazza, amelyek legfeljebb 2i darabA-beli elem összegeként előállnak (egytagú összegen magát a tagot értjük). Ha a feladatbeli feltétel teljesül, akkor azt mondjuk, hogy A α-sűrű. Ezzel a szóhasználattal és eddigi jelöléseinkkel élve a feladat annak a bizonyítása, hogy alkalmas i-re Ai már 1-sűrű.
1. Lemma. Ha M és N pozitív egészekból álló halmaz, továbbá M μ-sűrű és N ν-sűrű (μ,ν≥0), akkor M+N (μ+ν-μν)-sűrű.
Bizonyítás. Vezessük be minden pozitív egész x esetén az
M(x)=|M∩{1,2,...,x}|ésN(x)=|N∩{1,2,...,x}|

jelöléseket, akkor nyilván M(x)≥μx és N(x)≥νx a feltétel szerint. Ha μ=0 vagy ν=0, akkor semmitmondó az állítás. Tegyük fel ezért, hogy μ,ν>0, ekkor M(1)≥μ>0 és N(1)≥ν>0, azaz 1 eleme M-nek és N-nek. Most tehát tetszőleges pozitív egész x esetén az M+N halmazhoz tartoznak az alábbi különböző {1,2,...,x}-be eső számok:
1) Az M-ből választott 1=m1<m2<...<mM(x) egészek; ezek száma M(x).
2) Minden 1≤i<M(x) esetén az mi+n alakú egészek, ahol n∈N és 0<n<mi+1-mi; ezek száma N(mi+1-mi-1).
3) Az mM(x)+n alakú egészek, ahol n∈N és 0<n≤x-mM(x); ezek száma N(x-mM(x)).
Mindezek alapján
|(M+N)∩{1,2,...,x}|≥
≥M(x)+N(m2-m1-1)+N(m3-m2-1)+......+N(mM(x)-mM(x)-1-1)+N(x-mM(x))≥
≥M(x)+ν(m2-m1-1)+ν(m3-m2-1)+......+ν(mM(x)-mM(x)-1-1)+ν(x-mM(x))≥
≥M(x)+ν(x-M(x))=νx+(1-ν)M(x)≥νx+(1-ν)μx=(μ+ν-μν)x,

és ezt kellett igazolnunk.
2. Lemma. Ha M és N pozitív egészekből álló halmaz, továbá M μ-sűrű és N ν-sűrű (μ,ν≥0), ahol μ+ν≥1, akkor M+N 1-sűrű.
Bizonyítás. Használjuk az előző lemma bizonyításának jelöléseit. Ha μ=0, akkor ν=1, vagyis már N is 1-sűrű. Legyen ezért μ>0, és x tetszőleges pozitív egész. Azt kell megmutatnunk, hogy x∈M+N. Ha x∈M, akkor készen vagyunk. Egyébként pedig x>1 és
M(x-1)=M(x)≥μx>μ(x-1)ésN(x-1)≥ν(x-1).

Ezek szerint az {1,2,...,x-1} halmazba több, mint μ(x-1) darab M-beli, és legalább ν(x-1) darab N-beli szám esik. Mivel μ(x-1)+ν(x-1)≥x-1, azért a skatulyaelvet használva az x-n (n∈N,n≤x-1) alakú számok egyike megegyezik egy M-beli m számmal. Ez viszont éppen azt jelenti, hogy x m+n alakú, ahol m∈M és n∈N.
Ezzel a feladat állítását beláttuk.
Megjegyzés. A bizonyítás csekély módosításával az is igazolható, hogy minden pozitív egész szám előáll legfeljebb C darab A-beli elem összegeként, ha
C=2⌈log2log11-a⌉.