Matematyka dyskretna, studia zaoczne- semestr 2,
zestaw 4
Zasada szufladkowa Dirichleta
Mamy k szuflad i n kul, gdzie n>k. Jeśli powkładamy kule do szuflad to w przynajmniej jednej
szufladzie znajdÄ… siÄ™ przynajmniej dwie kule.
Uogólniona wersja zasady szufladkowej Dirichleta
Jeśli mamy k szuflad i n> mk kul, to jeśli powkładamy kule w szufladach, to w przynajmniej
jednej będzie przynajmniej m+1 kul
Zasada włączania i wyłączania (suma zbiorów nierozłącznych)
n
n-1
#"X *" X *"... X #"= #"- #"X )"X #"ƒÄ… #"X )" X )"X #"-...ƒÄ…śą-1źą Å" )"X )"...)"X #"
#"X
1 2 n "#"X i " i j " i j k 1 2 n
i=1 1Ä…Ä…i"Ä…jÄ…Ä…n 1Ä…Ä…i"Ä… j"Ä…kÄ…Ä… n
Zad 1
W sali znajduje się n osób (ne"2). Udowodnić za pomocą zasady szufladkowej Dirichleta, że co
najmniej dwie z tych osób mają taką samą liczbę znajomych. Zakładamy, że relacja znajomości jest
zwrotna, symetryczna, przechodnia.
Zad 2
Spośród liczb 1,...,9 wybrano sześć. Udowodnić, że spośród wybranych liczb można wybrać dwie,
które sumują się do 10.
Zad 3
Udowodnić, że jeśli w trójkącie równobocznym o boku długości 4 jednostki umieścimy 17 punktów,
to odległość dwóch spośród nich nie przekracza 1 jednostki.
Zad 4
Udowodnić, że dla dowolnych trzech liczb całkowitych można wybrać dwie, że ich suma dzieli się
przez 2.
Zad 5
Na sali znajduje się 47 osób. Udowodnić, (na podstawie uogólnionej zasady Dirichleta) że na sali
znajduje się 7 osób urodzonych tego samego dnia tygodnia.
Zad 6
Wśród 200 osób 150 uprawia pływanie lub jogging lub jedno i drugie. Jeśli 85 osób uprawia
pływanie, a 60 osób pływanie i jogging to ile osób uprawia jogging?
Zad 7
Ile jest sposobów rozmieszczenia n rozróżnialnych (ponumerowanych) kul w k rozróżnialnych
(ponumerowanych) komórkach, przy czym:
a) Rozmieszczenia sÄ… dowolne.
b) Rozmieszczenia są takie, że w każdej komórce jest co najwyżej jedna kula.
c) Rozmieszczenia są takie, że w każdej komórce jest co najmniej jedna kula.
Zad 8
Ile jest sposobów rozmieszczenia n nierozróżnialnych kul w k rozróżnialnych komórkach, przy
czym:
a) Rozmieszczenia sÄ… dowolne.
b) Rozmieszczenia są takie, że w każdej komórce jest co najwyżej jedna kula.
c) Rozmieszczenia są takie, że w każdej komórce jest co najmniej jedna kula.