Középiskolai Matematikai és Fizikai Lapok
Informatika rovattal
Kiadja a MATFUND Alapítvány
Már regisztráltál?
Új vendég vagy?

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