2015 Egzamin poprawkowy

Zadanie 1

Znajdź liczbę $k$-krotek zbiorów $\langle S_1, \dots, S_k \rangle$, gdzie $S_1, \dots, S_k \subseteq \{1, \dots, n\}$ oraz (a) $S_1 \subseteq S_2 \subseteq \dots \subseteq S_k$; (b) $\mid S_1 \cap \dots \cap S_k \mid = r$; (c) $S_1 \subseteq S_2 \supseteq S_3 \subseteq \dots $ (kierunek zawierania na zmianę).

Zadanie 2

Pagórek z monet to rozmieszczenie jednakowych monet w pewnej liczbie rzędów w taki sposób, że w każdym rzędzie monety tworzą jeden spójny blok, a każda moneta w każdym rzędzie oprócz najniższego dotyka dokładnie dwóch monet w rzędzie bezpośrednio poniżej, na przykład Niech $a_n$ ozbnacza liczbę pagórków, w którym najniższy rząd zawiera dokładnie $n$ monet. Znajdź funkcję tworzącą i zwarty wzór na $a_n$. WSKAZÓWKA: Nietrudno zgadnąć wynik po obliczeniu kilku pierwszych wyrazów ciągu z równania rekurencyjnego.

Zadanie 3

Znajdź Niech $G=(V,E)$ będzie grafem takim, że $E=E_1 \cup E_2$, gdzie graf $G_1=(V, E_1)$ jest planarny, zaś graf $G_2=(V, E_2)$ jest lasem. Udowodnij, że $\chi(G) < 9$.

Rozwiązanie

Wskazówka:

Narysuj 5 grafów $K_4$. Nazywij je $A, B, C, D, K$. Ich wierzchołki ponumeruj i nazwij według następującego schematu: graf $A$ posiada wierzchołki $a_1, a_2, a_3, a_4$.

Stwórz drzewa z korzeniami w wierzchołkach $K$. Niech $k_1$ będzie połączone z wierzchołkbmi $b_1, b_2, b_3, b_4$, $k_2$ z $b_1, b_2, b_3, b_4$, itd.

Zadanie 4

Oblicz $(1\cdot 3\cdot 5\dots 97)^2 \mod{101}$.

Rozwiązanie

Zauważmy, że $$ \begin{align*} 1 &\equiv -100 &&\pmod {101} \\ 3 &\equiv -98 &&\pmod {101} \\ 5 &\equiv -96 &&\pmod {101} \end{align*} $$ Stąd $$ x \equiv (1 \cdot 3 \cdot 5 \dots 97)((-100)\cdot(-98)\dots(-4)) \pmod{101} $$

Z twierdzenia Wilsona wiemy, że $100! \equiv -1 \pmod{101}$. Zatem $$ \begin{align*} &4x \equiv 2 \cdot 2\ (1 \cdot 3 \cdot 5 \dots 97)((-100)\cdot(-98)\dots(-4)) \pmod{101} \\ &4x \equiv 2 \cdot (-99)\ (1 \cdot 3 \cdot 5 \dots 97)((-100)\cdot(-98)\dots(-4)) \pmod{101} \\ &\begin{cases} 4x &\equiv 100! &&\pmod{101} \\ 100! &\equiv -1 &&\pmod{101} \end{cases} \\ &4x \equiv -1 \pmod{101} \\ \end{align*} $$ Stąd $x = 25$.

Wynik można sprawdzić poniższymi metodami:

Mathematica:


          Mod[Power[Product[i, {i, 3, 97, 2}], 2], 101]

WolframAlpha:


          (product 2*n+1, 1 to 48)^2 mod 101

Do badania kongruencji w Matematice przydaje się Reduce:


      Reduce[4x == -99*2*100!, Modulus -> 101]