Übung 6

ETH Zürich, D-INFK
HS 2015, 19. Oktober 2015
Prof. Ueli Maurer
Daniel Tschudi
Diskrete Mathematik
Übung 6
6.1
Abzählende Kombinatorik
(9 Punkte)
a) (?) In einer Prüfung gibt es 7 Aufgaben. Jede Aufgabe wird von genau 78 Studenten
korrekt gelöst und jeder Student löst genau 3 Aufgaben korrekt. Wie viele Studenten
nehmen an der Prüfung teil?
(1 Punkt)
b) (? ?) Bestimmen Sie die Anzahl ganzer Zahlen n, 1 ≤ n ≤ 1000, die durch keine der
Zahlen 3, 5 und 11 teilbar sind, indem Sie das Prinzip von Inklusion und Exklusion
anwenden.
(3 Punkte)
Hinweis: Eine natürliche Zahl ist genau dann durch das Produkt verschiedener Primzahlen teilbar, wenn sie durch jede dieser Primzahlen teilbar ist.
c) (? ? ?) Auf wie viele Arten können 20 identische Bälle in 4 unterscheidbare Urnen so
verteilt werden, dass keine Urne leer bleibt?
(3 Punkte)
d) (? ? ?) Auf wie viele verschiedene Arten kann man die sechs Seiten eines Würfels mit
jeweils einer von sechs Farben färben, ohne eine Farbe mehrfach zu benutzen? Zwei
Färbungen gelten dabei genau dann als verschieden, wenn sich die dadurch entstandenen Würfel nicht durch Rotationen ineinander überführen lassen.
(2 Punkte)
6.2
Wahlen (? ? ?)
Auf einer einsamen Insel finden Wahlen statt.
a) Zur Wahl des Inselrats (sieben Sitze) treten die Affenpartei (AP), die Bananenpartei
(BP) und die Piratenpartei (PP) an. Für die AP kandidieren zwei, für die BP sieben
und für die PP fünf Personen. Die Kandidaten sind unterscheidbar und kandidieren
jeweils nur für eine Partei. Wie viele Möglichkeiten gibt es, den Inselrat zu wählen,
falls keine Partei eine absolute Mehrheit im Rat erreichen wird?
b) Bei der Präsidentenwahl gibt es fünf Kandidaten. Die 11 Stimmberechtigten können
jeweils höchstens einen Kandidaten wählen. Wie viele mögliche Wahlausgänge (Stimmverteilung) gibt es, falls kein Kandidat mindestens 6 Stimmen erreicht?
6.3
Die Erde (? ?)
Gegeben sind fünf beliebige Punkte auf der Erdoberfläche. Zeigen Sie, dass eine Möglichkeit
existiert, die Erde in zwei Hälften zu teilen, so dass mindestens vier Punkte in der gleichen
Hemisphäre liegen (Punkte auf der Schnittebene zählen für beide Hemisphären).
6.4
Bücher und Ritter (? ? ? ?)
a) In einem Regal der Bibliothek einer einsamen Insel stehen n Bücher in einer Reihe.
Ein sonderbarer Bibliothekar möchte nie zwei benachbarte Bücher aus dem Regal
nehmen. Wie viele Möglichkeiten hat er, k ≤ n Bücher so auszuwählen, dass keine
zwei davon benachbart sind?
b) Es sitzen n Ritter an der Tafelrunde, das heisst jeder Ritter hat einen linken und einen
rechten Nachbarn. König Artus benötigt k ≤ n Ritter für seine Suche nach dem Heiligen Gral. Wie viele Möglichkeiten hat er, diese auszuwählen, ohne dass zwei benachbarte Ritter gewählt werden?
6.5
(12 Punkte)
Abzählbarkeit
a) Untersuchen Sie die folgenden Mengen auf Abzählbarkeit. Beweisen Sie Ihre Antworten.
i) (?) Die Menge aller Eiffel-Programme.
ii) (? ?) Die Vereinigung von abzählbar vielen abzählbaren Mengen.
(1 Punkt)
(2 Punkte)
iii) (? ?) Die Menge der unendlichen Folgen über {0, 1, . . . , 9}.
(2 Punkte)
iv) (? ? ?) Die Menge der Äquivalenzrelationen auf N.
(4 Punkte)
b) (? ? ?) Sie müssen ein U-Boot versenken. Das U-Boot fährt mit konstanter Geschwindigkeit v ∈ Z und befindet sich zum Zeitpunkt t ∈ N an der Position v · t + s0 ,
wobei s0 ∈ Z die Startposition ist. Die Grössen v und s0 sind Ihnen nicht bekannt. Sie
können zu jedem Zeitpunkt t ∈ N einen Torpedo auf eine Position s ∈ Z schiessen.
Falls sich das U-Boot gerade dort befindet, sinkt es. Gibt es eine Strategie, um das
U-Boot in endlicher Zeit zu versenken?
(3 Punkte)
Abgabe am 26. Oktober 2015
Korrigiert werden Aufgaben 6.1 und 6.5.

Download Report