Kurs:Diskrete Mathematik/19/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	4	0	0	4	0	0	6	0	0	3	0	5	0	0	0	0	0	28

Aufgabe (3 Punkte)

Definiere die folgenden (kursiv gedruckten) Begriffe.

1. Eine kommutative Gruppe.
2. Die Transitivität einer Relation ${}R$ auf einer Menge ${}M$.
3. Ein Ringhomomorphismus

   $\varphi \colon R\longrightarrow S$

   zwischen Ringen ${}R$ und ${}S$.

4. Der Minimalgrad eines Graphen ${}G=(V,E)$.
5. Ungerichteter Graph/Zusammenhängend/Punkte/Abstand/Definition/Begriff
6. Ungerichter Graph/Perfekte Paarung/Definition/Begriff

Lösung

1. Eine Gruppe ${}(G,\circ ,e)$ heißt kommutativ, wenn

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

   für alle ${}x,y\in G$ gilt.

2. Die Relation ${}R$ heißt transitiv, wenn aus ${}xRy$ und ${}yRz$ stets ${}xRz$ folgt.
3. Die Abbildung

   $\varphi \colon R\longrightarrow S$

   heißt Ringhomomorphismus, wenn folgende Eigenschaften gelten:

   1. ${}\varphi (a+b)=\varphi (a)+\varphi (b)$
   2. ${}\varphi (1)=1$
   3. ${}\varphi (a\cdot b)=\varphi (a)\cdot \varphi (b)$.
4. Ungerichteter Graph/Minimalgrad/Definition/Begriff/Inhalt
5. Ungerichteter Graph/Zusammenhängend/Punkte/Abstand/Definition/Begriff/Inhalt
6. Ungerichter Graph/Perfekte Paarung/Definition/Begriff/Inhalt

Aufgabe (3 Punkte)

Formuliere die folgenden Sätze.

1. /Fakt/Name
2. /Fakt/Name
3. /Fakt/Name

Lösung

1. /Fakt
2. /Fakt
3. /Fakt

Aufgabe (4 (1+3) Punkte)

In einer Höhle befinden sich im Innern am Ende des Ganges vier Personen. Sie haben eine Taschenlampe bei sich und der Gang kann nur mit der Taschenlampe begangen werden. Dabei können höchstens zwei Leute gemeinsam durch den Gang gehen. Die Personen sind unterschiedlich geschickt, die erste Person benötigt eine Stunde, die zweite Person benötigt zwei Stunden, die dritte Person benötigt vier Stunden und die vierte Person benötigt fünf Stunden, um den Gang zu durchlaufen. Wenn zwei Personen gleichzeitig gehen, entscheidet die langsamere Person über die Geschwindigkeit.

1. Die Batterie für die Taschenlampe reicht für genau ${}13$ Stunden. Können alle vier die Höhle verlassen?
2. Die Batterie für die Taschenlampe reicht für genau ${}12$ Stunden. Können alle vier die Höhle verlassen?

Lösung Höhle/Taschenlampe/Aufgabe/Lösung

Aufgabe (0 Punkte)

Lösung /Aufgabe/Lösung

Aufgabe (0 Punkte)

Lösung /Aufgabe/Lösung

Aufgabe (4 Punkte)

Mustafa Müller schreibt die natürlichen Zahlen

$0,1,2,3,\ldots ,998,999,1000$

hintereinander auf. Wie oft kommt dabei die Ziffern ${}0,1,2,\ldots ,9$ vor? Wie viele Kommata setzt er?

Lösung

Er setzt ${}1000$ Kommata. Wir überlegen uns, wie die Anzahl der Ziffern ist, wenn er jede dreistellige Zifferenkombination ${}abc$ mit ${}a,b,c\in \{0,1,\ldots ,9\}$ hinschreiben würde. Davon gibt es ${}10^{3}=1000$ Möglichkeiten, die den hingeschriebenen Zahlen (bis auf die ${}1000$) entsprechen, wenn man die Zahlen vorne durch Nullen auffüllt. Insgesamt kommen ${}3000$ Ziffern vor und jede Ziffer kommt gleich oft, also ${}300$ Mal vor. Deshalb kommen die Ziffern ${}2,3,\ldots ,9$ in der Mülleraufzählung ${}300$ hundert Mal vor und die ${}1$ kommt (wegen der ${}1000$) genau ${}301$ Mal vor. Die ${}0$ kommt aber in der Mülleraufzählung weniger oft vor, und zwar muss man ${}20$ Nullen für die einstelligen Zahlen und ${}90$ Nullen für die zweistelligen Zahlen abziehen. Deshalb kommt die ${}0$ in der Mülleraufzählung ${}300-20-90+3=193$ Mal vor.

Aufgabe (0 Punkte)

Lösung /Aufgabe/Lösung

Aufgabe (0 Punkte)

Lösung /Aufgabe/Lösung

Aufgabe (6 Punkte)

Zeige, dass jede rationale Zahl ${}z\neq 0$ eine eindeutige Darstellung der Form

${}z=\pm \prod _{p}p^{\nu _{p}(z)}\,$

besitzt, wobei das (endliche) Produkt sich über Primzahlen erstreckt und die Exponenten ${}{\nu _{p}(z)}\in \mathbb {Z}$ sind.

Lösung

Zum Beweis der Existenz sei

${}z={\frac {a}{b}}\,$

mit ${}a\in \mathbb {Z} \setminus \{0\}$ (sonst wäre die Zahl gleich ${}0$) und ${}b\in \mathbb {N} _{+}$. Wir schreiben die Zahlen in ihrer Primfaktorzerlegung, also

${}a=\pm \prod _{p}p^{\nu _{p}(a)}\,$

und

${}b=\prod _{p}p^{\nu _{p}(b)}\,,$

wobei wir annehmen dürfen, dass sich beide Produkte über die gleichen Primzahlen erstrecken (und manche Exponenten gleich ${}0$ sind). Dann ist unter der Verwendung von Potenzgesetzen

${}{\begin{aligned}z&={\frac {a}{b}}\\&={\frac {\pm \prod _{p}p^{\nu _{p}(a)}}{\prod _{p}p^{\nu _{p}(b)}}}\\&=\pm {\left(\prod _{p}p^{\nu _{p}(a)}\right)}{\left(\prod _{p}p^{\nu _{p}(b)}\right)}^{-1}\\&=\pm {\left(\prod _{p}p^{\nu _{p}(a)}\right)}{\left(\prod _{p}p^{-{\nu _{p}(b)}}\right)}\\&=\pm \prod _{p}p^{{\nu _{p}(a)}-{\nu _{p}(b)}}\end{aligned}}$

mit ${}{\nu _{p}(a)}-{\nu _{p}(b)}\in \mathbb {Z}$. Zum Beweis der Eindeutigkeit sei

${}\pm \prod _{p}p^{r_{p}}=\pm \prod _{p}p^{s_{p}}\,$

mit ${}r_{p},s_{p}\in \mathbb {Z}$, wobei wir annehmen können, dass sich die Produkte über die gleiche endliche Menge von Primzahlen erstrecken. Das Vorzeichen muss links und rechts gleich sein, da eine negative rationale Zahl nicht mit einer positiven rationalen Zahl übereinstimmen kann. Wir können also annehmen, dass zwei positive Zahlen vorliegen. Wenn ein Exponent ${}r_{p}$ negativ ist, so können wir mit ${}p^{-r_{p}}$ beidseitig multiplizieren und erhalten so letztlich eine Gleichheit, in der nur noch nichtnegative Exponenten vorkommen und somit positive natürliche Zahlen dastehen. Der Hauptsatz der elementaren Zahlentheorie ergibt, dass dann die Exponenten übereinstimmen müssen. Wegen der Abziehregel müssen auch die ursprünglichen Exponenten gleich gewesen sein.

Aufgabe (0 Punkte)

Lösung /Aufgabe/Lösung

Aufgabe (0 Punkte)

Lösung /Aufgabe/Lösung

Aufgabe (3 Punkte)

Beweise die universelle Eigenschaft der Quotientenmenge zu einer Äquivalenzrelation.

Lösung

Sei ${}[x]\in M/\sim$ gegeben. Die einzige Möglichkeit für ${}{\overline {\varphi }}$ ist ${}{\overline {\varphi }}([x]):=\varphi (x)$ zu setzen. Es muss aber gezeigt werden, dass diese Abbildung überhaupt wohldefiniert ist, also unabhängig von der Wahl des Repräsentanten ist. Es sei hierzu ${}[x]=[y]$, also ${}x\sim y$. Dann ist nach der Voraussetzung an ${}\varphi$ aber ${}\varphi (x)=\varphi (y)$.

Aufgabe (0 Punkte)

Lösung /Aufgabe/Lösung

Aufgabe (5 Punkte)

Beweise den Satz über die algebraische Struktur der Restklassenringe ${}R/{\mathfrak {a}}$ zu einem Ideal ${}{\mathfrak {a}}\subseteq R$ in einem kommutativen Ring ${}R$.

Lösung

Nach Satz 12.5 (Diskrete Mathematik (Osnabrück 2020)) gibt es nur eine Gruppenstruktur auf ${}R/{\mathfrak {a}}$ derart, dass die kanonische Abbildung ein Gruppenhomomorphismus ist. Da ein Ringhomomorphismus insbesondere ein Gruppenhomomorphismus bezüglich der Addition ist, ist dies die einzige additive Struktur, die in Frage kommt.

Da die kanonische Abbildung die Multiplikation respektieren soll, kommt nur ${}{\overline {1}}\,$ als neutrales Element der Multiplikation und

${}{\overline {a}}\,{\overline {b}}\,={\overline {ab}}\,\,$

als Multiplikation in Frage. Wir müssen zeigen, dass diese Multiplikation wohldefiniert ist. Es seien zwei Restklassen mit unterschiedlichen Repräsentanten gegeben, also ${}{\overline {a}}\,={\overline {a'}}\,$ und ${}{\overline {b}}\,={\overline {b'}}\,$. Dann ist ${}a-a'\in {\mathfrak {a}}$ und ${}b-b'\in {\mathfrak {a}}$ bzw. ${}a'=a+x$ und ${}b'=b+y$ mit ${}x,y\in {\mathfrak {a}}$. Daraus ergibt sich

${}a'b'=(a+x)(b+y)=ab+ay+xb+xy\,.$

Die drei hinteren Summanden gehören zum Ideal, so dass die Differenz ${}a'b'-ab\in {\mathfrak {a}}$ ist.

Aus der Wohldefiniertheit folgen die anderen Eigenschaften und insbesondere, dass ein Ringhomomorphismus in den Restklassenring vorliegt.

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