Blatt 5 DM Loesung - Wintersemester 16-17, Uebungen mit Lsg PDF

Preview

Summary

Wintersemester 16-17, Uebungen mit Lsg...

Description

¨ Ubungen zur Mathematik I f¨ ur Studierende Informatik und Wirtschaftsinformatik (Diskrete Mathematik) im Wintersemester 2016/2017 Fachbereich Mathematik, Stefan Geschke, Mathias Schacht

B: Hausaufgaben zum 24. und 25. November 2016 1. (a) Wahr oder falsch? (Kurze Begr¨undung!) i. ii. iii. iv.

177 ≡ 18 (mod 5) 177 ≡ −18 (mod 5) −123 ≡ 33 (mod 13) 251 ≡ 51 (mod 2)

(b) Bestimmen Sie ggT(3213, 234) mit dem euklidischen Algorithmus und finden sie s, t ∈ Z mit s · 3213 + t · 234 = ggT(3213, 234). L¨ osung. (a) i. 177 mod 5 = 2 und 18 mod 5 = 3. Also ist die Aussage falsch. ii. 177 − (−18) = 195 ist durch 5 teilbar. Damit ist die Aussage wahr. iii. −123 = −10 · 13 + 7 und 33 = 2 · 13 + 7. Damit ist die Aussage wahr. iv. 251 ist durch 2 teilbar. Also gilt 251 mod 2 = 0, w¨ahrend 51 mod 2 = 1 ist. Also ist die Aussage falsch. (b) Wir wenden den euklidischen Algorithmus an. 3213 234 171 63 45 18

= = = = = =

13 · 234 + 171 1 · 171 + 63 2 · 63 + 45 1 · 45 + 18 2 · 18 + 9 2·9+0

Der letzte von 0 verschiedene Rest in dieser Rechung ist 9, also ist ggT(3213, 234) = 9. Wir berechnen die B´ezout-Koeffizienten. Es gilt 9 = 45 − 2 · 18 = 45 − 2 · (63 − 45) = −2 · 63 + 3 · 45 = −2 · 63 + 3 · (171 − 2 · 63) = −8 · 63 + 3 · 171 = − 8 · (234 − 171)+ 3 · 171 = −8 ·234 + 11 · 171 = −8 · 234 + 11 · (3213 − 13 · 234) = 11 · 3213 − 151 · 234. 2. (a) Es seien X = {1, 2, 3, 4} und Y = {1, 2, 3, 4, 5, 6}. Wie viele Abbildungen g : X → Y gibt es und wie viele davon sind injektiv? (b) X und Y seien definiert wie eben. Wieviele Abbildungen g : X → Y gibt es, f¨ur die g(1), g(3) und g(4) paarweise verschieden sind? osung. (a) Es gibt 64 = 1296 Abbildungen von X nach Y . Davon sind 6 · 5 · 4 · 3 = 360 injektiv. L¨ (b) Es gibt 6 · 6 · 5 · 4 = 720 Abbildungen von X nach Y , f¨ur die g(1), g(3) und g(4) paarweise verschieden sind.

3. (a) Wie viele verschiedene Tipps gibt es beim Lotto 6 aus 49“? ” (b) Die Menge M habe 510 Elemente. Wie viele Teilmengen mit mindestens 508 Elementen hat M? L¨ osung. (a) Es gibt   49 · 48 · 47 · 46 · 45 · 44 49 = = 13983816 6·5·4·3·2·1 6 verschiedene Tipps. (b) Wir z¨ahlen nicht die Teilmengen mit mindestens 508 Elementen, sondern deren Komplemente, also Mengen mit h¨ochstens 2 Elementen. Es gibt eine Teilmenge mit 0 Elementen, leere Menge.   die 510·509 = 129795 Es gibt 510 Teilmengen mit genau einem Element. Schließlich gibt es noch 510 = 2·1 2 Teilmengen mit genau 2 Elementen. Insgesamt erhalten wir 129795 + 510 + 1 = 130306 Teilmengen mit h¨ochstens 2 Elementen. Das ist auch die Zahl der Teilmengen mit mindestens 508 Elementen. 4. (a) Wie viele (sinnvolle oder sinnlose) W¨orter lassen sich durch Ver¨anderung der Reihenfolge der Buchstaben des Wortes KAFFEE bilden? (b) Wie eben, aber f¨ ur das Wort CAPPUCCINO . L¨osung. (a) KAFFEE hat 6 Buchstaben, von denen A und K genau einmal auftreten. E und F treten jeweils genau zweimal auf. Gem¨ aß der L¨ osung von Grundaufgabe 5 lassen sich aus den Buchstaben des Wortes KAFFEE durch vertauschen der Reihenfolge genau 6! = 180 2! · 2! verschiedene W¨orter bilden. (b) Unter den 10 Buchstaben des Wortes kommt C dreimal vor, P zweimal und alle anderen Buchstaben je einmal. Nach der L¨osung von Grundaufgabe 5 gibt es also 10! = 302400 3! · 2! W¨ orter, die sich aus den Buchstaben des Wortes CAPPUCCINO bilden lassen. 5. Zeigen Sie mittels vollst¨andiger Induktion, dass f¨ur alle n ≥ 3 die Gleichung   n   X i n+1 = 3 n−3 i=3 gilt. L¨osung. Induktionsanfang: Die Gleichung gilt f¨ur n = 3. Es gilt n¨amlich     3   X i 3 3+1 = =1= . 3 3 0 i=3 Induktionsschritt: Wir nehmen an, dass n  X i i=3

3



  n+1 = n−3

f¨ur ein gewisses n ≥ 3 gilt und zeigen, dass die Gleichung f¨ ur n + 1 anstelle von n gilt. Es ist n+1  X i=3

i 3



=

n   X i i=3

      n + 1 I.A. n + 1 n+1 + + = 3 3 n−3 3       n+1 (n + 1) + 1 n+1 + = . = (n + 1) − 4 (n + 1) − 3 (n + 1) − 3

Das zeigt die Gleichung f¨ ur n + 1....