Ćwiczenia 11: powtórka przed egzaminem

Zadanie 1

Oblicz sumę \(\displaystyle\sum_k {{n}\choose{2k}} 2^{n-2k}\).

Zadanie 2

Oblicz, na ile sposobów można rozstawić n nieatakujących się wież na planszy
(a) \(\{(i,j): 1\leq i,j\leq n\mbox{ oraz }j\geq i-1\}\);
(b) \(\{(i,j): 1\leq i,j\leq n\mbox{ oraz }|i-j|\leq 1\}\).

Zadanie 3

Udowodnij, że każdy spójny, regularny graf dwudzielny jest dwuspójny. Podaj przykład pokazujący, że założenie o dwudzielności jest istotne.

Zadanie 4

Znajdź najmniejszą wielokrotność liczby 130013, której zapis w systemie dziesiątkowym składa się z samych dziewiątek.

Zadanie 5

Z ośmiu sześcianów o krawędzi 1, z których trzy mają po jednej ścianie czarnej i po pięć białych, a pozostałe mają wszystkie ściany białe, sklejamy sześcian o boku 2. Oblicz, na ile sposobów można to zrobić, jeśli dwa sposoby sklejenia utożsamiamy, gdy jeden z uzyskanych sześcianów o boku 2 przechodzi na drugi przy pewnym obrocie sześcianu w \(\mathbb{R}^3\) (zakładamy, że ścianki są nieprzezroczyste, więc wnętrze sześcianu jest niewidoczne).