Kurs:Diskrete Mathematik/8/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	8	5	0	2	0	6	7	0	0	0	0	0	0	0	0	7	46

Aufgabe (3 Punkte)

Definiere die folgenden (kursiv gedruckten) Begriffe.

1. Ein inverses Element zu einem Element ${}x\in M$ bezüglich einer Verknüpfung

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

   mit einem neutralen Element ${}e\in M$.

2. Eine lineare (oder totale) Ordnung ${}\preccurlyeq$ auf einer Menge ${}I$.
3. Verband/Distributiv/Definition/Begriff
4. Graph/Ungerichtet/Definition/Begriff
5. Matroid/Basis/Definition/Begriff
6. Ungerichteter Graph/Paarung/Alternierender Weg/Definition/Begriff

Lösung

1. Zu ${}x\in M$ heißt ${}y\in M$ inverses Element, wenn die Gleichheit

   ${}x\circ y=e=y\circ x\,$

   gilt.

2. Eine Ordnungsrelation ${}\preccurlyeq$ auf ${}I$ heißt lineare Ordnung, wenn zu je zwei Elementen ${}x,y\in I$ die Beziehung ${}x\preccurlyeq y$ oder ${}y\preccurlyeq x$ gilt.
3. Verband/Distributiv/Definition/Begriff/Inhalt
4. Graph/Ungerichtet/Definition/Begriff/Inhalt
5. Matroid/Basis/Definition/Begriff/Inhalt
6. Ungerichteter Graph/Paarung/Alternierender Weg/Definition/Begriff/Inhalt

Aufgabe (3 Punkte)

Formuliere die folgenden Sätze.

1. Der Satz über die Anzahl von Abbildungen zwischen endlichen Mengen.
2. Der Satz über die Nichtnullteilereigenschaft in einem Körper ${}K$.
3. Der Charakterisierungssatz für eulersche Graphen.

Lösung

1. Es seien ${}L$ und ${}M$ endliche Mengen mit ${}\ell$ bzw. ${}m$ Elementen. Dann gibt es ${}m^{\ell }$ Abbildungen von ${}L$ nach ${}M$.
2. Aus ${}a\cdot b=0$ mit ${}a,b\in K$ folgt ${}a=0$ oder ${}b=0$.
3. Für einen zusammenhängenden Graphen ${}G=(V,E)$ sind folgende Aussagen äquivalent.
   1. ${}G$ ist eulersch.
   2. Jeder Knotenpunkt von ${}G$ hat einen geraden Grad.
   3. ${}G$ ist die Vereinigung von kantendisjunkten Kreisen (wobei ein einzelner Punkt hier als Kreis gelte).

Aufgabe (5 Punkte)

Es sei ${}G$ eine Menge, die als disjunkte Vereinigung

${}G=A\uplus B\,$

gegeben ist. Definiere eine Bijektion zwischen der Potenzmenge ${}{\mathfrak {P}}\,(G)$ und der Produktmenge ${}{\mathfrak {P}}\,(A)\times {\mathfrak {P}}\,(B)$.

Lösung

Wir betrachten die Abbildungen

$\varphi \colon {\mathfrak {P}}\,(G)\longrightarrow {\mathfrak {P}}\,(A)\times {\mathfrak {P}}\,(B),\,T\longmapsto (T\cap A,T\cap B),$

und

$\psi \colon {\mathfrak {P}}\,(A)\times {\mathfrak {P}}\,(B)\longrightarrow {\mathfrak {P}}\,(G),\,(U,V)\longmapsto U\cup V,$

und behaupten, dass diese beiden Abbildungen zueinander invers sind. Die Verknüpfung ${}\psi \circ \varphi$ sendet insgesamt eine Teilmenge ${}T\subseteq G$ auf

$(T\cap A)\cup (T\cap B).$

Die Inklusion

${}(T\cap A)\cup (T\cap B)\subseteq T\,$

ist dabei klar. Wenn umgekehrt ${}x\in T$ liegt, so ist aufgrund der Voraussetzung ${}x\in A$ oder ${}x\in B$ und damit ist auch ${}x\in (T\cap A)\cup (T\cap B)$. Daher ist ${}\psi \circ \varphi$ die Identität.

Die Verknüpfung ${}\varphi \circ \psi$ sendet insgesamt ein Paar ${}(U,V)$ bestehend aus Teilmengen ${}U\subseteq A$ und ${}V\subseteq B$ auf

$((U\cup V)\cap A,(U\cup V)\cap B).$

Wir behaupten

${}(U\cup V)\cap A=U\,$

(und entsprechend für die zweite Komponente). Dabei ist die Inklusion ${}\supseteq$ klar. Wenn umgekehrt ${}x\in (U\cup V)\cap A$ ist, so ist ${}x\in A$ und ${}x\in U\cup V$. Wegen ${}V\subseteq B$ und der Disjunktheit von ${}B$ und ${}A$ kann nicht ${}x$ zu ${}V$ gehören, also ist ${}x\in U$. Daher ist auch ${}\varphi \circ \psi$ die Identität.

Aufgabe (8 (1+1+1+3+2) Punkte)

Zur großen Pause fährt der Eiswagen „Largo Maggiore“ auf den Pausenhof. Eisverkäufer Lorenzo di Napoli bietet ${}10$ Eissorten an. Lucy Sonnenschein hat heute Lust auf ein Eis mit drei Kugeln, die in der Eistüte übereinander gestapelt werden.

1. Wie viele Möglichkeiten gibt es für diesen Eiskauf, wenn Lucy drei verschiedene Sorten möchte und die Schleckreihenfolge mitberücksichtigt wird?
2. Wie viele Möglichkeiten gibt es für diesen Eiskauf, wenn Lucy drei verschiedene Sorten möchte und die Schleckreihenfolge nicht mitberücksichtigt wird?
3. Wie viele Möglichkeiten gibt es für diesen Eiskauf, wenn Sorten mehrfach auftreten dürfen und die Schleckreihenfolge mitberücksichtigt wird?
4. Wie viele Möglichkeiten gibt es für diesen Eiskauf, wenn Sorten mehrfach auftreten dürfen und die Schleckreihenfolge nicht mitberücksichtigt wird?
5. Wie kann man mit den Schritten mit denen man (4) beantwortet hat die Antworten zu (1) und zu (3) herleiten?

Lösung

1. Es gibt ${}10\cdot 9\cdot 8=720$ Möglichkeiten, da es für die erste Kugel ${}10$, für die nächste ${}9$, da diese von einer anderen Sorte als die erste sein muss, und für die dritte ${}8$ Möglichkeiten.
2. Es geht um die Anzahl der dreielementigen Teilmengen aus der zehnelementigen Eissortenmenge, also gibt es

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

   Möglichkeiten.

3. Für jede Kugel gibt es zehn Möglichkeiten, die Gesamtzahl ist also

   ${}10^{3}=1000\,.$

4. Wenn sie drei verschiedene Kugeln kauft, so sind das, wie unter (2) berechnet, ${}120$ Möglichkeiten. Wenn sie zwei verschiedene Kugeln kauft, so gibt es für die Auswahl der Sorten

   ${}{\binom {10}{2}}={\frac {10\cdot 9}{2\cdot 1}}=45\,$

   Möglichkeiten. Sodann muss man dabei aber noch festlegen, welche Sorte einmal und welche zweimal genommen wird. Daher gibt es hier ${}90$ Möglichkeiten. Wenn sie von einer Sorte drei Kugeln kauft, so gibt es dafür ${}10$ Möglichkeiten. Insgesamt gibt es also

   ${}120+90+10=220\,$

   Möglichkeiten.

5. Für die ${}120$ Möglichkeiten aus dem ersten Typ von (4) gibt es jeweils sechs Möglichkeiten, in welcher Reihenfolge sie aufgetürmt werden können, das macht die ${}720$ aus Teil (1). Für die ${}90$ Möglichkeiten aus dem zweiten Typ von (4) gibt es jeweils drei Möglichkeiten, in welcher Reihenfolge sie aufgetürmt werden können (an welcher Stelle kommen die einzelnen Kugeln?), das macht ${}270$ Möglichkeiten. Für den dritten Typ aus (4) ist die Reihenfolge unerheblich, es bleibt also bei den ${}10$ Möglichkeiten. Insgesamt ergeben sich so gerechnet

   ${}720+270+10=1000\,,$

   was dem Ergebnis aus Teil (3) entspricht.

Aufgabe (5 Punkte)

Es sei ${}K$ ein Körper und ${}a\in K$ ein beliebiges Element. Bestimme, welche Potenzen ${}a^{n}$ man (ausgehend von ${}a$ und bei optimaler Verwertung von Zwischenschritten) mit einer, zwei, drei oder vier Multiplikationen erhalten kann.

Lösung

Wir gehen rekursiv vor, da jede Potenz sich durch Multiplikation einer zuvor erhaltenen Potenz ergibt. Wenn dabei die Faktoren gleiche Potenzen verwenden, müssen diese nicht doppelt gezählt werden, da man ja die Ergebnisse von Zwischenmultiplikationen wiederverwenden kann.

Mit einer Multiplikation kann man offenbar nur ${}a^{2}=a\cdot a$ erhalten.

Mit zwei Multiplikationen kann man

${}a^{3}=a\cdot a^{2}\,$

und

${}a^{4}=(a^{2})\cdot (a^{2})\,$

erhalten und sonst keine Potenz, da ja alle möglichen Multiplikationen notiert wurden.

Mit drei Multiplikationen kann man

${}a^{5}=(a^{4})\cdot a\,,$

${}a^{6}=(a^{4})\cdot (a^{2})\,,$

${}a^{8}=(a^{4})\cdot (a^{4})\,$

erhalten. ${}a^{7}$ kann man nicht mit drei Multiplikationen erreichen, da in (dem einzigen ernsthaften Kandidat) ${}(a^{3})\cdot (a^{4})$ schon vier Multiplikationen drin sind.

Mit vier Multiplikationen kann man

${}a^{7}=(a^{6})\cdot a\,,$

${}a^{9}=(a^{8})\cdot a\,,$

${}a^{10}=(a^{8})\cdot (a^{2})\,,$

${}a^{12}=(a^{8})\cdot (a^{4})\,$

und

${}a^{16}=(a^{8})\cdot (a^{8})\,$

erhalten. Weitere Möglichkeiten gibt es nicht. Wenn nämlich ${}a^{8}$ nicht als Faktor vorkommt, so gibt es von den noch nicht abgedeckten Potenzen nur ${}(a^{5})\cdot (a^{6})$, doch dieser Aufbau braucht fünf Multiplikationen.

Aufgabe (0 Punkte)

Lösung /Aufgabe/Lösung

Aufgabe (2 Punkte)

Beweise den Satz über das inverse Element in einer Gruppe ${}(G,\circ ,e)$.

Lösung

Es sei

${}x\circ y=y\circ x=e\,$

und

${}x\circ z=z\circ x=e\,.$

Dann ist

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

Aufgabe (0 Punkte)

Lösung /Aufgabe/Lösung

Aufgabe (6 Punkte)

Beweise den Satz über die atomare Darstellung in einem booleschen Verband.

Lösung

Jedes Element ${}x\in B$ ist nur größergleich endlich vielen Atomen, wir führen zum Nachweis der Existenz Induktion über diese Anzahl. Bei ${}x=0$ nimmt man die leere Vereinigung. Ein Atom wird durch sich selbst dargestellt. Es sei ${}x\neq 0$ ein beliebiges Element. Nach Lemma 9.20 (Diskrete Mathematik (Osnabrück 2020))  (3) gibt es ein Atom ${}a\preccurlyeq x$. Wir betrachten

${}x'=x\sqcap \neg a\,.$

Wegen

${}x'\sqcap a=(x\sqcap \neg a)\sqcap a=x\sqcap (\neg a\sqcap a)=x\sqcap 0=0\,$

liegt ${}a$ nicht unterhalb von ${}x'$. Somit liegen unterhalb von ${}x'$ weniger Atome als unterhalb von ${}x$ und nach Induktionsvoraussetzung gibt es eine Darstellung

${}x'=a_{1}\sqcup \ldots \sqcup a_{n}\,$

und damit

${}{\begin{aligned}x&=x\sqcap 1\\&=x\sqcap (\neg a\sqcup a)\\&=(x\sqcap \neg a)\sqcup (x\sqcap a)\\&=(x\sqcap \neg a)\sqcup a\\&=x'\sqcup a\\&=a_{1}\sqcup \ldots \sqcup a_{n}\sqcup a.\end{aligned}}$

Zur Eindeutigkeit. Sei

${}a_{1}\sqcup \ldots \sqcup a_{n}=b_{1}\sqcup \ldots \sqcup b_{m}\,.$

Nehmen wir an, dass ${}b_{1}$ nicht in der ersten Darstellung vorkommt. Dann ist

${}{\left(a_{1}\sqcup \ldots \sqcup a_{n}\right)}\sqcap b_{1}=(a_{1}\sqcap b_{1})\sqcup \ldots \sqcup (a_{n}\sqcap b_{1})=0\,$

nach Lemma 9.20 (Diskrete Mathematik (Osnabrück 2020))  (2). Wenn man aber auf die rechte Seite ${}\sqcap b_{1}$ anwendet, so ergibt sich ${}b_{1}$, ein Widerspruch. Also kommen links und rechts die gleichen Atome vor.

Aufgabe (7 Punkte)

Es stehen zwei Eimer ohne Markierungen zur Verfügung, ferner eine Wasserquelle. Der eine Eimer hat ein Fassungsvermögen von ${}a$ und der andere ein Fassungsvermögen von ${}b$ Litern, wobei ${}a$ und ${}b$ teilerfremd seien. Zeige, dass man allein durch Auffüllungen, Ausleerungen und Umschüttungen erreichen kann, dass in einem Eimer genau ein Liter Wasser enthalten ist.

Lösung

Ohne Einschränkung sei ${}a\leq b$. Wir bezeichnen die Inhalte in den Eimern zu einem bestimmten Zeitpunkt in Paarschreibweise mit ${}(u,v)$, wobei ${}u$ zwischen ${}0$ und ${}a$ und ${}v$ zwischen ${}0$ und ${}b$ liegt. Es sei ${}r$ der Rest von ${}-b$ bei Division durch ${}a$. Wir behaupten, dass wenn man die Belegung ${}(u,0)$ durch die erlaubten Schritte erzielen kann, dass man dann auch ${}(u',0)$ erzielen kann, wobei ${}u'$ den Rest von ${}u+r$ modulo ${}a$ bezeichnet. Wir starten also mit

$(u,0).$

Durch Umschüttung kann man

$(0,u)$

erreichen. Durch Auffüllen des kleinen Eimers und anschließende Umfüllung in den großen kann man

$(0,u+a)$

erreichen, und ebenso der Reihe nach

$(0,u+2a),\,(0,u+2a),\ldots ,(0,u+ka),$

wobei ${}k$ so gewählt sei, dass

${}u+ka\leq b\,$

und

${}u+(k+1)a>b\,$

sei. Von hier aus erreichen wir

$(a,u+ka).$

Wir füllen nun den Inhalt des ersten Eimers in den zweiten, bis dieser voll ist. Es sei ${}m$ die umgefüllte Menge. Diese erfüllt

${}u+ka+m=b\,.$

Die im ersten Eimer verbleibende Wassermenge ist somit

${}a-m=a-(b-u-ka)=u+(k+1)a-b\,.$

Diese Menge ist also der Rest von ${}u-b=u+r$ modulo ${}a$, wie behauptet.

Aufgrund von dieser Beobachtung können wir der Reihe nach folgende Belegungen erzielen (bzw. die Reste davon modulo a).

$(0,0),(r,0),(2r,0),(3r,0),\ldots .$

Da ${}b$ teilerfremd zu ${}a$ ist, gibt es nach dem Lemma von Bezout positive ganze Zahlen ${}n,m$ mit

${}ma-nb=1\,$

(Falls ${}n,m$ negativ sind, betrachtet man einfach ${}(sb+m)a-(sa+n)b=1$ für ein ausreichend großes ${}s$).

Somit ist modulo ${}a$

${}nr\equiv -nb=1-ma=1\,,$

sodass bei Division durch ${}a$ für ein gewisses ${}n$ der Rest von ${}nr$ gleich ${}1$ ist.

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 (0 Punkte)

Lösung /Aufgabe/Lösung

Aufgabe (0 Punkte)

Lösung /Aufgabe/Lösung

Aufgabe (0 Punkte)

Lösung /Aufgabe/Lösung

Aufgabe (7 Punkte)

Beweise die eulersche Polyederformel.

Lösung

Wir führen Induktion über die Anzahl ${}g$ der Gebiete. Bei ${}g=1$ liegt ein Baum vor und nach Satz 17.22 (Diskrete Mathematik (Osnabrück 2020)) ist

${}n-m+1=n-(n-1)+1=2\,.$

Es sei die Aussage nun für einen jeden planaren Graphen mit ${}g$ Gebieten bewiesen und sei ${}G$ ein zusammenhängender planarer Graph mit ${}g+1$ Gebieten. Es ist dann ${}G$ kein Baum und besitzt daher einen Zykel und damit auch einen Kreis, sagen wir ${}v_{1}\sim v_{2}\sim \ldots \sim v_{r}$. Bei der Herausnahme der Kante ${}v_{1}v_{2}$ bleibt der Graph zusammenhängend und planar. Die Anzahl der Knoten bleibt gleich, die Anzahl der Kanten reduziert sich um ${}1$ und die beiden durch die Kante ${}v_{1}v_{2}$ begrenzten Gebiete werden zu einem Gebiet vereinigt, die anderen Gebiete ändern sich nicht. Insgesamt reduziert sich also die Anzahl der Gebiete um ${}1$. Da die Anzahl der Kanten und der Gebiete mit unterschiedlichem Vorzeichen in die Wechselsumme eingeht, ändert sich diese bei Herausnahme der Kante nicht. Nach Induktionsvoraussetzung ist die Wechselsumme des reduzierten Graphen gleich ${}2$, deshalb ist die Wechselsumme von ${}G$ ebenfalls gleich ${}2$.