Problem B. 5105. (May 2020)

B. 5105. Let \(\displaystyle n\) denote a positive integer. Determine the smallest number of colours \(\displaystyle k\) that are sufficient for colouring the edges of any directed simple graph of \(\displaystyle n\) vertices without producing a circuit of the same colour.

Proposed by K. Szabó, 11th grade student of Fazekas Mihály Primary and Secondary School and Training Centre, Budapest

(4 pont)

Deadline expired on June 10, 2020.

Sorry, the solution is available only in Hungarian. Google translation

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).

Statistics:

45 students sent a solution.
4 points:	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 points:	Molnár Lehel, Mosolygó László.
2 points:	1 student.
1 point:	3 students.
0 point:	1 student.

Problems in Mathematics of KöMaL, May 2020