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

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

Aufgabe (3 Punkte)

Definiere die folgenden (kursiv gedruckten) Begriffe.

1. Eine Untergruppe ${}H$ in einer Gruppe ${}G$.
2. Eine rechtsvollständige Relation  ${}R\subseteq M\times N$. 
3. Ein Supremum zu einer Teilmenge  ${}J\subseteq I$  in einer geordneten Menge ${}(I,\preccurlyeq )$.
4. Die Nachbarschaft zu einem Punkt  ${}v\in V$  in einem Graphen  ${}G=(V,E)$. 
5. Der Radius eines zusammenhängenden Graphen  ${}G=(V,E)$. 
6. Eine optimale Knotenüberdeckung eines Graphen  ${}G=(V,E)$. 

Lösung

1. Eine Teilmenge ${}H\subseteq G$ heißt Untergruppe von ${}G$, wenn Folgendes gilt.
   1. ${}e\in H$.
   2. Mit ${}g,h\in H$ ist auch ${}g\circ h\in H$.
   3. Mit ${}g\in H$ ist auch ${}g^{-1}\in H$.
2. Die Relation  ${}R\subseteq M\times N$  heißt rechtsvollständig, wenn es zu jedem  ${}y\in N$  ein  ${}x\in M$  mit  ${}(x,y)\in R$  gibt.
3. Ein Element  ${}t\in I$  heißt Supremum von ${}J$, wenn ${}s$ die kleinste obere Schranke von ${}J$ ist.
4. Man nennt

   ${}N(v)=\left\{u\in V\mid \{u,v\}\in E\right\}\,$

   die Nachbarschaft von ${}v$.

5. Der Radius ist der Ausdruck

   $\operatorname {min} \left(\operatorname {max} \left(d(u,v){|}u\in V\right){|}v\in V\right).$

6. Eine Knotenüberdeckung  ${}W\subseteq V$  heißt opitimal, wenn die Anzahl von ${}W$ minimal unter allen Anzahlen von Knotenüberdeckungen ist.

Aufgabe (3 Punkte)

Formuliere die folgenden Sätze.

1. Der Satz über die algebraische Struktur der Restklassenringe ${}R/{\mathfrak {a}}$ zu einem Ideal  ${}{\mathfrak {a}}\subseteq R$  in einem kommutativen Ring ${}R$.
2. Der Satz über die explizite Lösung einer Matrixrekursion im diagonalisierbaren Fall.
3. Der Vier-Farben-Satz.

Lösung

1. Es sei ${}R$ ein kommutativer Ring,  ${}{\mathfrak {a}}\subseteq R$  ein Ideal und ${}R/{\mathfrak {a}}$ die Quotientenmenge zur durch ${}{\mathfrak {a}}$ definierten Äquivalenzrelation auf ${}R$ mit der kanonischen Projektion

   $q\colon R\longrightarrow R/{\mathfrak {a}},\,g\longmapsto [g].$

   Dann gibt es eine eindeutig bestimmte Ringstruktur auf ${}R/{\mathfrak {a}}$ derart, dass ${}q$ ein Ringhomomorphismus

   ist.
2. Es sei ${}M$ eine ${}d\times d$-Matrix über dem Körper ${}K$. Es sei ${}w_{1},\ldots ,w_{d}$ eine Basis aus Eigenvektoren von ${}M$ mit den Eigenwerten ${}\lambda _{1},\ldots ,\lambda _{d}$. Es sei

   ${}v_{0}=\sum _{i=1}^{d}s_{i}w_{i}\,$

   ein Startvektor, der als Linearkombination in dieser Basis vorliegt.

   Dann ist

   ${}v_{n}=\sum _{i=1}^{d}\lambda _{i}^{n}s_{i}w_{i}\,$

   eine Lösung der Matrixrekursion

   ${}v_{n+1}=Mv_{n}\,$

   mit dem Startvektor ${}v_{0}$.
3. Für jeden ebenen Graphen besteht eine zulässige Färbung mit höchstens vier Farben.

Aufgabe (6 Punkte)

Man gebe ein Beispiel für eine kombinatorische Formel, die sowohl direkt als auch durch eine inhaltliche Überlegung bewiesen werden kann. Man führe beide Beweise vor.

Lösung erstellen

Aufgabe (6 (1+1+2+2) Punkte)

Professor Knopfloch möchte mit Dr. Eisenbeis essen gehen und hebt daher beim Bankautomat ${}100$ Euro in Scheinen ab.

1. Was ist die minimale Anzahl von Scheinen und was ist die maximale Anzahl von Scheinen, die er bekommen kann?
2. Ist es möglich, dass er ${}17$ Scheine bekommt?
3. Welche Anzahlen von Scheinen sind möglich?
4. Was ist die kleinste Anzahl von Scheinen, für die es zumindest zwei verschiedene Scheinverteilungen gibt?

Lösung

1. Das Minimum an Scheinen ist ${}1$ (ein Hunderter), das Maximum ist ${}20$ (${}20$ Fünfer).
2. Es ist

   ${}3\cdot 10+14\cdot 5=30+70=100\,,$

   ${}17$ Scheine sind also mit ${}3$ Zehnern und ${}14$ Fünfern möglich.

3. Es sind die Anzahlen ${}1-2$ und ${}4-20$ möglich, mit ${}3$ Scheinen ist es nicht möglich. ${}1$: ein Hunderter. ${}2$: zwei Fünfziger. ${}3$: Es kann höchstens ein Fünfziger vorkommen, mit zwei Zwanzigern bleibt man aber unterhalb von ${}100$. ${}4$: Ein Fünfziger und zwei Zwanziger und ein Zehner. ${}5$: Fünf Zwanziger. Um ${}6-10$ Scheine zu erreichen kann man sukzessive einen Zwanziger durch zwei Zehner ersetzen. ${}10$: ${}10$ Zehner. Um ${}11-20$ Scheine zu erreichen kann man sukzessive einen Zehner durch zwei Fünfer ersetzen.
4. Bei einem und zwei Scheinen gibt es offenbar nur eine Möglichekeit, mit drei Scheinen geht es gar nicht. Mit vier Scheinen gibt es nur die Möglichkeit ${}50+20+20+10$, da man ohne den Fünfziger nicht auskommt. Mit ${}5$ Scheinen gibt es die beiden Möglichkeiten entweder fünf Zwanziger oder ${}50+20+20+5+5$. Die Antwort ist also ${}5$.

Aufgabe (2 Punkte)

Heute ist Freitag. Welcher Wochentag ist in ${}1000$ Tagen?

Lösung

Es ist

${}1000=700+280+14+6\,,$

der Rest bei der Division von ${}1000$ durch ${}7$ ist also ${}6$. Daher ist in ${}1000$ Tagen Donnerstag.

Aufgabe (2 Punkte)

Skizziere sieben Geraden in der Ebene, die sich insgesamt in acht Punkten schneiden.

Lösung

Aufgabe (5 Punkte)

Beweise den binomischen Lehrsatz für einen kommutativen Halbring ${}R$.

Lösung

Es seien ${}a,b\in R$. Wir führen Induktion nach ${}n$. Für  ${}n=0$  steht einerseits  ${}(a+b)^{0}=1$  und andererseits  ${}a^{0}b^{0}=1$.  Es sei die Aussage bereits für ${}n$ bewiesen. Dann ist

${}{\begin{aligned}(a+b)^{n+1}&=(a+b)(a+b)^{n}\\&=(a+b)\left(\sum _{k=0}^{n}{\binom {n}{k}}a^{k}b^{n-k}\right)\\&=a\left(\sum _{k=0}^{n}{\binom {n}{k}}a^{k}b^{n-k}\right)+b\left(\sum _{k=0}^{n}{\binom {n}{k}}a^{k}b^{n-k}\right)\\&=\sum _{k=0}^{n}{\binom {n}{k}}a^{k+1}b^{n-k}+\sum _{k=0}^{n}{\binom {n}{k}}a^{k}b^{n-k+1}\\&=\sum _{k=1}^{n+1}{\binom {n}{k-1}}a^{k}b^{n-k+1}+\sum _{k=0}^{n+1}{\binom {n}{k}}a^{k}b^{n-k+1}\\&=\sum _{k=1}^{n+1}\left({\binom {n}{k-1}}+{\binom {n}{k}}\right)a^{k}b^{n+1-k}+b^{n+1}\\&=\sum _{k=1}^{n+1}{\binom {n+1}{k}}a^{k}b^{n+1-k}+b^{n+1}\\&=\sum _{k=0}^{n+1}{\binom {n+1}{k}}a^{k}b^{n+1-k}.\end{aligned}}$

Aufgabe (1 Punkt)

Es sei ${}G$ eine Gruppe. Es seien  ${}x,y\in G$  Elemente mit

${}x\cdot y=1\,$

Zeige, dass ${}y$ das Inverse von ${}x$ ist.

Lösung

Es sei ${}z$ das Inverse von ${}x$. Dann ist

${}y=1\cdot y=(z\cdot x)\cdot y=z(x\cdot y)=z\cdot 1=z\,,$

also ist ${}y$ gleich dem Inversen von ${}x$.

Aufgabe (2 Punkte)

Bestimme in ${}\mathbb {Z}$ mit Hilfe des euklidischen Algorithmus den größten gemeinsamen Teiler von ${}1071$ und ${}1029$.

Lösung

Der größte gemeinsame Teiler von 1071 und 1029 wird mit dem Euklidischen Algorithmus wie folgt berechnet:

${}1071=1\cdot 1029+42\,,$

${}1029=24\cdot 42+21\,,$

${}42=2\cdot 21+0\,.$

Der größte gemeinsame Teiler von 1071 und 1029 ist somit 21.

Aufgabe (3 Punkte)

Zeige durch Induktion, dass jede natürliche Zahl  ${}n\geq 2$  eine Zerlegung in Primzahlen besitzt.

Lösung

Wir beweisen die Existenz durch Induktion über ${}n$.  Für  ${}n=2$  liegt eine Primzahl vor. Bei  ${}n\geq 3$  ist entweder ${}n$ eine Primzahl, und diese bildet die Primfaktorzerlegung, oder aber ${}n$ ist keine Primzahl. In diesem Fall gibt es eine nichttriviale Zerlegung  ${}n=ab$  mit kleineren Zahlen  ${}a,b<n$.  Für diese Zahlen gibt es nach Induktionsvoraussetzung jeweils eine Zerlegung in Primfaktoren, und diese setzen sich zu einer Primfaktorzerlegung für ${}n$ zusammen. 

Aufgabe (3 (1+2) Punkte)

Wir betrachten auf den komplexen Zahlen die Relation, bei der zwei Zahlen ${}z,w$ als äquivalent gelten, wenn ihre ${}17$-te Potenz übereinstimmt.

1. Zeige, dass dies eine Äquivalenzrelation ist.
2. Wie viele Elemente beinhalten die Äquivalenzklassen (verwende, dass es ${}17$ komplexe Zahlen mit  ${}z^{17}=1$  gibt)?

Lösung

1. Zwei komplexe Zahlen gelten als äquivalent, wenn sie unter der Abbildung

   ${\mathbb {C} }\longrightarrow {\mathbb {C} },\,z\longmapsto z^{17},$

   den gleichen Wert besitzen. In einer solchen Situation liegt stets eine Äquivalenzrelation vor.

2. Da ${}{\mathbb {C} }$ ein Körper ist, besteht die Äquivalenzklasse zu ${}0$ allein aus ${}0$, sie ist also einelementig. Die Äquivalenzklasse zu ${}1$ besteht aus den ${}17$ ${}17$-ten Einheitswurzeln. Für von ${}0$ verschiedene Zahlen ist

   ${}z^{17}=w^{17}\,$

   genau dann, wenn

   ${}\left({\frac {w}{z}}\right)^{17}=1\,,$

   wenn also ${}w/z$ eine ${}17$-te Einheitswurzel ist. Somit besteht die Äquivalenzklasse zu  ${}z\neq 0$  aus der ${}17$ Elementen ${}z\zeta$, wobei ${}\zeta$ die ${}17$-ten Einheitswurzeln durchläuft.

Aufgabe (4 Punkte)

Zu  ${}n,k\in \mathbb {N}$  bezeichne ${}\operatorname {surj} (n,k)$ die Anzahl der surjektiven Abbildungen einer ${}n$-elementigen Menge in eine ${}k$-elementige Menge. Zeige, dass die Rekursionsformel

${}\operatorname {surj} (n+1,k)=k\cdot \operatorname {surj} (n,k)+k\cdot \operatorname {surj} (n,k-1)\,$

gilt.

Lösung

Wir betrachten direkt die Mengen

${}A=\{1\ldots ,n,n+1\}\,$

und

${}B=\{1,\ldots ,k\}\,$

und die surjektiven Abbildungen von ${}A$ nach ${}B$. Eine solche surjektive Abbildung ${}\varphi$ hat entweder die Eigenschaft, dass auch ${}\varphi {|}_{A\setminus \{n+1\}}$ surjektiv ist, oder aber nicht. Im ersten Fall entsprechen diese Abbildungen den surjektiven Abbildungen von ${}A\setminus \{n+1\}$ nach ${}B$ zusammen mit dem zusätzlichen Wert ${}\varphi (n+1)$. Dies ergibt den ersten Summand. Im zweiten Fall entsprechen diese Abbildungen den surjektiven Abbildungen von ${}A\setminus \{n+1\}$ nach ${}B\setminus \{\varphi (n+1)\}$, wobei es wiederum für den Wert ${}\varphi (n+1)$ ${}k$ Möglichkeiten gibt. Dies ergibt den zweiten Summanden.

Aufgabe (4 Punkte)

Erstelle ein Kartenspiel mit insgesamt sieben Symbolen und sieben Karten, wobei auf jeder Karte drei Symbole vorkommen mit der Eigenschaft, dass je zwei Karten genau ein Symbol gemeinsam haben.

Lösung

Die Karten entsprechen den Punkten, die Symbole darauf repräsentieren die projektiven Geraden, die durch diesen Punkt verlaufen.

Aufgabe (3 Punkte)

Bestimme die verschiedenen Typen zu den Permutationen auf einer vierelementigen Menge sowie die Anzahl der Permutationen, die diesen Typ besitzen.

Lösung

Die Typen sind

$(1,1,1,1),\,(1,1,2),\,(1,3),\,(2,2),(4).$

${}(1,1,1,1)$. Jedes Element ist ein Fixpunkt, das muss also die Identität sein, da gibt es nur eine Möglichkeit.

${}(1,1,2)$. Zwei Fixpunkte und ein Zweierzyklus. Dies ist durch die Auswahl einer zweielementigen Menge an Fixpunkten eindeutig bestimmt, hier gibt es ${}6$ Möglichkeiten.

${}(1,3)$. Ein Fixpunkt und ein Dreierzyklus. Für die Wahl des Fixpunktes gibt es ${}4$ Möglichkeiten. Auf der komplmentären dreielementigen Menge gibe es ${}2$ Möglichkeiten, wie der Dreierzyklus funktioniert. Dies ergibt insgesamt ${}8$ Möglichkeiten.

${}(2,2)$. Es geht um eine Partition in ${}2$ ${}2$-elementige Teilmengen. Dafür gibt es ${}3$ Möglichkeiten, die jeweiligen Transpositionen sind dann festgelegt.

${}(4)$. Es gibt einen Viererzyklus. Dafür gibt es ${}6$ Möglichkeiten.

Aufgabe (3 Punkte)

Es sei ${}M$ eine ${}d\times d$-Matrix über dem Körper ${}K$ mit der zugehörigen linear-rekursiven Folge  ${}v_{n}\in K^{d}$  zum Startvektor  ${}v_{0}\in K^{d}$.  Es sei ${}L$ eine invertierbare ${}d\times d$-Matrix und sei

${}N=LML^{-1}\,$

und  ${}w_{0}=L\left(v_{0}\right)\in K^{d}$.  Zeige, dass die linear-rekursive Folge ${}w_{n}$ zur Matrix ${}N$ und zum Startvektor ${}w_{0}$ die Beziehung

${}w_{n}=L\left(v_{n}\right)\,$

für alle ${}n$ erfüllt.

Lösung

Wir zeigen

${}L\left(v_{n}\right)=w_{n}\,$

durch Induktion über ${}n$, der Induktionsanfang ist unmittelbar durch die Startbedingung gegeben. Es sei also  ${}L\left(v_{n}\right)=w_{n}$  für ein ${}n$ vorausgesetzt. Dann ist

${}{\begin{aligned}w_{n+1}&=N\left(w_{n}\right)\\&=\left(LML^{-1}\right)\left(w_{n}\right)\\&=\left(LML^{-1}\right)\left(L\left(v_{n}\right)\right)\\&=LM\left(v_{n}\right)\\&=L\left(v_{n+1}\right)\end{aligned}}$

wie gefordert.

Aufgabe (2 Punkte)

Skizziere den Nullteilergraphen zum Ring ${}\mathbb {Z} /(10)$ überschneidungsfrei.

Lösung erstellen

Aufgabe (3 Punkte)

Zeige, dass die Verbundenheit zwischen Knotenpunkten in einem Graphen  ${}G=(V,E)$  eine Äquivalenzrelation auf der Knotenmenge ${}V$ ist.

Lösung

Jeder Knotenpunkt ist durch den leeren Kantenzug mit sich selbst verbunden. Dies sichert die Reflexivität. Wenn ${}u$ und ${}v$ durch den Kantenzug ${}u=v_{1},v_{2},\ldots ,v_{r-1},v_{r}=v$ miteinander verbunden sind, so ist ${}v$ mit ${}u$ durch den umorientierten Kantenzug ${}v_{r},v_{r-1},\ldots ,v_{2},v_{1}$ verbunden. Dies sichert die Symmetrie. Wenn ${}u$ mit ${}v$ durch den Kantenzug ${}u=v_{1},v_{2},\ldots ,v_{r}=v$ verbunden ist und ${}v$ mit ${}w$ durch den Kantenzug ${}v=w_{1},w_{2},\ldots ,w_{s}=w$ verbunden ist, so ist ${}u$ mit ${}w$ durch den zusammengesetzten Kantenzug ${}u=v_{1},v_{2},\ldots ,v_{r}=v=w_{1},w_{2},\ldots ,w_{s}=w$ verbunden. Dies sichert die Transitivität.

Aufgabe weiter

Bestimme zum Netzgraphen ${}G$ der Kopenhagener Metro die folgenden graphentheoretischen Invarianten (parallele Strecken verstehen wir einfach).
a) Die Blätter von ${}G$.
b) Den Abstand von Nordhavn zu Fasanvej.
c) Die Exzentrizität von Marmorkirken.
d) Den Durchmesser von ${}G$. Zwischen welchen Stationen wird er angenommen?
e) Den Radius von ${}G$. In welcher Station ist dies die Exzentrizität?
f) Den Grad von Frederiksberg.
g) Die Taille von ${}G$.
h) Den Umfang von ${}G$.

Lösung erstellen

Aufgabe (1 Punkt)

Man gebe ein Beispiel für einen Graphen ${}(V,E)$, der kein Baum ist, und dessen Knotenanzahl um ${}1$ größer als seine Kantenanzahl ist.

Lösung

Nach Satz 20.22 (Diskrete Mathematik (Osnabrück 2026)) darf ein solcher Graph nicht zusammenhängend sein, so erfüllt z. B. der vollständige Graph auf ${}3$ Knoten zusammen mit einem isolierten Punkt die gesuchte Eigenschaft.

Aufgabe (3 Punkte)

Das mathematische Institut plant das nächste Semester. Am Dienstag sollen zu den vier Zeiten ${}10-12,\,24-14,\,14-16,\,16-18$ die sechs Veranstaltungen Analysis, Lineare Algebra, diskrete Mathematik, algebraische Zahlentheorie, Singularitätentheorie und Chaostheorie untergebracht werden. Die ersten drei Kurse sind Bachelorkurse, die letzten drei Kurse sind Masterkurse, und die sollen nicht parallel stattfinden. Ferner wird diskrete Mathematik und algebraische Zahlentheorie vom gleichen Dozenten gehalten, und auch die lineare Algebra darf sich nicht mit der algebraischen Zahlentheorie überschneiden. Welches graphentheoretische Thema liegt diesem Problem zugrunde? Wie viele Möglichkeiten gibt es, die Veranstaltungen unter Berücksichtigung der beschriebenen Anforderungen aufzuteilen?

Lösung

Es handelt sich um ein Färbungsproblem, die vier Zeiten repräsentieren vier Farben, und die Ausschließungsbedingungen sind Kanten auf der sechselementigen Menge der Fächer.

Es gibt ${}4$ Möglichkeiten, die algebraische Zahlentheorie zu platzieren. Wenn dies fixiert ist, so kann man auf  ${}3\cdot 2=6$  verschiedene Arten die beiden anderen Masterkurse platzieren. Ebenso gibt es dann ${}6$ Möglichkeiten, die diskrete Mathematik und die lineare Algebra zu platzieren. Für die Analysis gibt es dann ${}2$ Möglichkeiten. Insgesamt gibt es also

${}4\cdot 6\cdot 6\cdot 2=288\,$

Möglichkeiten.