2019 Egzamin poprawkowy

Zadanie 1

Niech \(a_n\) oznacza liczbę prostokątów o niezerowym polu, bokach równoległych do osi układu współrzędnych i wierzchołkach należących do zbioru \(\{(x, y) \in \mathbb{N}^2 : 0 \leq x + y \leq n+1\}\) (np. \(a_0=0,a_1 = 1, a_2 = 5\) ). Znajdź funkcję tworzącą i zwarty wzór na \(a_n\).

Zadanie 2

Oblicz, ile dodatnich liczb naturalnych dzieli dokładnie jedną spośród liczb \(10^{40}, 20^{30}, 50^{25}\).

Zadanie 3

Niech \(G\) będzie grafem o liczbie chromatycznej \(\chi(G) \leq 8\). Udowodnij, że \(G\) jest sumą trzech rozłącznych krawędziowo grafów dwudzielnych.

Zadanie 4

Oblicz \(56! \cdot 199! \mod{257}\).