Feladat:	B.4763	Korcsoport: 16-17	Nehézségi fok: átlagos
Megoldó(k):	Várkonyi Dorka
Füzet:	2016/szeptember, 345 - 346. oldal		PDF  |  MathML
Témakör(ök):	Feladat, Gráfelmélet, Számhalmazok, Teljes indukció módszere
Hivatkozás(ok):	Feladatok: 2016/január: B.4763

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. Rendeljünk mindegyik élhez egy-egy különböző prímszámot, ez megtehető, mivel végtelen sok prímszám van. Legyen a ${\text{H}}_i$ halmazban azoknak a prímeknek az összes pozitív egész kitevős hatványa, amelyek azokon az éleken vannak, amik a ${\text{H}}_i$-hez tartozó csúcsból indulnak ki. Ha két csúcs össze van kötve egy éllel, akkor mindkét halmazban benne vannak az élhez rendelt prím pozitív egész kitevős hatványai, tehát a két halmaz metszete végtelen. Ha két csúcs nincsen éllel összeköteve, akkor különféle élekhez tartozó prímek hatványai szerepelnek csak a két halmazban, a metszetük üres halmaz. Ez a konstrukció megfelel a feladat feltételeinek.   II. megoldás. Először véges részhalmazokat rendelünk a csúcsokhoz úgy, hogy két ilyennek a metszete pontosan akkor üres, ha a megfelelő csúcsok nincsenek éllel összekötve. Ezt a csúcsok száma szerinti indukcióval láthatjuk be: egy vagy két csúcsra ez nyilvánvaló. Ha pedig $n-1$ csúcsú gráfokra igaz, és a halmazok uniójának legnagyobb eleme $k$, akkor az $n$-edik csúcs szomszédaihoz tartozó részhalmazokat bővítsük rendre $\left(k+1\right)$-gyel, $\left(k+2\right)$-vel stb.; az $n$-edik csúcshoz pedig tartozzon a $\left\{k+\mathrm{1,}k+\mathrm{2,}\text{...}\right\}$ halmaz. A $G$ gráf csúcsaihoz rendelt halmazok ,,végtelenítése'': ha a véges halmazok uniójának legnagyobb eleme $M$, akkor minden részhalmazhoz és annak mindegyik $t$ elemére vegyük hozzá az összes $t+iM$ számot, valamennyi $i>1$ egészre. Ha az így kapott (végtelen) halmazok közül kettőnek $t$ közös eleme, akkor van végtelen sok közös elemük is: $t+M$, $t+2M$, $\text{...}$ . Ha pedig két diszjunkt véges halmaz végtelenre bővítettjeinek $t_1+iM=t_2+jM$ közös eleme lenne, akkor $|t_1-t_2|=|i-j|M$, ahol $0<t_1\mathrm{,}{t}_2\le M$ és $t_1\ne t_2$ miatt a bal oldal értéke $M$-nél kisebb pozitív szám, a jobb oldal viszont nagyobb mint $M$, ami ellentmondás.