Kurs:Grundkurs Mathematik/Teil I/T4/Klausur mit Lösungen



Aufgabe 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22
Punkte 3 3 6 2 1 5 3 3 4 1 2 2 2 3 2 2 3 2 3 6 3 3 64




Aufgabe (3 Punkte)

Definiere die folgenden (kursiv gedruckten) Begriffe.

  1. Die Multiplikation von natürlichen Zahlen .
  2. Eine lineare (oder totale) Ordnung auf einer Menge .
  3. Die Differenz von natürlichen Zahlen mit .
  4. Eine Primzahl.
  5. Der Binomialkoeffizient .
  6. Die Multiplikation von ganzen Zahlen.


Lösung

  1. Das Produkt ist definiert als die -fache Summe der Zahl mit sich selbst.
  2. Eine Ordnungsrelation auf heißt lineare Ordnung, wenn zu je zwei Elementen die Beziehung oder gilt.
  3. Die Differenz ist diejenige natürliche Zahl für die gilt.
  4. Eine natürliche Zahl heißt eine Primzahl, wenn die einzigen natürlichen Teiler von ihr und sind.
  5. Der Binomialkoeffizient ist durch

    definiert.

  6. Die ganzen Zahlen haben die Form und mit natürlichen Zahlen . Die Multiplikation wird folgendermaßen definiert.


Aufgabe (3 Punkte)

Formuliere die folgenden Sätze.

  1. Der Satz von Euklid über Primzahlen.
  2. Die rekursive Beziehung zwischen den Binomialkoeffizienten (Pascalsches Dreieck).
  3. Die Division mit Rest für natürliche Zahlen.


Lösung

  1. Es gibt unendlich viele Primzahlen.
  2. Die Binomialkoeffizienten erfüllen die rekursive Beziehung
  3. Es sei eine fixierte positive natürliche Zahl. Dann gibt es zu jeder natürlichen Zahl eine eindeutig bestimmte natürliche Zahl und eine eindeutig bestimmte natürliche Zahl , , mit


Aufgabe (6 Punkte)

Es sei eine Menge, die als disjunkte Vereinigung

gegeben ist. Definiere eine Bijektion zwischen der Potenzmenge und der Produktmenge .


Lösung

Wir betrachten die Abbildungen

und

und behaupten, dass diese beiden Abbildungen zueinander invers sind. Die Verknüpfung sendet insgesamt eine Teilmenge auf

Die Inklusion

ist dabei klar. Wenn umgekehrt liegt, so ist aufgrund der Voraussetzung oder und damit ist auch . Daher ist die Identität.

Die Verknüpfung sendet insgesamt ein Paar bestehend aus Teilmengen und auf

Wir behaupten

(und entsprechend für die zweite Komponente). Dabei ist die Inklusion klar. Wenn umgekehrt ist, so ist und . Wegen und der Disjunktheit von und kann nicht zu gehören, also ist . Daher ist auch die Identität.


Aufgabe (2 Punkte)

Es seien natürliche Zahlen mit . Zeige

Gilt

in ?


Lösung

Aufgrund der Abziehregel können wir die Gleichheit dadurch zeigen, dass wir beidseitig dazuaddieren und dafür die Gleichheit zeigen. Diese ergibt sich aus

Die angegebene Beispielgleichung ist in nicht definiert, da der Ausdruck nicht definiert ist.


Aufgabe (1 Punkt)

Es seien Elemente in einem kommutativen Halbring . Berechne


Lösung

Nach dem Distributivgesetz ist


Aufgabe (5 Punkte)

Es sei eine fixierte natürliche Zahl und

Wir betrachten die beiden Verknüpfungen (Maximum und Minimum)

und

Zeige, dass mit diesen beiden Verknüpfungen (mit welchen neutralen Elementen?) ein kommutativer Halbring ist.


Lösung

Die Kommutativität und die Assoziativität der beiden Verknüpfungen ist klar. Das neutrale Element des Maximums ist die und das neutrale Element des Minimums ist , da ja nur Elemente aus vorkommen. Es bleibt also noch das Distributivgesetz zu zeigen, welches bei den gegebenen Verknüpfungen (wir setzen das Maximum als Addition und das Minimum als Multiplikation an)

bedeutet. Dies beweisen wir durch eine Fallunterscheidung. Da die Situation in und symmetrisch ist, können wir annehmen. Bei

ergibt sich links und rechts ebenfalls . Bei

ergibt sich links

und rechts ebenfalls

Bei

ergibt sich links

und rechts ebenfalls


Aufgabe (3 Punkte)

Wir betrachten die Gesamtmenge aller Finger und aller Zehen eines Menschen. Man gebe für jede Faktorzerlegung

eine möglichst natürliche Zerlegung dieser Körperteile in Teilmengen mit je Elemente an.


Lösung

Hier nimmt man die 20 Einzelfinger bzw. Einzelzehen als einelementige Mengen.

Die natürlichste Zerlegung in zweielementige Teilmengen (Paare) ist wohl die in zwei Zehen, zwei Zeigefinger, zwei Mittelfinger, zwei Ringfinger, zwei kleine Finger und entsprechend die Zehenpaare der Füße.

Die natürlichste Zerlegung dieser Körperteile in Teilmengen mit je Elemente ist wohl die, bei der die Daumen zusammen mit den großen Zehen, die Zeigefinger und die Zeigezehen, die Mittelfinger und die Mittelzehen, die Ringfinger und die Ringzehen, sowie die kleinen Finger und kleinen Zehen eine Teilmenge bilden.

Hier nimmt man die einzelnen Hände (also die Finger, die dran hängen) bzw. Füße als Teilmengen.

Hier nimmt man einerseits alle Finger und andererseits alle Zehen als Teilmengen (man könnte auch die linke und die rechte Hälfte nehmen).

Die Gesamtmenge aller Finger und Zehen.


Aufgabe (3 Punkte)

Zeige durch Induktion, dass jede natürliche Zahl eine Zerlegung in Primzahlen besitzt.


Lösung

Wir beweisen die Existenz durch Induktion über .  Für liegt eine Primzahl vor. Bei ist entweder eine Primzahl, und diese bildet die Primfaktorzerlegung, oder aber ist keine Primzahl. In diesem Fall gibt es eine nichttriviale Zerlegung mit kleineren Zahlen . Für diese Zahlen gibt es nach Induktionsvoraussetzung jeweils eine Zerlegung in Primfaktoren, und diese setzen sich zu einer Primfaktorzerlegung für zusammen. 


Aufgabe (4 Punkte)

Es sei eine -elementige Menge und sei

Zeige, dass

ist.


Lösung

Wir zeigen etwas allgemeiner, dass es zwischen zwei endlichen Mengen und , die beide Elemente besitzen, bijektive Abbildungen gibt. Dies zeigen wir durch Induktion nach , 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 Bilder 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 (1 Punkt)

Bestimme die Primfaktorzerlegung von


Lösung

Es ist


Aufgabe (2 Punkte)

Bestimme den Rest von bei Division durch .


Lösung

Die Reste bei Division von durch sind


Aufgabe (2 Punkte)

Siehe Extrablatt.


Lösung Extrablatt/Aufgabe/Lösung


Aufgabe (2 Punkte)

Betrachte im er System mit den Ziffern die Zahl

Wie sieht diese Zahl im Zehnersystem aus?


Lösung

Es ist


Aufgabe (3 Punkte)

Beschreibe einen Algorithmus, der zu einer beliebigen im Dezimalsystem gegebenen Zahl ihren Vorgänger im Dezimalsystem bestimmt.


Lösung

Die Zahl sei durch die Ziffernfolge im Dezimalsystem gegeben. Da ausgeschlossen ist, muss bei die Zahl zumindest zweistellig sein, also . Der Vorgänger zu dieser Zahl wird durch das folgende Verfahren bestimmt.

  1. Wenn ist, so ersetzt man die hinterste Ziffer durch ihren (einstelligen) Vorgänger. Dieser ist durch die Reihenfolge in der Liste bestimmt. Die anderen Ziffern werden übernommen.
  2. Wenn ist, so sei der Index durch die Eigenschaft charakterisiert, dass

    und ist. Da die Zahl nicht selbst ist, muss es ein solches geben. Der Vorgänger ergibt sich, wenn man an den hinteren Stellen die zusammenhängenden Nullen durch Neunen ersetzt, die Ziffer durch ihren einstelligen Vorgänger (gemäß Liste) ersetzt und die übrigen Ziffern beibehält.

Dieses Verfahren ist korrekt, da es den entsprechenden Nachfolgeralgorithmus invertiert.


Aufgabe (2 Punkte)

Führe die Multiplikation mit dem Jalousie-Verfahren durch.


Lösung


Aufgabe (2 (0.5+0.5+0.5+0.5) Punkte)

Bestimme, von welcher Art (im Sinne der Vorlesung) die folgenden Gleichungen sind.


Lösung

  1. Formel (für oder in einer Gruppe),
  2. Bedingungsgleichung,
  3. Elementgleichung,
  4. Definitionsgleichung unter der Voraussetzung .


Aufgabe (3 (1+2) Punkte)

  1. Finde eine quadratische Gleichung der Form

    mit , für die die einzige Lösung ist.

  2. Finde unendlich viele verschiedene quadratische Gleichungen der Form

    mit , für die eine Lösung ist.


Lösung

Für jede ganze Zahl ist generell

Dies führt zu einer quadratischen Gleichung mit und . Wenn man darin gleich setzt, ergibt sich wegen dem ersten Faktor. Somit sind unendlich viele quadratische Gleichungen mit Koeffizienten aus gefunden, die als Lösung besitzen. Wenn man

setzt, so erhält man die quadratische Gleichung

Für diese ist nur eine Lösung.


Aufgabe (2 Punkte)

Sie stehen an einem Klippenrand. Jemand sagt: „Innerhalb der ganzen Zahlen ist der Vorgänger des Nachfolgers und der Nachfolger des Vorgängers das Element selbst. Es ist also beispielsweise egal, ob ich zuerst einen Schritt nach vorne und dann nach hinten mache oder umgekehrt. Machen Sie also ruhig einen Schritt nach vorne.“ Klären Sie diese paradoxe Situation.


Lösung Klippe/Vorgänger und Nachfolger/Aufgabe/Lösung


Aufgabe (3 (1+2) Punkte)

Lucy Sonnenschein unternimmt eine Zeitreise. Sie reist zuerst Stunden nach vorne, dann (immer vom jeweiligen erreichten Zeitpunkt aus) Stunden nach vorne, dann Stunden zurück, dann Stunden zurück, dann Stunden nach vorne und dann Stunden zurück.

  1. Wo befindet sie sich am Ende dieser Zeitreise, wenn die Reise selbst keine Zeit verbraucht?
  2. Wo befindet sie sich am Ende dieser Zeitreise, wenn eine Zeitreise um eine Stunde, egal ob in die Zukunft oder in die Vergangenheit, immer eine Minute verbraucht?


Lösung

  1. Wir rechnen

    also Stunden zurück.

  2. Insgesamt reist sie

    Stunden, das verbraucht also Minuten, also eine Stunde und elf Minuten. Daher befindet sie sich am Ende der Zeitreise im Zeitpunkt vor Stunden und Minuten.


Aufgabe (6 Punkte)

Beweise das Lemma von Bezout für teilerfremde natürliche Zahlen und durch Induktion über das Maximum von und .


Lösung

Wir beweisen die Aussage durch Induktion über das Maximum von und , wobei wir ohne Einschränkung wählen können. Wenn das Maximum ist, so sind beide Zahlen und somit nicht teilerfremd. Wenn das Maximum ist, so ist und somit ergeben und eine Darstellung der . Es seien nun teilerfremd, und die Aussage sei für alle Zahlenpaare, deren Maxima kleiner als sind, schon bewiesen. Dann ist , da bei die beiden Zahlen nicht teilerfremd sind. Ebenso können wir ausschließen. Wir betrachten das Zahlenpaar und wollen darauf die Induktionsvoraussetzung anwenden. Das Maximum dieses neuen Paares ist jedenfalls kleiner als . Allerdings müssen wir, damit die Induktionsvoraussetzung wirklich angewendet werden kann, wissen, dass auch und teilerfemd sind. Dazu führen wir einen Widerspruchsbeweis.  Nehmen wir also an, dass und nicht teilerfremd sind. Dann gibt es eine natürliche Zahl , die sowohl als auch teilt. Dies bedeutet wiederum, dass es natürliche Zahlen mit und gibt. Doch dann ist

ebenfalls ein Vielfaches von , im Widerspruch zur Teilerfremdheit von und .  Die Induktionsvoraussetzung ist also auf und anwendbar und somit gibt es ganze Zahlen mit

Dann ist aber auch

und wir haben eine Darstellung der mit und gefunden.


Aufgabe (3 Punkte)

Bestimme in mit Hilfe des euklidischen Algorithmus den größten gemeinsamen Teiler von und und schreibe die beiden Zahlen als Vielfache des größten gemeinsamen Teilers.


Lösung

Es ist

Der größte gemeinsame Teiler ist also . Aus den Rechnungen erhält man

und


Aufgabe (3 Punkte)

Diskutiere Unterschiede und Gemeinsamkeiten zwischen der Abziehregel und der Kürzungsregel auf .


Lösung Abziehregel/Kürzungsregel/Vergleich/Aufgabe/Lösung