Feladat: 2006. évi Kürschák matematikaverseny 2. feladata Korcsoport: - Nehézségi fok: -
Füzet: 2007/február, 69 - 70. oldal  PDF  |  MathML 
Témakör(ök): Kürschák József (korábban Eötvös Loránd), Matematika, Részhalmazok, Számhalmazok
Hivatkozás(ok):Feladatok: 2007/február: 2006. é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.

Megoldás. Tekintsük az {1,2,...,n} halmaz azon a-t tartalmazó részhalmazait, melyekben bármely két különböző elem különbsége legalább t. Legyen H ezen részhalmazok halmaza. Álljon a K halmaz az {1,2,...,n} halmaz mindazon részhalmazaiból, amelyek a-t nem tartalmazzák, és amelyekben bármely két elem különbsége legalább t. Azt kell megmutatnunk, hogy |K|≤t2⋅|H| teljesül.
Ezt úgy bizonyítjuk be, hogy K minden eleméhez hozzárendeljük H egy-egy elemét úgy, hogy H minden egyes elemét K-nak legfeljebb t2 eleméhez rendeljük hozzá. Más szóval, mutatunk egy f:K→H leképezést, amire az teljesül, hogy H minden egyes eleme legfeljebb t2 elem képeként áll elő. Tetszőleges X∈K részhalmazhoz tekintsük az

f(X):=(X∖{a-t+1,a-t+2,...,a+t-2,a+t-1})∪{a}
halmazt, azaz hagyjuk el X-ből azokat az elemeket, amik a-hoz t-nél közelebb vannak, és vegyük be a-t f(X)-be. Világos, hogy f(X)∈H, hisz a∈f(X) teljesül, f(X)∖{a} bármely eleme legalább t-vel különbözik a-tól, továbbá f(X) bármely két a-tól különböző eleme egyúttal X-nek is eleme, ezért különbségük legalább t.
Megmutatjuk, hogy H bármely Y eleméhez legfeljebb t2-féleképpen választhatunk olyan X∈K-t, amelyre f(X)=Y. Hogyan képezhetjük egy adott Y-hoz ezeket az X halmazokat? Világos, hogy minden ilyen X-et megkaphatunk úgy, hogy Y-ból elhagyjuk az a elemet, majd további elemeket veszünk be az [a-t+1,a-1], illetve az [a+1,a+t-1] intervallumból úgy, hogy az így kapott halmazban is teljesüljön, hogy bármely két elem különbsége legalább t. Ez azt jelenti, hogy mind az [a-t+1,a-1], mind az [a+1,a+t-1] intervallumokból legfeljebb egy-egy elemet választhatunk ki. Mivel mindkét intervallum t-1 elemet tartalmaz, azért mindkét intervallum esetén t-féle választási lehetőségünk van: (t-1)-féleképp választhatunk ki egy elemet, illetve egyféleképp tehetjük meg, hogy nem választunk egyetlen elemet sem. Összességében tehát legfeljebb t⋅t=t2 a lehetőségeink száma. Ezért H tetszőleges eleme legfeljebb t2 K-beli elem képe, így csakugyan igaz, hogy
|K|≤t2|H|.□

 
Megjegyzés. A fenti becslés t>2 esetén javítható, ugyanis amikor Y∈H-hoz konstruálunk olyan X∈K-t, amire f(X)=Y teljesül, akkor általában nem tehetjük meg, hogy tetszőlegesen választjuk az [a-t+1,a-1]-beli és az [a+1,a+t-1]-beli elemeket. Ügyelnünk kell ugyanis arra is, hogy e két kiválasztott elem különbsége se legyen t-nél kisebb. Ezt figyelembe véve a becslésbeli t2 tényező 12⋅(t2+3t-2)-re javítható.