Kurs:Diskrete Mathematik/7/Klausur/kontrolle

Aufgabe	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17	18	19	${}\sum$
Punkte	3	3	3	3	4	3	0	2	0	8	2	0	1	0	0	0	0	0	0	32

Aufgabe * (3 Punkte)Referenznummer erstellen

Auf wie viele Arten kann man mit den üblichen Münzen einen Betrag von ${}20$ Cent begleichen?

Aufgabe * (3 Punkte)Referenznummer erstellen

Die Puzzleteile für ein Puzzle haben eine grob rechteckige Form, wobei die eine Seite erkennbar länger als die andere ist, und auf jeder Seite gibt es entweder eine Einbuchtung oder eine Ausbuchtung. Wie viele Typen von Puzzelteilen gibt es?

Aufgabe * (4 Punkte)Referenznummer erstellen

Beweise den Satz über die Anzahl von bijektiven Abbildungen.

Aufgabe * (3 Punkte)Referenznummer erstellen

Wie viele Teilquadrate mit positiver Seitenlänge gibt es in einem Quadrat der Seitenlänge ${}5$ ? Die Seiten der Teilquadrate sollen wie im Bild auf dem „Gitter“ liegen, ein einzelner Punkt gelte nicht als Quadrat.

Aufgabe (0 Punkte)Referenznummer erstellen

Aufgabe * (2 Punkte)Referenznummer erstellen

Beweise den Satz über die Lösbarkeit von Gleichungen in einer Gruppe ${}G$ .

Aufgabe (0 Punkte)Referenznummer erstellen

Aufgabe * (8 (1+2+3+2) Punkte)Referenznummer erstellen

Wir betrachten eine (einfachere, aber langsamere) Variante des euklidischen Algorithmus zur Bestimmung des größten gemeinsamen Teilers zu zwei gegebenen natürlichen Zahlen ${}a,b$ .

Der Algorithmus geht folgendermaßen. Wenn ${}a\neq b$ ist, so ersetzte das Paar ${}(a,b)$ durch das Paar, das aus der kleineren Zahl und der Differenz zwischen der kleineren und der größeren Zahl besteht. Wiederhole dies rekursiv. Wenn ${}a=b$ ist, so ist man fertig und es wird das Ergebnis ${}a$ ausgegeben.

Führe diesen Algorithmus für das Paar ${}(7,3)$ durch.
Zeige, dass dieser Algorithmus nach endlich vielen Schritten aufhört.
Zeige, dass dieser Algorithmus korrekt ist, also wirklich den größten gemeinsmen Teiler ausgibt.
Man gebe für jedes ${}n$ ein Beispiel, wo der euklidische Algorithmus nach einem Schritt fertig ist, wo aber die Variante ${}n$ Schritte benötigt.

Aufgabe * (2 Punkte)Referenznummer erstellen

Zeige, dass die auf ${}\mathbb {Z} \times \mathbb {N} _{+}$ durch

(a,b)\sim (c,d),{\text{ falls }}ad=bc,

festgelegte Relation eine Äquivalenzrelation ist.

Aufgabe (0 Punkte)Referenznummer erstellen

Aufgabe * (1 Punkt)Referenznummer erstellen

Bei einem vollständigen ungerichteten Graphen mit ${}4$ Ecken ist jede Ecke mit jeder (anderen) Ecke verbunden. Zeichne einen solchen Graphen in der Ebene ohne Überschneidungen.