Kurs:Diskrete Mathematik/21/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	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 $\phi :V\to 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 $ℳ$.

Lösung

1. Ein Körper $K$ ist ein kommutativer Ring, wenn $K\ne 0$ ist und wenn jedes von $0$ verschiedene Element in $K$ ein multiplikatives Inverses besitzt.
2. Die Relation $R$ heißt antisymmetrisch, wenn aus $xRy$ und $yRx$ stets $x=y$ folgt.
3. Die Bellzahl $B_n$ ist die Anzahl der Partitionen einer $n$-elementigen Menge.
4. Unter dem Bildgraphen zu $\phi$ versteht man denjenigen Graphen, dessen Knotenmenge durch das Bild  $W=\phi (V)\subseteq M$  von $\phi$ und dessen Kantenmenge durch

   $F=\{\{\phi (u),\phi (v)\}\mid \{u,v\}\in E,\phi (u)\ne \phi (v)\}$

   gegeben ist.

5. Ein aufspannender Baum ist ein Untergraph  $B\subseteq G$  von $G$, der ein Baum mit der vollen Knotenmenge $V$ ist.
6. Der Rang von $ℳ$ ist die gemeinsame Anzahl der Elemente in einer jeden Basis von $ℳ$.

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.

Lösung

1. Es seien $a,b\in \mathbb{N}$ zwei teilerfremde natürliche Zahlen. Dann gibt es ganze Zahlen $r,s\in \mathbb{Z}$ mit $ra+sb=1$.
2. Es sei $A$ eine $n$-elementige Menge und $B$ eine $k$-elementige Menge. Dann ist die Anzahl der surjektiven Abbildungen von $A$ nach $B$ gleich

   $\sum _{(r_1,\dots ,r_k):r_1+r_2+\cdots +r_k=n,r_j\ge 1}(\genfrac{}{}{0ex}{}{n}{r_1,\dots ,r_k}).$

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

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?

Lösung

1. Es gibt

   $(\genfrac{}{}{0ex}{}{10}{3})=\frac{10\cdot 9\cdot 8}{3\cdot 2\cdot 1}=10\cdot 3\cdot 4=120$

   Möglichkeiten dafür, welche Finger verstaucht sind.

2. Für den Daumen gibt es zwei Möglichkeiten, von den verbleibenden $8$ Nichtdaumenfingern sind zwei verstaucht, also gibt es insgesamt

   $2\cdot (\genfrac{}{}{0ex}{}{8}{2})=2\cdot \frac{8\cdot 7}{2}=56$

   Möglichkeiten in dieser Situation.

3. Für den Daumen gibt es wieder zwei Möglichkeiten. Es ist dann entweder auf der Hand des verstauchten Daumens ein weiterer Finger verstaucht oder aber auf der anderen Hand sind genau zwei Finger verstaucht. Deshalb gibt es

   $2\cdot (4\cdot 4+(\genfrac{}{}{0ex}{}{4}{2}))=2\cdot (16+6)=44$

   Möglichkeiten für diese Situation.

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?

Lösung

Die Tafeln $M$ und $H$ sind nicht gleichzeitig sichtbar, da (mindestens) eine davon durch $V$ verdeckt wird. Dagegen sind sowohl $V$ und $H$ ($M$ wird hinter $V$ geschoben) als auch $V$ und $M$ gleichzeitig einsehbar. Eine Beschreibungsreihenfolge erfüllt also genau dann die angegebene Bedingung, wenn $M$ und $H$ nicht direkt hintereinander beschrieben werden. Dies wird genau dann erreicht, wenn $V$ als zweite Tafel beschrieben wird. Erlaubt sind also die beiden Reihenfolgen $M-V-H$ und $H-V-M$.

Aufgabe (2 Punkte)

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

Lösung

Da jedes Element  $x\in L$  auf genau ein Element aus $M$ abgebildet wird, liegt eine disjunkte Vereinigung

$L=\underset{y\in M}{⨄}{f}^{-1}(y)$

vor. Nach Lemma 1.6 (Diskrete Mathematik (Osnabrück 2026)) ist daher die Gesamtanzahl der Menge gleich der Summe der Anzahlen der disjunkten Teilmengen.

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?

Lösung

Es sei $H$ die in Frage stehende Struktur mit der angegebenen Addition und Multiplikation. Die Abbildung

$\phi :\mathbb{N}⟶H,$

die $0$ auf $0$, $1$ auf $1$, $2$ auf $2$ und jede weitere Zahl auf $v$ abbildet, ist surjektiv und sie respektiert, wie eine direkte Durchsicht zeigt, die Addition und die Multiplikation. Somit übertragen sich die Gesetze eines kommutativen Halbringes von $\mathbb{N}$ nach $H$. Die Abziehregel gilt in $H$ nicht, da

$1+v=v=2+v$

ist, aber

$1\ne 2.$

Aufgabe (1 Punkt)

Es sei $(G,\cdot ,1)$ 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$?

Lösung

1. Das Inverse von $a$ ist $b\cdot c$.
2. Das Inverse von $a\cdot b$ ist $c$.
3. Das Inverse von $c$ ist $a\cdot b$.
4. Das Inverse von $a\cdot b\cdot c$ ist $1$.

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

Lösung

Betrachte das Polynom

$P=\frac{X(X-1)}{2}=\frac{X^2}{2}-\frac{X}{2}.$

Die Koeffizienten liegen in $\mathbb{Q}$, aber nicht in $\mathbb{Z}$. Wenn man in dieses Polynom eine ganze Zahl $n$ einsetzt, so ist genau eine der Zahlen $n$ und $n-1$ gerade. Also ist  $P(n)=\frac{n(n-1)}{2}$  ganzzahlig.

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?

Lösung

Wir bestimmen zuerst, auf welchen Positionen sich jeweils die beiden Flöhe befinden können, indem wir den euklidischen Algorithmus anwenden. Für Carlo ergibt sich

$561=2\cdot 255+51,$

$255=5\cdot 51,$

der größte gemeinsame Teiler der beiden Sprungweiten ist also $51$ und die möglichen Positionen von Carlo sind $51\mathbb{Z}$. Für Fredo ergibt sich

$595=1\cdot 357+238,$

$357=1\cdot 238+119,$

$238=2\cdot 119,$

der größte gemeinsame Teiler der beiden Sprungweiten ist also $119$ und die möglichen Positionen von Fredo sind $119\mathbb{Z}$. Die gemeinsamen Positionen von Carlo und Fredo werden durch

$51\mathbb{Z}\cap 119\mathbb{Z}$

beschrieben. Dafür müssen wir das kleinste gemeinsame Vielfache von $51$ und $119$ ausrechnen. Wegen

$51=3\cdot 17$

und

$119=7\cdot 17$

ist das kleinste gemeinsame Vielfache gleich

$\frac{51\cdot 119}{17}=3\cdot 119=357.$

Die beiden Flöhe können sich also in den Positionen $357\mathbb{Z}$ treffen.

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?

Lösung

a) Die Zahlen $3,13,23$ sind Primzahlen.

b) Wir zeigen, dass es außer dem soeben genannten Beispiel kein weiteres Tripel mit der besagten Eigenschaft gibt. Wir betrachten die Reste von $x,x+10,x+20$ bei Division durch $3$. Wenn $r$ der Rest von $x$ ist, so sind die beiden anderen Reste gleich $r+1$ bzw. $r+2$. Somit muss eine der drei Zahlen den Rest $0$ besitzen, also ein Vielfaches von $3$ sein. Da  $x=3$  ausgeschlossen ist, können nicht alle drei Zahlen Primzahlen sein.

Aufgabe (7 Punkte)

Wir betrachten die Abbildung

$\mathrm{\Psi }:{\mathbb{N}}^4⟶{\mathbb{N}}^4,$

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

$(|b-a|,|c-b|,|d-c|,|a-d|)$

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

Lösung

Es sei $m$ das Maximum der beteiligten vier Zahlen $a,b,c,d$. Wir zeigen, dass dieses Maximum nach endlich vielen Iterationen kleiner wird. Da wir uns innerhalb der natürlichen Zahlen befinden, folgt daraus, dass das Maximum irgendwann $0$ wird, was bedeutet, dass dann alle vier Zahlen $0$ sind. Da alle Zahlen aus $\mathbb{N}$ sind und die nichtnegative Differenz genommen wird, wird das Maximum bei einer Iteration definitiv nicht größer. Allerdings kann das Maximum gleich bleiben. Dies kann aber nur dann sein, wenn ein Nachbar (zyklisch gedacht, die vierte Zahl ist also auch ein Nachbar der ersten Zahl) des Maximums gleich $0$ ist. Wir müssen (durch zyklisches Vertauschen und Spiegeln) nur noch die Situation anschauen, wo das Tupel die Form

$(m,0,x,y)$

mit  $x,y\le m$  hat. Wenn  $x=y=0$  ist, so liefert die Abbildung

$(m,0,0,m).$

Wir müssen also nur noch die Situation anschauen, wo es höchstens zwei Nullen gibt. Bei

$(m,0,x,0)$

mit  $x\ne 0$  ergibt sich im nächsten Schritt

$(m,x,x,m),$

was keine Nullen mehr hat. Bei

$(m,0,0,y)$

mit  $y\ne 0$  ergibt sich im nächsten Schritt

$(m,0,y,m-y).$

Bei  $y<m$  besitzt dies nur eine Null, bei  $y=m$  sind wir in einem schon behandelten Fall. Es sei das Tupel jetzt

$(m,0,x,y)$

mit

$0<x,y\le m.$

Das Ergebnis ist

$(m,x,|x-y|,m-y).$

Bei  $x=m$  ist dies

$(m,m,m-y,m-y)$

mit dem Folgetupel

$(0,y,0,y).$

Bei  $y<m$  besitzt dies ein kleineres Maximum, bei  $y=m$  ist das Folgetupel gleich

$(m,m,m,m),$

und davon ist das Folgetupel

$(0,0,0,0).$

Es sei also  $x<m$.  Das Folgetupel ist bei  $y=m$  gleich

$(m,x,|x-y|,m-y)=(m,x,m-x,0),$

und dessen Folgetupel ist

$(m-x,|m-2x|,m-x,m).$

Allenfalls in der dritten Position könnte eine $0$ stehen, doch diese ist nicht benachbart zum einzigen Vorkommen von $m$, sodass das Folgetupel keine Null besitzt.

Das Folgetupel ist bei  $y<m$  gleich

$(m,x,|x-y|,m-y),$

und dabei ist wieder allenfalls in der dritten Position eine $0$, doch diese ist nicht benachbart zum einzigen Vorkommen von $m$, sodass das Folgetupel keine Null besitzt.

Aufgabe (4 Punkte)

Es seien $2\times 2$-Matrizen  $A=\left(\begin{array}{cc}{a}_{11}& a_{12}\\ a_{21}& a_{22}\end{array}\right)$  und  $B=\left(\begin{array}{cc}{b}_{11}& b_{12}\\ b_{21}& b_{22}\end{array}\right)$  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=(a_{11}+a_{22})\cdot (b_{11}+b_{22}),$

$m_2=(a_{21}+a_{22})\cdot b_{11},$

$m_3=a_{11}\cdot (b_{12}-b_{22}),$

$m_4=a_{22}\cdot (b_{21}-b_{11}),$

$m_5=(a_{11}+a_{12})\cdot b_{22},$

$m_6=(a_{21}-a_{11})\cdot (b_{11}+b_{12}),$

$m_7=(a_{12}-a_{22})\cdot (b_{21}+b_{22}).$

Zeige, dass für die Koeffizienten der Produktmatrix

$AB=C=\left(\begin{array}{cc}{c}_{11}& c_{12}\\ c_{21}& c_{22}\end{array}\right)$

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.

Lösung

Es ist

$\begin{array}{cc}{m}_1+m_4-m_5+m_7& =(a_{11}+a_{22})\cdot (b_{11}+b_{22})+a_{22}\cdot (b_{21}-b_{11})-(a_{11}+a_{12})\cdot b_{22}+(a_{12}-a_{22})\cdot (b_{21}+b_{22})\\ & =a_{11}{b}_{11}+a_{22}{b}_{11}+a_{11}{b}_{22}+a_{22}{b}_{22}+a_{22}{b}_{21}-a_{22}{b}_{11}-a_{11}{b}_{22}-a_{12}{b}_{22}+a_{12}{b}_{21}-a_{22}{b}_{21}+a_{12}{b}_{22}-a_{22}{b}_{22}\\ & =a_{11}{b}_{11}+a_{12}{b}_{21}\\ & =c_{11},\end{array}$

$\begin{array}{cc}{m}_3+m_5& =a_{11}\cdot (b_{12}-b_{22})+(a_{11}+a_{12})\cdot b_{22}\\ & =a_{11}{b}_{12}-a_{11}{b}_{22}+a_{11}{b}_{22}+a_{12}{b}_{22}\\ & =a_{11}{b}_{12}+a_{12}{b}_{22}\\ & =c_{12},\end{array}$

$\begin{array}{cc}{m}_2+m_4& =(a_{21}+a_{22})\cdot b_{11}+a_{22}\cdot (b_{21}-b_{11})\\ & =a_{21}{b}_{11}+a_{22}{b}_{11}+a_{22}{b}_{21}-a_{22}{b}_{11}\\ & =a_{21}{b}_{11}+a_{22}{b}_{21}\\ & =c_{21},\end{array}$

$\begin{array}{cc}{m}_1-m_2+m_3+m_6& =(a_{11}+a_{22})\cdot (b_{11}+b_{22})-(a_{21}+a_{22})\cdot b_{11}+a_{11}\cdot (b_{12}-b_{22})+(a_{21}-a_{11})\cdot (b_{11}+b_{12})\\ & =a_{11}{b}_{11}+a_{22}{b}_{11}+a_{11}{b}_{22}+a_{22}{b}_{22}-a_{21}{b}_{11}-a_{22}{b}_{11}+a_{11}{b}_{12}-a_{11}{b}_{22}+a_{21}{b}_{11}+a_{21}{b}_{12}-a_{11}{b}_{11}-a_{11}{b}_{12}\\ & =a_{21}{b}_{12}+a_{22}{b}_{22}\\ & =c_{22},\end{array}$

gelten.

Aufgabe (9 Punkte)

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

Lösung

Der Ausdruck links ist linear in $v$, daher genügt es, die Aussage für eine Basis von ${ℂ}^d$ zu zeigen. Ferner können wir $M$ durch die beschreibende Matrix bezüglich einer anderen Basis ersetzen. Wir verwenden die Jordansche Normalform $J$ von $M$, ohne Einschränkung sei also $M$ in jordanscher Normalform. $M$ ist also die direkte Summe von Jordanblöcken. Es sei $e$ ein Basisvektor, für den der $i$-te Jordanblock $J_i$

$\left(\begin{array}{ccccc}{\lambda }_i& 1& 0& \cdots & 0\\ 0& {\lambda }_i& 1& \cdots & 0\\ ⋮& \ddots & \ddots & \ddots & ⋮\\ ⋮& \cdots & 0& {\lambda }_i& 1\\ 0& \cdots & \cdots & 0& {\lambda }_i\end{array}\right)$

zuständig ist. Die anderen Jordanblöcke sind für die Berechnung von $M^{n}e$ irrelevant. Wir schreiben

$J_i=D_i+N_i,$

wobei $D_i$ die in $J_i$ enthaltene Diagonalmatrix bezeichnet. In dieser Situation ist

$D_i\circ N_i=N_i\circ D_i,$

vergleiche auch Satz 28.1 (Lineare Algebra (Osnabrück 2024-2025)). Nach Lemma 53.4 (Lineare Algebra (Osnabrück 2024-2025)) gilt

$\begin{array}{cc}{J}_i^n& =D_i^n+n{D}_i^{n-1}\circ N_i+(\genfrac{}{}{0ex}{}{n}{2})D_i^{n-2}\circ N_i^2+(\genfrac{}{}{0ex}{}{n}{3})D_i^{n-3}\circ N_i^3+\cdots +(\genfrac{}{}{0ex}{}{n}{d_i-1})D_i^{n-d_i+1}\circ N_i^{d_i-1},\\ \end{array}$

da die höheren Potenzen von $N$ gleich $0$ sind. Hier kann man $D_i^{n-d_i+1}$ ausklammern und erhält als anderen Faktor

$D_i^{d_i-1}+n{D}_i^{d_i-2}\circ N_i+(\genfrac{}{}{0ex}{}{n}{2})D_i^{d_i-3}\circ N_i^2+\cdots +(\genfrac{}{}{0ex}{}{n}{d_i-1})N_i^{d_i-1}.$

Die Binomialkoeffizienten sind Polynome in $n$ vom Grad $\le d_i-1$, die auftretenden Matrizen sind unabhängig von $n$. Diese Matrizen haben also die Form

$A_n={(Q_{rs}(n))}_{rs}$

mit Polynomen $Q_{rs}$ vom Grad $\le d_i-1$. Somit ist

$\begin{array}{cc}{(M^n(e))}_j& ={(J_i^n(e))}_j\\ & ={((A_n\circ D_i^{n-d_i+1})(e))}_j\\ & ={\left(A_n\left({\lambda }_i^{n-d_i+1}e\right)\right)}_j\\ & ={\lambda }_i^{n-d_i+1}{\left(A_n\left(e\right)\right)}_j\\ & ={\lambda }_i^{n-d_i+1}{Q}_{js}(n)\end{array}$

(dabei ist $s$ die Position von $e$, die Zeilennummer $j$ wird auch für $J_i$ verwendet). Bei  ${\lambda }_i\ne 0$  kann man das Polynom durch ${\lambda }_i^{d_i-1}$ teilen.

Aufgabe (2 Punkte)

Es sei $K$ ein Körper und  $x\in K$  ein Element mit  $x\ne 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}.$

Lösung

Für  $n=0$  steht beidseitig $1$. Es sei die Gleichung für ein bestimmtes $n$ bewiesen. Dann ist

$\begin{array}{cc}\sum _{k=0}^{n+1}{x}^k& =\sum _{k=0}^n{x}^k+x^{n+1}\\ & =\frac{x^{n+1}-1}{x-1}+x^{n+1}\\ & =\frac{x^{n+1}-1+x^{n+1}(x-1)}{x-1}\\ & =\frac{x^{n+1}-1+x^{n+2}-x^{n+1}}{x-1}\\ & =\frac{x^{n+2}-1}{x-1},\end{array}$

was die Behauptung für $n+1$ ist.

Aufgabe (2 Punkte)

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

Lösung erstellen

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.

Lösung erstellen

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

Lösung

1. $$
2. Kartoffeln in Beet $E$, Radieschen in Beet $D$, Tulpen in Beet $A$. Für die Zwiebeln gibt es dann keine Möglichkeit mehr.
3. Kartoffeln in Beet $E$, Radieschen in Beet $B$, Tulpen in Beet $A$, Zwiebeln in Beet $D$.
4. Das Beet $C$ wird bei (3) nicht besetzt, dort kann man eine Pflanze einsetzen, die sonniges Licht und einen sauren Boden bevorzugt und die es trocken mag.

Aufgabe (2 Punkte)

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

Lösung erstellen

Aufgabe (2 Punkte)

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

Lösung

Das ist nicht möglich. An Thüringen grenzen $5$ Länder an, die untereinander einen Kreis bilden, Bayern, Sachsen, Sachsen-Anhalt, Niedersachsen, Hessen. Dieser Kreis braucht jedenfalls drei Farben für eine zulässige Färbung, Thüringen braucht also eine vierte Farbe.