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	${}\sum$
Punkte	3	3	6	0	0	0	0	0	0	2	3	0	0	0	0	0	0	0	0	17

Definiere die folgenden (kursiv gedruckten) Begriffe.

Eine Teilmenge ${}H\subseteq G$ ${}H\subseteq G$ heißt Untergruppe von ${}G$ ${}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$ .
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.
Geordnete Menge/Teilmenge/Supremum/Definition/Begriff/Inhalt
Ungerichteter Graph/Nachbarn/Definition/Begriff/Inhalt
Ungerichteter Graph/Zusammenhängend/Radius/Definition/Begriff/Inhalt
Graph/Knotenüberdeckung/Optimal/Definition/Begriff/Inhalt

Formuliere die folgenden Sätze.

Der Satz über die algebraische Struktur der Restklassenringe ${}R/{\mathfrak {a}}$ zu einem Ideal ${}{\mathfrak {a}}\subseteq R$ in einem kommutativen Ring ${}R$ .
Der Satz über den Zusammenhang von Graphen mit Blättern.
Der Vier-Farben-Satz.

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.
Es sei ${}G=(V,E)$ ein Graph und ${}b\in V$ ein Blatt des Graphen. Dann ist ${}G$ genau dann zusammenhängend, wenn ${}G\setminus b$ zusammenhängend ist.
Für jeden ebenen Graphen besteht eine zulässige Färbung mit höchstens vier Farben.

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

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

Das Minimum an Scheinen ist ${}1$ (ein Hunderter), das Maximum ist ${}20$ ( ${}20$ Fünfer).
Es ist
${}3\cdot 10+14\cdot 5=30+70=100\,,$

${}17$ Scheine sind also mit ${}3$ Zehnern und ${}14$ Fünfern möglich.
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.
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$ .

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

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.

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

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

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.
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.