Kurs:Grundkurs Mathematik (Osnabrück 2018-2019)/Teil I/Arbeitsblatt 13

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.

Übungsaufgaben

Aufgabe

Interpretiere Satz 13.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.

Aufgabe

Berechne

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

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 *

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 *

Es findet das olympische 100-Meter-Finale mit acht Teilnehmern statt. Sie wissen, welche drei Teilnehmer eine Medaille gewinnen (aber nicht, wer welche Medaille gewinnt). Wie viele Möglichkeiten für das Gesamtergebnis aller acht Teilnehmer verbleiben (keine Platzierung ist doppelt besetzt)?

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

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 *

Vor einem Fußballspiel begrüßt jeder der elf Spieler einer Mannschaft jeden Spieler der anderen Mannschaft, jeder Spieler begrüßt die vier Unparteiischen und diese begrüßen sich alle untereinander. Wie viele Begrüßungen finden statt?

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

Mustafa Müller wird ${}8$ Jahre alt und darf deshalb zu seiner Geburtstagsfeier aus seiner Klasse, in der es insgesamt ${}25$ Schüler und Schülerinnen gibt, ${}8$ Leute einladen. Wie viele Möglichkeiten gibt es?

Aufgabe

Zu Ende des Schullandaufenthalts auf Juist soll ein Klassenfoto der ${}17$ Schüler und Schülerinnen gemacht werden. Dabei sollen ${}10$ Kinder in der ersten Reihe knien und ${}7$ Kinder in der zweiten Reihe stehen.

1. Wie viele Anordnungsmöglichkeiten für ein solches Gruppenfoto gibt es?
2. Wie viele Möglichkeiten gibt es, wenn man sich nur dafür interessiert, wer vorne und wer hinten ist?
3. Wenn man sich entschieden hat, wer vorne und wer hinten sein soll, wie viele Anordnungsmöglichkeiten gibt es dann noch insgesamt?

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 13.6 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 13.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

Gabi Hochster, Heinz Ngolo und Mustafa Müller backen bei der Oma von Mustafa Plätzchen. Die Oma hat auf das Blech schon in vier Reihen der Länge sechs die Teigmasse platziert. Den Kindern kommen folgende Aufgaben zu: Gabi soll auf jedes Plätzchen eine Haselnuss platzieren, Heinz Puderzucker drauf streuen und Mustafa einen Zitronenspritzer drauf spritzen. Dabei kommt es auf die Reihenfolge dieser drei Zugaben an. Wie viele Möglichkeiten gibt es für ein einzelnes Plätzchen und wie viele für das Gesamtblech?

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?

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 sei ${}m\geq n$. Wie viele injektive Abbildungen gibt es von ${}{\{1,\ldots ,n\}}$ nach ${}\{1,\ldots ,m\}$ und wie viele surjektive Abbildungen gibt es von ${}{\{1,\ldots ,n\}}$ nach ${}\{1,\ldots ,m\}$?

Für die folgende Aufgabe ist die allgemeine binomische Formel hilfreich.

Aufgabe *

Beweise durch Induktion, dass für ${}n\geq 10$ die Abschätzung

${}3^{n}\geq n^{4}\,$

gilt.

Aufgabe *

Zeige, dass für ${}n\geq 3$ die Abschätzung

${}n^{n+1}\geq (n+1)^{n}\,$

gilt.

Aufgabe *

Es sei ${}n\in \mathbb {N} _{+}$. Zeige, dass das Produkt von ${}n$ aufeinanderfolgenden natürlichen Zahlen von ${}n!$ geteilt wird.

Aufgaben zum Abgeben

Aufgabe (3 Punkte)

Gabi Hochster, Heinz Ngolo, Lucy Sonnenschein und Mustafa Müller wollen untereinander wichteln. Jede Person soll also genau von einer Person ein Geschenk bekommen, aber natürlich nicht von sich selbst. Wie viele Wichtelmöglichkeiten gibt es?

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 (3 Punkte)

Beweise die Formel

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

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.