Kurs:Diskrete Mathematik/7/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}{ 3 }
\renewcommand{\avier}{ 3 }
\renewcommand{\afuenf}{ 4 }
\renewcommand{\asechs}{ 3 }
\renewcommand{\asieben}{ 0 }
\renewcommand{\aacht}{ 2 }
\renewcommand{\aneun}{ 8 }
\renewcommand{\azehn}{ 2 }
\renewcommand{\aelf}{ 2 }
\renewcommand{\azwoelf}{ 2 }
\renewcommand{\adreizehn}{ 4 }
\renewcommand{\avierzehn}{ 1 }
\renewcommand{\afuenfzehn}{ 0 }
\renewcommand{\asechzehn}{ 0 }
\renewcommand{\asiebzehn}{ 0 }
\renewcommand{\aachtzehn}{ 0 }
\renewcommand{\aneunzehn}{ 0 }
\renewcommand{\azwanzig}{ 40 }
\renewcommand{\aeinundzwanzig}{ }
\renewcommand{\azweiundzwanzig}{ }
\renewcommand{\adreiundzwanzig}{ }
\renewcommand{\avierundzwanzig}{ }
\renewcommand{\afuenfundzwanzig}{ }
\renewcommand{\asechsundzwanzig}{ }
\punktetabelleneunzehn
\klausurnote
\newpage
\setcounter{section}{0}
\inputaufgabeklausurloesung
{3}
{
Definiere die folgenden \zusatzklammer {kursiv gedruckten} {} {} Begriffe. \aufzaehlungsechs{Eine \stichwort {endliche} {} Menge $M$ mit $n$ Elementen.
}{Ein
\stichwort {größtes Element} {}
\mathl{x \in I}{} in einer
\definitionsverweis {geordneten Menge}{}{}
\mathl{(I,\preccurlyeq)}{.}
}{Zwei \stichwort {teilerfremde} {} natürliche Zahlen \mathkor {} {a} {und} {b} {.}
}{Ein
\stichwort {kantenfreier} {}
Graph
\mavergleichskette
{\vergleichskette
{G
}
{ = }{(V,E)
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{.}
}{Eine
\stichwort {Paarung} {}
in einem
\definitionsverweis {Graphen}{}{}
\mavergleichskette
{\vergleichskette
{G
}
{ = }{ (V,E)
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{.}
}{Das \stichwort {chromatische Polynom} {} eines Graphen $G$. }
}
{
\aufzaehlungsechs{Eine Menge $M$ heißt endlich mit $n$ Elementen, wenn es eine
\definitionsverweis {Bijektion}{}{}
\maabbdisp {} {{ \{ 1 , \ldots , n \} } } { M } {}
gibt.
}{Ein Element
\mathl{x \in I}{} heißt größtes Element von $I$, wenn
\mavergleichskette
{\vergleichskette
{ y
}
{ \preccurlyeq }{x
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
für jedes
\mathl{y \in I}{} gilt.
}{Die beiden natürlichen Zahlen
\mathkor {} {a} {und} {b} {}
heißen teilerfremd, wenn sie keinen gemeinsamen
\definitionsverweis {Teiler}{}{}
\mathl{\geq 2}{} besitzen.
}{Der
\definitionsverweis {Graph}{}{}
$G$ heißt
kantenfrei,
wenn die Kantenmenge $E$ leer ist.
}{Eine
Paarung
in
\mavergleichskette
{\vergleichskette
{G
}
{ = }{ (V,E)
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
ist eine Kantenmenge
\mavergleichskette
{\vergleichskette
{P
}
{ \subseteq }{E
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{,}
wobei die Kanten aus $P$ zueinander disjunkt sind.
}{Unter dem
chromatischen Polynom
\mathl{P_{ G }}{} versteht man die Funktion, die durch
\mavergleichskettedisp
{\vergleichskette
{ P_{ G } \left( k \right)
}
{ =} { { \# { \left\{ f:V \rightarrow \{ 1 , \ldots , k \} \mid f \text{ zulässige Färbung} \right\} } }
}
{ } {
}
{ } {
}
{ } {
}
}
{}{}{}
gegeben ist.
}
}
\inputaufgabeklausurloesung
{3}
{
Formuliere die folgenden Sätze. \aufzaehlungdrei{Der Satz über die Teilmengenanzahl einer endlichen Menge.}{Der Satz über die Äquivalenzrelation zu einer Abbildung \maabb {f} { M} {N } {.}}{Der Satz von Ore.}
}
{
\aufzaehlungdrei{Die Anzahl der $k$-elementigen Teilmengen in einer $n$-elementigen Menge ist der \definitionsverweis {Binomialkoeffizient}{}{}
\mathdisp {\binom { n } { k }} { . }
}{Durch die Festlegung
\mavergleichskettedisp
{\vergleichskette
{ x
}
{ \sim} {y
}
{ } {
}
{ } {
}
{ } {
}
}
{}{}{,}
wenn
\mavergleichskettedisp
{\vergleichskette
{ f(x)
}
{ =} { f(y)
}
{ } {
}
{ } {
}
{ } {
}
}
{}{}{,}
wird eine Äquivalenzrelation auf $M$ definiert.}{Es sei
\mavergleichskette
{\vergleichskette
{ G
}
{ = }{(V,E)
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
ein
\definitionsverweis {Graph}{}{}
mit mindestens drei Elementen, der die Bedingung
\mavergleichskettedisp
{\vergleichskette
{ d(u) + d(v)
}
{ \geq} { { \# \left( V \right) }
}
{ } {
}
{ } {
}
{ } {
}
}
{}{}{}
für je zwei nicht adjazente Knoten $u,v$ erfüllt. Dann ist $G$
\definitionsverweis {hamiltonsch}{}{.}}
}
\inputaufgabeklausurloesung
{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.
}
\inputaufgabeklausurloesung
{3}
{
\bild{ \begin{center}
\includegraphics[width=5.5cm]{ \bildeinlesungsvg {Wikt puzzle favicon} {svg} }
\end{center}
\bildtext {} }
\bildlizenz { Wikt puzzle favicon.svg } {} {Ephemeron} {Commons} {CC-by-sa 3.0} {}
Die Puzzleteile für ein Puzzle haben eine grob rechteckige Form, wobei die eine Seite erkennbar länger als die andere ist, und auf jeder Seite gibt es entweder eine Einbuchtung oder eine Ausbuchtung. Wie viele Typen von Puzzelteilen gibt es?
}
{
Wir betrachten die Puzzleteile je nachdem, ob sie
\mathl{0,1,2,3}{} oder $4$ Ausbuchtungen haben
\zusatzklammer {was die Anzahl der Einbuchtungen festlegt} {} {.}
Bei keiner Ausbuchtung gibt es keine weitere Unterscheidung. Bei einer Ausbuchtung kann die Ausbuchtung an einer kurzen oder an einer langen Seite sein. Bei zwei Ausbuchtungen gibt es vier Möglichkeiten: Die beiden Ausbuchtungen können gegenüber an den kurzen Seiten, oder gegenüber an den langen Seiten, oder nebeneinander an einer kurzen und an einer langen Seite sein. Im letzteren Fall macht es aber noch einen Unterschied, ob, wenn man die Ausbuchtung an der kurzen Seite nach oben dreht, die Ausbuchtung an der langen Seite links oder rechts liegt. Für drei Ausbuchtungen gibt es wieder zwei und bei vier Ausbuchtungen wieder eine Möglichkeit. Insgesamt gibt es also
\mavergleichskettedisp
{\vergleichskette
{1+2+4+2+1
}
{ =} { 10
}
{ } {
}
{ } {
}
{ } {
}
}
{}{}{}
Typen.
}
\inputaufgabeklausurloesung
{4}
{
Beweise den Satz über die Anzahl von bijektiven Abbildungen.
}
{
Wir führen Induktion über $n$, wobei der Fall
\mavergleichskette
{\vergleichskette
{n
}
{ = }{ 1
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
klar ist. Die Aussage sei nun für $n$ schon bewiesen und es liegen zwei
\mathl{(n+1)}{-}elementige Mengen
\mathkor {} {M} {und} {N} {}
vor. Es sei
\mavergleichskette
{\vergleichskette
{x
}
{ \in }{ M
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
ein fixiertes Element. Dann gibt es für die Werte
\mathl{\varphi(x)}{} genau
\mathl{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
\mavergleichskettedisp
{\vergleichskette
{\varphi(x)
}
{ =} { y
}
{ } {
}
{ } {
}
{ } {
}
}
{}{}{}
den bijektiven Abbildungen von
\mathl{M \setminus \{x\}}{} nach
\mathl{N \setminus \{y\}}{.} Nach Induktionsvoraussetzung gibt es $n!$ solche bijektiven Abbildungen. Daher ist die Anzahl der bijektiven Abbildungen zwischen
\mathkor {} {M} {und} {N} {}
gleich
\mavergleichskettedisp
{\vergleichskette
{(n+1) \cdot n!
}
{ =} { (n+1)!
}
{ } {
}
{ } {
}
{ } {
}
}
{}{}{.}
}
\inputaufgabeklausurloesung
{3}
{
\bild{ \begin{center}
\includegraphics[width=5.5cm]{ \bildeinlesungsvg {Squares in a square grid} {svg} }
\end{center}
\bildtext {} }
\bildlizenz { Squares in a square grid.svg } {} {David Epstein} {Commons} {gemeinfrei} {}
Wie viele Teilquadrate mit positiver Seitenlänge gibt es in einem Quadrat der Seitenlänge $5$? Die Seiten der Teilquadrate sollen wie im Bild auf dem \anfuehrung{Gitter}{} liegen, ein einzelner Punkt gelte nicht als Quadrat.
}
{
Die möglichen Seitenlängen sind
\mathl{1,2,3,4,5}{.} Ein Unterquadrat ist durch die Lage des Eckes links oben eindeutig bestimmt, man muss bei fixierter Seitenlänge nur berücksichtigen, dass das Teilquadrat ganz im Grundquadrat liegt. Somit gibt es für die Seitenlänge $5$ eine Möglichkeit, für die Seitenlänge $4$ vier Möglichkeiten, für die Seitenlänge $3$ neun Möglichkeiten, für die Seitenlänge $2$ $16$ Möglichkeiten und für die Seitenlänge $1$ $25$ Möglickeiten, Insgesamt gibt es also
\mavergleichskettedisp
{\vergleichskette
{ 1+4+9+16+25
}
{ =} { 55
}
{ } {
}
{ } {
}
{ } {
}
}
{}{}{}
Unterquadrate.
}
\inputaufgabeklausurloesung
{0}
{
}
{ }
\inputaufgabeklausurloesung
{2}
{
Beweise den Satz über die Lösbarkeit von Gleichungen in einer Gruppe $G$.
}
{
Wir betrachten die linke Gleichung. Aus beidseitiger Multiplikation mit $a^{-1}$ von links folgt, dass nur
\mavergleichskettedisp
{\vergleichskette
{ x
}
{ =} { a^{-1} \circ b
}
{ } {
}
{ } {
}
{ } {
}
}
{}{}{}
als Lösung in Frage kommt. Wenn man dies einsetzt, so sieht man, dass es sich in der Tat um eine Lösung handelt.
}
\inputaufgabeklausurloesung
{8 (1+2+3+2)}
{
Wir betrachten eine
\zusatzklammer {einfachere, aber langsamere} {} {}
Variante des euklidischen Algorithmus zur Bestimmung des größten gemeinsamen Teilers zu zwei gegebenen natürlichen Zahlen
\mathl{a,b}{.}
Der Algorithmus geht folgendermaßen. Wenn
\mavergleichskette
{\vergleichskette
{a
}
{ \neq }{b
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
ist, so ersetzte das Paar
\mathl{(a,b)}{} durch das Paar, das aus der kleineren Zahl und der Differenz zwischen der kleineren und der größeren Zahl besteht. Wiederhole dies rekursiv. Wenn
\mavergleichskette
{\vergleichskette
{a
}
{ = }{b
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
ist, so ist man fertig und es wird das Ergebnis $a$ ausgegeben.
\aufzaehlungvier{Führe diesen Algorithmus für das Paar
\mathl{(7,3)}{} durch.
}{Zeige, dass dieser Algorithmus nach endlich vielen Schritten aufhört.
}{Zeige, dass dieser Algorithmus korrekt ist, also wirklich den größten gemeinsmen Teiler ausgibt.
}{Man gebe für jedes $n$ ein Beispiel, wo der euklidische Algorithmus nach einem Schritt fertig ist, wo aber die Variante $n$ Schritte benötigt.
}
}
{
\aufzaehlungvier{Der Algorithmus ersetzt sukzessive
\mathdisp {(7,3) \mapsto (4,3) \mapsto (3,1) \mapsto (2,1) \mapsto (1,1)} { , }
der größte gemeinsame Teiler ist also $1$.
}{Wenn
\mavergleichskette
{\vergleichskette
{a
}
{ = }{b
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
ist, so hört der Algorithmus auf. Wenn genau eine Zahl $0$ ist, so ist das Folgepaar
\mathl{(c,c)}{} und dann hört der Algorithmus auf. Es sei also ohne Einschränkung
\mavergleichskettedisp
{\vergleichskette
{a
}
{ >} { b
}
{ >} { 0
}
{ } {
}
{ } {
}
}
{}{}{.}
Das Folgepaar ist dann
\mathl{(a-b,b)}{} und beide Zahlen sind kleiner als $a$. D.h. unter dieser Voraussetzung wird das Maximum mit jedem Rechenschritt kleiner. Da sich alles innerhalb der natürlichen Zahlen abspielt, bricht das Verfahren irgendwann ab.
}{Bei
\mavergleichskette
{\vergleichskette
{a
}
{ = }{b
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
ist diese Zahl auch der größte gemeinsame Teiler. Wir zeigen, dass sich bei jedem Rekursionsschritt, bei dem
\mathl{(a,b)}{}
\zusatzklammer {es sei wieder \mathlk{a \geq b}{}} {} {}
durch
\mathl{(a-b,b)}{} ersetzt wird, der größte gemeinsame Teiler der beiden Paare übereinstimmt. Dazu muss man nur zeigen, dass
\mathkor {} {a} {und} {b} {}
einerseits und
\mathkor {} {a-b} {und} {b} {}
andererseits die gleichen gemeinsamen Teiler haben. Es sei also
\mathl{t \in \N}{} und
\mavergleichskette
{\vergleichskette
{a
}
{ = }{tm
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
und
\mavergleichskette
{\vergleichskette
{b
}
{ = }{tn
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{.}
Dann ist
\mavergleichskettedisp
{\vergleichskette
{a-b
}
{ =} { mt-nt
}
{ =} { (m-n) t
}
{ } {
}
{ } {
}
}
{}{}{}
ebenfalls ein Vielfaches von $t$. Wenn umgekehrt
\mavergleichskette
{\vergleichskette
{a-b
}
{ = }{ rt
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
und
\mavergleichskette
{\vergleichskette
{b
}
{ = }{ st
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
ist, so ist
\mavergleichskettedisp
{\vergleichskette
{a
}
{ =} { a-b+b
}
{ =} { rt +st
}
{ =} {(r+s)t
}
{ } {
}
}
{}{}{}
ebenfalls ein Vielfaches von $t$.
}{Wir betrachten das Paar
\mathl{(n,1)}{.} Der euklidische Algorithmus liefert
\mavergleichskettedisp
{\vergleichskette
{n
}
{ =} { n \cdot 1 +0
}
{ } {
}
{ } {
}
{ } {
}
}
{}{}{}
und ist fertig. Die Variante ersetzt
\mathl{(n,1)}{} durch
\mathl{(n-1,1)}{,} sie braucht also $n-1$ Schritte, um die Abbruchbedingung
\mathl{(1,1)}{} zu erreichen.
}
}
\inputaufgabeklausurloesung
{2}
{
Es sei $n$ eine natürliche Zahl. Wann ist die Zahl
\mathl{n^2-1}{} eine
\definitionsverweis {Primzahl}{}{?}
}
{
Es gilt generell die Zerlegung
\mavergleichskettedisp
{\vergleichskette
{n^2-1
}
{ =} {(n-1)(n+1)
}
{ } {
}
{ } {
}
{ } {
}
}
{}{}{.}
Bei
\mathl{n \geq 3}{} sind beide Faktoren
\mathl{\geq 2}{} und daher kann $n^2-1$ nicht prim sein. Bei
\mathl{n=2}{} ist
\mavergleichskettedisp
{\vergleichskette
{2^2-1
}
{ =} { 3
}
{ } {
}
{ } {
}
{ } {
}
}
{}{}{}
eine Primzahl. Bei
\mathl{n=0,1}{} liegt keine Primzahl vor.
}
\inputaufgabeklausurloesung
{2}
{
Es sei $n$ eine ganze Zahl, von der die folgenden Eigenschaften bekannt sind:
\aufzaehlungfuenf{ $n$ ist negativ.
}{ $n$ ist ein Vielfaches von $8$, aber nicht von
\mathl{-16}{.}
}{ $n$ ist kein Vielfaches von
\mathl{36}{.}
}{ $n$ ist ein Vielfaches von $150$, aber nicht von
\mathl{125}{.}
}{In der Primfaktorzerlegung von $n$ gibt es keine Primzahl, die größer als $5$ ist.
}
Was ist $n$?
}
{
Wir müssen nur für die Primzahlen
\mathl{2,3,5}{} bestimmen, mit welcher Potenz sie in $n$ vorkommen. Wegen (2) kommt $2$ mit der dritten Potenz vor, aber nicht mit der vierten. Wegen (3) ist $9$ kein Teiler von $n$, da ja $4$ ein Teiler ist, und wegen (4) ist $3$ ein Teiler von $n$. Wegen (4) kommt $5$ mit der zweiten Potenz vor, aber nicht mit der dritten. Daher ist
\mavergleichskettedisp
{\vergleichskette
{n
}
{ =} {- 2^3 \cdot 3 \cdot 5^2
}
{ =} { - 600
}
{ } {
}
{ } {
}
}
{}{}{.}
}
\inputaufgabeklausurloesung
{2}
{
Zeige, dass die auf $\Z \times \N_+$ durch
\mathdisp {(a,b) \sim (c,d), \text{ falls } ad=bc} { , }
festgelegte
\definitionsverweis {Relation}{}{}
eine
\definitionsverweis {Äquivalenzrelation}{}{}
ist.
}
{
Die Reflexivität und die Symmetrie ergeben sich unmittelbar aus der Definition. Zum Nachweis der Transitivität seien
\mavergleichskette
{\vergleichskette
{(a,b)
}
{ \sim }{ (c,d)
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
und
\mavergleichskette
{\vergleichskette
{(c,d)
}
{ \sim }{ (e,f)
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{.}
Dies bedeutet
\mavergleichskette
{\vergleichskette
{ ad
}
{ = }{bc
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
bzw.
\mavergleichskette
{\vergleichskette
{ cf
}
{ = }{ ed
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{.}
Somit ist
\mavergleichskettedisp
{\vergleichskette
{ adf
}
{ =} {bcf
}
{ =} {bde
}
{ } {
}
{ } {
}
}
{}{}{.}
Wegen
\mavergleichskette
{\vergleichskette
{ d
}
{ \neq }{0
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
ergibt die Kürzungsregel in $\Z$ die Gleichheit
\mavergleichskettedisp
{\vergleichskette
{af
}
{ =} { eb
}
{ } {
}
{ } {
}
{ } {
}
}
{}{}{,}
also
\mavergleichskette
{\vergleichskette
{ (a,b)
}
{ \sim }{ (e,f)
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{.}
}
\inputaufgabeklausurloesung
{4}
{
Es seien $n,m \in \Z$ ganze Zahlen. Zeige, dass $n$ genau dann ein Teiler von $m$ ist, wenn es einen Ringhomomorphismus \maabbdisp {} { \Z/(m) } { \Z/(n) } {} gibt. Zeige durch ein Beispiel, dass es einen injektiven Gruppenhomomorphismus \maabbdisp {} { \Z/(m) } { \Z/(n) } {} geben kann, ohne dass $n$ ein Teiler von $m$ ist.
}
{
Wenn $n$ ein Teiler von $m$ ist, so ist $m=an$ und daher ist $m \in \Z n$ und somit gilt die Idealinklusion $\Z m \subseteq \Z n$. Unter dem kanonischen Ringhomomorphismus
\maabbdisp {} {\Z} {\Z/(n)
} {} wird also $\Z m$ auf null abgebildet und daher gibt es nach dem Satz vom induzierten Homomorphismus einen Ringhomomorphismus
\maabbdisp {} {\Z/(m) } {\Z/(n)
} {.}
Wenn es umgekehrt einen solchen Ringhomomorphismus $\varphi$ gibt, so betrachten wir insgesamt den Ringhomomorphismus
\mathdisp {\Z \longrightarrow \Z/(m) \stackrel{\varphi}{\longrightarrow} \Z/(n)} { . }
Die Gesamtabbildung muss also $m$ auf null schicken, d.h. $m \mod n =0$, und $m$ ist ein Vielfaches von $n$.
Für das Beispiel betrachten wir $n=4$ und $m=2$. In $\Z/(4)$ bildet die Menge $\{ \bar{0}, \bar{2}\}$ eine Untergruppe, die zu $\Z/(2)$ isomorph ist, sodass ein injektiver Gruppenhomomorphismus $\Z/(2) \rightarrow \Z/(4)$ vorliegt.
}
\inputaufgabeklausurloesung
{1}
{
$\,$
\bild{ \begin{center}
\includegraphics[width=5.5cm]{ \bildeinlesungsvg {3-simplex_graph} {svg} }
\end{center}
\bildtext {} }
\bildlizenz { 3-simplex graph.svg } {} {Koko90} {Commons} {CC-by-sa 3.0} {}
Bei einem vollständigen ungerichteten Graphen mit $4$ Ecken ist jede Ecke mit jeder \zusatzklammer {anderen} {} {} Ecke verbunden. Zeichne einen solchen Graphen in der Ebene ohne Überschneidungen.
}
{
\bild{ \begin{center}
\includegraphics[width=5.5cm]{ \bildeinlesungsvg {3-demicube t0 B3} {svg} }
\end{center}
\bildtext {} }
\bildlizenz { 3-demicube t0 B3.svg } {} {Tomruen} {Commons} {gemeinfrei} {}
}
\inputaufgabeklausurloesung
{0}
{
}
{ }
\inputaufgabeklausurloesung
{0}
{
}
{ }
\inputaufgabeklausurloesung
{0}
{
}
{ }
\inputaufgabeklausurloesung
{0}
{
}
{ }
\inputaufgabeklausurloesung
{0}
{
}
{ }