MSG-Hausaufgaben Serie 32

MSG-Hausaufgaben Serie 32
Abgabe: 06.07.2016
Lucas Mann
Diese Hausaufgabenserie enthält für jedes in diesem Schuljahr behandelte Thema eine relativ
schwierige Aufgabe. Suche dir zwei oder drei der Aufgaben aus und löse sie.
Aufgabe 1. Gesucht ist ein einfacher Graph G, also ein Graph, der höchstens eine Kante zwischen
zwei Knoten hat und bei dem jede Kante zwei verschiedene Knoten verbindet. Es sei bekannt, dass
G genau 7 Knoten hat, wovon die ersten fünf Knoten die Grade 1, 1, 2, 2, 2 haben. Finde alle Möglichkeiten für die verbleibenden beiden Knotengrade, in jedem der folgenden Fälle:
a) G ist ein Baum (d.h. G ist zusammenhängend und enthält keinen Zyklus).
b) G besitzt einen Eulerweg (also ein Weg, der alle Kanten genau einmal benutzt).
Beweise in beiden Fällen, warum es keine weitere Möglichkeit gibt und finde für jede gefundene
Möglichkeit einen Beispielgraphen G.
Aufgabe 2. Seien a und b zwei nichtnegative reelle Zahlen mit a + b = 1. Zeige unter Benutzung
der Ungleichung vom arithmetischen und geometrischen Mittel, dass die folgende Ungleichung
erfüllt ist:
3ab + b ≤ 2 − a (1 + b).
Aufgabe 3. Die Hill-Chiffre ist eine Verschlüsselungsmethode, die wie folgt funktioniert: Der Schlüssel besteht aus vier Zahlen a, b, c, d in Z26 , die man üblicherweise in einer sogenannten Matrix
¡a b ¢
c d notiert. Um nun einen Text zu verschlüsseln, zerlegt man den Text zunächst in Zweierblöcke
und verschlüsselt jeden Zweierblock einzeln. Sei x y ein solcher Zweierblock, wobei x und y Buchstaben sind, die wir als Elemente von Z26 auffassen (A = 0, B = 1,C = 2, . . . ). Die Verschlüsselung
generiert einen neuen Block x 0 y 0 mit Buchstaben x 0 und y 0 gemäß der Formel
x 0 = ax + b y,
y 0 = cx + d y
(die Rechnung findet in Z26 statt).
¡
¢
a) Verschlüssle den Text DIE HILLCHIFFRE mit dem Schlüssel 10 10
5 .
b) Untersuche den Entschlüsselungsprozess: Wie kann man x und y aus x 0 und y 0 zurückgewinnen, wenn man den Schlüssel kennt? Du darfst der Einfachheit halber davon ausgehen,
dass c = 0. Welche Voraussetzungen müssen a und d erfüllen, damit man x und y eindeutig
bestimmen kann?
c) Wie sicher ist die Hill-Chiffre? Hast du eine Idee, wie man einen mit der Hill-Chiffre verschlüsselten Text knacken könnte?
Aufgabe 4. Gesucht ist eine reelle Zahl x mit x 5 − 4x 3 + x + 1 = 0. Aus der Theorie der Algebra
weiß man, dass es unmöglich ist, die Lösungen dieser Gleichung exakt anzugeben (also als Term
bestehend aus den Grundoperationen und Wurzeln). Aber man kann natürlich versuchen, eine
Näherung für eine Lösung zu finden.
Dir sei bekannt, dass die obige Gleichung genau eine Lösung zwischen 0 und 1 hat. Schreibe
einen Python-Algorithmus, der eine möglichst gute Näherung für diese Lösung findet.
Tipp: Eine mögliche Herangehensweise ist die folgende: Der Term auf der linken Seite der Gleichung ist positiv bei x = 0 und negativ bei x = 1. Wenn man x nun langsam von 0 bis 1 erhöht,
1
muss der Term also irgendwann einen Vorzeichenwechsel durchführen. Dieser Vorzeichenwechsel geschieht offenbar genau bei der gesuchten Lösung.
Aufgabe 5. Herr A geht jeden Morgen zwischen 7.15 Uhr und 7.20 Uhr aus dem Haus. Normalerweise kommt er gegen 17.30 Uhr nach Hause. Eines Tages kommt er kurz nach 15.30 Uhr zurück
und er stellt fest, dass die Zeiger seiner Uhr im Flur genau so stehen wie beim Verlassen des Hauses, nur dass der kleine und der große Zeiger vertauscht sind.
Ermittle die Uhrzeiten, für welche die Beobachtung von Herrn A zutrifft, auf die Sekunde (abgerundet) genau.
Aufgabe 6. Zu einer positiven ganzen Zahl m bezeichne ϕ(m) die Anzahl der in (Zm , ·) invertierbaren Elemente (also die Anzahl der Zahlen a in {0, 1, . . . , m − 1} für die es eine ganze Zahl x mit
ax ≡ 1 mod m gibt).
Seien nun m und n zwei teilerfremde positive ganze Zahlen.
a) Sei a ∈ Zmn invertierbar. Zeige, dass dann (a mod m) in Zm und (a mod n) in Zn invertierbar sind (jeweils bezüglich der Verknpüfung ·).
b) Sei umgekehrt a ∈ Zmn derart, dass (a mod m) in Zm und (a mod n) in Zn jeweils invertierbar sind. Zeige, dass dann a in Zmn invertierbar ist.
Tipp: Chinesischer Restsatz.
c) Folgere aus den letzten beiden Teilaufgaben, dass ϕ(mn) = ϕ(m) · ϕ(n).
Aufgabe 7. Die Summe 1 + 2 + · · · + n der ersten n natürlichen Zahlen wird als n-te Dreieckszahl
D n bezeichnet, denn sie beschreibt die Anzahl der Punkte in einem Dreieck mit Seitenlänge n, wie
folgt abgebildet:
...
¡ ¢
Bekanntlich gilt D n = n+1
2 .
Die Summe D 1 + D 2 + · · · + D n wird als n-te Tetraederzahl Tn bezeichnet, da sie die Anzahl der
Punkte in einem Tetraeder der Seitenlänge n zählt (Warum?).
a) Berechne die ersten fünf Tetraederzahlen.
¡ ¢
b) Finde eine allgemeine Formel für Tn , ähnlich wie die Formel D n = n+1
2 .
Tipp: Betrachte das Pascalsche Dreieck.
Aufgabe 8. In einem Kreis k halbiere der Durchmesser AB die Sehne C D. Ferner sei P ein beliebiger Punkt auf der Sehne C D und sei Q der von A verschiedene Schnittpunkt von AP mit k. Zeige,
2
dass unabhängig von der genauen Lage von P immer gilt: AP · AQ = AC .
Tipp: Sei E der Schnittpunkt von AB und C D. Zeige zunächst, dass gilt:
C P · P D = (C E − PE )(C E + PE ).
Benutze außerdem den Sehnensatz und den Satz des Pythagoras.
Aufgabe 9. Zu einer positiven ganzen Zahl m sei Z∗m die Menge der zu m teilerfremden Zahlen in
Zm .
a) Zeige, dass Z∗m genau diejenigen Elemente von Zm enthält, die in (Zm , ·) invertierbar sind.
Tipp: Ein Element a ∈ Zm ist genau dann invertierbar in (Zm , ·), wenn es ein x ∈ Zm mit
ax = 1 gibt. Dies ist gleichbedeutend damit, dass es ein x ∈ Z mit ax ≡ 1 mod m gibt. Dies
wiederum ist gleichbedeutend damit, dass es ganze Zahlen x und y mit ax + m y = 1 gibt.
Nun verwende den euklidischen Algorithmus.
b) Zeige, dass (Z∗m , ·) eine Gruppe ist. Du musst unter anderem zeigen, dass Z∗m unter · abgeschlossen ist, das heißt für a, b ∈ Z∗m gilt auch a · b ∈ Z∗m .
Insbesondere sehen wir, dass das in Aufgabe 6 eingeführte ϕ(m) gleich der Anzahl der zu m teilerfremden Zahlen in Zm ist (denn dies ist nach Teilaufgabe (a) ja gleich der Anzahl der invertierbaren
Zahlen in Zm ).
2

Download Report