Diskrete Modellierung
Wintersemester 2015/2016
Dipl.-Inf. Bert Besser
Mario Holldack
Prof. Dr. Georg Schnitger
Hannes Seiwert, M.Sc.
Institut für Informatik
AG Theoretische Informatik
Ausgabe: 19.11.15
Abgabe: 26.11.15
Übung 6
Aufgabe 6.1. Vollständige Induktionen
(18+12 = 30 Punkte)
a) Zeigen Sie jeweils mit vollständiger Induktion über n:
Pn−1
2
i)
i=0 (2i + 1) = n gilt für alle n ∈ N>0 .
ii) (1 + x)n ≥ 1 + nx gilt für alle n ∈ N, falls x ∈ R und x ≥ −1.
iii) an = 2n +3n gilt f.a. n ∈ N>0 , wobei a1 := 5, a2 := 13 und an+1 := 5an −6an−1 f.a. n ≥ 2.
b) Wir definieren die aussagenlogische Formel ϕn für alle n ∈ N>0 wie folgt:
ϕ1 := V1
ϕn+1 := ϕn → Vn+1
f.a. n ∈ N>0
Betrachten Sie die Belegung B : Avar → {0, 1} mit B(Vi ) :=
1, i ist ungerade,
0, i ist gerade.
i) Bestimmen Sie die Formel ϕ4 .
ii) Berechnen Sie Jϕ3 KB .
iii) Zeigen Sie mit vollständiger Induktion über n: Für alle n ∈ N>0 gilt Jϕn KB = B(Vn ).
Aufgabe 6.2. Rekursionsgleichungen verstehen und lösen
(5+5+5+5 = 20 Punkte)
Lösen Sie die folgenden Rekursionsgleichungen auf, d. h. finden Sie jeweils einen (möglichst einfachen)
geschlossenen Ausdruck für an und geben Sie jeweils eine kurze Begründung an.
Beispiel. Es gelte a1 := 1 und an+1 := an + 1 f.a. n ∈ N>0 . Dann lautet die Lösung der Rekursionsgleichung:
an = n
Begründung:
an = an−1 + 1 = an−2 + 1 + 1 = · · · = an−(n−1) +1
+ · · · + 1} = a1 + n − 1 = n
| + 1 {z
|{z}
(n−1)-mal
=1
a) a0 := 0, an+1 := 3 + an f.a. n ∈ N.
b) a1 := 0, an+1 := n + an f.a. n ∈ N>0 .
1
c) a1 := 1, an+1 := 1 − n+1
·an f.a. n ∈ N>0 . Bestimmen Sie zuerst a2 , a3 und a4 und geben
Sie dann einen geschlossenen Ausdruck für an an.
d) a1 := 2, an+1 := (an )2 f.a. n ∈ N>0 . Bestimmen Sie zuerst a2 , a3 und a4 und geben Sie dann
einen geschlossenen Ausdruck für an an, vorzugsweise als Zweierpotenz.
Bitte wenden!
1
Aufgabe 6.3. Rekursiv denken
((4+6+6)+(3+8+3) = 30 Punkte)
Die beiden Trolle Höllga Knochenbeißer und Trolgar Keulenhau sind frisch gebackene Eltern eines
mit allen drei Zahnreihen grinsenden 94 kg-Säuglings namens Sulpur. Nach alter Troll-Tradition wird
Sulpur von der ganzen Troll-Familie reich beschenkt.
a) Onkel Raudishor Grubentod schenkt Sulpur eine kleine Modelleisenbahn mit kleinen und
großen Wagen, welche 1 m bzw. 2 m lang sind. Leider kann Sulpur sein neues Geschenk überhaupt nicht ausprobieren, da zwischen den erwachsenen Trollen sofort eine heftige Diskussion
über die Anzahl möglicher Züge der Länge n ∈ N>0 entbrannt ist1 . Raudishor hat sich einen
1 m langen und Höllga einen 2 m langen Wagen geschnappt.
• Raudishor sagt: „Wenn ich nur wüsste, wie viele verschiedene Züge der Länge n − 1 es
gibt, dann wüsste ich auch, wie viele Züge der Länge n es gibt, die mit einem 1 m langen
Wagen beginnen.“
• Höllga sagt: „Und ich kann dieselbe Frage für die Züge beantworten, die mit einem 2 m
langen Wagen beginnen.“
k
Wir repräsentieren einen Zug mit genau k Wagen durch das Tupel z = (z1 , . . . , zk )∈{1,
Pk 2} ,
wobei zi die Länge des i-ten Wagens ist. Die Länge des Zugs ist durch länge(z)= i=1 zi
gegeben2 . Ein Beispiel können Sie Abbildung 1 entnehmen.
R
Abbildung 1: Ein Zug der Länge 5 mit k=4 Wagen und (z1 , z2 , z3 , z4 ) = (1, 2, 1, 1).
Für alle n ∈ N>0 bezeichne an die Anzahl möglicher Züge der Länge genau n, d. h. es gilt
an = |{z ∈ {1, 2}∗ : länge(z) = n}|.
i) Skizzieren Sie alle möglichen Züge der Längen 1, 2, 3 und 4 und bestimmen Sie a1 , a2 , a3
und a4 .
ii) Formulieren Sie eine Rekursionsgleichung für an+1 , indem Sie Raudishors und Höllgas
Gedanken weiterentwickeln. Stellen Sie sicher, dass Ihre Rekursionsgleichung konsistent
zu Ihren Ergebnissen aus Teil i) ist.
iii) Angenommen, jetzt stehen Wagen der Längen 1, 2 und 3 zur Verfügung. Wie lautet nun
die Rekursionsgleichung für an+1 ?
b) Sei n ∈ N>0 die Anzahl von Sulpurs Geschenken. Laut Troll-Tradition muss Sulpur sich von
den n vorhandenen Geschenken k Stück aussuchen (0 ≤ k ≤ n). Wie groß ist die Qual der
Wahl, d. h. wie viele k-elementige Teilmengen der Menge {1, 2, . . . , n} gibt es?
• Papa Trolgar rät Sulpur: „Wenn du die Modelleisenbahn behältst, dann musst du nur
noch k−1 aus n−1 Geschenken auswählen.“ Sulpurs Frage „Und wenn ich die Bahn nicht
behalten möchte?“ bleibt unbeantwortet.
Sei T (n, k) = |{A : A ⊆ {1, 2, . . . , n}, |A| = k}| die Anzahl k-elementiger Teilmengen von
{1, 2, . . . , n}.
i) Bestimmen Sie die Potenzmenge P({1, 2, 3}) sowie T (3, 0), T (3, 1), T (3, 2) und T (3, 3).
ii) Formulieren Sie eine Rekursionsgleichung für T (n, k), indem Sie Trolgars Idee weiterentwickeln. Bestimmen Sie zunächst die beiden Rekursionsanker T (n, n) und T (n, 0) direkt.
iii) Bestimmen Sie T (3, 2) mithilfe Ihrer Rekursionsgleichung.
Bitte wenden!
1
2
Das weitverbreitete Vorurteil, dass sich Trolle nicht für mathematische Fragestellungen interessieren, ist falsch!
Die Lokomotive bleibt hier der Einfachheit halber unberücksichtigt.
2
Aufgabe 6.4. Nim
(5+15 = 20 Punkte)
Sei n ∈ N>0 beliebig. Im Nim-Spiel liegen zu Anfang n Streichhölzer auf einem Stapel. Zwei Spieler,
Alice und Bob, wechseln sich ab: In jedem Zug darf der ziehende Spieler 1, 2 oder 3 Streichhölzer
vom Stapel nehmen, wobei Alice das Spiel beginnt. Wer das letzte Streichholz, bzw. die letzten zwei
oder drei Streichhölzer nimmt, gewinnt (und der andere Spieler verliert).
a) Wer gewinnt für n = 4, 5, 6 bzw. 7 Streichhölzer, wenn sowohl Alice als auch Bob optimal
spielen?
b) Für welche Anzahlen n kann Alice so spielen, dass sie sicher gewinnt? Bestimmen Sie die Menge
Win := {n ∈ N>0 : Alice gewinnt bei optimaler Spielweise im Nim-Spiel mit n Streichhölzern}.
Beschreiben Sie eine Strategie für Alice für alle Anzahlen n ∈ Win von Streichhölzern und
begründen Sie, warum diese Strategie zum Erfolg führt.
3
© Copyright 2024 ExpyDoc
