Feladat:	2016. évi Kürschák matematikaverseny 2. feladata	Korcsoport: 18-	Nehézségi fok: nehéz
Megoldó(k):	Fleiner Tamás
Füzet:	2017/február, 68 - 70. oldal		PDF  |  MathML
Témakör(ök):	Kürschák József (korábban Eötvös Loránd), Halmazelmélet, Oszthatóság
Hivatkozás(ok):	Feladatok: 2017/február: 2016. é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.   I. megoldás. A megoldás során az alábbi szóhasználattal élünk. Azt mondjuk, hogy a $b$ pozitív egész az $a$ pozitív egészet felülről dominálja, ha $a$ osztója $b$-nek, és alulról dominálja, ha $b+1$ osztója $\left(a+1\right)$-nek. (Minden pozitív egész tehát felülről és alulról is dominálja önmagát.) A $b$ egész akkor dominálja $a$-t, ha $b$ felülről vagy alulról dominálja $a$-t. Az $X$ halmaz pedig akkor dominálja az $Y$ halmazt, ha $Y$ minden $y$ eleméhez található olyan $x$ az $X$-ből, amely dominálja $y$-t. Végül, pozitív egészek egy $Z$ halmazát akkor nevezzük függetlennek, ha $Z$ egyetlen eleme sem dominálja $Z$ egy másik elemét. Az imént bevezetett terminológia segítségével a feladat állítása úgy fogalmazható meg, hogy a pozitív egészek minden véges $A$ halmazának van olyan független $B$ részhalmaza, amely dominálja $A$-t. Tekintsük az $A$ halmaz mindazon $C$ részhalmazait, melyekre $\left(a\right)$ $C$ független, másfelől $\left(b\right)$ ha $A$ valamely $x$ eleme alulról dominálja $C$ egy elemét, akkor $C$ felülről dominálja $x$-et. Létezik a fenti tulajdonságokat teljesítő $C$ halmaz, hisz az üreshalmaz például ilyen. Válasszuk a $B$ halmazt ezen $C$ halmazok közül úgy, hogy $B$ a lehető legtöbb elemét dominálja felülről az $A$ halmazban. Azt állítjuk, hogy egy eképpen választott $B$ halmaz rendelkezik a feladatban előírt tulajdonságokkal. Mivel $B$-t függetlennek választottuk, ezért csupán azt kell igazolni, hogy $B$ dominálja a teljes $A$ halmazt. Indirekt módon bizonyítunk, tegyük fel, hogy $B$ mégsem dominálja $A$-t. Legyen tehát $a$ az $A$ halmaz legkisebb olyan eleme, amit $B$ nem dominál, és legyen $B\text{'}:=B\setminus D\left(a\right)\cup \left\{a\right\}$, ahol $D\left(a\right)$ az $a$ osztóinak halmazát jelöli. Megmutatjuk, hogy $B$ választásának ellentmondva a $B\text{'}$ halmaz amellett, hogy több elemet dominál felülről, mint $B$, teljesíti az $\left(a\right)$ és $\left(b\right)$ tulajdonságokat is. A konstrukcióból adódóan $B\text{'}$ az $A$ halmaz minden olyan elemét felülről dominálja, amely elemeket $B$ felülről dominál, és ezen túl $B\text{'}$ felülről dominálja $a$-t is. Ezért $B\text{'}$ több elemet dominál felülről, mint $B$. A $B$ részhalmazaként $B\text{'}\setminus \left\{a\right\}$ független, továbbá az $a$ választásából adódóan $B\text{'}\setminus \left\{a\right\}$ nem dominálja $a$-t. Sőt, $a$ sem dominálja $B\text{'}\setminus \left\{a\right\}$ egyetlen elemét sem: alulról a $B$ halmaz $\left(b\right)$ tulajdonsága miatt, felülről pedig $B\text{'}$ definíciójából adódóan. Ezért a $B\text{'}$ halmaz csakugyan független. Végül, a $\left(b\right)$ tulajdonság igazolásához indirekt módon tegyük fel, hogy $x$ alulról dominálja $B\text{'}$ egy $y$ elemét. Ha mármost $y\in B$, akkor a $\left(b\right)$ tulajdonság miatt $B$ felülről dominálja $x$-et, így $B\text{'}$ is, tehát teljesül a $\left(b\right)$ tulajdonság. Ha pedig $y\notin B$, akkor $y=a$ és az alulról történő dominálás miatt $x<y$. Mivel $a$ az $A$ halmaz legkisebb olyan eleme, amit $B$ nem dominál, ezért $B$ dominálja $x$-et. Ha $B$ felülről dominálja $x$-et, akkor $B\text{'}$ is felülről dominálja $x$-et, a $\left(b\right)$ tulajdonság teljesül. Ha pedig $B$ egy $z$ eleme alulról dominálja $x$-et, akkor mivel $x$ alulról dominálja $a$-t, $z$ is alulról dominálja $a$-t. Ez azt jelenti, hogy $B$ mégiscsak dominálja $a$-t, ellentétben az $a$ választásával. A kapott ellentmondás pedig azt igazolja, hogy $B\text{'}$-re teljesül a $\left(b\right)$ tulajdonság, és ezzel a bizonyítást befejeztük. $\square$   II. megoldás. Az I. megoldásban bevezetett szóhasználatot tovább bővítjük. Pozitív egészek egy véges $H$ halmaza tetejének nevezzük azt a $H^{\uparrow }$ halmazt, melyet $H$ mindazon $h$ elemei alkotnak, amelyet nem dominál felülről a $H$ egyetlen $h$-tól különböző eleme sem. Hasonlóan, a $H$ halmaz $H^{\downarrow }$-val jelölt alja a $H$ azon $h$ elemeiből áll, amelyet a $H$-nak $h$-tól különböző eleme nem dominál alulról. Világos, hogy $H^{\uparrow }$ felülről, $H^{\downarrow }$ pedig alulról dominálja $H$-t, továbbá, hogy $H$ tetejének egyik eleme sem dominálja $H$ tetejének egy másik elemét felülről, illetve $H$ aljának egyetlen eleme sem dominálja $H$ aljának egy másik elemét alulról. Szükségünk lesz még az alábbi megfigyelésre. Ha egy $X$ halmaz alulról dominálja az $Y$ halmazt, továbbá az $Y$ alulról dominálja $Z$-t, akkor $X$ is alulról dominálja $Z$-t. Legyen ugyanis $z\in Z$ tetszőleges. Az $Y$ és $Z$ viszonya folytán létezik olyan $y\in Y$, amelyre $y+1$ osztója $\left(z+1\right)$-nek. Mivel $X$ alulról dominálja $Y$-t, ezért $X$-nek van olyan $x$ eleme, amelyre $x+1$ osztja $\left(y+1\right)$-et. Ám ekkor $x+1$ osztója $\left(z+1\right)$-nek is, azaz $X$ alulról dominálja $Z$ minden elemét. A továbbiakban megadunk egy véges eljárást, amely tetszőleges $A$ halmazhoz talál egy, a feladatban megkívánt tulajdonságokkal rendelkező $B$ részhalmazt. Legyen $\begin{array}{c}{\displaystyle A_0:=A\mathrm{,}{B}_0:=A_0^{\uparrow }\text{és}{X}_0:=B_0\setminus B_0^{\downarrow }\mathrm{.}}\end{array}$ Ha már meghatároztuk az $A_i$, $B_i$ és $X_i$ halmazokat, akkor legyen $\begin{array}{c}{\displaystyle A_{i+1}:=A_i\setminus X_i\mathrm{,}{B}_{i+1}:=A_{i+1}^{\uparrow }\text{és}{X}_{i+1}:=B_{i+1}\setminus B_{i+1}^{\downarrow }\mathrm{.}}\end{array}$ Figyeljük meg, hogy $B_{i+1}$ az $A_{i+1}$ teteje lévén felülről dominálja $A_{i+1}$-et és a $B_i^{\downarrow }$ alulról dominálja $B_i$-t, így $X_i$-t is. Ugyancsak a definícióból adódóan $B_i^{\downarrow }=B_i\setminus X_i\subseteq B_{i+1}$, ezért $B_{i+1}$ alulról dominálja $B_i^{\downarrow }$-t, így a $B_i^{\downarrow }$ által alulról dominált $X_i$-t is. Világos, hogy $A_0\supseteq A_1\supseteq A_2\supseteq \text{...}$, így az $A$ halmaz végessége miatt $A_k=A_{k+1}$ teljesül valamely $k$-ra. Ez azt jelenti, hogy $X_k=\varnothing$, azaz $B_k=B_k^{\downarrow }$. Mivel $B_k^{\uparrow }={\left(A_k^{\uparrow }\right)}^{\uparrow }=A_k^{\uparrow }=B_k$, ezért $B_k$ független. Megmutatjuk, hogy a $B=B_k$ halmaz megfelel a feladat feltételeinek. Láttuk, hogy $B_k$ független, így csupán azt kell bizonyítanunk, hogy $A$-t is dominálja. Korábban láttuk, hogy $B_k$ az $A_k$-t felülről dominálja. Elegendő tehát annyit bizonyítani, hogy $B_k$ alulról dominálja az $A\setminus A_k=X_0\cup X_1\cup \text{...}\cup X_{k-1}$ halmazt. Láttuk azt is, hogy $B_k$ alulról dominálja az $X_{k-1}$ halmazt. Mivel $B_{k-1}\subseteq B_k\cup X_{k-1}$, ezért $B_k$ a $B_{k-1}$-et is alulról dominálja. Hasonlóan, $B_{k-1}$ alulról dominálja $X_{k-2}$-t, így $B_{k-2}$-t is, tehát $B_k$ is alulról dominálja $B_{k-2}$-t. Ugyanez az érvelés mutatja, hogy $B_k$ alulról dominálja $X_i$-t és $B_i$-t minden $0\le i\le k$-ra. Mindezt összevetve kapjuk, hogy $B_k$ alulról dominálja az $X_0\cup X_1\cup \text{...}\cup X_{k-1}$ halmazt. Ezzel pedig beláttuk, hogy a $B=B_k$ halmaz rendelkezik a feladatban leírt tulajdonsággal. $\square$