Zadanie 1
Wierzchołki grafu permutacji $G_n$ są etykietowane permutacjami zbioru $n$-elementowego. Dwa wierzchołki w tym grafie są połączone krawędzią, jeśli odpowiadające im permutacje różnią się transpozycją sąsiednich elementów. Dla jakich $n$ graf $G_n$ jest planarny?
Zadanie 2
Pokaż nieplanarność grafu Petersena
(a) z tw. Kuratowskiego (zawiera podgraf homeomorf. z K3,3 lub K5);
(b) wyprowadzając ograniczenie górne na liczbę krawędzi dla grafów planarnych o obwodzie r.
Zadanie 3
Dla jakich k hiperkostka Qk jest planarna? Dla jakich r,s,t pełny graf trojdzielny Kr,s,t jest planarny?
Zadanie 4
Pokaż, że jeśli G ma co najmniej 11 wierzchołków, to G i dopełnienie G nie mogą być jednocześnie planarne. Podaj przykład 8-wierzchołkowego G takiego, że G i dopełnienie G są planarne.
Zadanie 5
Ile co najwyżej krawędzi może mieć n-wierzchołkowy graf zewnętrznie planarny? Pokaż, że każdy graf zewnętrznie planarny można pokolorować 3 kolorami.
Zadanie 6
Udowodnij "twierdzenie o 7 barwach" dla torusa:
a) K7 można narysować na torusie => czasem trzeba użyć 7 kolorów.
b) odpowiednik wzoru Eulera: n-m+f=0
c) odpowiednik m<=3n-6: m<=3n
d) odpowiednik faktu o istnieniu wierzchołka stopnia <=5: istnieje wierzchołek stopnia <=6
e) 7 kolorow zawsze wystarczy.
Zadanie 7
Graf Knesera K(r,n): V = {r-podzbiory {1..n}}
{A,B} jest krawędzia <=> część wspólna A i B jest pusta (Np. K(2,5) -
graf Petersena). Pokaż, ze χ(K(2,5))=3, χ(K(2,6))=4, ogólnie
χ(K(r,n))<=n-2r+2.
Zadanie 8
Graf Mycielskiego Mn: M2 = krawędź, Mk+1: do Mk dokładamy kopię M' samych wierzchołków z Mk. Każdy wierzchołek-kopia w M' jest połączony z sąsiadami swojego oryginału w Mk. Dokładamy jeszcze nowy wierzchołek połączony ze wszystkimi w M'. Pokaż, że
a) w Mk nie ma trójkątów
b) χ(M_k)=k.
Zadanie 9
Udowodnij tw. Koniga: kolorowanie krawędziowe grafu dwudzielnego o maksymalnym stopniu D wymaga tylko D kolorow.
Zadanie 10
Znajdź wielomian chromatyczny cyklu Cn, "koła o n szprychach", grafu K3,3.
Udowodnij, że każdy prostokąt łaciński można rozszerzyć do kwadratu.
Do kwadratu n x n wpisano po n liczb 1, 2,..., k (łącznie kn liczb) w taki sposób, że w żadnym wierszu ani kolumnie nie ma dwóch takich samych liczb. Udowodnij, że można uzupełnić ten kwadrat do kwadratu łacińskiego (tzn. w każdym wierszu i w każdej kolumnie zawierającego permutację liczb 1,...,n).
Pokaż, że jeśli w grafie dwudzielnym (V1, V2) stopnie wierzchołków w V1 są ≥ niż stopnie wierzchołków w V2, to istnieje pełne skojarzenie z V1 do V2.
Udowodnij, że jeśli w grafie dwudzielnym (V1, V2) jest spełniony warunek Halla i stopień każdego wierzchołka w V1 jest ≥ t, to pełne skojarzenie z V1 do V2 można wybrać na co najmniej t! sposobów, jeśli t≤|V1| i na co najmniej t!/(t-|V1|)! sposobów jeśli t>|V1|.
Problem haremu: jak wygląda warunek Halla w przypadku, kiedy i-ty chłopiec chce poślubić di dziewcząt?
Udowodnij, że przeliczalna rodzina zbiorów skończonych ma System Różnych Reprezentantów wtedy i tylko wtedy, gdy dla każdego naturalnego k dowolnych k zbiorów z tej rodziny zawiera w sumie co najmniej k elementów. Pokaż, że założenie o skończoności zbiorów jest istotne.
Pokaż, że jeśli n>2, to w sieci komutacyjnej Closa każdą permutację można zrealizować na przynajmniej dwa sposoby. Zaoprojektuj optymalny algorytm ustawiania przełączników.
Udowodnij, że iloczyn k kolejnych liczb całkowitych jest podzielny przez k!.
Udowodnij, że jeśli liczba 2n-1 jest pierwsza, to liczba n jest pierwsza.
Udowodnij, że jeśli liczba 2n+1 jest pierwsza, to n jest potęgą 2. Niech fn = 22n+1 oznacza n-tą liczbę Fermata. Uprość iloczyn f0...fn i udowodnij, że każde dwie różne liczby Fermata są względnie pierwsze.
Udowodnij, że
(a) NWD(na-1, nb-1) = nNWD(a,b)-1;
(b) NWD(Fa, Fb) = FNWD(a,b), gdzie Fn to n-ta liczba Fibonacciego.
Ile rozwiązań ma kongruencja ax ≡ b (mod n) w zbiorze {0,...,n-1}. Jak je efektywnie znajdować?
Udowodnij twierdzenie Wilsona: liczba n jest pierwsza <=> (n-1)! ≡ -1 (mod n).
Oto konstrukcja drzewa Sterna-Brocota:
zaczynamy od dwóch ułamków: 0⁄1 i 1⁄0 (ten drugi reprezentuje +∞)
między każde dwa kolejne elementy m⁄n i m'⁄n' wstawiamy ułamek (m+m')/(n+n').
Udowodnij, że w ten sposób uzyskamy wszystkie dodatnie ułamki nieskracalne, każdy dokładnie raz.
Udowodnij, że iloczyn trzech kolejnych liczb naturalnych, z których środkowa jest sześcianem, dzieli się przez 504.
Niech n = 100. Czy φ(n) to najmniejsza liczba λ o tej własności, że jeśli a⊥n, to aλ≡1(mod n)? Uogólnij tę obserwację.
Udowodnij, że istnieje 2011 kolejnych liczb naturalnych, z których każda jest podzielna przez sześcian liczby naturalnej >1.
Niech F(1) = 2, F(k+1) = 2F(k). Oblicz F(5) mod 2009.
Znajdź najmniejszą liczbę o sumie cyfr 204 podzielną przez 204.
Znajdź konstruktywny dowód chińskiego twierdzenia o resztach (czyli podaj efektywny algorytm znajdowania elementu spełniającego stosowny układ kongruencji).
W kryptosystemie RSA: niech p = 11, q = 29, klucz jawny e = 3. Znajdź klucz tajny d, zaszyfruj komunikat M = 100, a następnie zdeszyfruj go z powrotem.
Znajdź wszystkie rozwiązania kongruencji
x2≡1 (mod 784)
x2≡-1 (mod 4225)
10x≡8 (mod 17)
Wiedząc, że n = 3598057 jest iloczynem dwóch różnych liczb pierwszych oraz że 20779 jest pierwiastkiem z 1 modulo n, znajdź rozkład n na czynniki pierwsze.
Uogólnij chińskie twierdzenie o resztach na przypadek, kiedy moduły niekoniecznie są względnie pierwsze.
Rozważmy system kryptograficzny RSA z modułem n = 71⋅103 i wykładnikiem publicznym e=19. Oblicz, ile komunikatów M∈{0,...,n-1} jest punktami stałymi szyfrowania, tzn. spełnia warunek S(M) = M.
Iloczynem kartezjańskim grafów \(G_1 = \langle V_1, E_1\rangle\) i \(G_2 = \langle V_2, E_2\rangle\) nazywamy graf \(G_1\otimes G_2 = \langle V_1\times V_2, E\rangle\), gdzie
\[\{\langle v_1,v_2\rangle,\langle w_1,w_2\rangle\} \in E \Leftrightarrow (\{v_1,w_1\} \in E_1 \wedge \{v_2,w_2\} \in E_2)\ .\]
Udowodnij, że graf \(G_1\otimes G_2\) jest spójny wtedy i tylko wtedy, gdy obydwa grafy \(G_1\) i \(G_2\) są spójne i przynajmniej jeden z nich zawiera cykl nieparzystej długości.
Oblicz \(7^{8^9} \bmod 100\).
Udowodnij uogólnione Chińskie Twierdzenie o Resztach: Niech \(m_1,m_2>0\) niekoniecznie względnie pierwsze, \(m = \mbox{NWW}(m_1,m_2)\). Wtedy dla dowolnych \(u_1,u_2\geq 0\) istnieje dokładnie jedno u takie, że \( 0\leq u < m\) oraz \(u \equiv u_i (\mbox{mod } m_i)\) dla i=1,2, o ile \(u_1\equiv u_2 (\mbox{mod NWD}(m_1, m_2))\), a jeśli ten ostatni warunek nie jest spełniony, to takie u nie istnieje.
Znajdź minimalny zbiór generatorów grupy Sn.
Opisz wszystkie grupy rzędów 1,...,7.
Udowodnij, że grupa A4 nie zawiera podgrupy rzędu 6.
Rozstrzygnij, czy grupa S4 zawiera podgrupę
(a) Z2⊕Z3
(b) Z2⊕Z4
Podaj liczbę elementów każdego rzędu w grupie Z4⊕Z10.
Znajdź rząd podgrupy Sn generowanej przez n-cykle.
Rozstrzygnij, czy
(a) grupa obrotów sześcianu jest izomorficzna z S4 (grupą wszystkich permutacji zbioru 4-elementowego);
(b) grupa izometrii sześcianu jest izomorficzna z grupą automorfizmów grafu złożonego z 4 trójkątów A, B, C, D takich, że B, C, D sa rozłączne, zaś A ma dokładnie jeden wierzchołek wspólny z każdym z nich.
Niech P(G,k,j) oznacza liczbę istotnie różnych kolorowań grafu $G$, w których dokładnie $k$ wierzchołków jest białych, a $j = |V|-k$ wierzchołków jest czarnych. Dla grafu G niech S(G) oznacza stożek nad G, czyli graf powstający z G przez dodanie nowego wierzchołka połączonego ze wszystkimi w G.
Pokaż, że jeśli
(*) G nie ma wierzchołka stopnia |V(G)|-1,
to P(S(G),k,j) = P(G,k-1,j)+P(G,k,j-1), i podaj przykład pokazujacy, że założenie (*) jest istotne.
Podaj przykład grafu, którego grupą automorfizmów jest
(a) Z2 + Z2 (grupa czwórkowa Kleina); (b) Z3.
Podaj przykład grafu G o nietrywialnej grupie automorfizmów i takiego, że po usunięciu z G dowolnej krawędzi otrzymujemy graf o trywialnej grupie automorfizmów.
Wariant uproszczony:
słowo dowolnej zastąp przez pewnej.
Oblicz, ile jest nieizomorficznych turniejów o 5 wierzchołkach.
Kolorujemy wierzchołki czworościanu foremnego z użyciem 3 kolorów, a krawędzie z użyciem 2 kolorów. Oblicz, na ile istotnie różnych sposobów można to zrobić, jeśli utożsamiamy takie kolorowania, że jedno przechodzi na drugie przy pewnym obrocie czworościanu w R3.
Podaj przykład funkcji f takiej, że f(n) = ω((log n)a) oraz f(n) = o(nb) dla dowolnych a,b>0.
Pokaż, że jeśli b>1, T,S - niemalejące, T(bk) = Θ(S(bk)) i dodatkowo S spełnia warunek
S(bn) = Θ(S(n))
to T(n) = Θ(S(n)).
Sprawdź, czy ten warunek jest spełniony dla (a) S(n) = na; (b) S(n) = an.
Niech n oznacza łączną liczbę włosów na głowach wszystkich ludzi żyjących obecnie na Ziemi. Rozstrzygnij, co jest większe: długość zapisu dziesiętnego liczby 2n czy liczba końcowych zer w zapisie dziesiętnym liczby n!.
Niech f(n) będzie rozwiązaniem równania funkcyjnego x log1001x = n. Znajdź rząd wielkości funkcji f.
Znajdź rząd wielkości funkcji f(n) określonej zależnością \(f(n)^{f(n)^{f(n)}} = n\) dla \(n>0\).
Oszacuj sumę \(\sum_{n\geq 1} 1/n^3\) z błędem bezwzględnym 1/12.
Oszacuj sumę \(\frac{1}{n^2+1}+\frac{2}{n^2+2}+\cdots+\frac{n}{n^2+n}\) z błędem bezwzględnym \(O(1/n^2)\).
Oszacuj sumę \[\sum_{i=1}^n \frac{\mbox{lg }i}{\sqrt{i}}\] z błędem bezwzględnym \(O(1)\).
(a) Udowodnij, że \(|\{\langle a,b \rangle \in \mathbb{N}\times\mathbb{N}: a^2+b^2\le n\}| = \frac{\pi}{4}n +O(\sqrt{n})\).
(b) Oszacuj \(|\{\langle a,b,c \rangle \in \mathbb{N}^3: a^2+b^2+c^3\le n\}|\) z błędem bezwzględnym \(O(n)\).
Oblicz sumę \(\displaystyle\sum_k {{n}\choose{2k}} 2^{n-2k}\).
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\}\).
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.
Znajdź najmniejszą wielokrotność liczby 130013, której zapis w systemie dziesiątkowym składa się z samych dziewiątek.
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).