2019 Kolokwium 2
Zadanie 1
Niemalejący ciąg liczb naturalnych \(\langle s_1, \dots, s_n \rangle\) jest ciągiem stopni wyjściowych wierzchołków \(n\)-turnieju \(T\). Udowodnij, że \(T\) jest silnie spójny wtedy i tylko wtedy, gdy
\[\sum^{k}_{i=1} s_i > {k \choose 2} \quad \textrm{dla}\ 1 \le k < n.\]Zadanie 2
Niech \(G_n\) będzie grafem o zbiorze wierzchołków \(\{1, 2, \dots, n\}^2\), w którym \(\{\langle a, b \rangle, \langle c, d \rangle\}\) jest krawędzią wtedy i tylko wtedy, gdy \(a=c\) lub \(b=d\). Znajdź liczbę chromatyczną \(\chi(G_n)\).
Zadanie 3
Niech \(a_n\) oznacza liczbę powstającą przez konkatenację liczb Fibonacciego \(F_1, F_2, \dots, F_n\) (np. \(a_4 = 1123\)). Oblicz \(a_{2019}\mod 6\).