A B. 4763. feladat (2016. január)

B. 4763. Legyen $\displaystyle G$ egy $\displaystyle n$ csúcsú, irányítatlan, egyszerű gráf. Igazoljuk, hogy megadhatóak a gráfhoz a természetes számok olyan végtelen $\displaystyle \mathcal{H}_1,\mathcal{H}_2, \ldots, \mathcal{H}_n$ részhalmazai, amelyekre bármely két részhalmaz metszete végtelen, ha a hozzájuk tartozó csúcsok éllel összekötöttek, és üres, ha nincs él a megfelelő csúcsok között.

Javasolta: Mészáros Gábor (Budapest)

(4 pont)

A beküldési határidő 2016. február 10-én LEJÁRT.

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 $\displaystyle n-1$ csúcsú gráfokra igaz, és a halmazok uniójának legnagyobb eleme $\displaystyle k$, akkor az $\displaystyle n$-edik csúcs szomszédaihoz tartozó részhalmazokat bővítsük rendre $\displaystyle k+1$-gyel, $\displaystyle k+2$-vel, stb; az $\displaystyle n$-edik csúcshoz pedig tartozzon a $\displaystyle \{ k+1, k+2, \ldots \}$ halmaz.

A $\displaystyle G$ gráf csúcsaihoz rendelt halmazok ,,végtelenítése'': ha a véges halmazok uniójának legnagyobb eleme $\displaystyle M$, akkor minden részhalmazhoz és annak mindegyik $\displaystyle t$ elemére vegyük hozzá az összes $\displaystyle t+iM$ számot, valamennyi $\displaystyle i>1$ egészre.

Statisztika:

105 dolgozat érkezett.
4 pontot kapott:	99 versenyző.
3 pontot kapott:	3 versenyző.
2 pontot kapott:	2 versenyző.
1 pontot kapott:	1 versenyző.

A KöMaL 2016. januári matematika feladatai