Kurs:Diskrete Mathematik/16/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	0	3	3	6	7	0	3	2	3	3	0	0	0	5	0	0	0	41

Aufgabe (3 Punkte)

Definiere die folgenden (kursiv gedruckten) Begriffe.

1. Eine Relation zwischen Mengen ${}M$ und ${}N$.
2. Geordnete Mengen/Produktordnung/Definition/Begriff
3. Verband/Beschränkt/Definition/Begriff
4. Ungerichteter Graph/Untergraph/Definition/Begriff
5. Ungerichteter Graph/Disjunkte Vereinigung/Definition/Begriff
6. Ungerichteter Graph/Zusammenhängend/Durchmesser/Definition/Begriff

Lösung

1. Eine Relation ${}R$ zwischen den Mengen ${}M$ und ${}N$ ist eine Teilmenge der Produktmenge ${}M\times N$, also ${}R\subseteq M\times N$.
2. Geordnete Mengen/Produktordnung/Definition/Begriff/Inhalt
3. Verband/Beschränkt/Definition/Begriff/Inhalt
4. Ungerichteter Graph/Untergraph/Definition/Begriff/Inhalt
5. Ungerichteter Graph/Disjunkte Vereinigung/Definition/Begriff/Inhalt
6. Ungerichteter Graph/Zusammenhängend/Durchmesser/Definition/Begriff/Inhalt

Aufgabe (3 Punkte)

Formuliere die folgenden Sätze.

1. Der Satz über geordnete Mengen und Potenzmengen.
2. Die universelle Eigenschaft der Quotientenmenge.
3. /Fakt/Name

Lösung

1. Es sei ${}(M,\leq )$ eine geordnete Menge und ${}{\mathfrak {P}}\,(M)$ die Potenzmenge von ${}M$. Dann ist die Abbildung

   $M\longrightarrow {\mathfrak {P}}\,(M),\,x\longmapsto {\left\{y\in M\mid y\leq x\right\}},$

   ordnungsvolltreu und injektiv ist, wobei die Potenzmenge mit der Inklusion

   versehen ist.
2. Es sei ${}M$ eine Menge und ${}\sim$ eine Äquivalenzrelation auf ${}M$ mit der Quotientenmenge ${}M/\sim$. Es sei ${}\varphi \colon M\rightarrow W$ eine Abbildung mit ${}\varphi (x)=\varphi (y)$ für alle ${}x,y\in M$ mit ${}x\sim y$. Dann gibt es eine eindeutig bestimmte Abbildung ${}{\overline {\varphi }}\colon M/\sim \,\,\rightarrow W$ mit ${}\varphi ={\overline {\varphi }}\circ q$.
3. /Fakt

Aufgabe (0 Punkte)

Lösung /Aufgabe/Lösung

Aufgabe (3 Punkte)

Es seien ${}M$ und ${}N$ endliche Mengen mit ${}m$ bzw. ${}n$ Elementen und sei

$f\colon M\longrightarrow N$

eine injektive Abbildung. Wie viele Abbildungen

$g\colon N\longrightarrow M$

mit

${}g\circ f=\operatorname {Id} _{M}\,$

gibt es?

Lösung

Jedes ${}y\in N$ muss durch ${}g$ auf das aufgrund der Injektivität eindeutig bestimmte ${}x\in M$ mit ${}f(x)=y$ abgebildet werden. Für die restlichen ${}n-m$ Elemente in ${}N$ können die Bilder in ${}M$ frei gewählt werden. Dies ergibt insgesamt

$m^{n-m}$

Möglichkeiten.

Aufgabe (3 Punkte)

Heidi Gonzales macht Karate und isst gerne Schokolade. Um eine Schokolade schneller in ihre Teilstücke zerlegen zu können, hat sie einen speziellen Karateschlag entwickelt, mit dem sie beliebig viele Schokoladenstücke gleichzeitig längs einer Rille zerteilen kann, die Stücke müssen dabei nur derart übereinander liegen, dass die Rillen übereinander liegen. Heide hat nun eine Schokolade mit ${}4\times 6$ Teilstücken. Mit wie vielen Karateschlägen kann sie minimal die Schokolade vollständig zerlegen?

Lösung

Sie kann es mit fünf Karateschlägen schaffen. Mit dem ersten Schlag macht sie zwei ${}2\times 6$-Schokoladen, legt diese übereinander und macht daraus vier ${}1\times 6$-Schokoladen. Dann legt sie diese übereinander, haut in der Mitte durch und macht daraus acht ${}1\times 3$-Schokoladen. Dann legt sie diese acht Stück übereinander und haut das linke Drittel ab, wobei acht ${}1\times 1$-Stücke und acht ${}1\times 2$-Stücke entstehen. Zuletzt halbiert sie noch diese acht Stücke mit einem Schlag.

Mit vier Karateschlägen kann sie es nicht schaffen. Da mit jedem Schlag aus jeder Teilschokolade höchstens zwei Teilschokoladen entstehen, kann es nach vier Schlägen höchstens ${}2^{4}=16$ Stücke geben, aber keine ${}24$.

Aufgabe (6 (1+1+3+1) Punkte)

Der VfB Stuttgart spielt gegen Bayern München und gewinnt auch in dieser Höhe verdient mit ${}8:3$.

1. Wie viele Möglichkeiten für die Torreihenfolge gibt es?
2. Wie viele Möglichkeiten für den Spielverlauf gibt es, wenn man unter Spielverlauf die Torreihenfolge und den Halbzeitstand versteht.
3. Das Spiel dauerte genau ${}90$ Minuten und in jeder Minute fiel höchstens ein Tor. Wie viele Möglichkeiten für den Spielverlauf gibt es, wenn man darunter versteht, welche Mannschaft in welcher Minute ein Tor geschossen hat (hier genügt eine Formel)?
4. Wie viele Möglichkeiten für die Torreihenfolge gibt es, wenn man weiß, dass Stuttgart, abgesehen vom anfänglichen ${}0:0$, stets in Führung lag.

Lösung

1. Es fallen insgesamt ${}11$ Tore, die Torreihenfolge ist festgelegt, wenn man weiß, welche Tore davon von München erzielt wurden. Also ist die Anzahl der Möglichkeiten gleich

   ${}{\binom {11}{3}}={\frac {11\cdot 10\cdot 9}{3\cdot 2}}=11\cdot 5\cdot 3=165\,.$

2. Bei jeder der ${}165$ Torreihenfolgen gibt es für die Pause ${}12$ Möglichkeiten (vor dem ersten Tor, nach dem ersten Tor, nach dem zweiten Tor, ..., nach dem elften Tor), also ist die Anzahl gleich

   ${}12\cdot 165=1980\,.$

3. Für jede der ${}165$ Torreihenfolgen muss man noch festlegen, in welchen Minuten die Tore fielen. Für diese Torminuten gibt es ${}{\binom {90}{11}}$ Möglichkeiten, also gibt es ${}165\cdot {\binom {90}{11}}$ Möglichkeiten für den Spielverlauf im beschriebenen Sinn.
4. Da Stuttgart stets (bis auf den Anfang) in Führung liegt, muss Stuttgart das erste und das zweite Tor erzielen. Wir berechnen die Möglichkeiten je nachdem, ob Stuttgart genau die ersten zwei Toren, genau die ersten drei Tore oder zumindest die ersten vier Tore erzielt. Stuttgart erzielt genau die ersten beiden Tore. Dann erzielt München das dritte Tor und es steht ${}2:1$. Wegen der Führungseigenschaft erzielt Stuttgart das vierte Tor und es steht ${}3:1$. Für den weiteren Torverlauf gibt es somit ${}{\binom {7}{2}}=21$ Möglichkeiten, und davon ist nur der Fall ausgeschlossen, dass München die beiden folgenden Tore schießt. Also gibt es in diesem Fall ${}20$ Möglichkeiten. Stuttgart erzielt genau die ersten drei Tore. Dann erzielt München das vierte Tor und es steht ${}3:1$. In diesem Fall gibt es dann wieder ${}20$ Möglichkeiten. Stuttgart erzielt die ersten vier Tore. Dann ist bei jedem weiteren Torverlauf die Führungseigenschaft erfüllt. Davon gibt es ${}{\binom {7}{3}}=35$ Möglichkeiten. Insgesamt gibt es also

   ${}20+20+35=75\,$

   mögliche Torreihenfolgen, die die Führungsbedingung erfüllen.

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

Der Planet Trigeno wird von einer einzigen Tierart bevölkert, den Trigos. Diese Tierart besitzt drei Geschlechter: Antilopen (A), Büffel (B) und Cnus (C). Bei der Paarung treffen zwei Individuen zusammen und erzeugen ein neues Individuum. Wenn das Paar gleichgeschlechtlich ist, so ist das Ergebnis wieder dieses Geschlecht, wenn das Paar gemischtgeschlechtlich ist, so ist das Ergebnis das dritte unbeteiligte Geschlecht. Alle Tiere gehören einer eindeutigen Generation an.

1. Die ${}n$-te Generation bestehe nur aus einem einzigen Geschlecht. Zeige, dass jede weitere Generation auch nur aus diesem Geschlecht besteht.
2. Die ${}n$-te Generation bestehe nur aus zwei Individuen unterschiedlichen Geschlechts. Zeige, dass diese Geschlechter mit ihrer Generation aussterben.
3. Es gelte nun die zusätzliche Bedingung, dass jedes Paar nur einen Nachkommen erzeugen darf. Zeige, dass die Tierart genau dann aussterben muss, wenn es in einer Generation nur zwei oder weniger Individuen gibt.
4. Es gelte nun die zusätzliche Bedingung, dass jedes Paar nur einen Nachkommen erzeugen darf, und in jeder Generation gebe es genau drei Individuen. Beschreibe die möglichen Generationsabfolgen. Welche Periodenlängen treten auf?

Lösung

1. Wenn die Generation nur aus dem Geschlecht ${}X$ besteht, so sind nur Paarungen innerhalb dieses Geschlechts möglich und das Ergebnis gehört stets diesem Geschlecht an. Mit Induktion folgt, dass dies über alle folgenden Generationen so bleibt.
2. Die Generation bestehe aus einem Individuum des Geschlechts ${}X$ und aus einem Individuum des Geschlechts ${}Y\neq X$. Die Folgegeneration besteht dann ausschließlich aus dem dritten Geschlecht ${}Z$ und nach Teil (1) überträgt sich das auf alle folgenden Generationen.
3. Wenn es nur ein oder kein Individuum gibt, so ist keine Paarung möglich und die nächste Generation ist leer. Wenn es zwei Individuen gibt, so ist nur eine Paarung möglich und es gibt nur einen Nachkommen, der sich allein nicht fortpflanzen kann. Wenn es dagegen mindestens drei Individuen, egal welchen Geschlechts, gibt, so sind auch mindestens drei Paarungen möglich und die nächste Generation besitzt mindestens wieder drei Individuen.
4. Wenn drei gleichgeschlechtliche Individuen in einer Generation leben, so erzeugen die drei möglichen Paare stets wieder ebendieses Geschlecht. Die Möglichkeiten sind ${}A,A,A$ oder ${}B,B,B$ oder ${}C,C,C$ und die Periodenlänge ist ${}1$. Wenn drei unterschiedliche Geschlechter vertreten sind, so ist jedes Geschlecht durch genau ein Individuum vertreten, es liegt also ${}A,B,C$ vor. Die drei Paarungen führen dann wieder zu ${}A,B,C$ und die Periodenlänge ist ebenfalls ${}1$. Wenn ein Geschlecht durch zwei Individuen vertreten ist und ein zweites Geschlecht durch ein Individuum, sagen wir ${}X,X,Y$, so wird daraus ${}X,Z,Z$ und daraus ${}Y,Y,Z$ und daraus ${}X,X,Y$. Die Periodenlänge ist also ${}3$. Von diesem Typ gibt es zwei Generationsabfolgen, nämlich die mit ${}A,A,B$ (mit $A,C,C$ und $B,B,C$) und die mit ${}A,B,B$ (mit $B,C,C$ und $A,A,C$).

Aufgabe (0 Punkte)

Lösung /Aufgabe/Lösung

Aufgabe (3 Punkte)

Zeige, dass der Kern eines Ringhomomorphismus

$\varphi \colon R\longrightarrow S$

ein Ideal in ${}R$ ist.

Lösung

Sei

${}I:=\varphi ^{-1}(0)\,.$

Wegen ${}\varphi (0)=0$. ist ${}0\in I$. Es seien ${}a,b\in I$. Das bedeutet ${}\varphi (a)=0$ und ${}\varphi (b)=0$. Dann ist

${}\varphi (a+b)=\varphi (a)+\varphi (b)=0+0=0\,$

und daher ${}a+b\in I$.

Es sei nun ${}a\in I$ und ${}r\in R$ beliebig. Dann ist

${}\varphi (ra)=\varphi (r)\varphi (a)=\varphi (r)\cdot 0=0\,,$

also ist ${}ra\in I$.

Aufgabe (2 Punkte)

Bestimme die Primfaktorzerlegung von ${}831600$.

Lösung

Es ist

${}{\begin{aligned}831600&=2^{2}\cdot 5^{2}\cdot 8316\\&=2^{3}\cdot 5^{2}\cdot 4158\\&=2^{4}\cdot 5^{2}\cdot 2079\\&=2^{4}\cdot 3\cdot 5^{2}\cdot 693\\&=2^{4}\cdot 3^{2}\cdot 5^{2}\cdot 231\\&=2^{4}\cdot 3^{3}\cdot 5^{2}\cdot 77\\&=2^{4}\cdot 3^{3}\cdot 5^{2}\cdot 7\cdot 11.\end{aligned}}$

Aufgabe (3 (1+2) Punkte)

Auf einer Baustelle gibt es eine große Waage mit zwei Schalen und (beliebig viele) Gewichte der Schwere ${}12$ bzw. ${}50$ Kilogramm.

1. Erläutere, wie man damit sechs Kilogramm Sand abwiegen kann.
2. Bestimme, welche Massen man damit abwiegen kann.

Lösung

1. Wegen

   ${}3\cdot 50=6+12\cdot 12\,$

   kann man ${}6$ Kilo Sand abwiegen, indem man in die eine Schale dreimal das Fünfzigergewicht und in die andere zwölfmal das Zwölfergewicht drauflegt und die letzte Schale mit Sand auffüllt.

2. Da beide Zahlen Vielfache von ${}2$ sind, kann man auch nur Vielfache von ${}2$ abwiegen. Zwei kann man in der Tat abwiegen, wegen

   ${}50=2+4\cdot 12\,.$

   Indem man diese Situation vervielfacht, kann man jedes Vielfache von ${}2$ abwiegen.

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

Bestimme die Äquivalenzklassen zur Äquivalenzrelation, die durch die möglichen Züge des Springers im Schach gegeben ist, und zwar auf den folgenden Schachbrettern.

1. Das ${}2\times 2$-Brett.
2. Das ${}3\times 3$-Brett.
3. Das ${}4\times 4$-Brett.

Lösung

1. Jeder Pferdsprung würde das ${}2\times 2$-Brett verlassen, daher sind die vier einzelnen Felder die Äquivalenzklassen.

2. 

   Vom zentralen Feld aus würde jeder Pferdsprung das ${}3\times 3$-Brett verlassen, dieses bildet somit für sich eine Äquivalenzklasse. Die acht übrigen Felder sind mittels Pferdsprüngen untereinander verbindbar, wie die Skizze zeigt.

3. Die in der folgenden Matrix angegebene Zugreihenfolge

   ${\begin{pmatrix}1&6&15&10\\12&9&2&5\\7&4&11&14\\&13&8&3\end{pmatrix}}$

   zeigt, dass alle Felder bis auf das links unten miteinander durch Pferdsprünge verbunden sind. Letzteres ist mit dem mit ${}9$ markierten Feld durch einen Pferdsprung verbunden. Also sind alle Felder zueinander äquivalent und es gibt nur eine Äquivalenzklasse.

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

Beweise den Satz über die Potenzen der Adjazenzmatrix.

Lösung

Wir beweisen die Aussage durch Induktion über ${}\ell$, wobei der Induktionsanfang für ${}\ell =1$ unmittelbar aus der Definition der Adjazenzmatrix folgt, da ja die Kanten die einzigen Wege der Länge ${}1$ sind (bei ${}\ell =0$ stimmt die Aussage ebenfalls, da es nur die konstanten kantenleeren Wege der Länge ${}0$ gibt und die ${}0$-te Potenz der Matrix als Einheitsmatrix zu interpretieren ist). Ein Weg der Länge ${}\ell +1$ von ${}u$ nach ${}v$ startet mit einer Kante ${}\{u,w\}$ gefolgt von einem Weg von ${}w$ nach ${}v$ der Länge ${}\ell$. Es gilt also unter Verwendung der Induktionsvoraussetzung

${}{\begin{aligned}{\#\left({\text{ Weg von }}u{\text{ nach }}v{\text{ der Länge }}\ell +1\}\right)}&=\sum _{\{u,w\}\in E}{\#\left({\text{ Weg von }}w{\text{ nach }}v{\text{ der Länge }}\ell \}\right)}\\&=\sum _{\{u,w\}\in E}{\left(A^{\ell }\right)}_{(w,v)}\\&=\sum _{w\in V}A_{(u,w)}{\left(A^{\ell }\right)}_{(w,v)}\\&={\left(A\cdot A^{\ell }\right)}_{(u,v)}\\&={\left(A^{\ell +1}\right)}_{(u,v)}\end{aligned}}$

Aufgabe (0 Punkte)

Lösung /Aufgabe/Lösung

Aufgabe (0 Punkte)

Lösung /Aufgabe/Lösung

Aufgabe (0 Punkte)

Lösung /Aufgabe/Lösung