Zum Inhalt springen

Kurs:Diskrete Mathematik/7/Klausur mit Lösungen

Aus Wikiversity



Aufgabe 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19
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 mit Elementen.
  2. Ein größtes Element in einer geordneten Menge .
  3. Zwei teilerfremde natürliche Zahlen und .
  4. Ungerichteter Graph/Kantenfrei/Definition/Begriff
  5. Ungerichter Graph/Paarung/Definition/Begriff
  6. Das chromatische Polynom eines Graphen .


Lösung

  1. Eine Menge heißt endlich mit Elementen, wenn es eine Bijektion

    gibt.

  2. Ein Element heißt größtes Element von , wenn für jedes gilt.
  3. Die beiden natürlichen Zahlen und heißen teilerfremd, wenn sie keinen gemeinsamen Teiler besitzen.
  4. Ungerichteter Graph/Kantenfrei/Definition/Begriff/Inhalt
  5. Ungerichter Graph/Paarung/Definition/Begriff/Inhalt
  6. Unter dem chromatischen Polynom versteht man die Funktion, die durch

    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 .
  3. Der Satz von Ore.


Lösung

  1. Die Anzahl der -elementigen Teilmengen in einer -elementigen Menge ist der Binomialkoeffizient
  2. Durch die Festlegung

    wenn

    wird eine Äquivalenzrelation auf definiert.
  3. Es sei ein Graph mit mindestens drei Elementen, der die Bedingung

    für je zwei nicht adjazente Knoten erfüllt. Dann ist

    hamiltonsch.


Aufgabe (3 Punkte)

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


Lösung

Wir zählen zunächst die Möglichkeiten, mit den -, - und -Centmünzen die folgenden Beträge darzustellen:

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

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

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 oder 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

Typen.


Aufgabe (4 Punkte)

Beweise den Satz über die Anzahl von bijektiven Abbildungen.


Lösung

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

den bijektiven Abbildungen von nach . Nach Induktionsvoraussetzung gibt es solche bijektiven Abbildungen. Daher ist die Anzahl der bijektiven Abbildungen zwischen und gleich


Aufgabe (3 Punkte)

Wie viele Teilquadrate mit positiver Seitenlänge gibt es in einem Quadrat der Seitenlänge ? 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 . 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 eine Möglichkeit, für die Seitenlänge vier Möglichkeiten, für die Seitenlänge neun Möglichkeiten, für die Seitenlänge Möglichkeiten und für die Seitenlänge Möglickeiten, Insgesamt gibt es also

Unterquadrate.


Aufgabe (0 Punkte)


Lösung /Aufgabe/Lösung


Aufgabe (2 Punkte)

Beweise den Satz über die Lösbarkeit von Gleichungen in einer Gruppe .


Lösung

Wir betrachten die linke Gleichung. Aus beidseitiger Multiplikation mit (bzw. mit ) von links folgt, dass nur

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 .

Der Algorithmus geht folgendermaßen. Wenn ist, so ersetzte das Paar durch das Paar, das aus der kleineren Zahl und der Differenz zwischen der kleineren und der größeren Zahl besteht. Wiederhole dies rekursiv. Wenn ist, so ist man fertig und es wird das Ergebnis ausgegeben.

  1. Führe diesen Algorithmus für das Paar 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 ein Beispiel, wo der euklidische Algorithmus nach einem Schritt fertig ist, wo aber die Variante Schritte benötigt.


Lösung

  1. Der Algorithmus ersetzt sukzessive

    der größte gemeinsame Teiler ist also .

  2. Wenn ist, so hört der Algorithmus auf. Wenn genau eine Zahl ist, so ist das Folgepaar und dann hört der Algorithmus auf. Es sei also ohne Einschränkung

    Das Folgepaar ist dann und beide Zahlen sind kleiner als . 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 ist diese Zahl auch der größte gemeinsame Teiler. Wir zeigen, dass sich bei jedem Rekursionsschritt, bei dem (es sei wieder ) durch ersetzt wird, der größte gemeinsame Teiler der beiden Paare übereinstimmt. Dazu muss man nur zeigen, dass und einerseits und und andererseits die gleichen gemeinsamen Teiler haben. Es sei also und und . Dann ist

    ebenfalls ein Vielfaches von . Wenn umgekehrt und ist, so ist

    ebenfalls ein Vielfaches von .

  4. Wir betrachten das Paar . Der euklidische Algorithmus liefert

    und ist fertig. Die Variante ersetzt durch , sie braucht also Schritte, um die Abbruchbedingung zu erreichen.


Aufgabe (2 Punkte)

Zeige, dass die auf durch

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 und . Dies bedeutet bzw. . Somit ist

Wegen ergibt die Kürzungsregel in die Gleichheit

also .


Aufgabe (0 Punkte)


Lösung /Aufgabe/Lösung


Aufgabe (1 Punkt)

Bei einem vollständigen ungerichteten Graphen mit 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