Jaworski-Palka-Szymanski - Matematyka dyskretna dla informatykow.pdf

(148 KB) Pobierz
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ń
2 Podstawowe zasady i prawa przeliczania
3 Schematy wyboru i tożsamości kombinatoryczne
4 Zależności rekurencyjne
5 Aparat funkcji tworzących
6 Algebry Boole’a
1
5
9
13
17
21
1
Metody dowodzenia
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
jest liczbą nieparzystą, to
n
też jest liczbą nieparzystą.
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
√
co najmniej jeden dzielnik pierwszy
p
taki, że
p
≤
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)
6
,

Plik z chomika:

Inne pliki z tego folderu:

Inne foldery tego chomika:

Zgłoś jeśli naruszono regulamin