[ Pobierz całość w formacie PDF ]
Matematyka dyskretna
dla informatyków
ZADANIA
Część I: Elementy kombinatoryki
Jerzy Jaworski
Zbigniew Palka
Jerzy Szymański
Uniwersytet im. Adama Mickiewicza
Poznań 2007
Spis treści
1 Metody dowodzenia twierdzeń
1
2 Podstawowe zasady i prawa przeliczania
5
3 Schematy wyboru i tożsamości kombinatoryczne
9
4 Zależności rekurencyjne
13
5 Aparat funkcji tworzących
17
6 Algebry Boole’a
21
Metodydowodzenia
1
twierdzeń
Zadanie 1.1. Udowodnić wprost, że jeżeli a i b są nieparzystymi liczbami
całkowitymi, to a + b jest parzystą liczbą całkowitą.
Zadanie 1.2. Udowodnić nie wprost, że dla dowolnej liczby naturalnej n,
jeżeli n
2
Zadanie 1.3. Niech n będzie taką liczbą naturalną, że n > 1 i n nie jest
liczbą pierwszą. Udowodnić przez sprowadzenie do sprzeczności, że n posiada
n.
Zadanie 1.4. Korzystając z zadania 1.3 udowodnić wprost, że liczba 101
jest pierwsza.
Zadanie 1.5. Udowodnić przez zaprzeczenie następujące stwierdzenie:
Niech m
1
, m
2
, . . . , m
n
będą dodatnimi liczbami całkowitymi. Je
żeli
m
1
+ m
2
+ . . . + m
n
−n + 1
kul włożymy do n szufladek, to pierwsza szufladka będzie zawie
rać co najmniej m
1
kul lub druga szufladka zawierać będzie co
najmniej m
2
kul, lub ..., lub n–ta szufladka zawierać będzie co
najmniej m
n
kul.
Zadanie 1.6. Udowodnić, że dla każdego naturalnego n
(a) 1
2
+ 2
2
+ 3
2
+ . . . + n
2
=
n(n+1)(2n+1)
,
jest liczbą nieparzystą, to n też jest liczbą nieparzystą.
co najmniej jeden dzielnik pierwszy p taki, że p≤
√
6
[ Pobierz całość w formacie PDF ]

zanotowane.pl

doc.pisz.pl

pdf.pisz.pl

slaveofficial.keep.pl