Kurs:Diskrete Mathematik/21/Klausur

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

Aufgabe * (3 Punkte)

Definiere die folgenden (kursiv gedruckten) Begriffe.

1. Ein Körper ${}K$.
2. Die Antisymmetrie einer Relation ${}R$ auf einer Menge ${}M$.
3. Die Bellzahl ${}B_{n}$.
4. Der Bildgraph zu einer Abbildung ${}\varphi \colon V\rightarrow M$ in eine Menge ${}M$, wobei  ${}G=(V,E)$  einen Graphen bezeichnet.
5. Ein aufspannender Baum eines Graphen  ${}G=(V,E)$. 
6. Der Rang eines Matroids ${}{\mathcal {M}}$.

Aufgabe * (3 Punkte)

Formuliere die folgenden Sätze.

1. Das Lemma von Bézout für teilerfremde natürliche Zahlen ${}a$ und ${}b$.
2. Der Satz über die Anzahl der surjektiven Abbildungen mit Hilfe von Multinomialkoeffizienten.
3. Der Satz über den Zusammenhang von Graphen mit Blättern.

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

Professor Knopfloch war schwimmen. Beim Auswringen seiner Badehose hat er sich ungeschickt angestellt und sich dabei drei Finger verstaucht (er besitzt noch alle zehn Finger).

1. Wie viele Möglichkeiten für die verstauchten Finger gibt es?
2. Wie viele Möglichkeiten gibt es, wenn man weiß, dass genau ein Daumen verstaucht wurde?
3. Wie viele Möglichkeiten gibt es, wenn man weiß, dass genau ein Daumen verstaucht wurde und beide Hände betroffen sind?

Aufgabe * (3 Punkte)

In einem Hörsaal befindet sich ein Tafelgestell mit drei hintereinander liegenden, vertikal verschiebbaren Tafeln. Diese seien mit ${}V$ (vordere Tafel), ${}M$ (mittlere Tafel) und ${}H$ (hintere Tafel) bezeichnet. Aufgrund der Höhe des Gestells sind nur (maximal) zwei Tafeln gleichzeitig einsehbar. Die Lehrperson schreibt in der Vorlesung jede Tafel genau einmal voll. In welcher Reihenfolge (alle Möglichkeiten!) muss sie die Tafeln einsetzen, wenn beim Beschreiben einer Tafel stets die zuletzt beschriebene Tafel sichtbar sein soll?

Aufgabe * (2 Punkte)

Beweise den Satz über die Abbildungsanzahl zwischen einer ${}\ell$-elementigen Menge ${}L$ und einer ${}m$-elementigen Menge ${}M$.

Aufgabe * (3 Punkte)

Wir rechnen mit den Zahlen ${}0,1,2,{\text{viele}}\,\,(v)$ nach den folgenden Verknüpfungstabellen.

${}+$	${}0$	${}1$	${}2$	${}v$
${}0$	${}0$	${}1$	${}2$	${}v$
${}1$	${}1$	${}2$	${}v$	${}v$
${}2$	${}2$	${}v$	${}v$	${}v$
${}v$	${}v$	${}v$	${}v$	${}v$

und

${}\cdot$	${}0$	${}1$	${}2$	${}v$
${}0$	${}0$	${}0$	${}0$	${}0$
${}1$	${}0$	${}1$	${}2$	${}v$
${}2$	${}0$	${}2$	${}v$	${}v$
${}v$	${}0$	${}v$	${}v$	${}v$

Zeige, dass es sich dabei um einen kommutativen Halbring handelt. Gilt für diesen die Abziehregel?

Aufgabe * (1 Punkt)

Es sei ${}\left(G,\cdot ,1\right)$ eine Gruppe. Es seien  ${}a,b,c\in G$  Elemente mit

${}a\cdot b\cdot c=1\,.$

1. Was ist das Inverse von ${}a$?
2. Was ist das Inverse von ${}a\cdot b$?
3. Was ist das Inverse von ${}c$?
4. Was ist das Inverse von ${}a\cdot b\cdot c$?

Aufgabe * (3 Punkte)

Man gebe ein Polynom  ${}P\in \mathbb {Q} [X]$  an, das nicht zu ${}\mathbb {Z} [X]$ gehört, aber die Eigenschaft besitzt, dass für jede ganze Zahl ${}n$ gilt:  ${}P(n)\in \mathbb {Z}$. 

Aufgabe * (4 Punkte)

Die beiden Flöhe Carlo und Fredo sitzen im Nullpunkt eines beidseitig unendlich langen Zentimeterbandes. Carlo kann Sprünge der Weite ${}255$ und ${}561$ (in Zentimeter) machen, Fredo kann Sprünge der Weite ${}357$ und ${}595$ machen. Auf welchen Zentimeterpositionen können sich die beiden Flöhe begegnen?

Aufgabe * (4 (1+3) Punkte)

a) Gibt es eine Primzahl ${}x$ derart, dass auch ${}x+10$ und ${}x+20$ Primzahlen sind?

b) Gibt es mehr als eine Primzahl ${}x$ derart, dass auch ${}x+10$ und ${}x+20$ Primzahlen sind?

Aufgabe * (7 Punkte)

Wir betrachten die Abbildung

$\Psi \colon \mathbb {N} ^{4}\longrightarrow \mathbb {N} ^{4},$

die einem Vierertupel ${}(a,b,c,d)$ das Vierertupel

$(\vert {b-a}\vert ,\vert {c-b}\vert ,\vert {d-c}\vert ,\vert {a-d}\vert )$

zuordnet. Zeige, dass sich bei jedem Starttupel ${}(a,b,c,d)$ nach endlich vielen Iterationen dieser Abbildung stets das Nulltupel ergibt.

Aufgabe * (4 Punkte)

Es seien ${}2\times 2$-Matrizen  ${}A={\begin{pmatrix}a_{11}&a_{12}\\a_{21}&a_{22}\end{pmatrix}}$  und  ${}B={\begin{pmatrix}b_{11}&b_{12}\\b_{21}&b_{22}\end{pmatrix}}$  gegeben. Das Produkt ${}A\cdot B$ ergibt sich mit der üblichen Multiplikationsregel „Zeile x Spalte“, bei der man insgesamt ${}8$ Multiplikationen im Körper ${}K$ ausführen muss. Wir beschreiben, wie man diese Matrixmultiplikation mit nur ${}7$ Multiplikationen (aber mit mehr Additionen) durchführen kann. Wir setzen

${}m_{1}=\left(a_{11}+a_{22}\right)\cdot \left(b_{11}+b_{22}\right)\,,$

${}m_{2}=\left(a_{21}+a_{22}\right)\cdot b_{11}\,,$

${}m_{3}=a_{11}\cdot \left(b_{12}-b_{22}\right)\,,$

${}m_{4}=a_{22}\cdot \left(b_{21}-b_{11}\right)\,,$

${}m_{5}=\left(a_{11}+a_{12}\right)\cdot b_{22}\,,$

${}m_{6}=\left(a_{21}-a_{11}\right)\cdot \left(b_{11}+b_{12}\right)\,,$

${}m_{7}=\left(a_{12}-a_{22}\right)\cdot \left(b_{21}+b_{22}\right)\,.$

Zeige, dass für die Koeffizienten der Produktmatrix

${}AB=C={\begin{pmatrix}c_{11}&c_{12}\\c_{21}&c_{22}\end{pmatrix}}\,$

die Gleichungen

${}c_{11}=m_{1}+m_{4}-m_{5}+m_{7}\,,$

${}c_{12}=m_{3}+m_{5}\,,$

${}c_{21}=m_{2}+m_{4}\,,$

${}c_{22}=m_{1}-m_{2}+m_{3}+m_{6}\,,$

gelten.

Aufgabe * (9 Punkte)

Beweise den Satz über die explizite Lösung einer Matrixrekursion.

Aufgabe * (2 Punkte)

Es sei ${}K$ ein Körper und  ${}x\in K$  ein Element mit  ${}x\neq 1$.  Beweise für  ${}n\in \mathbb {N}$  durch Induktion die Beziehung

${}\sum _{k=0}^{n}x^{k}={\frac {x^{n+1}-1}{x-1}}\,.$

Aufgabe (2 Punkte)

Skizziere den Disjunktheitsgraphen zur Potenzmenge von ${}\{a,b,c\}$.

Aufgabe (3 Punkte)

Skizziere für die möglichen Wurzeln den angegebenen Baum derart, dass die Wurzel oben platziert ist und dass der Abstand eines Punktes zur Wurzel direkt über die Höhe der Platzierung erkennbar ist.

Aufgabe * (4 (1+1+1+1) Punkte)

In die Beete ${}A,B,C,D,E$ sollen Kartoffeln, Radieschen, Tulpen und Zwiebel gepflanzt werden. Dabei erfüllen die Beete bzw. die Pflanzen erfordern folgende Standortbedingungen.

Beet	Licht	Boden	Feuchtigkeit
A	${}{\text{sonnig}}$	${}{\text{sauer}}$	${}{\text{feucht}}$
B	${}{\text{sonnig}}$	${}{\text{normal}}$	${}{\text{trocken}}$
C	${}{\text{sonnig}}$	${}{\text{sauer}}$	${}{\text{trocken}}$
D	${}{\text{schattig}}$	${}{\text{normal}}$	${}{\text{trocken}}$
E	${}{\text{schattig}}$	${}{\text{normal}}$	${}{\text{feucht}}$

Pflanze	Licht	Boden	Feuchtigkeit
Kartoffeln	${}{\text{schattig}}$	${}{\text{egal}}$	${}{\text{egal}}$
Radieschen	${}{\text{egal}}$	${}{\text{normal}}$	${}{\text{trocken}}$
Tulpen	${}{\text{sonnig}}$	${}{\text{egal}}$	${}{\text{feucht}}$
Zwiebeln	${}{\text{schattig}}$	${}{\text{normal}}$	${}{\text{trocken}}$

1. Skizziere einen Graphen, der die möglichen Bepflanzungen ausdrückt.
2. Erstelle eine maximale Paarung zwischen Planzen und Beeten, die nicht optimal ist.
3. Erstelle eine optimale Paarung zwischen Planzen und Beeten.
4. Welche Bedingungen müsste eine fünfte Pflanze erfüllen, damit die optimale Paarung aus (3) ergänzt werden könnte

Aufgabe (2 Punkte)

Man erläutere anhand einer Krone den Satz von König!

Aufgabe * (2 Punkte)

Ist es möglich, die Karte der deutschen Bundesländer mit drei Farben zulässig einzufärben?