Feladat:	B.4334	Korcsoport: 18-	Nehézségi fok: nehéz
Megoldó(k):	Viharos Andor
Füzet:	2012/december, 539 - 540. oldal		PDF  |  MathML
Témakör(ök):	Feladat, Teljes indukció módszere, Ponthalmazok, Részhalmazok
Hivatkozás(ok):	Feladatok: 2011/február: B.4334

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. Az egyenest a számegyenessel, a $Z$ halmazt az egész számokkal azonosíthatjuk. Nyilván elég belátni, hogy a pozitív egészek halmaza felbontható $H$-val egybevágó részhalmazokra. Azt is feltehetjük, hogy $H=\left\{\mathrm{0,}a\mathrm{,}a+b\right\}$, ahol $0<a\le b$. A pozitív egészeknek $H$-val egybevágó részhalmazai ekkor $A_x=\left\{x\mathrm{,}x+a\mathrm{,}x+a+b\right\}$ vagy $B_x=\left\{x\mathrm{,}x+b\mathrm{,}x+a+b\right\}$ alakúak, ahol $x>0$. Az első lépésben fedjük le az $1$-et $A_1$-gyel, majd az $i$-edik lépésben (ahol $i=\mathrm{2,3,}\text{...}$) fedjük le a legkisebb, az azt megelőző lépésekben még le nem fedett $x$ pontot $A_x$-szel, ha $x+a$ addig fedetlen volt, ellenkező esetben pedig $B_x$-szel, ha $x+b$ volt addig fedetlen. Az $i$ szerinti indukcióval megmutatjuk, hogy legalább az egyik feltétel valóban teljesül, és az újonnan felhasznált háromelemű halmaz a már korábban felhasználtak mindegyikétől diszjunkt. Tételezzük fel először indirekten azt, hogy az $i$-edik lépést nem tudjuk végrehajtani, mivel a korábbi lépéseink során már $x+a$-t és $x+b$-t is lefedtük. A korábban felhasznált fedő halmazok nem tartalmazhatják $x$-et, és legkisebb elemük csak $x$-nél kisebb lehet; ezért $x+a$ fedésére az $A_{x-b}$ vagy $B_{x+a-b}$ jöhetett csak szóba (az utóbbi is csak akkor, ha $a<b$). Hasonlóan, $x+b$ fedése csak a $B_{x-a}$-val történhetett. Ez azonban ellentmondás, hiszen $B_{x-a}$ választása valamelyik $j<i$-edik lépésben arra utal, hogy akkor $x-a$ lefedésére $A_{x-a}$ nem volt alkalmas, azaz akkor $\left(x-a\right)+a=x$ már le volt fedve. Ezzel beláttuk, hogy végrehajtható az $i$-edik lépés. Az ennek során felhasznált $A_x$ vagy $B_x$ halmaz csak a legnagyobb elemében, $x+a+b$-ben metszhetné a korábban felhasznált fedő halmazok valamelyikét, de akkor az eljárásunk miatt annak is $x+a+b$ lenne a legnagyobb eleme, vagyis legkisebb elemeik is egyenlőek lennének; tehát $x$-et már korábban lefedtük volna. Indukciós bizonyításunk egyben algoritmus a pozitív egészek halmazának, és ennél fogva $Z$-nek is a kívánt felbontására.