Kurs:Diskrete Mathematik/21/Klausur mit Lösungen

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	0	0	0	0	0	4	0	0	0	0	0	0	0	0	0	0	13

Aufgabe (3 Punkte)

Definiere die folgenden (kursiv gedruckten) Begriffe.

Ein Körper ${}K$ .
Die Antisymmetrie einer Relation ${}R$ auf einer Menge ${}M$ .
Partitionen/Bellzahl/Definition/Begriff
Ungerichteter Graph/Menge/Abbildung/Bildgraph/Definition/Begriff
Ungerichteter Graph/Aufspannender Baum/Definition/Begriff
Matroid/Rang/Definition/Begriff

Lösung

Ein Körper ${}K$ ist ein kommutativer Ring, wenn ${}K\neq 0$ ist und wenn jedes von ${}0$ verschiedene Element in ${}K$ ein multiplikatives Inverses besitzt.
Die Relation ${}R$ heißt antisymmetrisch, wenn aus ${}xRy$ und ${}yRx$ stets ${}x=y$ folgt.
Partitionen/Bellzahl/Definition/Begriff/Inhalt
Ungerichteter Graph/Menge/Abbildung/Bildgraph/Definition/Begriff/Inhalt
Ungerichteter Graph/Aufspannender Baum/Definition/Begriff/Inhalt
Matroid/Rang/Definition/Begriff/Inhalt

Aufgabe (3 Punkte)

Formuliere die folgenden Sätze.

Lösung

Aufgabe (3 (1+1+1) Punkte)

Professor Knopfloch war schwimmen. Beim Auswringen seiner Badehose hat er sich ungeschickt angestellt und sich dabei drei Finger verstaucht (er besitzt noch alle zehn Finger).

Wie viele Möglichkeiten für die verstauchten Finger gibt es?
Wie viele Möglichkeiten gibt es, wenn man weiß, dass genau ein Daumen verstaucht wurde.
Wie viele Möglichkeiten gibt es, wenn man weiß, dass genau ein Daumen verstaucht wurde und beide Hände betroffen sind.

Lösung

Es gibt
${}{\binom {10}{3}}={\frac {10\cdot 9\cdot 8}{3\cdot 2\cdot 1}}=10\cdot 3\cdot 4=120\,$

Möglichkeiten dafür, welche Finger verstaucht sind.
Für den Daumen gibt es zwei Möglichkeiten, von den verbleibenden ${}8$ Nichtdaumenfingern sind zwei verstaucht, also gibt es insgesamt
${}2\cdot {\binom {8}{2}}=2\cdot {\frac {8\cdot 7}{2}}=56\,$

Möglichkeiten in dieser Situation.
Für den Daumen gibt es wieder zwei Möglichkeiten. Es ist dann entweder auf der Hand des verstauchten Daumens ein weiterer Finger verstaucht oder aber auf der anderen Hand sind genau zwei Finger verstaucht. Deshalb gibt es
${}2\cdot {\left(4\cdot 4+{\binom {4}{2}}\right)}=2\cdot {\left(16+6\right)}=44\,$

Möglichkeiten für diese Situation.

Aufgabe (4 (1+3) Punkte)

Gibt es eine Primzahl ${}x$ derart, dass auch ${}x+10$ und ${}x+20$ Primzahlen sind?
Gibt es mehr als eine Primzahl ${}x$ derart, dass auch ${}x+10$ und ${}x+20$ Primzahlen sind?

Lösung

Die Zahlen ${}3,13,23$ sind Primzahlen.
Wir zeigen, dass es außer dem soeben genannten Beispiel kein weiteres Tripel mit der besagten Eigenschaft gibt. Wir betrachten die Reste von ${}x,x+10,x+20$ bei Division durch ${}3$ . Wenn ${}r$ der Rest von ${}x$ ist, so sind die beiden anderen Reste gleich ${}r+1$ bzw. ${}r+2$ . Somit muss eine der drei Zahlen den Rest ${}0$ besitzen, also ein Vielfaches von ${}3$ sein. Da ${}x=3$ ausgeschlossen ist, können nicht alle drei Zahlen Primzahlen sein.