Zum Inhalt springen

Kurs:Diskrete Mathematik (Osnabrück 2020)/Arbeitsblatt 8

Aus Wikiversity



Die Pausenaufgabe

Es stehen zwei Eimer ohne Markierungen zur Verfügung, ferner eine Wasserquelle. Der eine Eimer hat ein Fassungsvermögen von und der andere ein Fassungsvermögen von Litern. Zeige, dass man allein durch Auffüllungen, Ausleerungen und Umschüttungen erreichen kann, dass in einem Eimer genau ein Liter Wasser enthalten ist.




Übungsaufgaben

Finde eine Darstellung der für das Zahlenpaar und .



Finde eine Darstellung der für die folgenden Zahlenpaare: und ; und ; und .



Die Wasserspedition „Alles im Eimer“ verfügt über -, - und -Liter Eimer, die allerdings keine Markierungen haben. Sie erhält den Auftrag, insgesamt genau einen Liter Wasser von der Nordsee in die Ostsee zu transportieren. Wie kann sie den Auftrag erfüllen?



Es seien und teilerfremde natürliche Zahlen. Es stehen beliebig viele Eimer ohne Markierungen zur Verfügung, deren Fassungsvermögen bzw. ist. Zeige, dass man allein durch Auffüllungen, Ausleerungen und Umschüttungen erreichen kann, dass in einem Eimer genau ein Liter Wasser enthalten ist.



Es stehen zwei Eimer ohne Markierungen zur Verfügung, ferner eine Wasserquelle. Der eine Eimer hat ein Fassungsvermögen von und der andere ein Fassungsvermögen von Litern, wobei und teilerfremd seien. Zeige, dass man allein durch Auffüllungen, Ausleerungen und Umschüttungen erreichen kann, dass in einem Eimer genau ein Liter Wasser enthalten ist.



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



Zeige, dass es zu ganzen Zahlen mit eindeutig bestimmte ganze Zahlen mit und mit

gibt.



Es seien positive Zahlen und es sei

mit und zwischen und . Wie erhält man daraus die Division mit Rest von durch ?



Zeige, dass es zu ganzen Zahlen mit eindeutig bestimmte ganze Zahlen mit

und mit

gibt.



Es seien mit und . Zeige, dass der Rest von bei Division durch gleich dem Rest von bei Division durch ist.



Es sei eine positive natürliche Zahl. Es seien natürliche Zahlen und es seien bzw. die Reste von bzw. bei Division durch . Zeige, dass der Rest von bei Division durch gleich dem Rest von bei Division durch ist. Formuliere und beweise die entsprechende Aussage für die Multiplikation.



Zeige, dass für zwei ganze Zahlen die folgenden Beziehungen äquivalent sind.

  1. teilt (also ).
  2. .
  3. .



In welcher Beziehung steht Aufgabe 8.13 zu Lemma 7.16?



Es seien ganze Zahlen und die davon erzeugte Untergruppe. Zeige, dass eine ganze Zahl genau dann ein gemeinsamer Teiler der ist, wenn ist, und dass genau dann ein größter gemeinsamer Teiler ist, wenn ist.



Es seien (beliebige viele) gemalte Pfeile der Länge und der Länge gegeben. Wie muss man die Pfeile hintereinanderlegen (wobei immer ein Pfeilende an der Pfeilspitze des Vorgängerpfeils anliegt), damit insgesamt ein Gesamtpfeil der Länge entsteht?



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

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



Auf den ganzen Zahlen lebe eine Kolonie von Flöhen, und jeder Flohsprung geht fünf Einheiten weit (in beide Richtungen). Wie viele Flohpopulationen gibt es? Wie kann man einfach charakterisieren, ob zwei Flöhe zur gleichen Population gehören oder nicht?



Bestimme in mit Hilfe des euklidischen Algorithmus den größten gemeinsamen Teiler von und .



Bestimme in mit Hilfe des euklidischen Algorithmus den größten gemeinsamen Teiler von und .



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.



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.



Es sei eine Primzahl. Zeige, dass es eine natürliche Zahl der Form (im Dezimalsystem)

gibt, die ein Vielfaches von ist.



Kaninchen werden bekanntlich immer zur Monatsmitte geboren, die Tragzeit beträgt einen Monat und die Geschlechtsreife erreichen sie im Alter von zwei Monaten. Jeder Wurf besteht aus genau einem Paar, und alle leben ewig.

Wir starten im Monat mit einem Paar, das einen Monat alt ist. Es sei die Anzahl der Kaninchenpaare im -ten Monat, also , . Beweise durch Induktion die Rekursionsformel

Diese Zahlfolge nennt man die Folge der Fibonacci-Zahlen. Wie viele der Paare sind im -ten Monat reproduktionsfähig?


Die Fibonacci-Zahlen sind somit


Wende auf zwei aufeinander folgende Fibonacci-Zahlen den euklidischen Algorithmus an. Welche Gesetzmäßigkeit tritt auf?



Beweise durch Induktion die Simpson-Formel oder Simpson-Identität für die Fibonacci-Zahlen . Sie besagt (für )



Es seien ganze Zahlen. Zeige, dass

ist, wobei das kleinste gemeinsame Vielfache der ist.



Zeige, dass für natürliche Zahlen folgende Aussagen gelten.

  1. Für teilerfremde ist
  2. Es gibt mit

    wobei teilerfremd sind.

  3. Es ist
  4. Es ist



Es sei die Menge der Primzahlen und die Menge aller Abbildungen von nach . Wir betrachten die Abbildung

die jeder natürlichen Zahl das Exponententupel zuordnet. Man betrachtet also die eindeutige Primfaktorzerlegung

wobei sich das Produkt über alle Primzahlen erstreckt und wobei nur endlich viele Exponenten ungleich sind.

  1. Zeige, dass injektiv ist.
  2. Bestimme das Bild von .
  3. Es sei mit der Teilbarkeitsrelation und mit der Produktordnung versehen. Zeige, dass eine ordnungsvolltreue Abbildung ist.



Zeige, dass es ganze Zahlen derart gibt, dass

gilt. Finde solche Zahlen.



Finde ganze Zahlen derart, dass

gilt.



Es seien positive natürliche Zahlen. Die Summe der Stammbrüche ist dann

  1. Zeige, dass bei teilerfremd diese Darstellung gekürzt ist.
  2. Zeige, dass im Allgemeinen diese Darstellung nicht gekürzt sein muss.



Zeige, dass jede rationale Zahl eine eindeutige Darstellung der Form

besitzt, wobei das (endliche) Produkt sich über Primzahlen erstreckt und die Exponenten sind.



Es sei diejenige Teilmenge, die aus allen natürlichen Zahlen besteht, die bei Division durch den Rest besitzen, also . Zeige, dass man innerhalb von auf zwei verschiedene Arten in Faktoren zerlegen kann, die in nicht weiter zerlegbar sind.




Aufgaben zum Abgeben

Aufgabe (2 Punkte)

Bestimme in mit Hilfe des euklidischen Algorithmus den größten gemeinsamen Teiler von und .



Aufgabe (4 Punkte)

Bestimme den größten gemeinsamen Teiler von und , sowie eine Darstellung desselben als eine Linearkombination der gegebenen Zahlen.



Aufgabe (2 Punkte)

Es seien ganze Zahlen. Zeige, dass die Menge

eine Untergruppe von ist.



Aufgabe (4 Punkte)

Es seien teilerfremde natürliche Zahlen. Zeige, dass jede natürliche Zahl

eine Darstellung

mit besitzt.



Aufgabe (3 Punkte)

Alle Flöhe leben auf einem unendlichen Zentimeter-Band. Ein Flohmännchen springt bei jedem Sprung cm und die deutlich kräftigeren Flohweibchen springen mit jedem Sprung cm. Die Flohmännchen Florian, Flöhchen und Carlo sitzen in den Positionen und . Die Flohweibchen Flora und Florentina sitzen in Position bzw. . Welche Flöhe können sich treffen?



Aufgabe (5 Punkte)

Wir betrachten eine digitale Uhr, die Stunden, Minuten und Sekunden anzeigt. Zur Karnevalszeit läuft sie aber nicht in Sekundenschritten, sondern addiert, ausgehend von der Nullstellung, in jedem Zählschritt immer Stunden, Minuten und Sekunden dazu. Wird bei dieser Zählweise jede mögliche digitale Anzeige erreicht? Nach wie vielen Schritten kehrt zum ersten Mal die Nullstellung zurück?



Aufgabe (3 Punkte)

Es seien und verschiedene Primzahlen. Zeige, dass es ganze Zahlen derart gibt, dass

gilt.



<< | Kurs:Diskrete Mathematik (Osnabrück 2020) | >>

PDF-Version dieses Arbeitsblattes

Zur Vorlesung (PDF)