Kurs:Diskrete Mathematik (Osnabrück 2020)/Arbeitsblatt 2



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.



Es seien und Mengen und sei fixiert. Zeige, dass die Auswertungsabbildung

surjektiv ist und bestimme für jedes die Faser über . Was kann man über die Mächtigkeit der Fasern bei und endlich sagen?



Es seien Mengen, wobei es eine Bijektion zwischen und und zwischen und gebe. Zeige, dass es dann auch eine Bijektion zwischen den Abbildungsmengen und .



Es seien und Mengen und fixiert. Zeige, dass die Abbildung

bijektiv ist.



Berechne

  1. ,
  2. ,
  3. ,
  4. .



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?



Es seien und Mengen, beide mit Elementen. Es sei ein fixiertes Element. Bestimme zur Auswertungsabbildung

die Fasern und ihre Anzahl und beweise damit und mit Satz 2.1 erneut Satz 2.4.



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



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.



Zeige, dass zwischen den Binomialkoeffizienten und der Zusammenhang

besteht.



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)

Zeige, dass für die Beziehung

gilt.



Aufgabe (2 Punkte)

Bestimme die Primfaktorzerlegung von



Aufgabe (4 Punkte)

Beweise die Formel

  1. durch Induktion und Rechnungen,
  2. durch eine inhaltliche Überlegung.

Für den zweiten Teil denke man an Geburtstagsparties.


Aufgabe (3 Punkte)

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?



Aufgabe (3 Punkte)

Zeige, dass eine nichtleere endliche Menge gleich viele Teilmengen mit gerader und mit ungerader Anzahl besitzt. Beweise diese Aussage unter Verwendung von Binomialkoeffizienten.



<< | Kurs:Diskrete Mathematik (Osnabrück 2020) | >>

PDF-Version dieses Arbeitsblattes

Zur Vorlesung (PDF)