Kurs:Grundkurs Mathematik/Teil I/T1/Klausur mit Lösungen/latex
%Daten zur Institution
%\input{Dozentdaten}
%\renewcommand{\fachbereich}{Fachbereich}
%\renewcommand{\dozent}{Prof. Dr. . }
%Klausurdaten
\renewcommand{\klausurgebiet}{ }
\renewcommand{\klausurtyp}{ }
\renewcommand{\klausurdatum}{ . 20}
\klausurvorspann {\fachbereich} {\klausurdatum} {\dozent} {\klausurgebiet} {\klausurtyp}
%Daten für folgende Punktetabelle
\renewcommand{\aeins}{ 3 }
\renewcommand{\azwei}{ 3 }
\renewcommand{\adrei}{ 2 }
\renewcommand{\avier}{ 3 }
\renewcommand{\afuenf}{ 3 }
\renewcommand{\asechs}{ 4 }
\renewcommand{\asieben}{ 4 }
\renewcommand{\aacht}{ 3 }
\renewcommand{\aneun}{ 1 }
\renewcommand{\azehn}{ 2 }
\renewcommand{\aelf}{ 6 }
\renewcommand{\azwoelf}{ 2 }
\renewcommand{\adreizehn}{ 2 }
\renewcommand{\avierzehn}{ 6 }
\renewcommand{\afuenfzehn}{ 5 }
\renewcommand{\asechzehn}{ 6 }
\renewcommand{\asiebzehn}{ 3 }
\renewcommand{\aachtzehn}{ 3 }
\renewcommand{\aneunzehn}{ 3 }
\renewcommand{\azwanzig}{ 64 }
\renewcommand{\aeinundzwanzig}{ }
\renewcommand{\azweiundzwanzig}{ }
\renewcommand{\adreiundzwanzig}{ }
\renewcommand{\avierundzwanzig}{ }
\renewcommand{\afuenfundzwanzig}{ }
\renewcommand{\asechsundzwanzig}{ }
\punktetabelleneunzehn
\klausurnote
\newpage
\setcounter{section}{0}
\inputaufgabepunkteloesung
{3}
{
Definiere die folgenden \zusatzklammer {kursiv gedruckten} {} {} Begriffe. \aufzaehlungsechs{Die \stichwort {leere} {} Menge.
}{Die \stichwort {Vereinigung} {} der Mengen \mathkor {} {L} {und} {M} {.}
}{Die
\stichwort {Kontraposition} {}
zu einer Implikation
\mathl{\alpha \rightarrow \beta}{.}
}{Eine \stichwort {injektive} {} Abbildung \maabbdisp {f} {L} {M } {.}
}{Eine \stichwort {surjektive} {} Abbildung \maabbdisp {f} {L} {M } {.}
}{Eine \stichwort {Verknüpfung} {} $\circ$ auf einer Menge $M$. }
}
{
\aufzaehlungsechs{Unter der leeren Menge versteht man diejenige Menge, die kein Element besitzt.
}{Die Menge
\mavergleichskettedisp
{\vergleichskette
{ L \cup M
}
{ =} { { \left\{ x \mid x \in L \text{ oder } x \in M \right\} }
}
{ } {
}
{ } {
}
{ } {
}
}
{}{}{}
heißt die Vereinigung der beiden Mengen.
}{Zur Implikation
\mathl{\alpha \rightarrow \beta}{} heißt die Implikation
\mathl{\neg \beta \rightarrow \neg \alpha}{} die
Kontraposition.
}{Die Abbildung
\maabbdisp {f} {L} {M
} {}
ist injektiv, wenn für je zwei verschiedene Elemente
\mathl{x,y \in L}{} auch
\mathl{f(x)}{} und
\mathl{f(y)}{} verschieden sind.
}{Die Abbildung $f$ heißt surjektiv, wenn es für jedes
\mathl{y \in M}{} mindestens ein Element
\mathl{x \in L}{} mit
\mathl{f(x)=y}{} gibt.
}{Eine Verknüpfung $\circ$ auf einer Menge $M$ ist eine
\definitionsverweis {Abbildung}{}{}
\maabbeledisp {\circ} {M\times M} {M
} {(x,y)} {x \circ y
} {.}
}
}
\inputaufgabepunkteloesung
{3}
{
Formuliere die folgenden Sätze. \aufzaehlungdrei{Der Satz über die Koeffizientenbedingung für die minimale Darstellung eines Betrages mit Eurozahlen.}{Der Satz über die Wohldefiniertheit der Anzahl.}{Das Induktionsprinzip für Aussagen.}
}
{
\aufzaehlungdrei{Eine Darstellung
\mavergleichskettedisp
{\vergleichskette
{w
}
{ =} {a_1 \cdot 1 + a_2 \cdot 2 +a_3 \cdot 5 + a_4 \cdot 10 +a_5 \cdot 20 +a_6 \cdot 50 + a_7 \cdot 100+ a_8 \cdot 200 + a_9 \cdot 500
}
{ } {
}
{ } {
}
{ } {
}
}
{}{}{}
ist genau dann minimal, wenn die folgenden Koeffizientenbedingungen erfüllt sind.
a) Die Koeffizienten $a_i$, die sich auf $1,5,10,50,100$ beziehen, sind $\leq 1$.
b) Die Koeffizienten $a_i$, die sich auf $2,20,200$ beziehen, sind $\leq 2$.
c) Falls der Koeffizient, der sich auf $2$
\zusatzklammer {bzw. $20$ bzw. $200$} {} {}
bezieht, gleich $2$ ist, so ist der vorhergehende Koeffizient
\zusatzklammer {der sich also auf $1$ bzw. $10$ bzw. $100$ bezieht} {} {}
gleich $0$.}{Wenn $M$ eine Menge ist und wenn
\maabbdisp {\varphi} { \{1 , \ldots , n\} } {M
} {}
und
\maabbdisp {\psi} { \{1 , \ldots , k\} } {M
} {}
bijektive Abbildungen sind, so ist
\mavergleichskettedisp
{\vergleichskette
{n
}
{ =} {k
}
{ } {
}
{ } {
}
{ } {
}
}
{}{}{.}}{Für jede natürliche Zahl
$n$ sei eine Aussage
\mathl{A(n)}{} gegeben. Es gelte
\aufzaehlungzwei {$A(0)$ ist wahr.
} {Für alle $n$ gilt: wenn
\mathl{A(n)}{} gilt, so ist auch
\mathl{A(n+1)}{} wahr.
}
Dann gilt
\mathl{A(n)}{} für alle $n$.}
}
\inputaufgabepunkteloesung
{2}
{
Führe die zweite binomische Formel für rationale Zahlen auf die zweite binomische Formel für ganze Zahlen zurück.
}
{
Wir schreiben die beteiligten rationalen Zahlen als
\mathdisp {a = { \frac{ k }{ m } } \text{ und } b = { \frac{ r }{ s } }} { . }
Unter Verwendung von grundlegenden Rechenregeln für Brüche erhalten wir
\mavergleichskettealign
{\vergleichskettealign
{(a-b)^2
}
{ =} { { \left( { \frac{ k }{ m } }- { \frac{ r }{ s } } \right) }^2
}
{ =} { { \left( { \frac{ ks-rm }{ ms } } \right) }^2
}
{ =} { { \frac{ (ks-rm)^2 }{ (ms)^2 } }
}
{ =} { { \frac{ (ks)^2-2ksrm +(rm)^2 }{ (ms)^2 } }
}
}
{
\vergleichskettefortsetzungalign
{ =} { { \frac{ (ks)^2 }{ (ms)^2 } } - 2 { \frac{ ksrm }{ (ms)^2 } } + { \frac{ (rm)^2 }{ (ms)^2 } }
}
{ =} { { \left( { \frac{ k }{ m } } \right) }^2 - 2 { \frac{ ks }{ ms } } \cdot { \frac{ rm }{ ms } } + { \left( { \frac{ r }{ s } } \right) }^2
}
{ =} { a^2 -2ab +b^2
}
{ } {}
}
{}{.}
}
\inputaufgabepunkteloesung
{3}
{
Illustriere die dritte binomische Formel durch eine geeignete geometrische Figur.
}
{Dritte binomische Formel/Illustriere geometrisch/Aufgabe/Lösung
}
\inputaufgabepunkteloesung
{3}
{
Auf wie viele Arten kann man mit den üblichen Münzen einen Betrag von $20$ Cent begleichen?
}
{
Wir zählen zunächst die Möglichkeiten, mit den $5$-, $10$- und $20$-Centmünzen die folgenden Beträge darzustellen:
\mathdisp {0 \text{ Cent}: 1 \text{ Möglichkeit}} { , }
\mathdisp {5 \text{ Cent}: 1 \text{ Möglichkeit}} { , }
\mathdisp {10 \text{ Cent}: 2 \text{ Möglichkeiten}} { , }
\mathdisp {15 \text{ Cent}: 2 \text{ Möglichkeiten}} { , }
\mathdisp {20\text{ Cent}: 4 \text{ Möglichkeiten}} { . }
Dann betrachten wir in jedem Fall, mit wie vielen $2$-Centmünzen man jeweils noch unterhalb von $20$ Cent bleibt, der verbleibende Rest wird mit $1$-Centmünzen aufgefüllt. Hierfür gibt es der Reihe nach
\mathdisp {11 , 8,6, 3 ,1 \text{ Möglichkeiten}} { . }
Diese Möglichkeiten für die Zweier muss man mit den obigen Möglichkeiten multiplizieren, das ergibt insgesamt
\mavergleichskettedisp
{\vergleichskette
{1 \cdot 11 + 1 \cdot 8 +2\cdot 6 + 2 \cdot 3 + 4 \cdot 1
}
{ =} { 11+8+12+6+4
}
{ =} { 41
}
{ } {
}
{ } {
}
}
{}{}{}
Möglichkeiten.
}
\inputaufgabepunkteloesung
{4 (2+1+1)}
{
Eine Geldfälscherin stellt $3$- und $7$-Euro-Scheine her. \aufzaehlungdrei{Zeige, dass es nur endlich viele \zusatzklammer {volle} {} {} Eurobeträge gibt, die sie nicht \zusatzklammer {exakt} {} {} begleichen kann. }{Was ist der höchste Betrag, den sie nicht begleichen kann? }{Beschreibe \zusatzklammer {ohne weitere Begründung} {} {} die Menge $M$ der Eurobeträge, die sie mit ihren Scheinen nicht begleichen kann. }
}
{
\aufzaehlungdrei{Es ist
\mavergleichskettedisp
{\vergleichskette
{12
}
{ =} {3+3+3+3
}
{ } {
}
{ } {
}
{ } {
}
}
{}{}{,}
\mavergleichskettedisp
{\vergleichskette
{ 13
}
{ =} {7+3+3
}
{ } {
}
{ } {
}
{ } {
}
}
{}{}{}
und
\mavergleichskettedisp
{\vergleichskette
{14
}
{ =} {7+7
}
{ } {
}
{ } {
}
{ } {
}
}
{}{}{,}
diese drei aufeinander folgenden Zahlen kann sie also begleichen. Alle höheren Zahlen kann sie auch begleichen, indem sie zur Darstellung von
\mathl{12,13}{} bzw. $14$ einfach eine gewisse Anzahl an $3$-Euroscheinen hinzugibt.
}{Die $11$ ist nicht darstellbar. In einer möglichen Darstellung der $11$ mit $3$ und $7$ kann höchstens eine $7$ vorkommen, da
\mavergleichskette
{\vergleichskette
{7+7
}
{ = }{14
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
schon zu groß ist. Es ist aber
\mavergleichskettedisp
{\vergleichskette
{7+3
}
{ =} {10
}
{ \neq} {11
}
{ } {
}
{ } {
}
}
{}{}{}
und da $11$ kein Vielfaches von $3$ ist kann man diese Zahl auch nicht nur mit $3$ darstellen. Alle Zahlen darüber kann sie nach Teil (1) begleichen. Also ist $11$ die größte Zahl, die sie nicht begleichen kann.
}{Nicht begleichbar sind
\mathdisp {1,2,4,5,8,11} { . }
}
}
\inputaufgabepunkteloesung
{4 (2+1+1)}
{
Folgende Aussagen seien bekannt. \aufzaehlungsieben{Der frühe Vogel fängt den Wurm. }{Doro wird nicht von Lilly gefangen. }{Lilly ist ein Vogel oder ein Igel. }{Für Igel ist 5 Uhr am Morgen spät. }{Doro ist ein Wurm. }{Für Vögel ist 5 Uhr am Morgen früh. }{Lilly schläft bis 5 Uhr am Morgen und ist ab 5 Uhr unterwegs. } Beantworte folgende Fragen. \aufzaehlungdrei{Ist Lilly ein Vogel oder ein Igel? }{Ist sie ein frühes oder ein spätes Tier? }{Fängt der späte Igel den Wurm? }
}
{
\aufzaehlungdrei{Lilly ist ein Igel. Beweis durch Widerspruch. Nehmen wir an, dass Lilly kein Igel ist. Dann ist sie nach (3) ein Vogel. Da Lilly nach (7) um $5$ Uhr schon unterwegs ist, ist nach (6) Lilly ein früher Vogel. Nach (1) fängt Lilly also den Wurm. Da nach (5) Doro ein Wurm ist, wird er von Lilly gefangen im Widerspruch zu (2). }{Nach dem ersten Teil ist Lilly ein Igel, und nach (7) steht sie um 5 Uhr auf. Dies ist nach (4) für Igel spät, Lilly ist also ein später Igel und somit ein spätes Tier. }{Da nach dem zweiten Teil Lilly ein später Igel ist und sie nach (2) Doro, die nach (5) ein Wurm ist, nicht fängt, fängt der späte Igel im Allgemeinen nicht den Wurm. }
}
\inputaufgabepunkteloesung
{3}
{
Zeige, dass der aussagenlogische Ausdruck
\mathdisp {{ \left( r \rightarrow { \left( p \wedge \neg q \right) } \right) } \rightarrow { \left( \neg p \rightarrow { \left( \neg r \vee q \right) } \right) }} { }
\definitionsverweis {allgemeingültig}{}{}
ist
}
{
Wir müssen zeigen, dass für jede Wahrheitsbelegung $\lambda$ der Variablen $r,p,q$ der Wahrheitswert der Gesamtaussage gleich $1$ ist. Bei
\mavergleichskette
{\vergleichskette
{\lambda(p)
}
{ = }{1
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
ist
\mavergleichskette
{\vergleichskette
{\lambda(\neg p)
}
{ = }{0
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
und damit ist der Nachsatz und die Gesamtaussage wahr. Es sei also im Folgenden
\mavergleichskette
{\vergleichskette
{\lambda(p)
}
{ = }{0
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{.}
Dann ist
\mavergleichskette
{\vergleichskette
{\lambda(p \wedge \neg q )
}
{ = }{0
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{.}
Bei
\mavergleichskette
{\vergleichskette
{\lambda(r)
}
{ = }{1
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
ist der Vordersatz falsch und somit die Gesamtaussage wahr. Es sei also
\mavergleichskette
{\vergleichskette
{\lambda(r)
}
{ = }{0
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{.}
Dann ist der Vordersatz wahr und wir müssen zeigen, dass auch der Nachsatz wahr ist. Es ist dann
\mavergleichskette
{\vergleichskette
{\lambda(\neg r)
}
{ = }{1
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
und
\mavergleichskette
{\vergleichskette
{\lambda( \neg r \vee q)
}
{ = }{1
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{,}
also ist auch in diesem Fall der Nachsatz und die Gesamtaussage wahr.
}
\inputaufgabepunkteloesung
{1}
{
Finde einen möglichst einfachen aussagenlogischen Ausdruck, der die folgende tabellarisch dargestellte Wahrheitsfunktion ergibt. \wahrheitstabellezweieins{ } {\tabellenzeiledrei {$ p $} {$ q $} {$? $} } {\tabellenzeiledrei {w} {w} {f} } {\tabellenzeiledrei {w} {f} {f} } {\tabellenzeiledrei {f} {w} {w} } {\tabellenzeiledrei {f} {f} {f} }
}
{
\mathl{\neg p \wedge q}{.}
}
\inputaufgabepunkteloesung
{2}
{
Negiere den Satz \anfuehrung{Kein Schwein ruft mich an und keine Sau interessiert sich für mich}{} durch (eine) geeignete Existenzaussage(n).
}
{
Es gibt ein Schwein, das mich anruft, oder es gibt eine Sau, die sich für mich interessiert.
}
\inputaufgabepunkteloesung
{6 (2+2+1+1)}
{
Wir betrachten die beiden Sätze \anfuehrung{Für jeden Topf gibt es einen Deckel}{} und \anfuehrung{Es gibt einen Deckel für jeden Topf}{,} die man im alltäglichen Verständnis wohl als gleichbedeutend ansehen würde. Wenn man aber die beiden Aussagen streng prädikatenlogisch
\zusatzklammer {quantorenlogisch} {} {}
von vorne nach hinten abarbeitet, so ergeben sich zwei unterschiedliche Bedeutungen.
\aufzaehlungvier{Formuliere die beiden Aussagen durch zusätzliche Wörter so um, dass die unterschiedlichen Bedeutungen deutlich hervortreten.
}{Es sei $T$ die Menge der Töpfe und $D$ die Menge der Deckel. Es sei
\mathl{P}{} ein zweistelliges Prädikat derart, dass
\zusatzklammer {für
\mavergleichskette
{\vergleichskette
{ x
}
{ \in }{ T
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
und
\mavergleichskette
{\vergleichskette
{ y
}
{ \in }{ D
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}} {} {}
\mathl{P(x,y)}{} besagt, dass $y$ auf $x$ passt. Formuliere die beiden Aussagen allein mit geeigneten mathematischen Symbolen.
}{Kann man aus der Aussage, dass es für jeden Topf einen Deckel gibt, logisch erschließen, dass es für jeden Deckel einen Topf gibt?
}{Wie kann man erklären, dass die beiden Aussagen im alltäglichen Verständnis als gleichbedeutend interpretiert werden?
}
}
{
\aufzaehlungvier{Erste Aussage: Für jeden Topf gibt es einen von diesem jeweiligen Topf abhängigen und zu diesem Topf passenden Deckel. Zweite Aussage: Es gibt einen bestimmten Deckel,
der gleichzeitig für überhaupt alle Töpfe gleichermaßen passt.
}{Die erste Aussage ist
\mathdisp {\forall x (x \in T \rightarrow \exists y (y \in D \wedge P(x,y) ))} { , }
die zweite Aussage ist
\mathdisp {\exists y (y \in D \wedge \forall x (x \in T \rightarrow P(x,y) ))} { . }
}{Nein, es kann ja sein, dass es beispielsweise in der Küche für die drei Töpfe jeweils den passenden Deckel gibt, es aber auch noch einen ganz anderen Deckel gibt, der mit keinem Topf was zu tun hat.
}{Das alltägliche Sprachverständnis versucht, Aussagen sinnvoll zu interpretieren. Da die Aussage, dass es wirklich nur einen Deckel gibt, der gleichzeitig für alle Töpfe passt, offenbar absurd ist, versteht man auch die zweite Formulierung im Sinne der ersten sinnvollen Aussage.
}
}
\inputaufgabepunkteloesung
{2}
{
Es seien
$A,\, B$ und $C$
Mengen. Beweise die Identität
\mavergleichskettedisp
{\vergleichskette
{A \setminus { \left( B \cap C \right) }
}
{ =} { { \left( A \setminus B \right) } \cup { \left( A \setminus C \right) }
}
{ } {
}
{ } {
}
{ } {
}
}
{}{}{.}
}
{
Es sei
\mathl{x \in A \setminus { \left( B \cap C \right) }}{.} Dann ist
\mathl{x \in A}{} und
\mathl{x \not\in B \cap C}{.} Letzteres bedeutet
\mathkor {} {x \not\in B} {oder} {x \not\in C} {.}
Im ersten Fall ist
\mathl{x \in A \setminus B}{,} im zweiten Fall
\mathl{x \in A \setminus C}{,} in beiden Fällen also
\mathl{x \in { \left( A \setminus B \right) } \cup { \left( A \setminus C \right) }}{.}
Wenn umgekehrt
\mathl{x \in { \left( A \setminus B \right) } \cup { \left( A \setminus C \right) }}{} gilt, so bedeutet dies
\mathl{x \in A \setminus B}{} oder
\mathl{x \in A \setminus C}{.} Im ersten Fall ist
\mathl{x \in A}{} und
\mathl{x \not\in B}{,} im zweiten Fall
\mathl{x \in A}{} und
\mathl{x \not\in C}{.} Also ist
\mathl{x \in A}{} und
\mathl{x \not\in B \cap C}{} und somit ist
\mathl{x \in A \setminus { \left( B \cap C \right) }}{.}
}
\inputaufgabepunkteloesung
{2}
{
Es seien
\mathl{L,M,N}{} Mengen und
\maabb {F} {L} {M
} {}
und
\maabb {G} {M} {N
} {}
\definitionsverweis {injektive Abbildungen}{}{.}
Zeige, dass die
\definitionsverweis {Hintereinanderschaltung}{}{}
\mathl{G \circ F}{} ebenfalls injektiv ist.
}
{
Es seien
\mavergleichskette
{\vergleichskette
{ x,x'
}
{ \in }{ L
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
mit
\mavergleichskettedisp
{\vergleichskette
{ G(F(x))
}
{ =} { G(F(x'))
}
{ } {
}
{ } {
}
{ } {
}
}
{}{}{}
gegeben. Aufgrund der Injektivität von $G$ folgt
\mavergleichskettedisp
{\vergleichskette
{F(x)
}
{ =} {F(x')
}
{ } {
}
{ } {
}
{ } {
}
}
{}{}{}
und aufgrund der Injektivität von $F$ folgt
\mavergleichskettedisp
{\vergleichskette
{x
}
{ =} {x'
}
{ } {
}
{ } {
}
{ } {
}
}
{}{}{,}
was die Injektivität von
\mathl{G \circ F}{} bedeutet.
}
\inputaufgabepunkteloesung
{6 (1+1+1+2+1)}
{
Wir betrachten die durch die Wertetabelle
\wertetabelleachtausteilzeilen { $x$ }
{\mazeileundfuenf {1} {2} {3} {4} {5} }
{\mazeileunddrei {6} {7} {8} }
{ $F(x)$ }
{\mazeileundfuenf {3} {5} {1} {7} {8} }
{\mazeileunddrei {2} {6} {4} }
gegebene Abbildung $F$ von
\mavergleichskettedisp
{\vergleichskette
{ M
}
{ =} { \{1,2 , \ldots , 8\}
}
{ } {
}
{ } {
}
{ } {
}
}
{}{}{}
in sich selbst.
\aufzaehlungfuenf{Erstelle eine Wertetabelle für
\mavergleichskette
{\vergleichskette
{F^2
}
{ = }{ F \circ F
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{.}
}{Erstelle eine Wertetabelle für
\mavergleichskette
{\vergleichskette
{F^3
}
{ = }{ F \circ F \circ F
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{.}
}{Begründe, dass sämtliche iterierten Hintereinanderschaltungen $F^n$
\definitionsverweis {bijektiv}{}{}
sind.
}{Bestimme für jedes
\mavergleichskette
{\vergleichskette
{ x
}
{ \in }{ M
}
{ }{}
{ }{}
{ }{}
}
{}{}{}
das minimale
\mavergleichskette
{\vergleichskette
{ n
}
{ \in }{ \N_+
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
mit der Eigenschaft, dass
\mavergleichskettedisp
{\vergleichskette
{F^n (x)
}
{ =} {x
}
{ } {
}
{ } {
}
{ } {
}
}
{}{}{}
ist.
}{Bestimme das minimale
\mavergleichskette
{\vergleichskette
{ n
}
{ \in }{ \N_+
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
mit der Eigenschaft, dass
\mavergleichskettedisp
{\vergleichskette
{F^n (x)
}
{ =} {x
}
{ } {
}
{ } {
}
{ } {
}
}
{}{}{}
für alle
\mavergleichskette
{\vergleichskette
{ x
}
{ \in }{ M
}
{ }{}
{ }{}
{ }{}
}
{}{}{}
ist.
}
}
{
\aufzaehlungfuenf{Es ist
\wertetabelleachtausteilzeilen { $x$ }
{\mazeileundfuenf {1} {2} {3} {4} {5} }
{\mazeileunddrei {6} {7} {8} }
{ $F(F(x))$ }
{\mazeileundfuenf {1} {8} {3} {6} {4} }
{\mazeileunddrei {5} {2} {7} }
}{Es ist
\wertetabelleachtausteilzeilen { $x$ }
{\mazeileundfuenf {1} {2} {3} {4} {5} }
{\mazeileunddrei {6} {7} {8} }
{ $F(F(F(x)))$ }
{\mazeileundfuenf {3} {4} {1} {2} {7} }
{\mazeileunddrei {8} {5} {6} }
}{Aus der Wertetabelle kann man unmittelbar entnehmen, dass $F$ bijektiv ist. Nach
Lemma 6.4 (Grundkurs Mathematik (Osnabrück 2022-2023))
sind dann sämtliche Hintereinanderschaltungen der Abbildung mit sich selbst wieder bijektiv.
}{Die Abbildungsvorschrift bewirkt
\mathdisp {1 \mapsto 3 \mapsto 1} { }
und
\mathdisp {2 \mapsto 5 \mapsto 8 \mapsto 4 \mapsto 7 \mapsto 6 \mapsto 2} { . }
Für
\mathl{x=1,3}{} ist also
\mavergleichskette
{\vergleichskette
{n
}
{ = }{2
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
und für
\mavergleichskette
{\vergleichskette
{x
}
{ = }{ 2,5,8,4,7,6
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
ist
\mavergleichskette
{\vergleichskette
{n
}
{ = }{6
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{.}
}{Bei
\mavergleichskette
{\vergleichskette
{n
}
{ = }{6
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
sind nach Teil (4) die Zahlen
\mathl{2,5,8,4,7,6}{} wieder an ihrer Stelle, aber auch $1,3$ sind an ihrer Stelle, da $6$ ein Vielfaches von $2$ ist.
}
}
\inputaufgabepunkteloesung
{5}
{
Betrachte die Abbildung \maabbeledisp {f} {\N} {\Z } {n} {\begin{cases} -\frac{n}{2}, \text{ falls } n \text{ gerade} \, ,\\ \frac{n+1}{2}, \text{ falls } n \text{ ungerade} \, . \end{cases} } {} Ist $f$ injektiv, surjektiv bzw. bijektiv?
}
{
Die Abbildung ist bijektiv und damit auch injektiv und surjektiv. Wir geben explizit eine Umkehrabbildung an, wir definieren
\maabbeledisp {g} {\Z} {\N
} {m} {\begin{cases} 2 \betrag { m } , \text{ falls } m \leq 0 \text{ ist} \, ,\\ 2 m-1, \text{ falls } m > 0 \text{ ist} \, . \end{cases}
} {}
Für
\mavergleichskette
{\vergleichskette
{n
}
{ \in }{ \N
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
gerade ist
\mavergleichskettedisp
{\vergleichskette
{g(f(n))
}
{ =} {g { \left( - { \frac{ n }{ 2 } } \right) }
}
{ =} { n
}
{ } {
}
{ } {
}
}
{}{}{}
und für
\mavergleichskette
{\vergleichskette
{n
}
{ \in }{ \N
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
ungerade ist
\mavergleichskettedisp
{\vergleichskette
{ g(f(n))
}
{ =} {g { \left( { \frac{ n+1 }{ 2 } } \right) }
}
{ =} { 2 { \frac{ n+1 }{ 2 } } -1
}
{ =} { n
}
{ } {
}
}
{}{}{.}
Umgekehrt ist für
\mavergleichskette
{\vergleichskette
{m
}
{ \in }{\Z
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
bei
\mavergleichskette
{\vergleichskette
{m
}
{ \leq }{0
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
\mavergleichskettedisp
{\vergleichskette
{f(g(m))
}
{ =} { f(2 \betrag { m } )
}
{ =} { f( - 2 m )
}
{ =} { - { \left( - m \right) }
}
{ =} { m
}
}
{}{}{}
und bei
\mavergleichskette
{\vergleichskette
{m
}
{ > }{0
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
\mavergleichskettedisp
{\vergleichskette
{f(g(m))
}
{ =} { f(2 m -1 )
}
{ =} { { \frac{ 2m-1+1 }{ 2 } }
}
{ =} { m
}
{ } {}
}
{}{}{.}
}
\inputaufgabepunkteloesung
{6}
{
Beweise den Satz über die Wohldefiniertheit der Anzahl einer endlichen Menge.
}
{
Es seien die bijektiven Abbildungen
\maabbdisp {\varphi} { { \{ 1 , \ldots , n \} } } {M
} {}
und
\maabbdisp {\psi} { \{ 1 , \ldots , k \} } {M
} {}
gegeben. Da man bijektive Abbildungen umkehren kann und da die Hintereinanderschaltung von bijektiven Abbildungen nach
Lemma 6.4 (Grundkurs Mathematik (Osnabrück 2022-2023)) (3)
wieder bijektiv ist, ist auch
\maabbdisp {\psi^{-1} \circ \varphi} { { \{ 1 , \ldots , n \} } } { \{ 1 , \ldots , k \}
} {}
bijektiv. Wir müssen also nur die endlichen Standardmengen
\mathl{{ \{ 1 , \ldots , n \} }}{} untereinander vergleichen. Wir müssen also zeigen, dass wenn eine bijektive Abbildung
\maabbdisp {\theta} { { \{ 1 , \ldots , n \} } } { \{ 1 , \ldots , k \}
} {}
vorliegt, dass dann
\mavergleichskettedisp
{\vergleichskette
{n
}
{ =} {k
}
{ } {
}
{ } {
}
{ } {
}
}
{}{}{}
ist. Dies zeigen wir durch Induktion nach $n$. Wenn
\mavergleichskette
{\vergleichskette
{n
}
{ = }{ 0
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
ist, so ist die Menge links leer und somit muss auch die rechte Menge leer sein, also ist dann auch
\mavergleichskette
{\vergleichskette
{k
}
{ = }{ 0
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{.}
Es seien nun
\mathl{n,k}{} nicht $0$, so dass sie also jeweils einen Vorgänger haben. Es sei $m$ der Vorgänger von $n$ und $\ell$ der Vorgänger von $k$. Diese Zahlen sind eindeutig bestimmt, da die Nachfolgerabbildung injektiv ist. Wir setzen
\mavergleichskettedisp
{\vergleichskette
{ z
}
{ =} {\theta (n)
}
{ \in} { \{ 1 , \ldots , k \}
}
{ } {
}
{ } {
}
}
{}{}{.}
Dann gibt es nach der Herausnahme von $n$ bzw. $z$ eine bijektive Abbildung
\maabbdisp {} { \{ 1 , \ldots , m \} = { \{ 1 , \ldots , n \} } \setminus \{n\} } { \{ 1 , \ldots , k \} \setminus \{z\}
} {.}
Nach
Lemma 6.9 (Grundkurs Mathematik (Osnabrück 2022-2023))
gibt es eine bijektive Abbildung zwischen
\mathkor {} {\{1 , \ldots , \ell \}} {und} {\{ 1 , \ldots , k \} \setminus \{z\}} {.}
Somit gibt es dann auch insgesamt eine bijektive Abbildung zwischen
\mathkor {} {\{ 1 , \ldots , m \}} {und} {\{1 , \ldots , \ell \}} {.}
Nach Induktionsvoraussetzung ist
\mavergleichskette
{\vergleichskette
{m
}
{ = }{\ell
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{,}
also auch
\mavergleichskettedisp
{\vergleichskette
{n
}
{ =} {m'
}
{ =} {\ell'
}
{ =} {k
}
{ } {
}
}
{}{}{.}
}
\inputaufgabepunkteloesung
{3}
{
Beweise durch Induktion die folgende Formel für
\mavergleichskette
{\vergleichskette
{n
}
{ \geq }{1
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{.}
\mavergleichskettedisp
{\vergleichskette
{ \sum_{k = 1}^n k
}
{ =} {{ \frac{ n(n+1) }{ 2 } }
}
{ } {
}
{ } {
}
{ } {
}
}
{}{}{.}
}
{
Beim Induktionsanfang ist
\mavergleichskette
{\vergleichskette
{n
}
{ = }{1
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{,}
daher besteht die Summe links nur aus einem Summanden, nämlich der $1$, und daher ist die Summe $1$. Die rechte Seite ist
\mavergleichskette
{\vergleichskette
{ { \frac{ 1 \cdot 2 }{ 2 } }
}
{ = }{1
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{,}
so dass die Formel für
\mavergleichskette
{\vergleichskette
{n
}
{ = }{1
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
stimmt.
Für den Induktionsschritt setzen wir voraus, dass die Formel für ein
\mavergleichskette
{\vergleichskette
{n
}
{ \geq }{1
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
gilt, und müssen zeigen, dass sie auch für
\mathl{n+1}{} gilt. Dabei ist $n$ beliebig. Es ist
\mavergleichskettealign
{\vergleichskettealign
{\sum_{k = 1}^{n+1} k
}
{ =} {\left(\sum_{k = 1}^{n} k\right) + n+1
}
{ =} { { \frac{ n(n+1) }{ 2 } } + n+1
}
{ =} { { \frac{ n(n+1) +2(n+1) }{ 2 } }
}
{ =} { { \frac{ (n+2)(n+1) }{ 2 } }
}
}
{}
{}{.}
Dabei haben wir für die zweite Gleichheit die Induktionsvoraussetzung verwendet. Der zuletzt erhaltene Term ist die rechte Seite der Formel für
\mathl{n+1}{,} also ist die Formel bewiesen.
}
\inputaufgabepunkteloesung
{3}
{
Zeige durch vollständige Induktion, dass für jedes
\mavergleichskette
{\vergleichskette
{n
}
{ \in }{ \N
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
die Zahl
\mathdisp {6^{n+2} + 7^{2n+1}} { }
ein Vielfaches von $43$ ist.
}
{
Induktionsanfang. Für
\mavergleichskette
{\vergleichskette
{n
}
{ = }{0
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
ist
\mavergleichskettedisp
{\vergleichskette
{6^2+7
}
{ =} {43
}
{ } {
}
{ } {
}
{ } {
}
}
{}{}{}
ein Vielfaches von $43$. Induktionsschritt. Es sei nun die Aussage für $n$ bewiesen und betrachten wir den Ausdruck für
\mathl{n+1}{.} Dieser ist
\mavergleichskettealign
{\vergleichskettealign
{ 6^{n+1+2} + 7^{2(n+1)+1}
}
{ =} { 6 \cdot 6^{n+2} + 7^2 \cdot 7^{2n+1}
}
{ =} { 6 \cdot 6^{n+2} + (6+43) 7^{2n+1}
}
{ =} { 6 { \left( 6^{n+2} +7^{2n+1} \right) } + 43 \cdot 7^{2n+1}
}
{ =} { 6 \cdot 43 \cdot s + 43 \cdot 7^{2n+1}
}
}
{
\vergleichskettefortsetzungalign
{ =} { 43 \cdot { \left( 6 \cdot s + 7^{2n+1} \right) }
}
{ } {}
{ } {}
{ } {}
}
{}{,}
wobei im vorletzten Schritt die Induktionsvoraussetzung verwendet wurde
\zusatzklammer {nämlich die Eigenschaft, dass \mathlk{6^{n+2} +7^{2n+1}}{} ein Vielfaches von $43$ ist} {} {.}
Daher ist diese Zahl ein Vielfaches von $43$.
}
\inputaufgabepunkteloesung
{3}
{
Beweise in $\N$ die Gleichheit
\mavergleichskettedisp
{\vergleichskette
{(n+k)'
}
{ =} {n' +k
}
{ } {
}
{ } {
}
{ } {}
}
{}{}{}
durch Induktion über $k$ unter Verwendung der Gleichung
\mavergleichskette
{\vergleichskette
{n+k'
}
{ = }{(n+k)'
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{,}
wobei $x \mapsto x^\prime$ die Nachfolgerabbildung bezeichnet.
}
{
Wir beweisen die Aussage für ein beliebiges $n$ durch Induktion über $k$. Bei
\mathl{k=0}{} steht beidseitig $n^\prime$. Es sei die Aussage nun für $k$ schon bewiesen und betrachten wir $k^\prime$. Dann ist
\mavergleichskettedisp
{\vergleichskette
{ (n+ k^\prime)^\prime
}
{ =} { ( (n+k)^\prime)^\prime
}
{ =} {( n^\prime +k )^\prime
}
{ =} { n^\prime + k^\prime
}
{ } {
}
}
{}{}{.}
}