Matematyka dyskretna

AGH

DZIAŁ ZLICZANIE – cz. III

wszystkie zadania warte są 1 punkt

Zad. 1.
Udowodnij, że w grupie 2012 osób przynajmniej 2 osoby mają taką samą liczbę znajomych
(osoba A zna osobę B wtedy i tylko wtedy, gdy osoba B zna osobę A).

Zad. 2.
Udowodnij, że w gronie 6 osób albo pewne 3 osoby się znają, albo pewne 3 osoby się nie
znają.

Zad. 3.
Udowodnij, że wśród dowolnych 7 różnych liczb całkowitych musza być takie 2, których
suma lub różnica dzieli się przez 10.

Zad. 4.
Spośród liczb 1,2,3,…,9 wybrano sześć .Udowodnij, że spośród wybranych liczb można
wybrać dwie których suma wynosi 10.

Zad. 5.
Przy Okrągłym Stole siedzi 12 Rycerzy. W czasie obrad każdych dwóch siedzących obok
siebie pokłóciło się. Król Artur musi posłać w misję 5 Rycerzy. Na ile sposobów może to
zrobić jeśli nie chce, aby wśród wysłanych byli jacyś kłócący się Rycerze?

Zad. 6.
Mnich – benedyktyn wpisuje na oprawie każdej z ksiąg znajdujących się w bibliotece
klasztornej kolejny numer. Ile razy napisze cyfrę 9, jeśli wiadomo, że księgozbiór liczy sobie
77777 woluminów, zaś mnich rozpoczyna numerowanie od 1?

Zad. 7.
Towarzystwo złożone z 8 par małżeńskich dzieli się na 4 grupy po 4 osoby dla odbycia
spaceru łódką.

a) Na ile sposobów można to zrobić tak, aby w każdej łódce znalazły się 2 panie i 2

panów?

b) W ilu przypadkach danych mężczyzna znajdzie się w łódce ze swoją żoną?

Łódki nie są numerowane.

Zad. 8.
W ilu permutacjach liczb 1,…,5 żadna z liczb nie stoi na swoim miejscu?