Kurs:Diskrete Mathematik/14/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	5	3	4	1	2	4	2	4	2	0	0	0	0	0	8	0	0	41

Aufgabe (3 Punkte)

Definiere die folgenden (kursiv gedruckten) Begriffe.

1. Eine relationstreue Abbildung ${}\varphi \colon M\rightarrow N$, wobei auf ${}M$ und ${}N$ jeweils Relationen fixiert sind.
2. Die (zugehörige) Ordnung in einem algebraischen Verband ${}(M,\sqcap ,\sqcup )$.
3. Stirling-Zahl/2. Art/Partition/Definition/Begriff
4. Ungerichteter Graph/Homomorphismus/Definition/Begriff
5. Ungerichteter Graph/Rundgang/Definition/Begriff
6. Graph/Knotenüberdeckung/Minimal/Definition/Begriff

Lösung

1. Es seien ${}(M,R)$ und ${}(N,S)$ Mengen mit darauf erklärten Relationen ${}R$ bzw. ${}S$. Man nennt eine Abbildung

   $\varphi \colon M\longrightarrow N$

   relationstreu, wenn für alle ${}x,y\in M$ mit ${}xRy$ auch ${}\varphi (x)S\varphi (y)$ gilt.

2. In einem algebraischen Verband ${}(M,\sqcap ,\sqcup )$ nennt man die durch

   ${}y\geq x\,,$

   falls

   ${}x\sqcap y=x\,,$

   definierte Ordnung, die zugehörige Ordnung.

3. Stirling-Zahl/2. Art/Partition/Definition/Begriff/Inhalt
4. Ungerichteter Graph/Homomorphismus/Definition/Begriff/Inhalt
5. Ungerichteter Graph/Rundgang/Definition/Begriff/Inhalt
6. Graph/Knotenüberdeckung/Minimal/Definition/Begriff/Inhalt

Aufgabe (3 Punkte)

Formuliere die folgenden Sätze.

1. Die rekursive Beziehung zwischen den Binomialkoeffizienten (Pascalsches Dreieck).
2. Die Potenzgesetze für ein Monoid.
3. Der Sechs-Farben-Satz.

Lösung

1. Die Binomialkoeffizienten erfüllen die rekursive Beziehung

   ${}{\binom {n+1}{k}}={\binom {n}{k}}+{\binom {n}{k-1}}\,.$

2. Es sei ${}M$ ein Monoid, ${}a,b\in M$ und ${}m,n\in \mathbb {N}$. Dann gelten die folgenden Potenzgesetze.

   1. ${}a^{m+n}=a^{m}\cdot a^{n}\,.$

   2. ${}(a^{m})^{n}=a^{mn}\,.$

   3. Wenn ${}M$ kommutativ ist, so ist

      ${}(a\cdot b)^{n}=a^{n}\cdot b^{n}\,.$

3. Für jeden ebenen Graphen besteht eine zulässige Färbung mit höchstens sechs Farben.

Aufgabe (5 (3+2) Punkte)

Es seien ${}M_{1},\ldots ,M_{k}$ und ${}N_{1},\ldots ,N_{k}$ nichtleere Mengen und

$\varphi _{i}\colon M_{i}\longrightarrow N_{i}$

Abbildungen für ${}i=1,\ldots ,k$. Es sei ${}M=M_{1}\times \cdots \times M_{k}$, ${}N=N_{1}\times \cdots \times N_{k}$, und ${}\varphi$ die Produktabbildung, also

$\varphi \colon M\longrightarrow N,\,(x_{1},\ldots ,x_{k})\longmapsto (\varphi _{1}(x_{1}),\ldots ,\varphi _{k}(x_{k})).$

a) Zeige, dass ${}\varphi$ genau dann surjektiv ist, wenn alle ${}\varphi _{i}$ surjektiv sind.

b) Zeige, dass a) nicht gelten muss, wenn die beteiligten Mengen leer sein dürfen.

Lösung

a) Es seien alle ${}\varphi _{i}$ surjektiv und sei ${}y=(y_{1},\ldots ,y_{k})\in N$. Zu jedem ${}i$ gibt es ein ${}x_{i}\in M_{i}$ mit ${}\varphi (x_{i})=y_{i}$. Daher ist ${}x=(x_{1},\ldots ,x_{k})$ ein Urbild von ${}y$ unter ${}\varphi$.

Es sei umgekehrt ${}\varphi$ surjektiv, und sei ${}y_{i}\in N_{i}$ gegeben. Da die ${}N_{j}$ alle nicht leer sind, gibt es jeweils ein ${}a_{j}\in N_{j}$. Wir setzen

$y=(a_{1},\ldots ,a_{i-1},y_{i},a_{i+1},\ldots ,a_{k})\in N.$

Dafür gibt es nach Voraussetzung ein Urbild ${}x\in M$. Für die ${}i$-te Komponente davon muss ${}\varphi _{i}(x_{i})=y_{i}$ gelten.

b) Es sei ${}M_{1}=N_{1}=\emptyset$, sei ${}\varphi _{1}$ die leere Abbildung und seien ${}M_{2}$ und ${}N_{2}$ irgendwelche (nichtleere) Mengen und sei ${}\varphi _{2}\colon M_{2}\rightarrow N_{2}$ eine beliebige nicht surjektive Abbildung. Dann ist ${}M=\emptyset \times M_{2}=\emptyset$ und ${}N=\emptyset \times N_{2}=\emptyset$ und daher ist die Produktabbildung ${}\varphi =\varphi _{1}\times \varphi _{2}$ ebenfalls die leere Abbildung, also surjektiv, obwohl nicht alle ${}\varphi _{i}$ surjektiv sind.

Aufgabe (3 Punkte)

Petra hat folgende Informationen über die Erfolge von Deutschland bei Fußballweltmeisterschaften:

1. Die Fußballweltmeisterschaft findet alle vier Jahre statt.
2. Deutschland war schon viermal Weltmeister.
3. Deutschland war zum ersten Mal 1954 und zum letzten Mal 2014 Weltmeister.
4. Deutschland war nie zweimal hintereinander Weltmeister.

Wie viele Möglichkeiten für die Jahre, in denen Deutschland die zweite bzw. die dritte Weltmeisterschaft gewann, verbleiben?

Lösung

Die zweite und die dritte Weltmeisterschaft muss zwischen 1962 und 2006 (einschließlich) gewonnen worden sein. In diesem Zeitraum fanden 12 Weltmeisterschaften statt. Daher gibt es in diesem Zeitraum ${}{\binom {12}{2}}=66$ Jahrespaare, in denen die Gewinne stattgefunden haben können. Da Petra weiß, dass Deutschland nie direkt hintereinander gewonnen hat, muss sie die aufeinanderfolgenden Paare abziehen. Davon gibt es 11. Also verbleiben insgesamt ${}66-11=55$ Möglichkeiten.

Aufgabe (4 Punkte)

Beweise durch Induktion, dass für ${}n\geq 10$ die Abschätzung

${}3^{n}\geq n^{4}\,$

gilt.

Lösung

Induktionsanfang für ${}n=10$. Es ist

${}3^{10}=9^{5}=81\cdot 81\cdot 9\geq 6000\cdot 9\geq 10000=n^{4}\,.$

Zum Induktionsschluss sei ${}n\geq 10$. Dann ist

${}3^{n+1}=3\cdot 3^{n}\geq 3\cdot n^{4}=n^{4}+{\frac {1}{2}}n^{4}+{\frac {1}{2}}n^{4}+{\frac {1}{2}}n^{4}+{\frac {1}{2}}n^{4}\,.$

Andererseits ist nach der binomischen Formel

${}(n+1)^{4}=n^{4}+4n^{3}+6n^{2}+4n+1\,.$

Wir müssen

${}n^{4}+{\frac {1}{2}}n^{4}+{\frac {1}{2}}n^{4}+{\frac {1}{2}}n^{4}+{\frac {1}{2}}n^{4}\geq n^{4}+4n^{3}+6n^{2}+4n+1\,$

nachweisen. Der erste Summand stimmt links und rechts überein, für die anderen Summanden zeigen wir, dass die linken, also jeweils ${}{\frac {1}{2}}n^{4}$, mindestens so groß wie die rechten sind. Dies folgt aber direkt aus ${}n^{4}\geq 8n^{3}$ (da ${}n\geq 10$), aus ${}n^{4}\geq 12n^{2}$, da ja ${}n^{2}\geq 12$ ist, aus ${}n^{4}\geq 8n$ und aus ${}n^{4}\geq 2$.

Aufgabe (1 Punkt)

Es sei ${}M$ eine Menge. Wir betrachten die Verknüpfung

${\mathfrak {P}}\,(M)\times {\mathfrak {P}}\,(M)\longrightarrow {\mathfrak {P}}\,(M),\,(A,B)\longmapsto A\setminus B.$

Ist diese Verknüpfung assoziativ?

Lösung

Diese Verknüpfung ist nicht assoziativ. Um dies zu zeigen, kann man einfach

${}A=B=C=M\,$

nehmen, wobei ${}M$ eine nichtleere Menge sei. Dann ist ${}M\setminus M=\emptyset$ und somit ist einerseits

${}(M\setminus M)\setminus M=\emptyset \setminus M=\emptyset \,$

und andererseits

${}M\setminus (M\setminus M)=M\setminus \emptyset =M\,.$

Aufgabe (2 Punkte)

Zeige, dass ein Ring mit ${}0=1$ der Nullring ist.

Lösung

Es sei ${}R$ ein Ring mit ${}1=0$ und sei ${}a\in R$ ein Ringelement. Dann gilt nach Eigenschaften der Multiplikation

${}a=1\cdot a=0\cdot a=0\,.$

Also ist jedes Element gleich ${}0$ und der Ring ist der Nullring.

Aufgabe (4 Punkte)

Zeige durch Induktion, dass jede nichtleere Teilmenge ${}T\subseteq \mathbb {N}$ ein kleinstes Element besitzt.

Lösung

Wir betrachten die Aussage

${}A(n)$ = Alle Teilmengen von ${}\mathbb {N}$, die ${}n$ enthalten, besitzen ein Minimum.

Da jede nichtleere Teilmenge mindestens ein ${}n\in \mathbb {N}$ besitzt, ist die Aussage des Satzes äquivalent zur Gültigkeit von ${}A(n)$ für alle ${}n$. Diese Aussage können wir durch Induktion beweisen. Die Aussage ${}A(0)$ besagt, dass jede Teilmenge ${}M\subseteq \mathbb {N}$, die die ${}0$ enthält, auch ein Minimum enthält. Dies ist aber klar, da dann eben ${}0$ das Minimum ist. Es sei die Aussage ${}A(k)$ nun für alle ${}k\leq n$ schon bewiesen. Wir müssen ${}A(n+1)$ beweisen. Es sei also ${}M\subseteq \mathbb {N}$ eine Teilmenge, die ${}n+1$ enthält. Wenn ${}M$ auch eine Zahl ${}k<n+1$ besitzt, so besitzt ${}M$ nach der Induktionsvoraussetzung ein Minimum. Andernfalls besitzt ${}M$ keine Zahl, die kleiner als ${}n+1$ ist. Dann ist aber ${}n+1$ das Minimum von ${}M$.

Aufgabe (2 Punkte)

Beweise die Formel

${}2^{n}=\sum _{k=0}^{n}{\binom {n}{k}}\,$

mit Hilfe des allgemeinen binomischen Lehrsatzes.

Lösung

Der binomische Lehrsatz besagt

${}(a+b)^{n}=\sum _{k=0}^{n}{\binom {n}{k}}a^{k}b^{n-k}\,.$

Wir setzen ${}a=b=1$. Dann ergibt sich auf der linken Seite

${}(1+1)^{n}=2^{n}\,$

und auf der rechten Seite einfach ${}\sum _{k=0}^{n}{\binom {n}{k}}$.

Aufgabe (4 Punkte)

Beweise die Eindeutigkeit der Primfaktorzerlegung für natürliche Zahlen.

Lösung

Die Eindeutigkeit wird durch Induktion über ${}n$ gezeigt. Für ${}n=2$ liegt eine Primzahl vor. Es sei nun ${}n\geq 3$ und seien zwei Zerlegungen in Primfaktoren gegeben, sagen wir

${}n=p_{1}{\cdots }p_{r}=q_{1}{\cdots }q_{s}\,.$

Wir müssen zeigen, dass nach Umordnung die Primfaktorzerlegungen übereinstimmen. Die Gleichheit bedeutet insbesondere, dass die Primzahl ${}p_{1}$ das Produkt rechts teilt. Nach dem Lemma von Euklid muss dann ${}p_{1}$ einen der Faktoren rechts teilen. Nach Umordnung können wir annehmen, dass ${}q_{1}$ von ${}p_{1}$ geteilt wird. Da ${}q_{1}$ selbst eine Primzahl ist, folgt, dass ${}p_{1}=q_{1}$ sein muss. Daraus ergibt sich durch Kürzen, dass

${}p_{2}{\cdots }p_{r}=q_{2}{\cdots }q_{s}\,$

ist. Nennen wir diese Zahl ${}n'$. Da ${}n'<n$ ist, können wir die Induktionsvoraussetzung auf ${}n'$ anwenden und erhalten, dass links und rechts die gleichen Primzahlen stehen.

Aufgabe (2 Punkte)

Seien ${}M$ und ${}N$ Mengen und sei ${}f\colon M\rightarrow N$ eine Abbildung. Zeige, dass durch die Festlegung

${}x\sim y\,,$

wenn

${}f(x)=f(y)\,,$

eine Äquivalenzrelation auf ${}M$ definiert wird.

Lösung

Da der Funktionswert ${}f(x)$ eindeutig bestimmt und die Gleichheit reflexiv ist, gilt offenbar ${}x\sim x$. Wenn ${}x\sim y$ ist, so bedeutet das ${}f(x)=f(y)$ und wegen der Symmetrie der Gleichheit folgt ${}f(y)=f(x)$, was wiederum ${}y\sim x$ bedeutet. Wenn ${}x\sim y$ und ${}y\sim z$ ist, so bedeutet dies einerseits ${}f(x)=f(y)$ und andererseits ${}f(y)=f(z)$. Wegen der Transitivität der Gleichheit folgt ${}f(x)=f(z)$, was ${}x\sim z$ bedeutet.

Aufgabe (0 Punkte)

Lösung /Aufgabe/Lösung

Aufgabe (0 Punkte)

Lösung /Aufgabe/Lösung

Aufgabe (0 Punkte)

Lösung /Aufgabe/Lösung

Aufgabe (0 Punkte)

Lösung /Aufgabe/Lösung

Aufgabe (0 Punkte)

Lösung /Aufgabe/Lösung

Aufgabe (8 Punkte)

Beweise den Satz von Ore.

Lösung

Wir argumentieren bei einer fixierten Knotenmenge absteigend über die Kantenmenge. Für einen vollständigen Graphen ist die Aussage richtig. Wir müssen zeigen, dass die Aussage richtig bleibt, wenn man aus einem Graphen, für den die Aussage gilt, eine Kante herausnimmt. Es sei also ${}G$ ein Graph, für den es einen Hamiltonkreis gibt, und es sei ${}L=\{x,y\}$ die Kante, die wir herausnehmen. Es sei ${}H$ der verkleinerte Graph. Wenn es in ${}G$ einen Hamiltonkreis gibt, in dem ${}L$ nicht vorkommt, so ist dies direkt ein Hamiltonkreis für ${}H$. Es sei also (alle ${}\sim$ beziehen sich auf ${}G$)

${}x=v_{1}\sim v_{2}\sim \ldots \sim v_{n-1}\sim v_{n}=y\,$

mit ${}n={\#\left(V\right)}$ ein Hamiltonkreis von ${}G$. Wir betrachten die Mengen

${}A={\left\{v_{i}\mid x{\text{ und }}v_{i+1}{\text{ sind benachbart}}\right\}}\,$

und

${}B={\left\{v_{i}\mid y{\text{ und }}v_{i}{\text{ sind benachbart}}\right\}}\,.$

Dabei ist (in der Definition von ${}A$) ${}v_{n+1}$ als ${}v_{1}$ zu interpretieren und die Nachbarschaften beziehen sich auf ${}H$. Aufgrund der Voraussetzung über die Grade (${}x$ und ${}y$ sind nicht adjazent und ${}A$ ist so groß wie ${}N(x)$) ist

${}{\#\left(A\right)}+{\#\left(B\right)}\geq n\,.$

Das Element ${}y$ gehört nicht zur Vereinigung ${}A\cup B$, da ein Knotenpunkt nicht mit sich selbst benachbart ist. Daher gibt es nach der Siebformel ein Element

${}v_{k}\in A\cap B\,.$

Es gibt also die Verbindungskanten ${}\{x,v_{k+1}\}$ und ${}\{y,v_{k}\}$ und somit den Hamiltonkreis

${}x\sim v_{2}\sim \ldots \sim v_{k-1}\sim v_{k}\sim y\sim v_{n-1}\sim \ldots \sim v_{k+1}\,,$

der ohne die Kante ${}L$ auskommt und daher ein Hamiltonkreis in ${}H$ ist.

Aufgabe (0 Punkte)

Lösung /Aufgabe/Lösung

Aufgabe (0 Punkte)

Lösung /Aufgabe/Lösung