A B. 5105. feladat (2020. május)

B. 5105. Legyen $\displaystyle n$ pozitív egész. Határozzuk meg azt a legkisebb $\displaystyle k$ számot, ahány színnel bármilyen $\displaystyle n$ csúcsú irányított egyszerű gráf élei színezhetők úgy, hogy ne legyen benne egyszínű kör.

Javasolta: Szabó Kornél (Budapesti Fazekas M. Gyak. Ált. Isk. és Gimn., 11. évf.)

(4 pont)

A beküldési határidő 2020. június 10-én LEJÁRT.

Megoldás. Ha $\displaystyle n=1$ vagy $\displaystyle n=2$, akkor egyetlen szín elegendő, hiszen a gráfban nem lehet irányított kör. Tehát ekkor $\displaystyle k=1$.

Tegyük fel, hogy $\displaystyle n\geq 3$. Ekkor $\displaystyle k\geq 2$ kell legyen, hiszen ha például a gráf egy irányított $\displaystyle k$ hosszú kör, akkor egy szín nem elég. Megmutatjuk, hogy $\displaystyle k=2$ szín már igen. Számozzuk meg a gráf csúcsait az $\displaystyle 1,2,\dots,n$ számokkal, és egy $\displaystyle i$ csúcsból egy $\displaystyle j$ csúcsba mutató irányított él legyen piros, ha $\displaystyle i<j$, és legyen kék, ha $\displaystyle i>j$. Ha az $\displaystyle i_1,i_2,\dots,i_l$ csúcsok ebben a sorrendben egy egyszínű irányított kör csúcsai lennének, akkor vagy $\displaystyle i_1<i_2<\dots<i_l<i_1$-nek, vagy $\displaystyle i_1>i_2>\dots>i_l>i_1$-nek kellene teljesülnie, azonban világos, hogy ezek egyike sem állhat fenn. Ezzel mutattunk olyan színezést 2 színnel, ami megfelelő.

Tehát $\displaystyle n=1,2$ esetén $\displaystyle k=1$ szín elég, $\displaystyle n\geq 3$ esetén pedig $\displaystyle k=2$ szín elég (de 1 nem biztosan).

Statisztika:

45 dolgozat érkezett.
4 pontot kapott:	Andó Viola, Argay Zsolt, Bán-Szabó Áron, Baski Bence, Beinschroth Ninett, Beke Csongor, Bognár 171 András Károly, Csizmadia Miklós, Czett Mátyás, Fekete Richárd, Fleiner Zsigmond, Füredi Erik Benjámin, Gábriel Tamás, Geretovszky Anna, Hervay Bence, Kercsó-Molnár Anita, Kerekes Boldizsár, Király Csaba Regő, Kovács 129 Tamás, Lengyel Ádám, Lovas Márton, Mácsai Dániel, Mohay Lili Veronika, Molnár-Szabó Vilmos, Móra Márton Barnabás, Móricz Benjámin, Nádor Benedek, Nagy 551 Levente, Németh Márton, Sándor Péter, Seres-Szabó Márton, Szabó 991 Kornél, Szakács Ábel, Sztranyák Gabriella, Terjék András József, Tóth 057 Bálint, Varga Boldizsár, Wiener Anna.
3 pontot kapott:	Molnár Lehel, Mosolygó László.
2 pontot kapott:	1 versenyző.
1 pontot kapott:	3 versenyző.
0 pontot kapott:	1 versenyző.

A KöMaL 2020. májusi matematika feladatai