Matematyka dyskretna
Dr Marek Zakrzewski
Wykład 05
Wzór włączeń i wyłączeń
#"A*"B#"=#"A#"�ą#"B#"-#"A)"B#"
#"A*"B*"C#"=#"A#"�ą#"B#"�ą#"C#"-#"A)"B#"-#"A)"C#"-#"B)"C#"�ą#"A)"B)"C#"
Wzór włączeń i wyłączeń:
A1*" A2*"...*" An należy dodać liczebności #"Ai#"
Aby obliczyć liczebność zbioru , odjąć
#"Ai)"A #" #"Ai)"A )"Ak#"
liczebność , dodać itd.
j j
n
#"A1*"...*"An#"= #"Ai#"- #"Ai)" A #"�ą...�ąśą-1źąk�ą1 #"Ai )"Ai )"...)"Ai #"�ą...
" " "
j
1 2 n
i=1 1d"i"ą jd"n 1d"i1"ą..."ąi d"n
j
Dowód:
x "A1*" A2*"...*" An. Ai
Rozważmy ustalony element . Niech m będzie liczba zbiorów
x x
do których należy. Pokażemy, że przy sumowaniu po prawej stronie wzoru liczone
jest dokładnie raz.
m
m=
#"Ai#"
Przy składnikach postaci x jest liczone razy.
śą źą
1
m
#"Ai)"A #"
Przy składnikach postaci x jest liczone razy.
j
śą źą
2
m
#"Ai)"A )"Ak#"
Przy składnikach postaci x jest liczone razy.
j
śą źą
3
x
A
ącznie uwzględniając znaki jest brane:
m m m m
- �ą - �ą...=1
śą źą śą źą śą źą śą źą
1 2 3 4
Innymi słowy mamy pokazać, że:
m m m m
- �ą - �ą...=0
śą źą śą źą śą źą śą źą
0 1 2 3
m m m m
0=śą1-1źąm= - �ą - �ą...
tzn. co ze wzoru Newtona jest prawdą.
śą źą śą źą śą źą śą źą
0 1 2 3
Zadanie:
Na ile sposobów można pokolorować sześcian za pomocą 3 kolorów tak, aby każdy kolor był
wykorzystany?
Rozwiązanie:
Ai
Niech - pokolorowanie nie wykorzystujące i-tego koloru.
A1*" A2*" A3 - pokolorowanie nie wykorzystujące któregoś koloru.
Zatem
#"A1*" A2*" A3#"= #"Ai#"- #"Ai)" A #"�ą #"Ai)" A )" Ak#"=3"26-3"16�ą06
" " "
j j
Wszystkich pokolorowań jest , a więc takich, które wykorzystują wszystkie 3 kolory jest
36
36-3"26�ą3"16=729-192�ą3=540 albo inaczej:
3 3 3
36- 26�ą 16- 06=540
śą źą śą źą śą źą
1 2 3
k n
Dla kolorów i ścian:
k
k k k
kn- śą k -1źąn�ą śą k -2źąn�ą...= śą k -iźąnśą-1źąi
"
śą źą śą źą śą źą
1 2 i
i =0
Zadanie o roztargnionej sekretarce:
n n
Załóżmy, że sekretarka ma różnych listów i zaadresowanych kopert. Jakie jest
prawdopodobieństwo, że wszystkie włoży z
le?
Rozwiązanie:
Ai
Niech - liczba włożeń, przy których i-ty trafia to i-tej koprty.
#"Ai#"=śąn-1źą !
#"Ai)"A #"=śąn-2źą!
j
#"Ai)"A )"Ak#"=śąn-3źą!
j
n n
#"Aż A2*"...*"An#"=n śąn-1źą !- śąn-2źą !�ą śąn-3źą!-...=
śą źą śą źą
2 3
n śąn-1źą nśą n-1źąśąn-2źą
n ! n ! n !
=n !- śąn-2źą!�ą śąn-3źą!-...=n !- �ą - �ą...=
2 ! 3 ! 2 ! 3 ! 4 !
1 1 1 1
=n ! 1- �ą - �ą -...
śą źą
2! 3! 4! 5!
Zatem prawdopodobieństwo, że któraś trafi na właściwe miejsce wynosi:
śą źą 1 1 1 1
Pn= =1- �ą - �ą -...=1 H"0,37
n ! 2! 3 ! 4 ! 5 ! e
Czy prawdopodobieństwo, że żadna nie trafi wynosi około 0,63.
Funkcja Eulera
�ąśą nźą - ilość liczb względnie pierwszych z przedziału
[1,n]
�ąśą pźą= p-1 dla liczb pierwszych.
�ąśą1źą=1 1
pk 1
�ąśą 2źą=1 1 dla potęg liczb pierwszych.
�ąśą pkźą= pk- = pk 1-
śą źą
p p
�ąśą3źą=2 1,2
�ąśą 4źą=2 1,3
�ąśą5źą=4 1,2,3 ,4
�ąśą6źą=2 1,5
�ąśą 7źą=6 1,2,3 ,4 ,5,6
�ąśą8źą=4 1,3,5 ,7
�ąśą9źą=6 1,2,4 ,5 ,7,8
�ąśą10źą=4 1,3 ,7,9
Twierdzenie:
1 1 1
1 2 n
�ąśą nźą=n 1- 1- ... 1-
Jeżeli n= p�ą p�ą ... p�ą ,to
1 2 n
śą źąśą źą śą źą
p1 p2 pn
Dowód: (dla k=3 )
Ai pi
[1, n]
Niech oznacza zbiór takich liczb z , które dzielą się przez .
Zatem
#"A1*" A2*" A3#"= #"Ai#"- #"Ai)" A #"�ą #"Ai)" A )" Ak#"=
" " "
j j
n n n n n n n
= �ą �ą - �ą �ą �ą
śą źą śą źą
p1 p2 p3 p1 p2 p1 p3 p2 p3 p1 p2 p3
Zatem
n n n n n n n
�ąśą nźą=n- �ą �ą - �ą �ą �ą =
śą źą śą źą
[ p1 p2 p3 p1 p2 p1 p3 p2 p3 p1 p2 p3]
n n n n n n n n n
=n 1- �ą �ą �ą �ą �ą - �ą �ą =
śą źą śą źą śą źą
[ p1 p2 p3 p1 p2 p1 p3 p2 p3 ] p1 p2 p1 p3 p2 p3
1 1 1
=n 1- 1- 1-
śą źąśą źąśą źą
[ p1 p2 p3 ]
1
�ąśą1000 000źą=�ąśą106źą=�ąśą26"56źą=1000 000 1- 1-1 =1000 000"1"4 =400 000
śą źąśą źą
2 5 2 5
Zasady szufladkowe:
1. Uzasadnij, że pośród 11 liczb są co najmniej dwie mające tę samą końcową cyfrę.
Oznaczamy szufladki numerami 0,1 ,2 , ...,9 . Liczbę wkładamy do i-tej szufladki,
i
jeśli jej ostatnią cyfrą jest . Ponieważ jest 10 szufladek, 11 liczb to dwie muszą
trafić do jednej szufladki, tzn. kończą się tą samą cyfrą.
2. W każdym wielościanie są przynajmniej dwie ściany o tej samej liczbie krawędzi.
k N
Dowód: Ściany o krawędziach wkładamy do k-tej szufladki. Niech -
maksymalna liczba krawędzi. Zatem numery szufladek to 3,4 ,... , N . Skoro istnieje
N
ściana o krawędziach, to jest przynajmniej N �ą1 ścian. Zatem mamy N �ą1
N
(lub więcej ścian), -2 szufladek, tzn. w którejś szufladce są dwie lub więcej
ścian, czyli w każdym wielościanie są przynajmniej dwie ściany o tej samej liczbie
krawędzi.
3. Czy spośród 10 monet (w tym jedna lżejsza) można wykryć tę lżejszą za pomocą 2
ważeń na wadze szalkowej?
NIE
Każdej monecie przyporządkowujemy kod typu LO  w I ważeniu na lewej szalce, w
II poza szalkami.
Takich kodów (L,R,O) jest 3"3=9 , a więc dwie monety mają ten sam kod, a
wówczas nie dają się odróżnić.
Frank Ramsey
Dwie osoby rysują na zmianę kolejno linie swojego koloru tak aby utworzyć
jednolity trójkąt.
Dla 6 punktów i 2 graczy gra jest zawsze rozstrzygnięta.
Załóżmy, że wszystkie linie są już narysowane. Rozważmy 5 linii z ustalonego
punktu. Są przynajmniej 3 jednego koloru, a to oznacza, że niezależnie od
ruchu przeciwnika da się zamknąć trójkąt.
Zależność między liczbą graczy a ilością potrzebnych punktów, aby gra była zawsze
[n !e ]�ą1
rozstrzygnięta wyraża się wzorem:
2 osoby  6 punktów
3 osoby  17 punktów
W przypadku czworokąta zupełnego tzn. ze wszystkimi przekątnymi gra jest rozstrzygnięta
dla 2 osób przy 18 punktach.
W przypadku pięciokąta zupełnego nie da się tego obliczyć. Ale jest to liczba z przedziału
[42,55]