Kurs:Grundkurs Mathematik/Teil I/T4/Klausur mit Lösungen

Aufgabe	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17	18	19	20	21	22	${}\sum$
Punkte	3	3	6	2	1	5	3	3	4	1	2	2	2	3	2	2	3	2	3	6	3	3	64

Aufgabe (3 Punkte)

Definiere die folgenden (kursiv gedruckten) Begriffe.

Die Multiplikation ${}a\cdot b$ von natürlichen Zahlen ${}a,b$ .
Eine lineare (oder totale) Ordnung ${}\preccurlyeq$ auf einer Menge ${}I$ .
Die Differenz ${}a-b$ von natürlichen Zahlen ${}a,b$ mit ${}b\leq a$ .
Eine Primzahl.
Der Binomialkoeffizient ${}{\binom {n}{k}}$ .
Die Multiplikation von ganzen Zahlen.

Lösung

Das Produkt ${}a\cdot b$ ist definiert als die ${}a$ -fache Summe der Zahl ${}b$ mit sich selbst.
Eine Ordnungsrelation ${}\preccurlyeq$ auf ${}I$ heißt lineare Ordnung, wenn zu je zwei Elementen ${}x,y\in I$ die Beziehung ${}x\preccurlyeq y$ oder ${}y\preccurlyeq x$ gilt.
Die Differenz ${}a-b$ ist diejenige natürliche Zahl ${}c$ für die ${}a=b+c$ gilt.
Eine natürliche Zahl ${}n\geq 2$ heißt eine Primzahl, wenn die einzigen natürlichen Teiler von ihr ${}1$ und ${}n$ sind.
Der Binomialkoeffizient ist durch
${}{\binom {n}{k}}={\frac {n!}{k!(n-k)!}}\,$

definiert.
Die ganzen Zahlen haben die Form ${}\pm a$ und ${}\pm b$ mit natürlichen Zahlen ${}a,b$ . Die Multiplikation wird folgendermaßen definiert.
${}a\cdot b:=a\cdot b\,,$

${}a\cdot (-b):=-(a\cdot b)\,,$

${}(-a)\cdot b:=-(a\cdot b)\,,$

${}(-a)\cdot (-b):=a\cdot b\,.$

Aufgabe (3 Punkte)

Formuliere die folgenden Sätze.

Der Satz von Euklid über Primzahlen.
Die rekursive Beziehung zwischen den Binomialkoeffizienten (Pascalsches Dreieck).
Die Division mit Rest für natürliche Zahlen.

Lösung

Es gibt unendlich viele Primzahlen.
Die Binomialkoeffizienten erfüllen die rekursive Beziehung
${}{\binom {n+1}{k}}={\binom {n}{k}}+{\binom {n}{k-1}}\,.$
Es sei ${}d$ eine fixierte positive natürliche Zahl. Dann gibt es zu jeder natürlichen Zahl ${}n$ eine eindeutig bestimmte natürliche Zahl ${}q$ und eine eindeutig bestimmte natürliche Zahl ${}r$ , ${}0\leq r\leq d-1$ , mit
${}n=qd+r\,.$

Aufgabe (6 Punkte)

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)$ .

Lösung

Wir betrachten die Abbildungen

\varphi \colon {\mathfrak {P}}\,(G)\longrightarrow {\mathfrak {P}}\,(A)\times {\mathfrak {P}}\,(B),\,T\longmapsto (T\cap A,T\cap B),

und

\psi \colon {\mathfrak {P}}\,(A)\times {\mathfrak {P}}\,(B)\longrightarrow {\mathfrak {P}}\,(G),\,(U,V)\longmapsto U\cup V,

und behaupten, dass diese beiden Abbildungen zueinander invers sind. Die Verknüpfung ${}\psi \circ \varphi$ sendet insgesamt eine Teilmenge ${}T\subseteq G$ auf

(T\cap A)\cup (T\cap B).

Die Inklusion

{}(T\cap A)\cup (T\cap B)\subseteq T\,

ist dabei klar. Wenn umgekehrt ${}x\in T$ liegt, so ist aufgrund der Voraussetzung ${}x\in A$ oder ${}x\in B$ und damit ist auch ${}x\in (T\cap A)\cup (T\cap B)$ . Daher ist ${}\psi \circ \varphi$ die Identität.

Die Verknüpfung ${}\varphi \circ \psi$ sendet insgesamt ein Paar ${}(U,V)$ bestehend aus Teilmengen ${}U\subseteq A$ und ${}V\subseteq B$ auf

((U\cup V)\cap A,(U\cup V)\cap B).

Wir behaupten

{}(U\cup V)\cap A=U\,

(und entsprechend für die zweite Komponente). Dabei ist die Inklusion ${}\supseteq$ klar. Wenn umgekehrt ${}x\in (U\cup V)\cap A$ ist, so ist ${}x\in A$ und ${}x\in U\cup V$ . Wegen ${}V\subseteq B$ und der Disjunktheit von ${}B$ und ${}A$ kann nicht ${}x$ zu ${}V$ gehören, also ist ${}x\in U$ . Daher ist auch ${}\varphi \circ \psi$ die Identität.

Aufgabe (2 Punkte)

Es seien ${}a,b,c$ natürliche Zahlen mit ${}a,b\geq c$ . Zeige

{}(a-c)+b=a+(b-c)\,.

Gilt

{}(8-5)+3=8+(3-5)\,

in ${}\mathbb {N}$ ?

Lösung

Aufgrund der Abziehregel können wir die Gleichheit dadurch zeigen, dass wir beidseitig ${}c$ dazuaddieren und dafür die Gleichheit zeigen. Diese ergibt sich aus

{}(a-c)+b+c=(a-c)+c+b=a+b=a+(b-c)+c\,.

Die angegebene Beispielgleichung ist in ${}\mathbb {N}$ nicht definiert, da der Ausdruck ${}3-5$ nicht definiert ist.

Aufgabe (1 Punkt)

Es seien ${}a,b$ Elemente in einem kommutativen Halbring ${}R$ . Berechne

(a+2b)\cdot (2a+3b).

Lösung

Nach dem Distributivgesetz ist

{}{\begin{aligned}(a+2b)\cdot (2a+3b)&=a\cdot (2a+3b)+2b\cdot (2a+3b)\\&=2a^{2}+3ab+4ab+6b^{2}\\&=2a^{2}+7ab+6b^{2}.\end{aligned}}

Aufgabe (5 Punkte)

Es sei ${}n$ eine fixierte natürliche Zahl und

{}M={\{1,\ldots ,n\}}\,.

Wir betrachten die beiden Verknüpfungen (Maximum und Minimum)

M\times M\longrightarrow M,\,(a,b)\longmapsto \operatorname {max} (a,b),

und

M\times M\longrightarrow M,\,(a,b)\longmapsto \operatorname {min} (a,b).

Zeige, dass ${}M$ mit diesen beiden Verknüpfungen (mit welchen neutralen Elementen?) ein kommutativer Halbring ist.

Lösung

Die Kommutativität und die Assoziativität der beiden Verknüpfungen ist klar. Das neutrale Element des Maximums ist die ${}1$ und das neutrale Element des Minimums ist ${}n$ , da ja nur Elemente aus ${}{\{1,\ldots ,n\}}$ vorkommen. Es bleibt also noch das Distributivgesetz zu zeigen, welches bei den gegebenen Verknüpfungen (wir setzen das Maximum als Addition und das Minimum als Multiplikation an)

{}\operatorname {min} (a,\operatorname {max} (b,c))=\operatorname {max} (\operatorname {min} (a,b),\operatorname {min} (a,c))\,

bedeutet. Dies beweisen wir durch eine Fallunterscheidung. Da die Situation in ${}b$ und ${}c$ symmetrisch ist, können wir ${}b\leq c$ annehmen. Bei

{}a\leq b\leq c\,

ergibt sich links ${}a$ und rechts ebenfalls ${}\operatorname {max} (a,a)=a$ . Bei

{}b\leq a\leq c\,

ergibt sich links

{}\operatorname {min} (a,\operatorname {max} (b,c))=\operatorname {min} (a,c)=a\,

und rechts ebenfalls

{}\operatorname {max} (\operatorname {min} (a,b),\operatorname {min} (a,c))=\operatorname {max} (b,a)=a\,.

Bei

{}b\leq c\leq a\,

ergibt sich links

{}\operatorname {min} (a,\operatorname {max} (b,c))=\operatorname {min} (a,c)=c\,

und rechts ebenfalls

{}\operatorname {max} (\operatorname {min} (a,b),\operatorname {min} (a,c))=\operatorname {max} (b,c)=c\,.

Aufgabe (3 Punkte)

Wir betrachten die Gesamtmenge aller Finger und aller Zehen eines Menschen. Man gebe für jede Faktorzerlegung

{}20=a\cdot b\,

eine möglichst natürliche Zerlegung dieser ${}20$ Körperteile in ${}a$ Teilmengen mit je ${}b$ Elemente an.

Lösung

{}20=20\cdot 1\,.

Hier nimmt man die 20 Einzelfinger bzw. Einzelzehen als einelementige Mengen.

{}20=10\cdot 2\,.

Die natürlichste Zerlegung in ${}10$ zweielementige Teilmengen (Paare) ist wohl die in zwei Zehen, zwei Zeigefinger, zwei Mittelfinger, zwei Ringfinger, zwei kleine Finger und entsprechend die Zehenpaare der Füße.

{}20=5\cdot 4\,.

Die natürlichste Zerlegung dieser ${}20$ Körperteile in ${}5$ Teilmengen mit je ${}4$ Elemente ist wohl die, bei der die Daumen zusammen mit den großen Zehen, die Zeigefinger und die Zeigezehen, die Mittelfinger und die Mittelzehen, die Ringfinger und die Ringzehen, sowie die kleinen Finger und kleinen Zehen eine Teilmenge bilden.

{}20=4\cdot 5\,.

Hier nimmt man die einzelnen Hände (also die Finger, die dran hängen) bzw. Füße als Teilmengen.

{}20=2\cdot 10\,.

Hier nimmt man einerseits alle Finger und andererseits alle Zehen als Teilmengen (man könnte auch die linke und die rechte Hälfte nehmen).

{}20=1\cdot 20\,.

Die Gesamtmenge aller Finger und Zehen.

Aufgabe (3 Punkte)

Zeige durch Induktion, dass jede natürliche Zahl ${}n\geq 2$ eine Zerlegung in Primzahlen besitzt.

Lösung

Wir beweisen die Existenz durch Induktion über ${}n$ . Für ${}n=2$ liegt eine Primzahl vor. Bei ${}n\geq 3$ ist entweder ${}n$ eine Primzahl, und diese bildet die Primfaktorzerlegung, oder aber ${}n$ ist keine Primzahl. In diesem Fall gibt es eine nichttriviale Zerlegung ${}n=ab$ mit kleineren Zahlen ${}a,b<n$ . Für diese Zahlen gibt es nach Induktionsvoraussetzung jeweils eine Zerlegung in Primfaktoren, und diese setzen sich zu einer Primfaktorzerlegung für ${}n$ zusammen.

Aufgabe (4 Punkte)

Es sei ${}M$ eine ${}n$ -elementige Menge und sei

B={\left\{F:M\rightarrow M{\text{ Abbildung}}\mid F{\text{ bijektiv}}\right\}}.

Zeige, dass

{}{\#\left(B\right)}=n!\,

ist.

Lösung

Wir zeigen etwas allgemeiner, dass es zwischen zwei endlichen Mengen ${}M$ und ${}N$ , die beide ${}n$ Elemente besitzen, ${}n!$ bijektive Abbildungen gibt. Dies zeigen wir durch Induktion nach ${}n$ , wobei der Fall ${}n=1$ klar ist. Die Aussage sei nun für ${}n$ schon bewiesen und es liegen zwei ${}(n+1)$ -elementige Mengen ${}M$ und ${}N$ vor. Es sei ${}x\in M$ ein fixiertes Element. Dann gibt es für die Bilder ${}\varphi (x)$ genau ${}n+1$ Möglichkeiten, nämlich die Anzahl der Menge ${}N$ . Wenn dies festgelegt ist, so entsprechen die bijektiven Abbildungen von ${}M$ nach ${}N$ mit

{}\varphi (x)=y\,

den bijektiven Abbildungen von ${}M\setminus \{x\}$ nach ${}N\setminus \{y\}$ . Nach Induktionsvoraussetzung gibt es ${}n!$ solche bijektiven Abbildungen. Daher ist die Anzahl der bijektiven Abbildungen zwischen ${}M$ und ${}N$ gleich

{}(n+1)\cdot n!=(n+1)!\,.

Aufgabe (1 Punkt)

Bestimme die Primfaktorzerlegung von

{\binom {15}{5}}.

Lösung

Es ist

{}{\binom {15}{5}}={\frac {15\cdot 14\cdot 13\cdot 12\cdot 11}{5\cdot 4\cdot 3\cdot 2\cdot 1}}={\frac {14\cdot 13\cdot 12\cdot 11}{4\cdot 2}}={\frac {7\cdot 13\cdot 3\cdot 11}{1}}=3\cdot 7\cdot 11\cdot 13\,.

Aufgabe (2 Punkte)

Bestimme den Rest von ${}10$ bei Division durch ${}1,2,3,4,5,6,7,8,9$ .

Lösung

Die Reste ${}r$ bei Division von ${}10$ durch ${}d$ sind

${}d$	${}1$	${}2$	${}3$	${}4$	${}5$	${}6$	${}7$	${}8$	${}9$
${}r$	${}0$	${}0$	${}1$	${}2$	${}0$	${}4$	${}3$	${}2$	${}1$

Aufgabe (2 Punkte)

Siehe Extrablatt.

Lösung Extrablatt/Aufgabe/Lösung

Aufgabe (2 Punkte)

Betrachte im ${}13$ er System mit den Ziffern ${}0,1,\ldots ,8,9,A,B,C$ die Zahl

B4AC.

Wie sieht diese Zahl im Zehnersystem aus?

Lösung

Es ist

{}{\begin{aligned}B4AC&=11\cdot 13^{3}+4\cdot 13^{2}+10\cdot 13+12\\&=11\cdot 2197+4\cdot 169+130+12\\&=24167+676+142\\&=24985.\end{aligned}}

Aufgabe (3 Punkte)

Beschreibe einen Algorithmus, der zu einer beliebigen im Dezimalsystem gegebenen Zahl ${}n\geq 1$ ihren Vorgänger im Dezimalsystem bestimmt.

Lösung

Die Zahl sei durch die Ziffernfolge ${}a_{k}\ldots a_{1}a_{0}$ im Dezimalsystem gegeben. Da ${}0$ ausgeschlossen ist, muss bei ${}a_{0}=0$ die Zahl zumindest zweistellig sein, also ${}k\geq 1$ . Der Vorgänger zu dieser Zahl wird durch das folgende Verfahren bestimmt.

Wenn ${}a_{0}\neq 0$ ist, so ersetzt man die hinterste Ziffer ${}a_{0}$ durch ihren (einstelligen) Vorgänger. Dieser ist durch die Reihenfolge in der Liste ${}0,1,2,3,4,5,6,7,8,9$ bestimmt. Die anderen Ziffern werden übernommen.
Wenn ${}a_{0}=0$ ist, so sei der Index ${}s$ durch die Eigenschaft charakterisiert, dass
${}a_{0}=a_{1}=\ldots =a_{s}=0\,$

und ${}a_{s+1}\neq 0$ ist. Da die Zahl nicht selbst ${}0$ ist, muss es ein solches ${}s$ geben. Der Vorgänger ergibt sich, wenn man an den hinteren ${}s+1$ Stellen die zusammenhängenden Nullen durch Neunen ersetzt, die Ziffer ${}a_{s+1}$ durch ihren einstelligen Vorgänger (gemäß Liste) ersetzt und die übrigen Ziffern beibehält.

Dieses Verfahren ist korrekt, da es den entsprechenden Nachfolgeralgorithmus invertiert.

Aufgabe (2 Punkte)

Führe die Multiplikation ${}8092\cdot 714$ mit dem Jalousie-Verfahren durch.

Lösung

{\begin{matrix}&&&&&&2&&\cdot &&7&&&&\\&&&&&&&\diagup &{|}&\diagdown &&&&&\\&&&&9&&\diagup &1&{|}&4&\diagdown &&1&&\\&&&&&\diagup &{|}&\diagdown &{|}&\diagup &{|}&\diagdown &&&\\&&0&&\diagup &6&{|}&3&\cdot &0&{|}&2&\diagdown &&4\\&&&\diagup &{|}&\diagdown &{|}&\diagup &{|}&\diagdown &{|}&\diagup &{|}&\diagdown &\\8&&\diagup &0&{|}&0&\cdot &0&{|}&9&\cdot &0&{|}&8&\cdot \\&\diagup &{|}&\diagdown &{|}&\diagup &{|}&\diagdown &{|}&\diagup &{|}&\diagdown &{|}&\diagup &\\\cdot &5&{|}&6&\cdot &0&{|}&0&\cdot &3&{|}&6&\diagup &&\\&\diagdown &{|}&\diagup &{|}&\diagdown &{|}&\diagup &{|}&\diagdown &{|}&\diagup &&&\\&&\diagdown &0&{|}&8&\cdot &0&{|}&0&\diagup &&&&\\&&&\diagdown &{|}&\diagup &{|}&\diagdown &{|}&\diagup &&&&&\\&&&&\diagdown &3&{|}&2&\diagup &&&&&\\&&&&&\diagdown &{|}&\diagup &&&&&&&\\&&&&&&\cdot &&&&&&&&\\&&&1&&&&1&&&&&&&\\\cdots &\cdots &\cdots &\cdots &\cdots &\cdots &\cdots &\cdots &\cdots &\cdots &\cdots &\cdots &\cdots &\cdots &\cdots \\&5&&7&&7&&7&&6&&8&&8&\end{matrix}}

Aufgabe (2 (0.5+0.5+0.5+0.5) Punkte)

Bestimme, von welcher Art (im Sinne der Vorlesung) die folgenden Gleichungen sind.

${}-(-x)=x\,,$
${}x^{2}-3x+5=0\,.$
${}13-8=5\,,$
${}a_{n}a_{n-1}\ldots a_{2}a_{1}a_{0}=\sum _{i=0}^{n}a_{i}10^{i}\,.$

Lösung

Formel (für ${}\mathbb {Z}$ oder in einer Gruppe),
Bedingungsgleichung,
Elementgleichung,
Definitionsgleichung unter der Voraussetzung ${}a_{i}\leq 9$ .

Aufgabe (3 (1+2) Punkte)

Finde eine quadratische Gleichung der Form
${}x^{2}+px+q=0\,$

mit ${}p,q\in \mathbb {Z}$ , für die ${}17$ die einzige Lösung ist.
Finde unendlich viele verschiedene quadratische Gleichungen der Form
${}x^{2}+px+q=0\,$

mit ${}p,q\in \mathbb {Z}$ , für die ${}17$ eine Lösung ist.

Lösung

Für jede ganze Zahl ${}k$ ist generell

{}(x-17)(x-k)=x^{2}-(k+17)x+17k\,.

Dies führt zu einer quadratischen Gleichung mit ${}p=-(k+17)$ und ${}q=17k$ . Wenn man darin ${}x$ gleich ${}17$ setzt, ergibt sich ${}0$ wegen dem ersten Faktor. Somit sind unendlich viele quadratische Gleichungen mit Koeffizienten aus ${}\mathbb {Z}$ gefunden, die ${}17$ als Lösung besitzen. Wenn man

{}k=17\,

setzt, so erhält man die quadratische Gleichung

{}(x-17)(x-17)=x^{2}-34x+289=0\,.

Für diese ist nur ${}17$ eine Lösung.

Aufgabe (2 Punkte)

Sie stehen an einem Klippenrand. Jemand sagt: „Innerhalb der ganzen Zahlen ist der Vorgänger des Nachfolgers und der Nachfolger des Vorgängers das Element selbst. Es ist also beispielsweise egal, ob ich zuerst einen Schritt nach vorne und dann nach hinten mache oder umgekehrt. Machen Sie also ruhig einen Schritt nach vorne.“ Klären Sie diese paradoxe Situation.

Lösung Klippe/Vorgänger und Nachfolger/Aufgabe/Lösung

Aufgabe (3 (1+2) Punkte)

Lucy Sonnenschein unternimmt eine Zeitreise. Sie reist zuerst ${}16$ Stunden nach vorne, dann (immer vom jeweiligen erreichten Zeitpunkt aus) ${}5$ Stunden nach vorne, dann ${}26$ Stunden zurück, dann ${}4$ Stunden zurück, dann ${}8$ Stunden nach vorne und dann ${}12$ Stunden zurück.

Wo befindet sie sich am Ende dieser Zeitreise, wenn die Reise selbst keine Zeit verbraucht?
Wo befindet sie sich am Ende dieser Zeitreise, wenn eine Zeitreise um eine Stunde, egal ob in die Zukunft oder in die Vergangenheit, immer eine Minute verbraucht?

Lösung

Wir rechnen
${}16+5+(-26)+(-4)+8-12=-13\,,$

also ${}13$ Stunden zurück.
Insgesamt reist sie
${}16+5+26+4+8+12=71\,$

Stunden, das verbraucht also ${}71$ Minuten, also eine Stunde und elf Minuten. Daher befindet sie sich am Ende der Zeitreise im Zeitpunkt vor ${}11$ Stunden und ${}49$ Minuten.

Aufgabe (6 Punkte)

Beweise das Lemma von Bezout für teilerfremde natürliche Zahlen ${}a$ und ${}b$ durch Induktion über das Maximum von ${}a$ und ${}b$ .

Lösung

Wir beweisen die Aussage durch Induktion über das Maximum von ${}a$ und ${}b$ , wobei wir ohne Einschränkung ${}a\leq b$ wählen können. Wenn das Maximum ${}0$ ist, so sind beide Zahlen ${}0$ und somit nicht teilerfremd. Wenn das Maximum ${}1$ ist, so ist ${}b=1$ und somit ergeben ${}r=0$ und ${}s=1$ eine Darstellung der ${}1$ . Es seien nun ${}a\leq b$ teilerfremd, ${}b\geq 2$ und die Aussage sei für alle Zahlenpaare, deren Maxima kleiner als ${}b$ sind, schon bewiesen. Dann ist ${}a<b$ , da bei ${}a=b$ die beiden Zahlen nicht teilerfremd sind. Ebenso können wir ${}a=0$ ausschließen. Wir betrachten das Zahlenpaar ${}(a,b-a)$ und wollen darauf die Induktionsvoraussetzung anwenden. Das Maximum dieses neuen Paares ist jedenfalls kleiner als ${}b$ . Allerdings müssen wir, damit die Induktionsvoraussetzung wirklich angewendet werden kann, wissen, dass auch ${}a$ und ${}b-a$ teilerfemd sind. Dazu führen wir einen Widerspruchsbeweis. Nehmen wir also an, dass ${}a$ und ${}b-a$ nicht teilerfremd sind. Dann gibt es eine natürliche Zahl ${}t\geq 2$ , die sowohl ${}a$ als auch ${}b-a$ teilt. Dies bedeutet wiederum, dass es natürliche Zahlen ${}m,n$ mit ${}a=mt$ und ${}b-a=nt$ gibt. Doch dann ist

{}b=(b-a)+a=nt+mt=(n+m)t\,

ebenfalls ein Vielfaches von ${}t$ , im Widerspruch zur Teilerfremdheit von ${}a$ und ${}b$ . Die Induktionsvoraussetzung ist also auf ${}a$ und ${}b-a$ anwendbar und somit gibt es ganze Zahlen ${}r,s$ mit

{}ra+s(b-a)=1\,.

Dann ist aber auch

{}(r-s)a+sb=ra+s(b-a)=1\,

und wir haben eine Darstellung der ${}1$ mit ${}a$ und ${}b$ gefunden.

Aufgabe (3 Punkte)

Bestimme in ${}\mathbb {Z}$ mit Hilfe des euklidischen Algorithmus den größten gemeinsamen Teiler von ${}1085$ und ${}806$ und schreibe die beiden Zahlen als Vielfache des größten gemeinsamen Teilers.