Treści zadań mogą być trochę niezrozumiałe, ponieważ przepisywałem je z pamięci po egzaminie
Nie chciałem robić 10 oddzielnych postów ponieważ chodzi mi tylko o sprawdzenie rozwiązań (mam nadzieję że rozumiecie)
1. Ułóż wzór rekurencyjny na liczbę ciagów, a następnie rozwiąż otrzymane równanie rekruencyjne. Dany jest ciąg, w którym na każdej pozycji może znajdować 0, 1 lub 2, ale ułożenia '00' lub '01' nie mogą się w nim znaleźć.
\(\displaystyle{ a_1= 3 \Rightarrow {0,1,2}}\)
\(\displaystyle{ a_2= 7 \Rightarrow {10, 11, 12, 20, 21, 22, 02}}\)
Następnie opracowałem algorytm na tworzenie kolejnych wyrazów (dla \(\displaystyle{ n>2}\)):
\(\displaystyle{ a_n = 2 \cdot a_{n-1} + a_{n-2}}\)
Ponieważ do każdego kolejnego wyrazu możemy dodać z jego LEWEJ strony '1' '2' (zatem \(\displaystyle{ 2 \cdot a_{n-1}}\)),
dodatkowo 0 możemy dodać tylko wtedy gdy po jego prawej stronie jest 2( a takich liczb jest \(\displaystyle{ a_{n-2}}\))
i tutaj pojawia się problem... ponieważ wydaje mi się, że nie da się tego równania rozwiązać :c
ponieważ otrzymujemy:
\(\displaystyle{ x^2-2x-1=0}\)
\(\displaystyle{ \Delta = 8}\)
\(\displaystyle{ x_1= 1 - \sqrt{2}}\)
\(\displaystyle{ x_2= 1 + \sqrt{2}}\)
zatem
\(\displaystyle{ a_n= C_1(1 - \sqrt{2})^n + C_2(1 + \sqrt{2})^n}\)
dostajemy więc układ równań:
\(\displaystyle{ 3=C_1(1 - \sqrt{2}) + C_2(1 + \sqrt{2})}\)
\(\displaystyle{ 7=C_1(1 - \sqrt{2})^2 + C_2(1 + \sqrt{2})^2}\)
którego za żadne skarby nie daje rady rozwiązać
Natomiast sama rekurencja jest przecież dobra, przetestowałem ją w komputerze i wszystkie wyniki się zgadzają
2. W koszyku znajduje się \(\displaystyle{ 10}\) bananów, \(\displaystyle{ 8}\) jabłek, \(\displaystyle{ 6}\) pomarańczy oraz \(\displaystyle{ 4}\) gruszki. Ile różnych zestawów, każdy składający się z \(\displaystyle{ 8}\) owoców, można utworzyć przy założeniu, że każdy taki zestaw zawiera co najmniej jednego banana, co najmniej \(\displaystyle{ 2}\) jabłka, liczba pomarańczy jest parzysta a gruszek nieparzysta? Zadanie należy rozwiązać z wykorzystaniem funkcji tworzącej.
ułożyłem funkcje tworzącą:
\(\displaystyle{ A(x)=(x^1 + x^2 + x^3 + ... + x^{10})( x^2 + x^3 + ... + x^8)(1+x^2 + x^4 + x^6)(x+x^3)}\)
następnie wymnożyłem i sprawdzając wartość \(\displaystyle{ a_8}\) dostałem wynik 13
3. Dany jest Graf \(\displaystyle{ K_{n,n+1}}\).
a) ile najmniej należy dołożyć krawędzi do grafu by stał się eulerowski,
b) ile najmniej krawędzi należy odjąć od grafy by ten stał się eulerowski
Graf posiada cykl eulera jeżeli wszystkie stopnie jego wierzchołków są parzyste i graf jest spójny.
Ad a) Graf będzie posiadał cykl eulera jeżeli dodamy:
jeśli n parzyste: \(\displaystyle{ \frac{n}{2} }\) krawędzi aby wyeliminować wierzchołki stopnia nieparzystego, dokładając odpowiednio krawędzie "po stronie n"
jeśli n nieparzyste:\(\displaystyle{ \frac{n+1}{2}}\) -||-, dokładając odpowiednio krawędzie "po stronie n+1"
Ad b) Graf bedzie posiadał cykl eulera jeżeli usuniemy: (dla \(\displaystyle{ n \leq 3}\))
jeśli n parzyste: \(\displaystyle{ n }\) krawędzi aby wyeliminować wierzchołki stopnia nieparzystego,
jeśli n nieparzyste: \(\displaystyle{ n+1}\).
4. Dany jest graf \(\displaystyle{ C_8}\), dołożono do niego 3 najdłuższe przekątne, wykaż na podstawie jakiejś definicji, że graf jest/nie jest planarny.
Graf nie jest planarny ponieważ zawiera podgraf będący rozdzieleniem grafu \(\displaystyle{ K_{3,3}}\)
5. Wykaż, że wśród dowolnych 5ciu punktów wybranych z kwadratu o boku 2 znajdują się 2 punkty, których odległość wzajemna wynosi co najwyżej 2. Uzasadnij, jak zmieni się ograniczenie na odległość, gdy zamiast 5ciu wybranych zostanie 10 punktów z tego kwadratu.
Dziele kwadrat na 4 mniejsze kwadraty o bokach 1x1 \(\displaystyle{ \Rightarrow}\) mam 4 szufladki, z ZSD wynika że conajmniej dwa punkty trafią do tego samego kwadratu.
W kwadracie najdalsza możliwa odległość to odległość dwóch najdalszych wierzchołków \(\displaystyle{ \Rightarrow}\) odległość wynosi conajwyżej \(\displaystyle{ \sqrt{2}}\)
Gdy wybierzemy 10 pkt, to potrzebujemy 9 szufladek \(\displaystyle{ \Rightarrow }\) dzielimy nasz kwadrat na 9 mniejszych kwadratów o bokach \(\displaystyle{ \frac{1}{3}}\) \(\displaystyle{ \Rightarrow }\) (na podstawie ZSD) istenija dwa punkty których maksymalna odległość między nimi wynosi \(\displaystyle{ \frac{1}{3} \cdot \sqrt{2}}\).
Dzieląc kwadrat na większe kawałki nie uzyskalibyśmy "minimalnego maksymalnego" ograniczenia na odległość dwóch punktów, natomiast dzieląc na drobniejsze kwadraciki, nie można by obliczyć tej odległości, ponieważ liczba "szufladek" była by większa niż liczba "kul".
6. Dla każdej takiej pary liczb naturalnych \(\displaystyle{ n}\) i \(\displaystyle{ k }\), że \(\displaystyle{ n \geq 3}\) oraz \(\displaystyle{ 0 \leq k \leq n-3}\), skonstruuj graf zawierający \(\displaystyle{ n}\) wierzchołków, \(\displaystyle{ n}\) krawędzi oraz \(\displaystyle{ k}\) wierzchołków stopnia \(\displaystyle{ 1}\). Narysuj wszystkie nieizomorficzne grafy dla \(\displaystyle{ n=6}\) i \(\displaystyle{ k=3}\).
Aby skonstruować taki graf należy np:
1. narysować cykl długości \(\displaystyle{ n-k}\),
2. Doczepić w dowolne miejsca \(\displaystyle{ k}\) "liści".
W ten sposób nasz graf zawiera \(\displaystyle{ n}\) krawędzi \(\displaystyle{ n}\) wierzchołków oraz \(\displaystyle{ k}\) wierzchołków 1 stopnia.
Grafy nieizomorficzne \(\displaystyle{ n=6 }\) \(\displaystyle{ k =3 }\): PATRZ KOMENTARZ
7. Określ liczbę tych permutacji \(\displaystyle{ f: A \rightarrow A }\) zbioru \(\displaystyle{ A= \{1,2,...,9\}}\), w których dla każdej liczby nieparzystej i zachodzi własność \(\displaystyle{ f(i)!=i}\), a dla każdej parzystej j zachodzi własność \(\displaystyle{ f(j)=10-j}\).
Parzyste mogą być tylko w jednym ułożeniu, aby spełniały warunki zadania. Do permutowania zostało tylko 5 liczb nieparzystych które nie mogą znajdować się na swoim miejscu \(\displaystyle{ \Rightarrow }\) trzeba je ułożyć w nieporządki \(\displaystyle{ D_5}\) tzn
\(\displaystyle{ 5! - {5 \choose 1} \cdot 4!+ {5 \choose 2} \cdot 3! - {5 \choose 3} \cdot 2! + {5 \choose 4} \cdot 1! - {5 \choose 5} \cdot 0! }\)
8. Dany jest graf, taki że zbiorem wierzchołków są wszystkie ciągi binarne długości 6. Dwa wierzchołki tworzą krawędź wtedy i tylko wtedy gdy różnią się nieparzystą liczbą bitów. Wyznacz stopień wierzchołków, liczbę chromatyczną oraz indeks chromatyczny.
liczba wierzchołków: \(\displaystyle{ 2^6}\)
stopień: \(\displaystyle{ {6 \choose 1} + {6 \choose 3} + {6 \choose 5}}\) (wybieramy nieparzyste pozycje)
liczba chromatyczna: graf jest dwudzielny (dwa zbiory wierzchołków w którym wierzchołki różnią się parzystą liczbę pozycji) zatem \(\displaystyle{ X=2}\)
indeks chromatyczny: to największy stopień grafu (ponieważ jest dwudzielny) tj \(\displaystyle{ X'= {6 \choose 1} + {6 \choose 3} + {6 \choose 5}}\)
9. Dane jest \(\displaystyle{ X=\{1,2,3\}}\) oraz \(\displaystyle{ Y=\{1,2,3,...,n\}}\).
a) ile jest funkcji \(\displaystyle{ X \to Y}\), ile jest funkcji różnowartościowych?
b) udowodnij indukcyjnie z podpunktu a) że liczba funkcji jest większa od liczby funkcji różnowartościowych.
Ad a) funkcji \(\displaystyle{ X \rightarrow Y}\) jest \(\displaystyle{ n^3}\), a funkcji różnowartościowych \(\displaystyle{ \frac{n!}{n-3!}}\)
Ad b)
1'
dla \(\displaystyle{ n_0=3 }\)
\(\displaystyle{ 3^3=27>\frac{3!}{0!}=6}\)
2'
Założenie: \(\displaystyle{ n^3 > \frac{n!}{(n-3)!}}\) dla \(\displaystyle{ n \geq 3}\)
Twierdzenie: \(\displaystyle{ (n+1)^3 > \frac{(n+1)!}{(n-2)!}}\)
Dowód:
\(\displaystyle{ n^3 + 3n^2 + 3n + 1 > \frac{n! \cdot (n+1)}{(n-3)! \cdot (n-2)}}\)
niestety nie wiem jak uzyskać prawidłowy wynik
10. Wypisz wszystkie permutacjie izometryczny grafu \(\displaystyle{ K_{2,3}}\).
Na podstawie twierdzenie Burnside'a oblicz liczbę kolorowań wierzchołków grafu 2'ma kolorami.
Graf wygląda tak: PATRZ KOMENTARZ
Izometrie:
\(\displaystyle{ G = \{ id,~~ob_{180},~~ s_{35},~~ s_{12} \}}\)
Permutacje:
\(\displaystyle{ id~~(1)(2)(3)(4)(5)~~ mon(id)=Z_1^6}\)
\(\displaystyle{ ob_{180} ~~(12)(35)(4) ~~mon(ob_{180})=Z_2^2 \cdot Z_1^1}\)
\(\displaystyle{ s_{35}~~ (3)(4)(5)(12) ~~mon(s_{35})=Z_1^3 \cdot Z_2^1}\)
\(\displaystyle{ s_{12} ~~(1)(2)(4)(35) ~~mon(s_{12})=Z_1^3 \cdot Z_2^1}\)
Kolorowanie:
\(\displaystyle{ N=\frac{1}{|G|} \cdot (2^6 + 2^2 \cdot 2 + 2^3 \cdot 2 +2^3 \cdot 2) = 26}\)
