UW/Matematyka dyskretna (mat)
Archive
Spis treści |
[edytuj] Egzaminy z poprzednich lat
[edytuj] 2006
[edytuj] zad 1
udowodnij, że dla dowolnych liczb naturalnych n, m k takich, że n > 0, k <=m oraz m+k <= n zachodzi tożsamość:
(n po k)(n po m)=suma od i=0 do k (n po m+i)(m+i po k)(k po i).
lewa strona: wybieramy zbiór k-elementowy M, a następnie m-elementowy K z [n]
prawa strona: najpierw wybieramy z [n] podzbiór (m+i)-elementowy A, nastepnie z niego wyodrębniamy podzbiór k-elementowy B, a następnie z B wybieramy zbiór i-elementowy C. B\C wyznacza część wspólną zbiorów A\C i B. Zbiór A\C odpowiada K, a zbiór B odpowiada M.
[edytuj] zad 2
Korzystając z zasady wł-wył udowodnij, że jeśli n>=3, to zbiór wszystkich liczb n-cyfrowych zapisanych za pomocą cyfr 1,2 i 3 oraz spełniających (jednocześnie) dwa warunki:
- każda z cyfr 1, 2, 3 występuje co najmniej raz,
- jedynka nie występuje na pierwszym m-cu, 2 na drugim i 3 na 3-cim,
ma 8*3^(n-3)-3*2^(n-2) elementów.
Mamy 8 sposobów zapełnienia 3 pierwszych miejsc. Pozostałe zapełniamy na 3^(n-3) sposobów. Zatem jest 8*3^(n-3) ciągów spełniających (ii) Teraz odejmujemy te, które nie spełniają (i). Definiuję A(k)-zbiór ciągów spełniających (ii) dł. n takich, że nie występuje w nich k. Potem liczę ze wzoru.
[edytuj] zad 3
Ile jest słów dł. n>=1 nad alfabetem {a, b, c, d, e, f, g, h, i, j, k, l, m} zbudowanych za pomocą liter a, b, c, d, e, f oraz "zbitek" gg, hh, ii, jj, kk, ll, mm?
Równanie to a(n)=7a(n-2)+6a(n-1)
[edytuj] zad 4
Kolorujemy wierzchołki 12kąta 3 kolorami.
[edytuj] zad 5
Dany jest siedmiokąt wypukły o następującej własności: istnieją sokładnie dwa punkty w których przecinają się po trzy jego przekątne, natomiast w kazdym innym punkcie, będącym punktem przecięcia przekątnych, przecinają się dwie przekątne (oczywiście mówimy wyłącznie o punktach znajdujących się wewnatrz 7kąta). rozważmy graf płaski G, którego wierzchołkami są wierzchołki danego 7kąta oraz punkty przecięcia jego przektnych, zaś krawędziami są boki 7kąta i odcinki jego przekątnych, łączące wierzchołki grafu.
Znajdź liczbę wierzchołków, krawędzi oraz ścian ograniczonych (czyli obszarów, na które krawędzie grafu dzielą wnętrze 7kąta) grafu G.
Najlepiej na początku policzyć wierzchołki G, gdyby nie było punktów, w których przecinają się 3 przekątne, a następnie od tej liczby odjąć 4 - bo zamiast 6 punktów przecięć mamy 2. Reszta wychodzi ze wzorów.
