Kurs:Diskrete Mathematik/24/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	2	3	6	2	3	5	2	2	3	6	2	5	5	3	4	4	1	64

Aufgabe (3 Punkte)

Definiere die folgenden (kursiv gedruckten) Begriffe.

1. Die Assoziativität einer Verknüpfung

   $\circ \colon M\times M\longrightarrow M,\,(x,y)\longmapsto x\circ y.$

2. Eine Ordnungsrelation ${}\preccurlyeq$ auf einer Menge ${}I$.
3. Die Äquivalenzklasse zu einem Element ${}x\in M$ in einer Menge ${}M$ mit einer Äquivalenzrelation ${}\sim$.
4. Ein Automorphismus eines Graphen  ${}G=(V,E)$. 
5. Das charakteristische Polynom zu einem Graphen ${}G$.
6. Ein Hamiltonkreis in einem Graphen ${}(V,E)$.

Lösung

1. Eine Verknüpfung

   $\circ \colon M\times M\longrightarrow M,\,(x,y)\longmapsto x\circ y,$

   heißt assoziativ, wenn für alle ${}x,y,z\in M$ die Gleichheit

   ${}(x\circ y)\circ z=x\circ (y\circ z)\,$

   gilt.

2. Die Relation ${}\preccurlyeq$ heißt Ordnungsrelation, wenn folgende drei Bedingungen erfüllt sind.
   1. Es ist ${}i\preccurlyeq i$ für alle ${}i\in I$.
   2. Aus ${}i\preccurlyeq j$ und ${}j\preccurlyeq k$ folgt stets ${}i\preccurlyeq k$.
   3. Aus ${}i\preccurlyeq j$ und ${}j\preccurlyeq i$ folgt ${}i=j$.
3. Die Äquivalenzklasse zu ${}x$ ist die Menge

   ${}[x]=\left\{y\in M\mid y\sim x\right\}\,.$

4. Ein Automorphismus ist ein Isomorphismus ${}\varphi \colon G\rightarrow G$.
5. Das charakteristische Polynom von ${}G$ ist das charakteristische Polynom der Adjazenzmatrix von ${}G$.
6. Ein Hamiltonkreis ist ein Kreis, in dem jeder Knotenpunkt vorkommt.

Aufgabe (3 Punkte)

Formuliere die folgenden Sätze.

1. Der Satz über das asymptotische Verhalten von fixpunktfreien Permutationen.
2. Die Rekursionsformel für die Stirling-Zahlen zweiter Art.
3. Die eulersche Polyederformel.

Lösung

1. Die Wahrscheinlichkeit ${}w(n)$, dass eine Permutation auf einer ${}n$-elementigen Menge fixpunktfrei ist, konvergiert für ${}n\rightarrow \infty$ gegen ${}e^{-1}$.
2. Die Stirling-Zahlen zweiter Art erfüllen die Rekursionsformel

   ${}S({n+1},{k})=k\cdot S({n},{k})+S({n},{k-1})\,.$

3. Es sei ${}G$ ein zusammenhängender planarer Graph mit ${}n$ Knotenpunkten, ${}m$ Kanten und ${}g$ Gebieten. Dann gilt die eulersche Polyederformel

   ${}n-m+g=2\,.$

Aufgabe (2 Punkte)

Professor Knopfloch und Dr. Eisenbeis stehen am Ufer des Rubbenbruchsees und können sich nicht einigen, ob sie mit dem oder gegen den Uhrzeigersinn drumrum laufen sollen. Deshalb läuft Professor Knopfloch gegen den Uhrzeigersinn und Dr. Eisenbeis mit dem Uhrzeigersinn. Das Verhältnis ihrer Geschwindigkeiten ist ${}5:4$, und daher läuft Knopfloch fünfmal um den See und Eisenbeis viermal um den See. Wie oft begegnen sie sich (Begegnung ganz am Anfang und am Ende mitzählen)?

Lösung

Die erste Begegnung (nach der Begegnung am Start) findet statt, wenn Knopfloch ${}{\frac {5}{9}}$ und Eisenbeis ${}{\frac {4}{9}}$ des Sees umrundet haben. Dieser Rhythmus bleibt konstant, d.h. Eisenbeis begegnet Knopfloch stets nach einer Wegstrecke von ${}{\frac {4}{9}}$ des Seeumfanges. Da sie viermal den See umrundet, sind das insgesamt ${}10$ Begegnungen (${\frac {0}{9}},{\frac {4}{9}},{\frac {8}{9}},\ldots ,{\frac {36}{9}}$).

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

Die Fußballmannschaft des TSV Wildberg verfügt über drei Torwarte, sieben Verteidigungsspieler, sechs Mittelfeldspieler und vier Angreifer. Im anstehenden Spiel gegen Effringen will sie (neben einem Torwart) mit vier Verteidigern, drei Mittelfeldspielern und drei Angreifern agieren.

1. Wie viele Aufstellungsmöglichkeiten gibt es?
2. Wie viele Aufstellungsmöglichkeiten gibt es, wenn man zusätzlich noch berücksichtigt, dass einer der eingesetzten Spieler der Kapitän sein soll?
3. Wildberg geht in der ${}80.$ Minute mit ${}1:0$ in Führung und entschließt sich, die Verteidigung zu stärken, indem zwei Angreifer durch zwei Verteidiger ersetzt werden. Wie viele Auswechslungsmöglichkeiten gibt es dafür?

Lösung

1. Es gibt

   ${}{\begin{aligned}{\binom {3}{1}}{\binom {7}{4}}{\binom {6}{3}}{\binom {4}{3}}&=3\cdot {\frac {7\cdot 6\cdot 5}{3\cdot 2\cdot 1}}\cdot {\frac {6\cdot 5\cdot 4}{3\cdot 2\cdot 1}}\cdot 4\\&=3\cdot 35\cdot 20\cdot 4\\&=8400\end{aligned}}$

   Möglichkeiten, die Mannschaft aufzustellen.
2. Es gibt  ${}8400\cdot 11=92400$  Möglichkeiten, die Mannschaft aufzustellen und dabei einen Kapitän festzulegen.
3. Es sind drei Angreifer auf dem Platz und drei Verteidiger auf der Bank. Also gibt es

   ${}{\binom {3}{2}}{\binom {3}{2}}=9\,$

   Auswechselmöglichkeiten.

Aufgabe (6 Punkte)

Es sei ${}G$ eine Menge und es seien ${}A_{i}\subseteq G$, ${}i=1,\ldots ,n$, endliche Teilmengen. Für eine Teilmenge  ${}J\subseteq \{1,\ldots ,n\}$  sei

${}A_{J}=\bigcap _{i\in J}A_{i}\,.$

Beweise die Anzahlformel (Siebformel)

${}{\#\left(\bigcup _{i=1}^{n}A_{i}\right)}=\sum _{k=1}^{n}(-1)^{k+1}\left(\sum _{J\subseteq \{1,\ldots ,n\},\,{\#\left(J\right)}=k}{\#\left(A_{J}\right)}\right)\,.$

Lösung

Wir beweisen die Aussage durch Induktion über ${}n$, wobei der Fall  ${}n=1$  klar ist. Für  ${}n=2$  siehe Aufgabe 1.19 (Diskrete Mathematik (Osnabrück 2026)). Es ist

${}{\begin{aligned}{\#\left(\bigcup _{i=1}^{n+1}A_{i}\right)}&={\#\left(\left(\bigcup _{i=1}^{n}A_{i}\right)\cup A_{n+1}\right)}\\\\&={\#\left(\bigcup _{i=1}^{n}A_{i}\right)}+{\#\left(A_{n+1}\right)}-{\#\left(\left(\bigcup _{i=1}^{n}A_{i}\right)\cap A_{n+1}\right)}\\&=\sum _{k=1}^{n}(-1)^{k+1}\left(\sum _{J\subseteq \{1,\ldots ,n\},\,{\#\left(J\right)}=k}{\#\left(A_{J}\right)}\right)+{\#\left(A_{n+1}\right)}-{\#\left(\bigcup _{i=1}^{n}\left(A_{i}\cap A_{n+1}\right)\right)}\\&=\sum _{k=1}^{n}(-1)^{k+1}\left(\sum _{J\subseteq \{1,\ldots ,n\},\,{\#\left(J\right)}=k}{\#\left(A_{J}\right)}\right)+{\#\left(A_{n+1}\right)}-\sum _{\ell =1}^{n}(-1)^{\ell +1}\left(\sum _{L\subseteq \{1,\ldots ,n\},\,{\#\left(L\right)}=\ell }{\#\left(A_{L}\cap A_{n+1}\right)}\right)\\&=\sum _{k=1}^{n+1}(-1)^{k+1}\left(\sum _{J\subseteq \{1,\ldots ,n,n+1\},\,n+1\notin J,\,{\#\left(J\right)}=k}{\#\left(A_{J}\right)}\right)+\sum _{k=1}^{n+1}(-1)^{k+1}\left(\sum _{J\subseteq \{1,\ldots ,n,n+1\},\,{\#\left(J\right)}=k,\,n+1\in J}{\#\left(A_{J}\right)}\right)\\&=\sum _{k=1}^{n+1}(-1)^{k+1}\left(\sum _{J\subseteq \{1,\ldots ,n,n+1\},\,{\#\left(J\right)}=k}{\#\left(A_{J}\right)}\right),\,\end{aligned}}$

wobei wir für die zweite Gleichung den Fall von zwei Teilmengen und für die dritte und die vierte Gleichung die Induktionsvoraussetzung verwendet haben. Für die fünfte Gleichung führen wir hinten die Indexverschiebung  ${}k=\ell +1$  durch, und der mittlere Term wird in die rechte Summe integriert. Die sechste Gleichung ergibt sich von unten nach oben gelesen, wenn man die Teilmengen

${}J\subseteq \{1,\ldots ,n,n+1\}\,$

je nachdem aufspaltet, ob ${}n+1$ dazu gehört oder nicht.

Aufgabe (2 Punkte)

Skizziere möglichst viele wesentlich verschiedene Konfigurationen von fünf Geraden in der Ebene, die sich insgesamt in vier Schnittpunkten treffen.

Lösung

${}\,$

Aufgabe (3 Punkte)

Zeige, dass die Anzahl der Permutationen auf einer ${}n$-elementigen Menge, die ein voller Zyklus sind, gleich ${}(n-1)!$ ist.

Lösung

Es sei ${}\varphi$ ein voller Zyklus auf der ${}n$-elementigen Menge ${}M$, und sei  ${}x\in M$.  Dann ist  ${}\varphi (x)\neq x$,  andernfalls wäre der Zyklus durch ${}x$ einelementig. Weiter ist

${}\varphi ^{2}(x)\neq x,\varphi (x)\,,$

andernfalls wäre der Zyklus durch ${}x$ zweielementig. So ist stets für  ${}k<n$ 

${}\varphi ^{k}(x)\neq x,\varphi (x),\varphi ^{2}(x),\ldots ,\varphi ^{k-1}(x)\,,$

da andernfalls der Zyklus durch ${}x$ ${}k$-elementig wäre. Somit gibt es für ${}\varphi (x)$ genau ${}n-1$ mögliche Werte, für ${}\varphi ^{2}(x)$ gibt es ${}n-2$ mögliche Werte, u.s.w., und daher gibt es insgesamt

${}(n-1)!=(n-1)(n-2)\cdots 2\cdot 1\,$

volle Zyklen.

Aufgabe (5 Punkte)

Es sei ${}n$ eine fixierte natürliche Zahl und

${}M=\{1,\ldots ,n\}\,.$

Wir betrachten die beiden Verknüpfungen (Maximum und Minimum)

$M\times M\longrightarrow M,\,(a,b)\longmapsto \operatorname {max} (a,b),$

und

$M\times M\longrightarrow M,\,(a,b)\longmapsto \operatorname {min} (a,b).$

Zeige, dass ${}M$ mit diesen beiden Verknüpfungen (mit welchen neutralen Elementen?) ein kommutativer Halbring ist.

Lösung

Die Kommutativität und die Assoziativität der beiden Verknüpfungen sind klar. Das neutrale Element des Maximums ist die ${}1$ und das neutrale Element des Minimums ist ${}n$, da ja nur Elemente aus ${}\{1,\ldots ,n\}$ vorkommen. Es bleibt also noch das Distributivgesetz zu zeigen, welches bei den gegebenen Verknüpfungen (wir setzen das Maximum als Addition und das Minimum als Multiplikation an)

${}\operatorname {min} (a,\operatorname {max} (b,c))=\operatorname {max} (\operatorname {min} (a,b),\operatorname {min} (a,c))\,$

bedeutet. Dies beweisen wir durch eine Fallunterscheidung. Da die Situation in ${}b$ und ${}c$ symmetrisch ist, können wir  ${}b\leq c$  annehmen. Bei

${}a\leq b\leq c\,$

ergibt sich links ${}a$ und rechts ebenfalls  ${}\operatorname {max} (a,a)=a$.  Bei

${}b\leq a\leq c\,$

ergibt sich links

${}\operatorname {min} (a,\operatorname {max} (b,c))=\operatorname {min} (a,c)=a\,$

und rechts ebenfalls

${}\operatorname {max} (\operatorname {min} (a,b),\operatorname {min} (a,c))=\operatorname {max} (b,a)=a\,.$

Bei

${}b\leq c\leq a\,$

ergibt sich links

${}\operatorname {min} (a,\operatorname {max} (b,c))=\operatorname {min} (a,c)=c\,$

und rechts ebenfalls

${}\operatorname {max} (\operatorname {min} (a,b),\operatorname {min} (a,c))=\operatorname {max} (b,c)=c\,.$

Aufgabe (2 (1+1) Punkte)

Es seien ${}a,m,n$ natürliche Zahlen mit  ${}a\geq 1$. 

1. Bestimme ${}\operatorname {ggT} (a^{m},a^{n})$.
2. Bestimme ${}\operatorname {kgV} (a^{m},a^{n})$.

Lösung

Es sei

${}n\geq m\,.$

Dann ist

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

und somit ist ${}a^{m}$ ein Teiler von ${}a^{n}$. In einem solchen Fall ist der Teiler der größte gemeinsame Teiler und das Vielfache das kleinste gemeinsame Vielfache. Also ist

${}\operatorname {ggT} (a^{m},a^{n})=a^{m}\,$

und

${}\operatorname {kgV} (a^{m},a^{n})=a^{n}\,.$

Aufgabe (2 Punkte)

Bestimme für das Polynom

${}P=-6X^{9}-5X^{8}-4X^{7}+{\frac {1}{9}}X^{6}+X^{2}+X\,$

den Grad, den Leitkoeffizienten, den Leitterm und den Koeffizienten zu ${}X^{6}$.

Lösung

Der Grad ist ${}9$, der Leitkoeffizient ist ${}-6$, der Leitterm ist ${}-6X^{9}$ und der Koeffizient zu ${}X^{6}$ ist ${}{\frac {1}{9}}$.

Aufgabe (3 Punkte)

Zeige, dass die folgende Relation eine Äquivalenzrelation auf ${}\mathbb {Z}$ ist:

$x\sim y,{\text{ falls }}6{\text{ ein Teiler von }}x-y{\text{ ist}}.$

Lösung

Es ist ${}6$ ein Teiler von

${}0=x-x\,,$

daher ist  ${}x\sim x$,  was die Reflexivität bedeutet. Sei  ${}x\sim y$.  Dies bedeutet, dass ${}6$ ein Teiler von ${}x-y$ ist, was wiederum bedeutet, dass

${}x-y=6\cdot c\,$

mit einem gewissen  ${}c\in \mathbb {Z}$  ist. Durch Multiplikation mit ${}-1$ erhält man

${}y-x=-(x-y)=6\cdot (-c)\,.$

Also ist ${}6$ auch ein Teiler von ${}y-x$ und somit ist  ${}y\sim x$,  was insgesamt die Symmetrie bedeutet. Zum Nachweis der Transitivität seien schließlich  ${}x\sim y$  und  ${}y\sim z$.  Somit ist

${}x-y=6c\,$

und

${}y-z=6d\,$

mit gewissen  ${}c,d\in \mathbb {Z}$.  Insgesamt ergibt sich

${}x-z=(x-y)+(y-z)=6c+6d=6(c+d)\,,$

sodass auch ${}x-z$ ein Vielfaches von ${}6$ ist. Also ist  ${}x\sim z$. 

Aufgabe (6 (3+3) Punkte)

Es sei ${}K$ ein Körper und sei

${}M=\left\{{\begin{pmatrix}a&b\\c&d\end{pmatrix}}\mid a,b,c,d\in K,\,ad-bc\neq 0\right\}\,$

die Menge aller invertierbaren ${}2\times 2$-Matrizen.

a) Zeige (ohne Bezug zur Determinante), dass ${}M$ mit der Matrizenmultiplikation eine Gruppe bildet.

b) Zeige (ohne Bezug zur Determinante), dass die Abbildung

$M\longrightarrow K^{\times },\,{\begin{pmatrix}a&b\\c&d\end{pmatrix}}\longmapsto ad-bc,$

ein Gruppenhomomorphismus ist.

Lösung erstellen

Aufgabe (2 Punkte)

Zeige, dass es keinen Ringhomomorphismus von ${}{\mathbb {C} }$ nach ${}\mathbb {R}$ gibt.

Lösung

Nehmen wir an, dass es einen Ringhomomorphismus

$\varphi \colon {\mathbb {C} }\longrightarrow \mathbb {R}$

gebe. Dann wäre

${}\varphi ({\mathrm {i} })\cdot \varphi ({\mathrm {i} })=\varphi ({\mathrm {i} }\cdot {\mathrm {i} })=\varphi (-1)=-1\,.$

In ${}\mathbb {R}$ sind aber alle Quadrate positiv und ${}-1$ besitzt keine Quadratwurzel, sodass ein Widerspruch vorliegt.

Aufgabe (5 Punkte)

Es sei ${}M$ eine endliche Menge und ${}\sigma$ eine Permutation auf ${}M$. Zeige, dass es eine Darstellung

${}\sigma =\sigma _{1}\cdots \sigma _{k}\,$

gibt, wobei die ${}\sigma _{i}$ Zyklen der Ordnung ${}\geq 2$ sind mit disjunkten Wirkungsbereichen.

Lösung

Es sei ${}F$ die Fixpunktmenge von ${}\sigma$ und es seien ${}Z_{1},\ldots ,Z_{k}$ diejenigen Teilmengen von ${}M$ mit mindestens zwei Elementen derart, dass ${}\sigma$ die Elemente aus jedem ${}Z_{i}$ zyklisch vertauscht. Dann ist ${}M$ die disjunkte Vereinigung aus ${}F$ und den ${}Z_{i}$. Zu ${}i$, ${}1\leq i\leq k$, sei ${}\sigma _{i}$ der Zyklus auf ${}M$, der auf ${}M\setminus Z_{i}$ die Identität ist und auf ${}Z_{i}$ mit ${}\sigma$ übereinstimmt. Wir behaupten

${}\sigma =\sigma _{1}\cdots \sigma _{k}\,.$

Um dies einzusehen, sei  ${}x\in M$  beliebig. Bei  ${}x\in F$  ist ${}x$ ein Fixpunkt für alle ${}\sigma _{i}$ und daher kommt links und rechts wieder ${}x$ raus. Es sei also ${}x$ kein Fixpunkt der Permutation. Dann gehört  ${}x\in Z_{i}$  für genau ein ${}i$. Für alle ${}j\neq i$ ist ${}x$ ein Fixpunkt von ${}\sigma _{j}$. Da

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

ebenfalls zu ${}Z_{i}$ gehört, ist auch ${}y$ ein Fixpunkt von ${}\sigma _{j}$ für alle  ${}j\neq i$.  Wendet man daher die rechte Seite auf ${}x$ an, so wird ${}x$ auf ${}x$ abgebildet bis man zu ${}\sigma _{i}$ kommt. Dieses bildet ${}x$ auf ${}y$ ab und die folgenden ${}\sigma _{j}$ bilden ${}y$ auf ${}y$ ab, sodass die rechte Seite insgesamt ${}x$ auf ${}y$ schickt und daher mit ${}\sigma$ übereinstimmt.

Aufgabe (5 (3+2) Punkte)

Zu  ${}n\in \mathbb {N}$  sei ${}f(n)$ der minimale Eurobetrag, für den man mindestens ${}n$ Euromünzen/Scheine braucht, um diesen Betrag zu begleichen.

1. Erstelle eine Tabelle, aus der die Werte für ${}f(n)$ ablesbar sind!
2. Was ist ${}f(1000000)$?

Lösung

1. Gemäß Aufgabe 17.6 (Diskrete Mathematik (Osnabrück 2026)) ist die minimale Darstellung einer Zahl mit den Eurozahlen eindeutig, man erhält sie, indem man rekursiv die größtmöglichen Scheine/Münzen einsetzt. Damit gelangt man zu folgender Tabelle.

   ${}n$

   ${}0$

   ${}1$

   ${}2$

   ${}3$

   ${}4$

   ${}5$

   ${}6$

   ${}7$

   ${}8$

   ${}9$

   ${}10$

   ${}11$

   ${}f(n)$

   ${}0$

   ${}1$

   ${}3$

   ${}8$

   ${}18$

   ${}38$

   ${}88$

   ${}188$

   ${}388$

   ${}888$

   ${}1388$

   ${}1888$

   Für alle weiteren ${}n$ muss man ${}500$ dazuaddieren.

2. Es ist

   ${}f(1000000)=1388+999990\cdot 500=1388+499995000=499996388\,.$

Aufgabe (3 Punkte)

Bestimme die erzeugende Funktion zur Folge der Fibonacci-Zahlen.

Lösung

Es sei ${}f_{n}$ die ${}n$-te Fibonacci-Zahl. Nach Satz 17.12 (Diskrete Mathematik (Osnabrück 2026)) wissen wir, dass es eine rationale Darstellung

${}\sum _{n=0}f_{0}t^{n}={\frac {P(t)}{1-t-t^{2}}}\,$

mit einem Polynom ${}P(t)$ maximal vom Grad ${}1$ geben muss. Aus der Identität

${}\left(t+t^{2}+2t^{3}+\ldots \right)\left(1-t-t^{2}\right)=t+\dots =P(t)\,$

folgt direkt  ${}P(t)=t$,  die erzeugende Funktion ist also ${}{\frac {t}{1-t-t^{2}}}$.

Aufgabe (4 Punkte)

Man erläutere grundlegende graphentheoretische Konzepte anhand der Osnabrücker U-Bahn!

Lösung erstellen

Aufgabe (4 Punkte)

Zeige, dass ein gerichteter Graph auf der Menge ${}M$ genau dann symmetrisch ist, wenn für jede Teilmenge  ${}T\subseteq M$  die Beziehung

${}T\subseteq M\setminus \operatorname {Vorg} \left(M\setminus \operatorname {Vorg} \left(T\right)\right)\,$

gilt.

Lösung

Wir zeigen, dass die Negationen der beiden Eigenschaften zueinander äquivalent sind.

Es sei zuerst die Relation nicht symmetrisch. Dann gibt es ${}x,y$ mit ${}xRy$, aber ${}yRx$ gilt nicht. Dann ist ${}y$ kein Vorgänger von ${}x$ und daher ist  ${}y\in M\setminus \operatorname {Vorg} \left(\{x\}\right)$.  Es ist somit  ${}x\in \operatorname {Vorg} \left(M\setminus \operatorname {Vorg} \left(\{x\}\right)\right)$  und also  ${}x\notin M\setminus \operatorname {Vorg} \left(M\setminus \operatorname {Vorg} \left(\{x\}\right)\right)$.  Daher gilt die Vorgängereigenschaft für

${}T=\{x\}\,$

nicht.

Es sei nun die Vorgängereigenschaft nicht erfüllt, es gebe also eine Teilmenge  ${}T\subseteq M$  mit

${}T\not \subseteq M\setminus \operatorname {Vorg} \left(M\setminus \operatorname {Vorg} \left(T\right)\right)\,.$

Dann gibt es ein  ${}x\in T$  mit  ${}x\in \operatorname {Vorg} \left(M\setminus \operatorname {Vorg} \left(T\right)\right)$.  Dies bedeutet, dass es ein  ${}y\in M\setminus \operatorname {Vorg} \left(T\right)$  mit ${}xRy$ gibt. Wegen  ${}y\notin \operatorname {Vorg} \left(T\right)$  ist insbesondere nicht ${}yRx$, also ist die Relation nicht symmetrisch.

Aufgabe (1 Punkt)

Man gebe ein Beispiel für eine maximale Paarung in einem Graphen ${}G$, die nicht optimal ist.

Lösung