Kurs:Grundkurs Mathematik (Osnabrück 2016-2017)/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

Es seien ${}L$ und ${}M$ endliche Mengen mit ${}\ell$ bzw. ${}m$ Elementen. Wie viele Abbildungen gibt es von ${}L$ nach ${}M$?

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 *

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 *

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 ${}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.

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.