Kurs:Diskrete Mathematik (Osnabrück 2020)/Arbeitsblatt 2/kontrolle
- Die Pausenaufgabe
Auf einer Party begrüßen sich manche Gäste mit einem Handschlag, manche nicht. Jede Person merkt sich, wie oft sie im Laufe des Abends eine Hand geschüttelt hat. Zeige, dass die Summe über all diese Zahlen stets gerade ist.
Tipp: Ein Handschütteln ist eine zweielementige Teilmenge. Es ist hier sinnvoll, dieses doppelt zu zählen und einmal als Paar und einmal als zu sehen.
- Übungsaufgaben
Interpretiere Satz 2.1 für den Fall, wo und endliche Mengen sind, ihre Produktmenge ist und
die Projektion auf die zweite Komponente ist.
Wir betrachten die Abbildung
Bestimme für jedes die Urbildmenge und die Anzahl ihrer Elemente.. Bestimme auf verschiedene Arten.
Wir betrachten die Abbildung
Bestimme für jedes die Urbildmenge und die Anzahl ihrer Elemente. Bestimme auf verschiedene Arten.
Kommentar:
Bei einer Abbildung sollte die erste automatische Frage eigentlich immer sein: injektiv? surjektiv? bijektiv? Bei endlichen Elementen sollte man immer direkt nach ihrer Anzahl fragen, oder zumindest nach einer Abschätzung dafür. In diesem Fall stehen links und rechts jeweils Elemente, in diesem Fall könnte die Abbildungen von den numerischen Bedingungen her injektiv sein (und wäre dann nach Lemma 1.5 auch surjektiv). Da die Abbildung das Multiplizieren mit natürlichen Zahlen ist, sollte man sofort an Teilbarkeit, Primzahlen, Primfaktorzerlegung denken. Damit ist sofort klar, dass die Abbildung nicht surjektiv ist, da die Primzahlen größer als nicht getroffen werden. Es wird also nicht getroffen. Das ist aber noch nicht alles. Auch
und und werden nicht getroffen. Wegen der Nichtsurjektivität ist auch nicht injektiv. Dies ist auch direkt klar und links eine Produktmenge steht, wo ja die Paare wie und verschieden sind, aber beide auf gehen. Ferner hat man noch das Phänomen, dass alle auf gehen. Man lasse sich hier auch nicht von der Eindeutigkeit der Primfaktorzerlegung in die Irre führen.
Bestimme wir nun für jedes die Anzahl der Elemente in der Urbildmenge . Dabei geht man möglichst systematisch vor. Knüpfen wir an die obige Überlegung zu nicht surjektiv an, also bestimmen wir die Elemente rechts mit leerer Faser. Es geht um alle Zahlen zwischen und , die man nicht als ein Produkt mit zwei Faktoren schreiben kann, die beide aus bis kommen. Das sind, wie oben erwähnt, die Primzahlen größer als , und die zerlegbaren Zahlen, wo es keine Faktorzerlegung in die kleine Faktoren gibt. Dies heißt, dass ein Faktor zumindest ist. Gehen wir diese ohne die Primzahlen durch.
ist im Bild, ist im Bild, ist im Bild, ist im Bild, ist im Bild, ist nicht im Bild, da eine Primzahl ist, ist im Bild, ist im Bild (es gibt auch die Faktorzerlegung , die spielt aber in der derzeitigen Abbildung keine Rolle). ist nicht im Bild, da beide nichttriviale Faktorzerlegung mit zwei Faktoren einen zu goßen Faktor benötigen, das haben wir oben übersehen, ist im Bild, ist nicht im Bild, ist nicht im Bild, ist im Bild. Die Fasern zu
sind also leer.
Zu welchen Zahlen sind die Fasern einelement? Wegen der Produktmenge kommen dafür nur Quadratzahlen in Frage. Hier spielt aber die eine besondere Rolle, da für die die Faser aus Elementen besteht. Die Quadratzahlen
haben genau ein Urbild.
Genau zwei Urbilder. Diese Zahlen sind insbesondere Produkte von zwei verschiedenen Zahlen aus bis . Da es
zweielementige Teilmengen gibt, erhalten wir Produkte, für die es (wegen der Vertauschungsmöglichkeit) zumindest Urbilder gibt. Dab ist die aber wieder dabei, das dürfen wir nicht mehrfach zählen. Die Zahlen
besitzen genau Urbilder. Die Summe ist nach Satz 2.1 gleich der Mächtigkeit der Ausgangsmenge, also gleich . Dies ergibt sich auch als
Es seien Mengen, wobei es eine Bijektion zwischen und und zwischen und gebe. Zeige, dass es dann auch eine Bijektion zwischen den Abbildungsmengen und .
Berechne
- ,
- ,
- ,
- .
Die Folge , sei rekursiv durch
definiert. Zeige, dass für
gilt.
Warum gibt es für das Produkt der ersten aufeinanderfolgenden Zahlen ein eigenes Symbol, nicht aber für die Summe der ersten aufeinanderfolgenden Zahlen?
In einem Hörsaal befindet sich ein Tafelgestell mit drei hintereinander liegenden, vertikal verschiebbaren Tafeln. Diese seien mit (vordere Tafel), (mittlere Tafel) und (hintere Tafel) bezeichnet. Aufgrund der Höhe des Gestells sind nur (maximal) zwei Tafeln gleichzeitig einsehbar. Die Lehrperson schreibt in der Vorlesung jede Tafel genau einmal voll. In welcher Reihenfolge (alle Möglichkeiten!) muss sie die Tafeln einsetzen, wenn beim Beschreiben einer Tafel stets die zuletzt beschriebene Tafel sichtbar sein soll.
Prof. Knopfloch, Dr. Eisenbeis und Vorli fahren zwecks Teambildung in die Alpen und wollen dort Berge besteigen, und zwar den Golz, den Kamelhöcker, den kleinen Hechel, den großen Hechel und die kalte Schnauze. Wie viele Besteigungsreihenfolgen gibt es? Wie viele Besteigungsreihenfolgen gibt es insgesamt, wenn man berücksichtigt, dass die drei jeweils hintereinander den Gipfel besteigen?
Kommentar:
Bei einer solchen Fragestellung aus dem Leben muss man sich erstmal klar machen, was mit den Formulierungen gemeint ist, um das eigentliche kombinatorische Problem herauszuschälen. Was ist mit Möglichkeit gemeint, was soll identifiziert werden, was nicht, was ist unterscheidbar, was nicht? Jedenfalls kann hier nicht gemeint sein, wie viele Möglichkeiten es für den zeitlichen Abstand der Besteigungen gibt, es macht keinen Unterschied, ob sie unterwegs zum Höllenwirt gehen oer auf der Alm einkehren. Es sind einfach Berge hintereinander zu besteigen und es geht um die möglichen Reihenfolgen. Das ist einfach .
Im zweiten Aufgabenteil muss man sich auch fragen, wie das gemeint sein muss. Sie gehen jedenfalls nach wie vor als Gruppe auf die einzelnen Berge, etwas wie zuerst geht Vorli auf den Golz, dann Dr. Eisenbeis auf den Kamelhöcker, dann Vorli auf den Kleinen Hechel, wäre keine erlaubte Reihenfolge. Es ist hier zu erkennen, dass im ersten Teil die Groben Möglichkeiten gezählt werden, die dann im zweiten Teil verfeinert werden. Man möchte jetzt zusätzlich für jeden Berg wissen, in welcher Reihenfolge die drei den Gipfel erreichen. Dafür gibt es jeweils Möglichkeiten, und dies muss man mit multiplizieren.
Es seien und endliche Mengen mit bzw. Elementen mit . Zeige, dass es injektive Abbildungen von nach gibt.
Es sei . Vergleiche die Anzahl der injektiven Abbildungen von einer -elementigen Menge in eine -elementige Menge mit der Anzahl der surjektiven Abbildungen von einer -elementigen Menge in eine -elementige Menge in den folgenden Fällen.
a) ,
b) ,
c) .
Es soll ein Schaubild über ein Netzwerk angefertigt werden. In dem Netzwerk ist jeder Punkt (jede Person, jeder Gesichtspunkt) mit jedem anderen direkt verbunden (beispielsweise durch einen Pfeil mit zwei Spitzen). Wie viele Pfeile sind in Abhängigkeit von der Anzahl der Punkte zu zeichnen?
Heinz-Peter schaut am Morgen in den Spiegel und entdeckt fünf Pickel auf seiner Stirn. Diese müssen alle ausgedrückt werden, wobei zwei Pickel so nah beieinander liegen, dass sie unmittelbar hintereinander behandelt werden müssen. Wie viele Reihenfolgen gibt es, die Pickel auszudrücken?
Im Sportunterricht wird ein Zirkeltraining mit den Stationen
Trampolin, Kletterwand, Schwebebalken, Basketballkorb, Laufband, Medizinball
durchgeführt. Bei einem Durchlauf soll die Kletterwand und der Schwebebalken unmittelbar hintereinander absolviert werden (die Reihenfolge ist aber egal), die beiden Ballstationen (Basketballkorb und Medizinball) sollen aber nicht unmittelbar hintereinander absolviert werden.
Wie viele Möglichkeiten (Reihenfolgen) gibt es für einen vollständigen Durchlauf, wenn diese beiden Bedingungen erfüllt sein sollen?
Die Räuberbande „Robin Hood“ besteht aus fünf Personen. Sie legt für ihr Diebesgut eine Schatztruhe an, die sie mit verschiedenen Schlössern sichern möchte, wobei die (mehrfachen) Schlüssel an die Mitglieder verteilt werden sollen. Dabei soll erreicht werden, dass je zwei Bandenmitglieder allein nicht an den Schatz kommen, dass aber je drei Bandenmitglieder die Truhe aufschließen können. Wie viele Schlösser braucht man dafür und wie müssen die Schlüssel verteilt werden?
Es sei eine Menge und ihre Potenzmenge. Zeige, dass die Abbildung
bijektiv ist. Wie lautet die Umkehrabbildung?
Zu Mengen wird mit die Menge aller Abbildungen von nach bezeichnet.
Es sei eine Menge. Stifte eine Bijektion zwischen
Kommentar:
Es sollen also die Teilmengen den Abbildungen von nach entsprechen. Bei eine Abbildung in eine zweielementige Menge hat man ja nur die Auswahl das eine Element oder das andere Element. Dieses Auswahlprinzip gibt es aber auch auf der Teilmengenseite. Eine Teilmenge ist durch die in ihr enthaltenen Elemente gegeben. Das kann man sich aber auch so vorstellen, dass die Grundmenge durchgegangen wird und bei jedem Element gesagt wird, ob es zu gehört oder nicht. Eine Party kann man durch die Auflistung der Gäste festlegen, oder durch eine Durchsicht aller potentiellen Gäste, und bei jedem festlegen: wird eingeladen oder nicht. Deshalb ist es sinnvoll, eine Teilmenge auf diejenige Abbildung abzubilden, die bei den Wert und bei den Wert besitzt. Diese Abbildung heißt die Indikatorabbildung zu . Aus dieser Abbildung lässt sich die vorgegebene Teilmenge als Urbild (Faser) zu rekonstruieren, und damit haben wir zugleich die Umkehrabbildung. Einer Abbildung von nach wird die Faser über zugeordnet. Deshalb ist die Gesamtzuordnung bijektiv.
Wenn man die Menge durchnummeriert, so kann man die Indikatorfunktion auch als eine -Folge auffassen. Dann entsprechen die Teilmengen auch den Dualzahlen der Länge , wenn die Anzahl von ist.
Es sei eine endliche Menge mit Elementen. Zeige, dass die Potenzmenge genau Elemente besitzt.
Bei der folgenden Aufgabe denke man an Mädchen der Klasse, Jungs der Klasse.
Es sei eine Menge, die als disjunkte Vereinigung
gegeben ist. Definiere eine Bijektion zwischen der Potenzmenge und der Produktmenge .
Es sei eine beliebige Menge. Zeige, dass es keine surjektive Abbildung von in die Potenzmenge geben kann.
Es sei eine -elementige Teilmenge. Wir bezeichnen mit die Menge der -elementigen Teilmengen von und mit die Menge der bijektiven Abbildungen von nach (also alle Nummerierungen von ). Beweise Satz 2.5 unter Verwendung der Abbildung
und Satz 2.1.
Man beweise die Formel
indem man die Anzahl der zweielementigen Teilmengen einer -elementigen Menge auf zwei verschiedene Arten bestimmt.
Es sei fixiert. Zeige, dass die Binomialkoeffizienten für bzw. bis wachsend sind.
Unter einer Geburtstagsfeier der Klasse 1c versteht man eine Party, wobei die Menge der Gäste eine Teilmenge der Klasse ist und wobei es ein Geburtstagskind aus der Klasse gibt, das auf der Party anwesend ist. Wie viele Geburtstagsparties gibt es, wenn die Klasse nur aus vier Kindern besteht?
Beweise die Formel
Zeige: Für mit gilt
Wie viele Teilquadrate (unterschiedlicher Seitenlänge) besitzt ein Schachbrett? Man finde möglichst viele Strategien, diese Anzahl zu bestimmen.
Es sei ein Gitter mit Querkästchen und mit Hochkästchen gegeben. Wie viele Möglichkeiten gibt es, von links unten nach rechts oben entlang der Gitterkanten zu wandern, wenn man in jedem Schritt nur nach rechts oder nach oben wandern darf?
- Aufgaben zum Abgeben
Aufgabe (2 Punkte)Referenznummer erstellen
Zeige, dass für die Beziehung
gilt.
Aufgabe (2 Punkte)Referenznummer erstellen
Bestimme die Primfaktorzerlegung von
Aufgabe (4 Punkte)Referenznummer erstellen
Beweise die Formel
- durch Induktion und Rechnungen,
- durch eine inhaltliche Überlegung.
Für den zweiten Teil denke man an Geburtstagsparties.
Aufgabe (3 Punkte)Referenznummer erstellen
Ein Adventskranz hat vier Kerzen, wobei am ersten Advent genau eine Kerze, am zweiten Advent genau zwei Kerzen usw. brennen sollen. Wie viele Möglichkeiten gibt es, den Adventskranz „abzubrennen“? Wie viele Möglichkeiten gibt es, wenn die Kerzen, die zuvor schon angezündet waren, wieder angezündet werden sollen, und wie viele, wenn stets so viele neue Kerzen wie möglich angezündet werden?
Zeige, dass eine nichtleere endliche Menge gleich viele Teilmengen mit gerader und mit ungerader Anzahl besitzt. Beweise diese Aussage unter Verwendung von Binomialkoeffizienten.