2017 Pierwszy termin

Zadanie 1

Znajdź \(|\{b \in \{0,1\}^* : \#_{0}(b) + 2\#_{1}(b) \leq n\}|\), gdzie \(\#_{x}(b)\) oznacza liczbę wystąpień symbolu \(x\) w ciągu \(b\).

Zadanie 2

Iloczyn Hadamarda szeregów potęgowych \(A(x) = \sum_{n \geq 0} a_n x^n\) i \(B(x) = \sum_{n \geq 0} b_n x^n\) to szereg \(A(x) \bigodot B(x) = \sum_{n \geq 0} a_{n} b_{n} x^n\). Udowodnij, że jeśli \(A\) i \(B\) są funkcjami wymiernymi (czyli ilorazami wielomianów), to \(A \bigodot B\) też jest funkcją wymierną. Wskazówka: jakie ciągi \( \langle a_{n} \rangle\) mają wymierną funkcję tworzącą \(A(x)\)?

Zadanie 3

Udowodnij, że jeśli \(m,n > 1\) i \(m \mid 2^n - 1\), to \(l(m) > l(n)\), gdzie \(l(x)\) oznacza najmniejszy dzielnik pierwszy liczby \(x\). Wskazówka: Rozważ rząd elementu \(2\) w \(\mathbb{Z}_{l(m)}^*\).

Wskazówka wakacyjna

\(\mathbb{Z}_{t(m)}^*\) to nic innego jak grupa multiplikatywna modulo \(t(m)\). Jej elementy to liczby względnie pierwsze z \(t(m)\), działanie grupowe to mnożenie modulo. Zastanów się co dzieli się przez rząd elementu \(2\).

Rozwiązanie

Najpierw zauważmy, że \(m\) jest nieparzyste, więc \(l(m) \neq 2\). Stąd \(2 \in \mathbb{Z}_{l(m)}^* \). Oznaczmy rząd \(2\) w tej grupie jako \(r\). Z twierdzenia Lagrange'a \(r \mid l(m)-1\). Zatem \(r < l(m)\). Skoro \(m \mid 2^n-1\), to także \(l(m) \mid 2^n-1\), czyli \(2^n \equiv 1 \bmod l(m) \). To oznacza z kolei, że \(r \mid n\), gdyż \(r\) jest rzędem \(2\) (patrz definicja rzędu). Zachodzi teraz taka nierówność: \(l(n) \leq r < l(m)\), gdyż \(r\) jest dzielnikiem \(n\), a \(l(n)\) to najmniejsza liczba pierwsza w rozkładzie \(n\).

Zadanie 4

Macierz \(2 \times 3\) wypełniamy liczbami ze zbioru \(\{1,2,3\}\), przy czym każda z liczb musi wystąpić przynajmniej raz. Oblicz, na ile istotnie różnych sposobów można to zrobić, jeśli dwie macierze utożsamiamy, gdy jedną można otrzymać z drugiej strony przez pewną permutację wierszy i/lub kolumn.