Diskrete Mathematik (D-ITET)

ETH Zürich
Institut für Theoretische Informatik
Prof. Dr. Emo Welzl
Dr. Johannes Lengler
HS 2014
Lösungsvorschlag zu Übungsblatt 1
Diskrete Mathematik (D-ITET)
Aufgabe 1
(a) Es gibt 36 viele 3 × 2 Matrizen mit Einträgen aus {0, 1, 2} und 26 3 × 2 Matrizen mit Einträgen
aus {0, 1}. Um die Anzahl aller Matrizen mit Einträgen aus {0, 1, 2} mit mindestens einer 2
zu erhalten, können wir die Anzahl aller Matrizen mit Einträgen aus {0, 1, 2} betrachten und
die Anzahl aller Matrizen, die keine 2 enthalten abziehen. Da eine {0, 1, 2} Matrix, die keine
2 enthält, eine {0, 1} Matrix ist, erhalten wir 36 − 26 = 729 − 64 = 665.
(b) Die richtige Formel lautet
3n − 3 · 2n + 3.
Begründung: Insgesamt gibt es 3n verschiedene Folgen der Länge n. Sei m die Anzahl der
Folgen, welche nicht alle drei Zeichen enthalten. Dann ist die gesuchte Anzahl 3n − m.
Um m zu berechnen, betrachten wir die folgenden drei Mengen. Sei A die Menge der Folgen,
welche nur aus $ und # bestehen, B die Menge der Folgen, welche nur aus $ und @ bestehen,
sowie C die Menge der Folgen, welche nur aus # und @ bestehen. Es gilt |A| = |B| = |C| = 2n .
Mit Hilfe von A, B und C lässt sich m ausdrücken als |A ∪ B ∪ C|. Nach dem Prinzip der
Inklusion-Exklusion gilt
|A ∪ B ∪ C| = |A| + |B| + |C| − |A ∩ B| − |A ∩ C| − |B ∩ C| + |A ∩ B ∩ C|.
Es ist einfach zu sehen, dass |A ∩ B| = |A ∩ C| = |B ∩ C| = 1, da zum Beispiel A ∩ B nur
die Folge $$ . . . $ enthält. Die Menge A ∩ B ∩ C enthält gar kein Element. Somit erhalten wir
m = 3 · 2n − 3 und damit die obige Formel.
Aufgabe 2
• Wir bezeichnen einen Schritt nach rechts mit dem Buchstaben r und einen Schritt nach
oben mit o. Jeder Weg von (0, 0) nach (4, 4) ist nun eindeutig durch ein Wort der Länge
acht darstellbar, wobei dieses Wort aus je vier r’s und vier o’s besteht, also z.B. rooroorr.
Die Aufgabe ist damit auf das Problem reduziert, zu bestimmen auf wieviele verschiedene
Arten man vier ununterscheidbare Symbole (rrrr) auf acht Plätzen anordnen kann, bzw. zu
bestimmen wieviele vier-elementige Teilmengen von {1, 2, 3, 4, 5, 6, 7, 8} es gibt. Bekanntlich
ist dies 84 = 70.
• Hierzu berechnen wir zunächst die Anzahl w1 der Wege von (0, 0) nach (2, 1) sowie
die
Anzahl w2 der Wege von (2, 1) nach (4, 4). Analog zum ersten Fall erhalten wir w1 = 31 = 3
und w2 = 53 = 10. Jedes Paar solcher Wege können wir zusammenfügen zu einem Pfad von
(0, 0) nach (4, 4), der über (2, 1) läuft. Umgekehrt können wir jeden Pfad von (0, 0) nach
(4, 4), der über (2, 1) läuft, in die beiden Teilstücke von (0, 0) nach (2, 1) sowie von (2, 1)
nach (4, 4) zerlegen. Insgesamt stehen daher die Wege von (0, 0) nach (4, 4) über (2, 1) in
Bijektion zu den Paaren von Wegen von (0, 0) nach (2, 1) und von (2, 1) nach (4, 4). Offenbar
gibt es genau w1 · w2 = 30 viele solcher Paare, und somit auch 30 Wege von (0, 0) nach (4, 4)
über (2, 1).
1
• Aus dem ersten Teil wissen wir, dass es genau 70 Wege von (0, 0) nach (4, 4) gibt. Hiervon
müssen wir diejenigen
abziehen, die über (3, 3) führen. Analog zum vorigen Punkt
Wege
sehen wir, dass es 63 · 21 = 20 · 2 = 40 solcher Wege gibt. Die anderen 70 − 40 = 30 Wege
führen demzufolge nicht über (3, 3).
Aufgabe 3
Da die Gerade keinen Punkt aus S enthalten darf, teilt sie die sieben Punkte in zwei disjunkte
Mengen A und B auf. Auf der einen Seite der Geraden sind k Punkte (k ∈ {0, 1, 2, 3}), auf der
anderen Seite folglich 7 − k Punkte. Verbindet man zwei Punkte aus A (oder zwei Punkte aus B),
so schneidet dieses Segment die Gerade nicht. Hingegen ergibt jedes Segment von einem Punkt aus
A zu einem Punkt aus B einen Schnittpunkt mit der Geraden. Insgesamt erhält man so k · (7 − k)
Schnittpunkte. Diese Zahl wird durch k = 3 maximiert und nimmt den Wert 12 an.
Allgemein: Sei S = {(i, i2 ) : i = −m, . . . , −1, 0, 1, . . . , m}. Man hat nun 2m + 1 =: n Punkte. Auf
dieselbe Art wie vorher bekommt man k · (n − k) Schnittpunkte (k ∈ {0, 1, . . . , (n − 1)/2}). Für
k = (n − 1)/2 wird diese Zahl maximiert und nimmt den Wert (n2 − 1)/4 an.
Aufgabe 4
(a) Die Menge {true,false}3 besteht aus 23 = 8 Elementen. Jede Funktion kann man sich als
Tabelle vorstellen, bei denen den 8 Elementen jeweils true oder false zugeordnet wird. Da man
für jedes der 8 Elemente 2 Möglichkeiten hat, erhält man 28 verschiedene Funktionen.
(b) Die Menge {true,false}2 enthält 4 Elemente. Wir interessieren uns für Funktionen, die zwei
dieser Elemente true zuordnen und zwei Elementen false. Wenn wir wissen,
welchen Elementen true zugeordnet wird, kennen wir die gesamte Funktion. Es gibt 42 = 6 Möglichkeiten
die beiden Elemente auszuwählen, denen true zugeordnet wird. Dies ist die Anzahl der uns
interessierenden Funktionen.
(c) Jeder der fünf Bausteine hat drei Schaltzustände. Damit kann die Schaltung höchstens 35
verschiedene Funktionen realisieren. Das Produkt der Firma hält nicht was es verspricht, da
35 = 243 < 28 = 256.
2

Download Report