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