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

Die Pausenaufgabe

Aufgabe

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 ${}(a,\{a,b\})$ und einmal als ${}(b,\{a,b\})$ zu sehen.

Übungsaufgaben

Aufgabe

Interpretiere Satz 2.1 für den Fall, wo ${}N$ und ${}M$ endliche Mengen sind, ${}L=N\times M$ ihre Produktmenge ist und

$f\colon L=N\times M\longrightarrow M,\,(x,y)\longmapsto y,$

die Projektion auf die zweite Komponente ist.

Aufgabe

Wir betrachten die Abbildung

$f\colon \{1,2,3,4,5\}\times \{1,2,3,4,5\}\longrightarrow \{2,3,4,5,6,7,8,9,10\},\,(x,y)\longmapsto x+y.$

Bestimme für jedes ${}z\in \{2,3,4,5,6,7,8,9,10\}$ die Urbildmenge ${}f^{-1}(\{z\})$ und die Anzahl ihrer Elemente.${}f^{-1}(\{z\})$. Bestimme ${}\sum _{z\in \{2,\ldots ,10\}}{\#\left(f^{-1}(\{z\})\right)}$ auf verschiedene Arten.

Aufgabe

Wir betrachten die Abbildung

$f\colon \{1,2,3,4,5\}\times \{1,2,3,4,5\}\longrightarrow \{1,2,3,\ldots ,25\},\,(x,y)\longmapsto x\cdot y.$

Bestimme für jedes ${}z\in \{1,2,3,\ldots ,25\}$ die Urbildmenge ${}f^{-1}(\{z\})$ und die Anzahl ihrer Elemente. Bestimme ${}\sum _{z\in \{1,\ldots ,25\}}{\#\left(f^{-1}(\{z\})\right)}$ 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 ${}25$ 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 ${}5$ nicht getroffen werden. Es wird also ${}7,11,13,17,19,23$ nicht getroffen. Das ist aber noch nicht alles. Auch

${}14=2\cdot 7\,,$

${}21$ und ${}22$ und ${}24$ werden nicht getroffen. Wegen der Nichtsurjektivität ist ${}f$ auch nicht injektiv. Dies ist auch direkt klar und links eine Produktmenge steht, wo ja die Paare wie ${}(2,3)$ und ${}(3,2)$ verschieden sind, aber beide auf ${}6$ gehen. Ferner hat man noch das Phänomen, dass ${}(1,4),(4,1),(2,2)$ alle auf ${}4$ gehen. Man lasse sich hier auch nicht von der Eindeutigkeit der Primfaktorzerlegung in die Irre führen.

Bestimme wir nun für jedes ${}z\in \{1,2,3,\ldots ,25\}$ die Anzahl der Elemente in der Urbildmenge ${}f^{-1}(\{z\})$. 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 ${}1$ und ${}25$, die man nicht als ein Produkt mit zwei Faktoren schreiben kann, die beide aus ${}1$ bis ${}5$ kommen. Das sind, wie oben erwähnt, die Primzahlen größer als ${}5$, und die zerlegbaren Zahlen, wo es keine Faktorzerlegung in die kleine Faktoren gibt. Dies heißt, dass ein Faktor zumindest ${}6$ ist. Gehen wir diese ohne die Primzahlen durch.

${}6=2\cdot 3$ ist im Bild, ${}8=2\cdot 4$ ist im Bild, ${}9=3\cdot 3$ ist im Bild, ${}10=2\cdot 5$ ist im Bild, ${}12=3\cdot 4$ ist im Bild, ${}14=2\cdot 7$ ist nicht im Bild, da ${}7$ eine Primzahl ist, ${}15=3\cdot 5$ ist im Bild, ${}16=4\cdot 4$ ist im Bild (es gibt auch die Faktorzerlegung ${}2\cdot 8$, die spielt aber in der derzeitigen Abbildung keine Rolle). ${}18=2\cdot 3\cdot 3=6\cdot 3=2\cdot 9$ ist nicht im Bild, da beide nichttriviale Faktorzerlegung mit zwei Faktoren einen zu goßen Faktor benötigen, das haben wir oben übersehen, ${}20=4\cdot 5$ ist im Bild, ${}21=3\cdot 7$ ist nicht im Bild, ${}22=2\cdot 11$ ist nicht im Bild, ${}25=5\cdot 5$ ist im Bild. Die Fasern zu

$7,11,13,17,18,19,21,23,24$

sind also leer.

Zu welchen Zahlen sind die Fasern einelement? Wegen der Produktmenge kommen dafür nur Quadratzahlen in Frage. Hier spielt aber die ${}4$ eine besondere Rolle, da für die ${}4$ die Faser aus ${}3$ Elementen besteht. Die Quadratzahlen

$1,9,16,25$

haben genau ein Urbild.

Genau zwei Urbilder. Diese Zahlen sind insbesondere Produkte von zwei verschiedenen Zahlen aus ${}1$ bis ${}5$. Da es

${}{\binom {5}{2}}=10\,$

zweielementige Teilmengen gibt, erhalten wir ${}10$ Produkte, für die es (wegen der Vertauschungsmöglichkeit) zumindest ${}2$ Urbilder gibt. Dab ist die ${}4$ aber wieder dabei, das dürfen wir nicht mehrfach zählen. Die ${}9$ Zahlen

$2,3,5,6,8,10,12,15,20$

besitzen genau ${}2$ Urbilder. Die Summe ${}\sum _{z\in \{1,\ldots ,25\}}{\#\left(f^{-1}(\{z\})\right)}$ ist nach Satz 2.1 gleich der Mächtigkeit der Ausgangsmenge, also gleich ${}25$. Dies ergibt sich auch als

${}4\cdot 1+9\cdot 2+1\cdot 3=25\,.$

 

Aufgabe

Es seien ${}L$ und ${}M$ Mengen und sei ${}x\in L$ fixiert. Zeige, dass die Auswertungsabbildung

$\operatorname {Abb} \,{\left(L,M\right)}\longrightarrow M,\,\varphi \longmapsto \varphi (x)$

surjektiv ist und bestimme für jedes ${}y\in M$ die Faser über ${}y$. Was kann man über die Mächtigkeit der Fasern bei ${}L$ und ${}M$ endlich sagen?

Aufgabe

Es seien ${}A,B,L,M$ Mengen, wobei es eine Bijektion zwischen ${}A$ und ${}L$ und zwischen ${}B$ und ${}M$ gebe. Zeige, dass es dann auch eine Bijektion zwischen den Abbildungsmengen ${}\operatorname {Abb} \,{\left(A,B\right)}$ und ${}\operatorname {Abb} \,{\left(L,M\right)}$.

Aufgabe

Es seien ${}L$ und ${}M$ Mengen und ${}x\in L$ fixiert. Zeige, dass die Abbildung

$\operatorname {Abb} \,{\left(L,M\right)}\longrightarrow M\times \operatorname {Abb} \,{\left(L\setminus \{x\},M\right)},\,\varphi \longmapsto (\varphi (x),\varphi {|}_{L\setminus \{x\}}),$

bijektiv ist.

Aufgabe

Berechne

1. ${}((((2!)!)!)!)!$,
2. ${}(3!)!$,
3. ${}(3!)^{2}$,
4. ${}(3^{2})!$.

Aufgabe

Die Folge ${}a_{n},\,n\in \mathbb {N}$, sei rekursiv durch

$a_{1}=1{\text{ und }}a_{n}=\sum _{k=1}^{n-1}ka_{k}{\text{ für }}n\geq 2$

definiert. Zeige, dass für ${}n\geq 2$

${}a_{n}={\frac {1}{2}}n!\,$

gilt.

Aufgabe

Warum gibt es für das Produkt der ersten ${}n$ aufeinanderfolgenden Zahlen ein eigenes Symbol, nicht aber für die Summe der ersten ${}n$ aufeinanderfolgenden Zahlen?

Aufgabe *

In einem Hörsaal befindet sich ein Tafelgestell mit drei hintereinander liegenden, vertikal verschiebbaren Tafeln. Diese seien mit ${}V$ (vordere Tafel), ${}M$ (mittlere Tafel) und ${}H$ (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.

Aufgabe

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:

„Wann sind wir denn endlich auf dem Gipfel? Ich will zurück in die Vorlesung“ sagt wer?

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 ${}5$ Berge hintereinander zu besteigen und es geht um die möglichen Reihenfolgen. Das ist einfach ${}5!$.

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 ${}3!=6$ Möglichkeiten, und dies muss man mit ${}5!$ multiplizieren.

 

Aufgabe

Es seien ${}L$ und ${}M$ Mengen, beide mit ${}n$ Elementen. Es sei ${}x\in L$ ein fixiertes Element. Bestimme zur Auswertungsabbildung

$\operatorname {Bij} \,{\left(L,M\right)}\longrightarrow M,\,\varphi \longmapsto \varphi (x),$

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

Aufgabe

Es seien ${}L$ und ${}M$ endliche Mengen mit ${}\ell$ bzw. ${}m$ Elementen mit ${}\ell \leq m$. Zeige, dass es ${}m(m-1)(m-2)\cdots (m-\ell +1)$ injektive Abbildungen von ${}L$ nach ${}M$ gibt.

Aufgabe *

Es sei ${}n\in \mathbb {N} _{+}$. Vergleiche die Anzahl der injektiven Abbildungen von einer ${}n$-elementigen Menge in eine ${}n+1$-elementige Menge mit der Anzahl der surjektiven Abbildungen von einer ${}n+1$-elementigen Menge in eine ${}n$-elementige Menge in den folgenden Fällen.

a) ${}n=1$,

b) ${}n=2$,

c) ${}n=3$.

Aufgabe

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?

Aufgabe *

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?

Aufgabe *

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?

Aufgabe

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?

Aufgabe

Es sei ${}G$ eine Menge und ${}{\mathfrak {P}}\,(G)$ ihre Potenzmenge. Zeige, dass die Abbildung

${\mathfrak {P}}\,(G)\longrightarrow {\mathfrak {P}}\,(G),\,T\longmapsto \complement T,$

bijektiv ist. Wie lautet die Umkehrabbildung?

Zu Mengen ${}L,M$ wird mit ${}\operatorname {Abb} \,{\left(L,M\right)}$ die Menge aller Abbildungen von ${}L$ nach ${}M$ bezeichnet.

Aufgabe

Es sei ${}G$ eine Menge. Stifte eine Bijektion zwischen

${\mathfrak {P}}\,(G)\,\,{\text{ und }}\,\,\operatorname {Abb} \,{\left(G,\{0,1\}\right)}.$

Kommentar:

Es sollen also die Teilmengen ${}T\subseteq G$ den Abbildungen von ${}G$ nach ${}\{0,1\}$ 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 ${}T$ 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 ${}x\in T$ den Wert ${}1$ und bei ${}x\notin T$ den Wert ${}0$ besitzt. Diese Abbildung heißt die Indikatorabbildung zu ${}T$. Aus dieser Abbildung lässt sich die vorgegebene Teilmenge als Urbild (Faser) zu ${}1$ rekonstruieren, und damit haben wir zugleich die Umkehrabbildung. Einer Abbildung von ${}G$ nach ${}\{0,1\}$ wird die Faser über ${}1$ zugeordnet. Deshalb ist die Gesamtzuordnung bijektiv.

Wenn man die Menge ${}G$ durchnummeriert, so kann man die Indikatorfunktion auch als eine ${}0-1$-Folge auffassen. Dann entsprechen die Teilmengen auch den Dualzahlen der Länge ${}n$, wenn ${}n$ die Anzahl von ${}G$ ist.

 

Aufgabe

Es sei ${}G$ eine endliche Menge mit ${}n$ Elementen. Zeige, dass die Potenzmenge ${}{\mathfrak {P}}\,(G)$ genau ${}2^{n}$ Elemente besitzt.

Bei der folgenden Aufgabe denke man an ${}A=$ Mädchen der Klasse, ${}B=$ Jungs der Klasse.

Aufgabe *

Es sei ${}G$ eine Menge, die als disjunkte Vereinigung

${}G=A\uplus B\,$

gegeben ist. Definiere eine Bijektion zwischen der Potenzmenge ${}{\mathfrak {P}}\,(G)$ und der Produktmenge ${}{\mathfrak {P}}\,(A)\times {\mathfrak {P}}\,(B)$.

Aufgabe *

Es sei ${}M$ eine beliebige Menge. Zeige, dass es keine surjektive Abbildung von ${}M$ in die Potenzmenge ${}{\mathfrak {P}}\,(M)$ geben kann.

Aufgabe

Es sei ${}M$ eine ${}n$-elementige Teilmenge. Wir bezeichnen mit ${}{\mathfrak {P}}_{k}\,(M)$ die Menge der ${}k$-elementigen Teilmengen von ${}M$ und mit ${}\operatorname {Num} {\left(M\right)}$ die Menge der bijektiven Abbildungen von ${}\{1,2,3,\ldots ,n\}$ nach ${}M$ (also alle Nummerierungen von ${}M$). Beweise Satz 2.5 unter Verwendung der Abbildung

$\Psi \colon \operatorname {Num} {\left(M\right)}\longrightarrow {\mathfrak {P}}_{k}\,(M),\,\varphi \longmapsto \{\varphi (1),\varphi (2),\ldots ,\varphi (k)\},$

und Satz 2.1.

Aufgabe

Man beweise die Formel

${}{\binom {n+1}{2}}={\frac {n(n+1)}{2}}=\sum _{k=1}^{n}k\,,$

indem man die Anzahl der zweielementigen Teilmengen einer ${}(n+1)$-elementigen Menge auf zwei verschiedene Arten bestimmt.

Aufgabe *

Zeige, dass zwischen den Binomialkoeffizienten ${}{\binom {n}{k}}$ und ${}{\binom {n}{k+1}}$ der Zusammenhang

${}{\binom {n}{k+1}}={\binom {n}{k}}\cdot {\frac {n-k}{k+1}}\,$

besteht.

Aufgabe

Es sei ${}n\in \mathbb {N}$ fixiert. Zeige, dass die Binomialkoeffizienten ${}{\binom {n}{k}}$ für ${}k=0,1,\ldots ,{\frac {n}{2}}$ bzw. bis ${}{\frac {n-1}{2}}$ wachsend sind.

Aufgabe

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?

Aufgabe

Beweise die Formel

${}2^{n}=\sum _{k=0}^{n}{\binom {n}{k}}\,.$

Aufgabe

Zeige: Für ${}n,k\in \mathbb {N}$ mit ${}n\geq k$ gilt

${}{\binom {n+1}{k+1}}=\sum _{m=k}^{n}{\binom {m}{k}}\,.$

Aufgabe

Wie viele Teilquadrate (unterschiedlicher Seitenlänge) besitzt ein Schachbrett? Man finde möglichst viele Strategien, diese Anzahl zu bestimmen.

Aufgabe *

Es sei ein Gitter mit ${}n$ Querkästchen und mit ${}m$ 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 ${}n\geq 4$ die Beziehung

${}2^{n}\leq n!\,$

gilt.

Aufgabe (2 Punkte)

Bestimme die Primfaktorzerlegung von

${\binom {20}{10}}.$

Aufgabe (4 Punkte)

Beweise die Formel

${}n2^{n-1}=\sum _{k=0}^{n}k{\binom {n}{k}}\,$

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 ${}M$ gleich viele Teilmengen mit gerader und mit ungerader Anzahl besitzt. Beweise diese Aussage unter Verwendung von Binomialkoeffizienten.