 |
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