Kurs:Diskrete Mathematik/7/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	4	3	0	2	0	8	2	0	1	0	0	0	0	0	0	32

Aufgabe (3 Punkte)

Definiere die folgenden (kursiv gedruckten) Begriffe.

1. Eine endliche Menge ${}M$ mit ${}n$ Elementen.
2. Ein größtes Element ${}x\in I$ in einer geordneten Menge ${}(I,\preccurlyeq )$.
3. Zwei teilerfremde natürliche Zahlen ${}a$ und ${}b$.
4. Ungerichteter Graph/Kantenfrei/Definition/Begriff
5. Ungerichter Graph/Paarung/Definition/Begriff
6. Das chromatische Polynom eines Graphen ${}G$.

Lösung

1. Eine Menge ${}M$ heißt endlich mit ${}n$ Elementen, wenn es eine Bijektion

   ${\{1,\ldots ,n\}}\longrightarrow M$

   gibt.

2. Ein Element ${}x\in I$ heißt größtes Element von ${}I$, wenn ${}y\preccurlyeq x$ für jedes ${}y\in I$ gilt.
3. Die beiden natürlichen Zahlen ${}a$ und ${}b$ heißen teilerfremd, wenn sie keinen gemeinsamen Teiler ${}\geq 2$ besitzen.
4. Ungerichteter Graph/Kantenfrei/Definition/Begriff/Inhalt
5. Ungerichter Graph/Paarung/Definition/Begriff/Inhalt
6. Unter dem chromatischen Polynom ${}P_{G}$ versteht man die Funktion, die durch

   ${}P_{G}\left(k\right)={\#{\left\{f:V\rightarrow \{1,\ldots ,k\}\mid f{\text{ zulässige Färbung}}\right\}}}\,$

   gegeben ist.

Aufgabe (3 Punkte)

Formuliere die folgenden Sätze.

1. Der Satz über die Teilmengenanzahl einer endlichen Menge.
2. Der Satz über die Äquivalenzrelation zu einer Abbildung ${}f\colon M\rightarrow N$.
3. Der Satz von Ore.

Lösung

1. Die Anzahl der ${}k$-elementigen Teilmengen in einer ${}n$-elementigen Menge ist der Binomialkoeffizient

   ${\binom {n}{k}}.$

2. Durch die Festlegung

   ${}x\sim y\,,$

   wenn

   ${}f(x)=f(y)\,,$

   wird eine Äquivalenzrelation auf ${}M$ definiert.
3. Es sei ${}G=(V,E)$ ein Graph mit mindestens drei Elementen, der die Bedingung

   ${}d(u)+d(v)\geq {\#\left(V\right)}\,$

   für je zwei nicht adjazente Knoten ${}u,v$ erfüllt. Dann ist ${}G$

   hamiltonsch.

Aufgabe (3 Punkte)

Auf wie viele Arten kann man mit den üblichen Münzen einen Betrag von ${}20$ Cent begleichen?

Lösung

Wir zählen zunächst die Möglichkeiten, mit den ${}5$-, ${}10$- und ${}20$-Centmünzen die folgenden Beträge darzustellen:

$0{\text{ Cent}}:1{\text{ Möglichkeit}},$

$5{\text{ Cent}}:1{\text{ Möglichkeit}},$

$10{\text{ Cent}}:2{\text{ Möglichkeiten}},$

$15{\text{ Cent}}:2{\text{ Möglichkeiten}},$

$20{\text{ Cent}}:4{\text{ Möglichkeiten}}.$

Dann betrachten wir in jedem Fall, mit wie vielen ${}2$-Centmünzen man jeweils noch unterhalb von ${}20$ Cent bleibt, der verbleibende Rest wird mit ${}1$-Centmünzen aufgefüllt. Hierfür gibt es der Reihe nach

$11,8,6,3,1{\text{ Möglichkeiten}}.$

Diese Möglichkeiten für die Zweier muss man mit den obigen Möglichkeiten multiplizieren, das ergibt insgesamt

${}1\cdot 11+1\cdot 8+2\cdot 6+2\cdot 3+4\cdot 1=11+8+12+6+4=41\,$

Möglichkeiten.

Aufgabe (3 Punkte)

Die Puzzleteile für ein Puzzle haben eine grob rechteckige Form, wobei die eine Seite erkennbar länger als die andere ist, und auf jeder Seite gibt es entweder eine Einbuchtung oder eine Ausbuchtung. Wie viele Typen von Puzzelteilen gibt es?

Lösung

Wir betrachten die Puzzleteile je nachdem, ob sie ${}0,1,2,3$ oder ${}4$ Ausbuchtungen haben (was die Anzahl der Einbuchtungen festlegt). Bei keiner Ausbuchtung gibt es keine weitere Unterscheidung. Bei einer Ausbuchtung kann die Ausbuchtung an einer kurzen oder an einer langen Seite sein. Bei zwei Ausbuchtungen gibt es vier Möglichkeiten: Die beiden Ausbuchtungen können gegenüber an den kurzen Seiten, oder gegenüber an den langen Seiten, oder nebeneinander an einer kurzen und an einer langen Seite sein. Im letzteren Fall macht es aber noch einen Unterschied, ob, wenn man die Ausbuchtung an der kurzen Seite nach oben dreht, die Ausbuchtung an der langen Seite links oder rechts liegt. Für drei Ausbuchtungen gibt es wieder zwei und bei vier Ausbuchtungen wieder eine Möglichkeit. Insgesamt gibt es also

${}1+2+4+2+1=10\,$

Typen.

Aufgabe (4 Punkte)

Beweise den Satz über die Anzahl von bijektiven Abbildungen.

Lösung

Wir führen Induktion über ${}n$, wobei der Fall ${}n=1$ klar ist. Die Aussage sei nun für ${}n$ schon bewiesen und es liegen zwei ${}(n+1)$-elementige Mengen ${}M$ und ${}N$ vor. Es sei ${}x\in M$ ein fixiertes Element. Dann gibt es für die Werte ${}\varphi (x)$ genau ${}n+1$ Möglichkeiten, nämlich die Anzahl der Menge ${}N$. Wenn dies festgelegt ist, so entsprechen die bijektiven Abbildungen von ${}M$ nach ${}N$ mit

${}\varphi (x)=y\,$

den bijektiven Abbildungen von ${}M\setminus \{x\}$ nach ${}N\setminus \{y\}$. Nach Induktionsvoraussetzung gibt es ${}n!$ solche bijektiven Abbildungen. Daher ist die Anzahl der bijektiven Abbildungen zwischen ${}M$ und ${}N$ gleich

${}(n+1)\cdot n!=(n+1)!\,.$

Aufgabe (3 Punkte)

Wie viele Teilquadrate mit positiver Seitenlänge gibt es in einem Quadrat der Seitenlänge ${}5$? Die Seiten der Teilquadrate sollen wie im Bild auf dem „Gitter“ liegen, ein einzelner Punkt gelte nicht als Quadrat.

Lösung

Die möglichen Seitenlängen sind ${}1,2,3,4,5$. Ein Unterquadrat ist durch die Lage des Eckes links oben eindeutig bestimmt, man muss bei fixierter Seitenlänge nur berücksichtigen, dass das Teilquadrat ganz im Grundquadrat liegt. Somit gibt es für die Seitenlänge ${}5$ eine Möglichkeit, für die Seitenlänge ${}4$ vier Möglichkeiten, für die Seitenlänge ${}3$ neun Möglichkeiten, für die Seitenlänge ${}2$ ${}16$ Möglichkeiten und für die Seitenlänge ${}1$ ${}25$ Möglickeiten, Insgesamt gibt es also

${}1+4+9+16+25=55\,$

Unterquadrate.

Aufgabe (0 Punkte)

Lösung /Aufgabe/Lösung

Aufgabe (2 Punkte)

Beweise den Satz über die Lösbarkeit von Gleichungen in einer Gruppe ${}G$.

Lösung

Wir betrachten die linke Gleichung. Aus beidseitiger Multiplikation mit ${}a^{-1}$ (bzw. mit ${}a$) von links folgt, dass nur

${}x=a^{-1}\circ b\,$

als Lösung in Frage kommt. Wenn man dies einsetzt, so sieht man, dass es sich in der Tat um eine Lösung handelt.

Aufgabe (0 Punkte)

Lösung /Aufgabe/Lösung

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

Wir betrachten eine (einfachere, aber langsamere) Variante des euklidischen Algorithmus zur Bestimmung des größten gemeinsamen Teilers zu zwei gegebenen natürlichen Zahlen ${}a,b$.

Der Algorithmus geht folgendermaßen. Wenn ${}a\neq b$ ist, so ersetzte das Paar ${}(a,b)$ durch das Paar, das aus der kleineren Zahl und der Differenz zwischen der kleineren und der größeren Zahl besteht. Wiederhole dies rekursiv. Wenn ${}a=b$ ist, so ist man fertig und es wird das Ergebnis ${}a$ ausgegeben.

1. Führe diesen Algorithmus für das Paar ${}(7,3)$ durch.
2. Zeige, dass dieser Algorithmus nach endlich vielen Schritten aufhört.
3. Zeige, dass dieser Algorithmus korrekt ist, also wirklich den größten gemeinsmen Teiler ausgibt.
4. Man gebe für jedes ${}n$ ein Beispiel, wo der euklidische Algorithmus nach einem Schritt fertig ist, wo aber die Variante ${}n$ Schritte benötigt.

Lösung

1. Der Algorithmus ersetzt sukzessive

   $(7,3)\mapsto (4,3)\mapsto (3,1)\mapsto (2,1)\mapsto (1,1),$

   der größte gemeinsame Teiler ist also ${}1$.

2. Wenn ${}a=b$ ist, so hört der Algorithmus auf. Wenn genau eine Zahl ${}0$ ist, so ist das Folgepaar ${}(c,c)$ und dann hört der Algorithmus auf. Es sei also ohne Einschränkung

   ${}a>b>0\,.$

   Das Folgepaar ist dann ${}(a-b,b)$ und beide Zahlen sind kleiner als ${}a$. D.h. unter dieser Voraussetzung wird das Maximum mit jedem Rechenschritt kleiner. Da sich alles innerhalb der natürlichen Zahlen abspielt, bricht das Verfahren irgendwann ab.

3. Bei ${}a=b$ ist diese Zahl auch der größte gemeinsame Teiler. Wir zeigen, dass sich bei jedem Rekursionsschritt, bei dem ${}(a,b)$ (es sei wieder $a\geq b$) durch ${}(a-b,b)$ ersetzt wird, der größte gemeinsame Teiler der beiden Paare übereinstimmt. Dazu muss man nur zeigen, dass ${}a$ und ${}b$ einerseits und ${}a-b$ und ${}b$ andererseits die gleichen gemeinsamen Teiler haben. Es sei also ${}t\in \mathbb {N}$ und ${}a=tm$ und ${}b=tn$. Dann ist

   ${}a-b=mt-nt=(m-n)t\,$

   ebenfalls ein Vielfaches von ${}t$. Wenn umgekehrt ${}a-b=rt$ und ${}b=st$ ist, so ist

   ${}a=a-b+b=rt+st=(r+s)t\,$

   ebenfalls ein Vielfaches von ${}t$.

4. Wir betrachten das Paar ${}(n,1)$. Der euklidische Algorithmus liefert

   ${}n=n\cdot 1+0\,$

   und ist fertig. Die Variante ersetzt ${}(n,1)$ durch ${}(n-1,1)$, sie braucht also ${}n-1$ Schritte, um die Abbruchbedingung ${}(1,1)$ zu erreichen.

Aufgabe (2 Punkte)

Zeige, dass die auf ${}\mathbb {Z} \times \mathbb {N} _{+}$ durch

$(a,b)\sim (c,d),{\text{ falls }}ad=bc,$

festgelegte Relation eine Äquivalenzrelation ist.

Lösung

Die Reflexivität und die Symmetrie ergeben sich unmittelbar aus der Definition. Zum Nachweis der Transitivität seien ${}(a,b)\sim (c,d)$ und ${}(c,d)\sim (e,f)$. Dies bedeutet ${}ad=bc$ bzw. ${}cf=ed$. Somit ist

${}adf=bcf=bde\,.$

Wegen ${}d\neq 0$ ergibt die Kürzungsregel in ${}\mathbb {Z}$ die Gleichheit

${}af=eb\,,$

also ${}(a,b)\sim (e,f)$.

Aufgabe (0 Punkte)

Lösung /Aufgabe/Lösung

Aufgabe (1 Punkt)

Bei einem vollständigen ungerichteten Graphen mit ${}4$ Ecken ist jede Ecke mit jeder (anderen) Ecke verbunden. Zeichne einen solchen Graphen in der Ebene ohne Überschneidungen.

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

Aufgabe (0 Punkte)

Lösung /Aufgabe/Lösung

Aufgabe (0 Punkte)

Lösung /Aufgabe/Lösung