Diskrete Strukturen SS 2001

5th September 2001

1. Übungen (1-12) mit Musterlösungen des Lehrstuhls 2. Präsenzübungen (1-9)

3. Scheinklausur

4. Hinweise zur Organisation

1. Übung zur Vorlesung ,,Diskrete Strukturen“ (SS 01)

Prof. Dr. H. Pahlings

Hausaufgaben

Aufgabe 1. [Vordiplom-Aufgabe 1999.] Beweisen Sie einmal algebraisch und dann kombinatorisch mit Hilfe von Teilmengen die Formel

( \begin{matrix}n \\ r \end{matrix} ) ( \begin{matrix}r \\ k \end{matrix} ) = ( \begin{matrix}n \\ k \end{matrix} ) ( \begin{matrix}n − k \\ r − k \end{matrix} ) für k ≤ r ≤ n ∈ ℕ_{0}

und leiten Sie daraus ab:

∑_{k=0}^{r} ( \begin{matrix}n \\ k \end{matrix} ) ( \begin{matrix}n − k \\ r − k \end{matrix} ) = 2^{r} ( \begin{matrix}n \\ r \end{matrix} ) .

Aufgabe 2. Zeigen Sie: Für m, n ∈ ℕ_{0} gilt

∑_{k=0}^{m} ( \begin{matrix}n + k \\ k \end{matrix} ) = ( \begin{matrix}n + m + 1 \\ m \end{matrix} ) .

Aufgabe 3. Wie viele (x_{1}, …, x_{r}) ∈ ℕ_{0}^{r} gibt es zu gegebenem n ∈ ℕ mit

n = x_{1} + ⋯ + x_{r} ?

Geben Sie eine (kurze) kombinatorische Lösung und zusätzlich einen Induktionsbeweis, z. B. unter Benutzung von Aufgabe 2.

Aufgabe 4. Es sei wie in der Vorlesung für n ∈ ℕ_{0} und x ∈ ℂ

x\underline{n} = x (x − 1) ⋯ (x − n + 1) und x\overline{n} = x (x + 1) ⋯ (x + n − 1).

Zeigen Sie: Für x, y ∈ ℂ gilt

(x + y)\underline{n} = ∑_{k=0}^{n} ( \begin{matrix}n \\ k \end{matrix} ) x\underline{k} y\underline{n−k} und (x + y)\overline{n} = ∑_{k=0}^{n} ( \begin{matrix}n \\ k \end{matrix} ) x\overline{k} y\overline{n−k}.

Abgabe: Mittwoch, den 25. 4., bis 14.00 Uhr im Übungskasten des Lehrstuhls.

1. Übung zur Vorlesung ,,Diskrete Strukturen“ (SS 01)

Prof. Dr. H. Pahlings

Lösung zu Aufgabe 2. Es ist zu zeigen: Für m, n ∈ ℕ_{0} gilt ∑_{k=0}^{m} \binom{n + k}{k} = \binom{n + m + 1}{m}.

Algebraischer Beweis Es sei n ∈ ℕ_{0} beliebig. Wir beweisen die Behauptung durch Induktion nach m. Induktionsanfang: Für m = 0 ist

∑_{k=0}^{m} \binom{n + k}{k} = \binom{n}{0} = 1 = \binom{n + 1}{0} = \binom{n + m + 1}{m}.

Induktionsannahme: Es sei m ≥ 0 und die Behauptung sei bereits bewiesen für m. Induktionsschritt (Schluss von m auf m + 1):

∑_{k=0}^{m+1} \binom{n + k}{k} = ∑_{k=0}^{m} \binom{n + k}{k} + \binom{n + m + 1}{m + 1}

= \binom{n + m + 1}{m} + \binom{n + m + 1}{m + 1} nach Induktionsannahme
= \binom{n + (m + 1) + 1}{m + 1} nach Vorlesung Kap. I, §1, Satz2.

Kombinatorischer Beweis Es sei M = {1, …, m + n + 1}. Für k = 1, …, m + 1 setzen wir

M_{k} = \{ X ∈ \binom{M}{m} | min(M \ X) = k \}

(das ist die Menge aller m-Teilmengen von M, die die k −1 kleinsten Zahlen aus M enthalten, aber nicht die Zahl k selber). Dann ist

\binom{M}{m} = M_{1} ∪^{.} M_{2} ∪^{.} ⋯ ∪^{.} M_{m+1}

und

|M_{k}| = \binom{(n + m + 1) − k}{m − (k − 1)} = \binom{n + (m + 1 − k)}{m + 1 − k} für 1 ≤ k ≤ m + 1,

also

∑_{k=0}^{m} \binom{n + k}{k} = ∑_{k=0}^{m} |M_{m+1−k}| = |\binom{M}{m}| = \binom{n + m + 1}{m}.

Hausaufgaben

Aufgabe 5. Zeigen Sie, dass für die Binomialkoeffizienten ( \begin{matrix}n \\ k \end{matrix} ) gilt:

( \begin{matrix}n \\ 0 \end{matrix} ) < ( \begin{matrix}n \\ 1 \end{matrix} ) < … < ( \begin{matrix}n \\ ⌊\frac{n}{2}⌋ \end{matrix} ) = ( \begin{matrix}n \\ ⌈\frac{n}{2}⌉ \end{matrix} ) > … > ( \begin{matrix}n \\ n \end{matrix} ) ,

wobei wie üblich für a ∈ ℝ

⌊a⌋ = max{k ∈ ℤ | k ≤ a}

und

⌈a⌉ = min{k ∈ ℤ | a ≤ k}

definiert sei.

Aufgabe 6. Geben Sie einen kombinatorischen Beweis der folgenden Darstellung der Stirlingzahlen zweiter Art an:

S_{n,k} = \frac{1}{k!} ∑_{j=0}^{k} (−1)^{k−j} ( \begin{matrix}k \\ j \end{matrix} ) j^{n}.

Hinweis: Zählen Sie mit Hilfe des Inklusion-Exklusion-Prinzips die Anzahl der surjektiven Abbildungen von \underline{n} nach \underline{k}.

Aufgabe 7. Zeigen Sie (z. B. mittels Induktion): S_{m+n+1,m} = ∑_{k=0}^{m} k S_{n+k,k}.

Vergleichen Sie dies mit Aufgabe 2.

Aufgabe 8. [Klausuraufgabe TU München 2001.] Zehn befreundete Radrennfahrer nehmen an einem Radrennen der Länge 125, 5 km teil und fahren immer hintereinander. Jeden Kilometer wechseln sie ihre Reihenfolge wie folgt:

• Der erste Fahrer wird der letzte,

• der zweite Fahrer der vorletzte,

• der dritte Fahrer der drittletzte,

• alle anderen Fahrer wechseln um 3 Positionen nach vorne.

(a) Nach wie vielen Wechseln ist zum ersten Mal wieder derselbe Fahrer wie zu Beginn des Rennens an der Spitze? Begründen Sie Ihre Antwort.

(a) Wie häufig kommt es insgesamt im Laufe des Rennens vor, dass alle zehn Radfahrer in derselben Reihenfolge fahren wie zu Beginn des Rennens (die Startaufstellung ist hierbei nicht mit zu zählen)? Begründen Sie Ihre Antwort.

(a) In welcher Reihenfolge kommen die zehn Fahrer ins Ziel? Geben Sie als Antwort neben der Begründung auch die Reihenfolge der Startnummern der Fahrer an, wenn zu Beginn des Rennens der Radfahrer an Position i die Startnummer i hatte.

Lösung zu Aufgabe 6. Es sei A = \underline{n} = \{1, …, n\} und B = \underline{k} = \{1, …, k\}. Dann ist k! · S_{n,k} = | Surj (A, B)| die Anzahl der surjektiven Abbildungen und k^{n} = |Abb (A, B)| die Anzahl aller Abbildungen von A nach B. Wir beweisen die gegebene Formel, indem wir die t := k^{n}−k!·S_{n,k} nicht surjektiven Abbildungen von A nach B abzählen. Dazu betrachten wir für jedes i ∈ B die Menge

X_{i} = {f: A → B | i ∉ Bild f}

der Abbildungen von A nach B, in deren Bild i nicht enthalten ist. Dann ist

t = |X_{1} ∪ … ∪ X_{k}|.

Nach dem Inklusion-Exklusion-Prinzip ergibt sich t zu

t = | ⋃_{i=1}^{k} X_{i}| = ∑_{j=1}^{k} ∑_{I∈\binom{B}{j}}(−1)^{j+1}|X_{I}|

mit X_{I} = ⋂_{i∈I} X_{i}. Da X_{I} = Abb (A, B \ I) ist, also |X_{I}| = (k − j)^{n}, ergibt sich

t = ∑_{j=1}^{k}(−1)^{j+1}\binom{k}{j}(k − j)^{n} = ∑_{j=0}^{k−1}(−1)^{k−j+1}\binom{k}{j}j^{n}

(mit Summationsverschiebung j′ = k − j). Also ist

k! · S_{n.k} = k^{n} + ∑_{j=0}^{k−1}(−1)^{k−j}\binom{k}{j}j^{n}

woraus die Behauptung unmittelbar folgt.

Lösung zu Aufgabe 8.

Die Regeln des Wechselns kann man auch als Permutation der Positionen betrachten:

σ = ( \begin{matrix}1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 \\ 10 & 9 & 8 & 1 & 2 & 3 & 4 & 5 & 6 & 7 \end{matrix} ) = (1 10 7 4)(2 9 6 3 8 5) ∈ S_{10}.

(a) Es ist (1 10 7 4)^{4} = id, aber (1 10 7 4)^{n} ≠ id für n ∈ ℕ, n < 4. Also fährt der erste Fahrer nach vier Wechseln zum ersten Mal wieder vorne.

(b) Für n ∈ ℕ_{0} gilt genau dann σ^{n} = id, wenn n ein gemeinsames Vielfaches der Längen der beiden Zyklen von σ ist. Das kleinste gemeinsame Vielfache von 4 und 6 ist 12. Also fahren die Fahrer jeweils nach dem 12., 24., 36., … Wechsel wieder in der ursprünglichen Reihenfolge. Da es 125 Wechsel gibt, geschieht das zum letzten Mal nach dem 120. Wechsel und damit insgesamt 10 mal.

(c) Die Fahrer wechseln 125 mal. Das entspricht der Permutation

σ^{125} = σ^{10·12+5} = id^{10}∘σ^{5} = (1 10 7 4)(2 5 8 3 6 9) = ( \begin{matrix}1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 \\ 10 & 5 & 6 & 1 & 8 & 9 & 4 & 3 & 2 & 7 \end{matrix} ) .

Die Fahrer kommen also in der Reihenfolge 4, 9, 8, 7, 2, 3 ,10, 5, 6, 1 im Ziel an.

3. Übung zur Vorlesung ,,Diskrete Strukturen“ (SS 01)

Prof. Dr. H. Pahlings

Hausaufgaben

Aufgabe 9. Für n ∈ ℕ_{0} sei B_{n} = ∑_{k=0}^{n} S_{n,k} (die Anzahl \underline{aller} Partitionen einer n-Menge = Zeilensumme im Stirling-Dreieck 2. Art).

(a) Zeigen Sie: B_{n+1} = ∑_{k=0}^{n} ( \begin{matrix}n \\ k \end{matrix} ) B_{k}.

Anleitung: Betrachten Sie für k = 0, …, n die Menge X_{k} = {P = {A_{1}, …, A_{l}} ∈ Part_{l}{1, …, n + 1} | n + 1 ∈ A_{l}, |A_{l}| = k + 1, l ∈ ℕ_{0}}.

(b) Zeigen Sie mit Hilfe von (a): ∑_{k=1}^{n} k S_{n,k} = ∑_{k=0}^{n−1} ( \begin{matrix}n \\ k \end{matrix} ) B_{k}.

Aufgabe 10. [Vordiplomklausur-Aufgabe September 2000.]

(a) Bestimmen Sie für n ≥ 4 die Anzahl F (n, n − 3) der Permutationen aus S_{n} mit mindestens n − 3 Fixpunkten.

(b) Gibt es mehr oder weniger als 2 ( \begin{matrix}n + 1 \\ 3 \end{matrix} ) solcher Permutationen?

Aufgabe 11.

Für n ∈ ℕ sei F_{i} = {σ ∈ S_{n} | σ(i) = i}, und für I ⊆ {1, …, n} sei F_{I} = ⋂_{i∈I} F_{i}.

(a) Was ist |F_{I}|?

(b) Berechnen Sie f_{n} =| S_{n} \ ⋃_{i=1}^{n} F_{i} |,

also die Anzahl der ,,fixpunktfreien” Permutationen.

(c) Was ist \frac{f_{10000}}{10000!} ungefähr?

Hausaufgaben

Aufgabe 12. Es sei M = {a, b, c, …, z}, N = {0, 1} und C_{n} der ,,Code”, der aus allen Folgen der Länge k mit 1 ≤ k ≤ n besteht, die man aus 0 < i < k Buchstaben aus M gefolgt von k − i Ziffern aus N bilden kann. Wie viele Folgen der Länge k gibt es in C_{n}? Was ist |C_{n}|? Es wird eine summationsfreie Darstellung der Ergebnisse (mittels erzeugender Funktionen) verlangt. Wie groß muss man n machen, wenn man mit C_{n} einen Text mit 20000 verschiedenen Worten verschlüsseln (d. h. komprimieren) will?

Aufgabe 13. Berechnen Sie explizit (1 + x + x^{2})^{−1} ∈ 𝔽_{2}[[x]]. Dabei ist 𝔽_{2} der Körper mit 2 Elementen.

Aufgabe 14.

Es sei ∑_{n=0}^{∞} a_{n}x^{n} = \frac{4 + x − x^{2}}{3 − 5x + x^{2} + x^{3}} ∈ ℚ[[x]] . Bestimmen Sie die a_{n}.

\underline{Anleitung}: Faktorisieren Sie den Nenner und finden Sie so α_{1}, α_{2} ∈ ℚ mit

3 − 5x + x^{2} + x^{3} = (α_{1} − x) (α_{1} − x) (α_{2} + x).

Bestimmen Sie dann a, b, c ∈ ℚ mit

\frac{4 + x − x^{2}}{3 − 5x + x^{2} + x^{3}} = \frac{a}{α_{1} − x} + \frac{b}{(α_{1} − x)^{2}} + \frac{c}{α_{2} + x}.

Aufgabe 15. Mr. John F. Moneymaker, der berühmte New Yorker Millionär, hat neulich verraten wie er seine erste Million ,,gemacht hat”. Er begann völlig mittellos, und nach einem Jahr harter ehrlicher Arbeit betrug sein Nettovermögen genau einen Dollar. Am Ende des zweiten Jahres waren es fünf Dollar. Da beschloss er, in Zukunft in jedem Jahr für das Sechsfache dessen, was er zu Beginn des vorhergehenden Jahres besessen hatte, Waren zu kaufen und sie für das Vierfache dessen, was er zu Beginn des laufenden Jahres besaß, wieder zu verkaufen.

Es sei u_{n} das Vermögen von Mr. Moneymaker am Ende des n-ten Jahres. Finden Sie eine Rekursionsgleichung für u_{n} und lösen Sie sie. Wie viele Jahre brauchte Mr. Moneymaker um Millionär zu werden?

Hausaufgaben

Aufgabe 16. Es sei D : K[[x]] → K[[x]] wie in der Vorlesung die formale Ableitung. Beweisen Sie die Produktregel

D(A · B) = D(A) · B + A · D(B)

für A, B ∈ K[[x]].

Aufgabe 17.

[Vordiplomklausur-Aufgabe März 2001.] Die Folge (a_{n})_{n∈ℕ_{0}} sei rekursiv definiert durch a_{0} = 0, a_{1} = 2 und a_{n} = a_{n−1} + 2 a_{n−2} für alle n ≥ 2. Bestimmen Sie mit Hilfe der erzeugenden Funktion die explizite Darstellung der Folgenglieder a_{n}.

Aufgabe 18. Lösen Sie explizit die folgenden gekoppelten Rekursionsgleichungen mittels erzeugender Funktionen.

a_{0} = 1, b_{0} = 0,
a_{n} = 3 a_{n−1} + 2 b_{n−1},
b_{n} = a_{n−1} + b_{n−1}.

Aufgabe 19.

(a) Es sei K ein Körper, A = ∑_{n=0}^{∞} a_{n}x^{n} ∈ K[[x]] und s_{n} = a_{0} + a_{1} + … + a_{n} für n ≥ 0 .

Zeigen Sie: ∑_{n=0}^{∞} s_{n}x^{n} = \frac{A}{1 − x}.

(b) Zeigen Sie: ∑_{n=0}^{∞} n^{2}x^{n} = \frac{x(1 + x)}{(1 − x)^{3}}.

(c) Benutzen Sie (a) und (b) um eine Formel für ∑_{k=0}^{n} k^{2} herzuleiten.

5. Übung zur Vorlesung ,,Diskrete Strukturen“ (SS 01)

Prof. Dr. H. Pahlings

Lösung zu Aufgabe 19.

(a) Ist A = ∑_{n=0}^{∞} a_{n}x^{n} ∈ K[[x]] und s_{n} = ∑_{k=0}^{n} a_{k} für n ∈ ℕ_{0}, so gilt offensichtlich

\frac{A}{1 − x} = ∑_{n=0}^{∞} a_{n}x^{n} · ∑_{n=0}^{∞} x^{n} = ∑_{n=0}^{∞} (∑_{k=0}^{n} a_{k} · 1) x^{n} = ∑_{n=0}^{∞} s_{n}x^{n}.

(b) Mit Hilfe von Folgerung 2 aus §4 erhalten wir

\frac{x(1 + x)}{(1 − x)^{3}} = (x + x^{2}) ∑_{n=0}^{∞} \binom{n + 2}{2} · x^{n}

= ∑_{n=1}^{∞} \binom{n + 1}{2}x^{n} + ∑_{n=2}^{∞} \binom{n}{2}x^{n}

= ∑_{n=0}^{∞} (\binom{n + 1}{2} + \binom{n}{2}) x^{n} (wegen \binom{k}{2} = 0 für k < 2)

= ∑_{n=0}^{∞} \frac{n(n + 1) + n(n − 1)}{2}x^{n} = ∑_{n=0}^{∞} n^{2}x^{n}.

(c) Setzen wir A = ∑_{n=0}^{∞} a_{n}x^{n} mit a_{n} = n^{2} und s_{n} = ∑_{k=0}^{n} k^{2} = ∑_{k=0}^{n} a_{k} für n ∈ ℕ_{0}, so folgt

∑_{n=0}^{∞} s_{n}x^{n} = \frac{A}{1 − x} (nach (a))

= \frac{∑_{n=0}^{∞} n^{2}x^{n}}{1 − x} = \frac{x(1 + x)}{(1 − x)^{4}} (nach (b))

= (x + x^{2}) ∑_{n=0}^{∞} \binom{n + 3}{3}x^{n} (nach §4 Folgerung 2)

= ∑_{n=1}^{∞} \binom{n + 2}{3}x^{n} + ∑_{n=2}^{∞} \binom{n + 1}{3}x^{n}

= ∑_{n=0}^{∞} (\binom{n + 2}{3} + \binom{n + 1}{3}) x^{n} (wegen \binom{k}{3} = 0 für k < 3)

und damit ∑_{k=0}^{n} k^{2} = s_{n} = \binom{n + 1}{3} + \binom{n + 2}{3} = \frac{1}{6}n(n + 1)(2n + 1).

Hausaufgaben

Aufgabe 20. Es sei A = [ \begin{matrix}1 & 1 \\ 1 & 0 \end{matrix} ] ∈ ℤ^{2×2}. Zeigen Sie:

(a) A^{n} = [ \begin{matrix}F_{n+1} & F_{n} \\ F_{n} & F_{n−1} \end{matrix} ] mit den Fibonaccizahlen F_{n}.

(b) F_{n+1}F_{n−1} − F_{n}^{2} = (−1)^{n} für n ≥ 1.

(c) F_{n+1}^{2} − F_{n+1}F_{n} − F_{n}^{2} = (−1)^{n} für n ≥ 0.

Aufgabe 21. Für n ∈ ℕ_{0} sei a_{n} = (1 + \sqrt{3})^{n} + (1 − \sqrt{3})^{n}.

(a) Zeigen Sie: a_{n} ∈ ℕ für alle n.

(b) Geben Sie eine Rekursionsgleichung für a_{n} an.

(c) Zeigen Sie: 2^{n+1} teilt a_{2n} und es gilt a_{2n−1} = 2^{n} · u_{n} mit ungeradem u_{n}.

(d) Zeigen Sie: ⌊(1 + \sqrt{3})^{2n−1}⌋ enthält den Faktor 2^{n}.

Aufgabe 22. Lösen Sie die folgende Rekursionsgleichung:

a_{0} = 1, a_{1} = 0 und a_{n} = ∑_{k=2}^{n} a_{k−2} a_{n−k} für n ≥ 2.

Aufgabe 23. Es sei P_{n,k} = { (n_{1}, …, n_{j}) | k ≥ n_{1} ≥ n_{2} ≥ … ≥ n_{j} ≥ 1, n_{1} + ⋯ + n_{j} = n, j ∈ ℕ }. Bestimmen Sie die erzeugende Funktion für |P_{n,k}| für festes k = 1, 2, 3, ….

Hausaufgaben

Aufgabe 24. Wie viele Lösungen hat jeweils die Gleichung x^{3} = x bzw. x^{2} + x = 1

(a) in ℤ_{2}, (b) in ℤ_{5}, (c) in ℤ_{6} ? Aufgabe 25. In welchen der Ringe (Körper) ℤ_{p} für p ∈ {2, 3, 5, 7} gilt die Implikation

a^{2} + b^{2} = 0 ⇒ a = b = 0 ?

Aufgabe 26. Berechnen Sie mit dem euklidischen Algorithmus einen ggT (größten gemeinsamen Teiler) d von

(a) f = 13090 und g = 6239 in R = ℤ,

(b) f = x^{4} + 3x^{3} + x^{2} + 4 und g = x^{4} + 2x^{3} − x − 2 in R = ℚ[x] und stellen Sie d jeweils in der Form d = af + bg mit a, b ∈ R dar. Aufgabe 27. Berechnen Sie alle irreduziblen Polynome vom Grad ≤ 4 in ℤ_{2}[x].

Hausaufgaben

Aufgabe 28. Auf M = ℕ_{0} × ℕ_{0} sei die Relation ∼ definiert durch (a, b) ∼ (c, d) ⇔ b − a = d − c.

(a) Ist ∼ eine Äquivalenzrelation? Wenn ja, geben Sie ein vollständiges Vertretersystem der Äquivalenzklassen an (also eine Teilmenge V ⊆ M mit M = ˙ ⋃_{v∈V} [v]_{∼}).

(b) Ist ∼ eine Kongruenzrelation des Monoids (M, +, (0, 0)), wobei

(a, b) + (c, d) = (a + c, b + d)

für a, b, c, d ∈ ℕ_{0} definiert sei?

Aufgabe 29. Gibt es Zahlen a, b, c, d ∈ ℕ mit a^{2} + b^{2} − 3 c^{2} − 3 d^{2} = 0 ?

Aufgabe 30. Es sei R ein Hauptidealring (also ein Integritätsbereich, in dem jedes Ideal ein Hauptideal ist).

(a) Zeigen Sie:

Ra + Rb = Rd

für d ∈ ggT (a, b). Insbesondere existieren in einem Hauptidealring stets größte gemeinsame Teiler. Hierbei ist die Summe der Ideale Ra und Rb natürlich so definiert:

Ra + Rb = {ya + zb | y ∈ R, z ∈ R}.

(b) Definieren Sie analog zum ggT ein kgV und zeigen Sie:

Ra ∩ Rb = Rd

für d ∈ kgV (a, b).

Aufgabe 31. Es sei R = ℤ_{2}[x] und f = x^{3} + 1 ∈ R und

\overline{R} = R/fR = \{ [g]_{f} | g ∈ R \},

wobei [g]_{f} = g + fR ist.

(a) Zeigen Sie: |\overline{R} | = 8.

(b) Bestimmen Sie alle Einheiten in \overline{R} (also \overline{R}^{∗}).

(c) Bestimmen Sie alle Quadrate in \overline{R}.

(d) Wie viele [g]_{f} in \overline{R} gibt es mit [g]_{f}^{2} = [g]_{f} ?

Hausaufgaben

Aufgabe 32.

Es sei K = ℤ_{2} und f = x^{3} + x^{2} + 1 ∈ K[x] und L = K[x] /fK[x] (nach § 5 Satz 2 und Aufgabe 27 ist dies ein Körper mit 8 Elementen). Die Elemente von L werden durch 3 Bits

dargestellt: [a_{0} + a_{1}x + a_{2}x^{2}]_{f} ⟼ a_{0} a_{1} a_{2} (a_{i} ∈ ℤ_{2}).

Berechnen Sie die 3-Bit-Darstellungen der Potenzen ([x]_{f})^{i} für i = 1, 2, …, 7.

Aufgabe 33.

(a) Bestimmen Sie alle Lösungen in ℤ von x ≡ 1 mod 4

x ≡ 2 mod 5
x ≡ 3 mod 7.

(b) Drei Sender geben alle 5, 7, beziehungsweise 11 Minuten ein Signal ab. Zuletzt wurden ihre Signale vor 1, 4, beziehungsweise 10 Minuten empfangen. Wann werden das nächste Mal alle drei Signale gleichzeitig empfangen?

Aufgabe 34.

Es sei R = ℤ[\sqrt{−5} ] = \{a + b\sqrt{−5} | a, b ∈ ℤ\}. (Hierbei ist \sqrt{−5} eine komplexe Zahl, deren Quadrat −5 ist.) Zeigen Sie:

(a) R ist ein kommutativer Ring.

(b) \overline{R} = R/3R hat 9 Elemente.

(c) (\overline{R}, +) ≅ (ℤ_{3} × ℤ_{3}, +) als abelsche Gruppe.

(d) \overline{R} hat genau 4 Ideale.

Bemerkung zu Aufgabe 32. Diese Aufgabe ist völlig analog zu dem Beispiel am Ende von § 5 (Kap. II) der Vorlesung.

Lösung zu Aufgabe 34.

(a) Es soll gezeigt werden, dass R = ℤ[\sqrt{−5} ] = \{a + b\sqrt{−5} | a, b ∈ ℤ\} ein kommutativer Ring ist. Da R in ℂ liegt und da ℂ ein Körper und damit erst recht ein kommutativer Ring ist, genügt es zu zeigen, dass R ein Teilring von ℂ ist, also dass R die Zahlen 0 und 1 enthält und dass mit je zwei Elementen r_{1} = a_{1} + b_{1}\sqrt{−5} und r_{2} = a_{2} + b_{2}\sqrt{−5} aus R auch die Zahlen r_{1} + r_{2} und r_{1} − r_{2} und r_{1}·r_{2} in R liegen. Dass die ersten vier dieser fünf Bedingungen erfüllt sind, sieht man sofort. Für das Produkt gilt

r_{1}·r_{2} = (a_{1} + b_{1}\sqrt{−5}) · (a_{2} + b_{2}\sqrt{−5}) = (a_{1}a_{2} − 5b_{1}b_{2}) + (a_{1}b_{2} + a_{2}b_{1})\sqrt{−5} ∈ R.

Also is R ein kommutativer Ring.

(b) Für \overline{R} = R/3R bildet die Menge V = \{a + b\sqrt{−5} | a, b ∈ \{0, 1, 2\} \} ⊆ R offensichtlich ein vollständiges Vertretersystem. Also hat \overline{R} genau 9 Elemente.

(c) Wir betrachten die Abbildung φ: (\overline{R}, +) → (ℤ_{3} × ℤ_{3}, +) mit [a + b\sqrt{−5} ]_{3} ↦ ( [a]_{3}, [b]_{3})

von der additiven Gruppe (\overline{R}, +) in die additive Gruppe (ℤ_{3} × ℤ_{3}, +). Diese Abbildung ist einerseits ein (Gruppen-)Homomorphismus, denn für alle a_{1}, B_{1}, a_{2}, b_{2} ∈ ℤ gilt

φ((a_{1} + b_{1}\sqrt{−5}) + (a_{2} + b_{2}\sqrt{−5})) = ( [a_{1} + a_{2}]_{3}, [b_{1} + b_{2}]_{3}))
= φ(a_{1} + b_{1}\sqrt{−5}) + φ(a_{2} + b_{2}\sqrt{−5}).

Andererseits ist sie offensichtlich surjektiv und deshalb wegen |\overline{R}| = |ℤ_{3} × ℤ_{3}| = 9 < ∞ bijektiv. Insgesamt folgt, dass φ ein (Gruppen-)Isomorphismus von \overline{R} auf ℤ_{3} × ℤ_{3} ist.

Dieser Isomorphismus erlaubt es uns, die Elemente [a + b\sqrt{−5} ]_{3} aus \overline{R} in der Form ( [a]_{3}, [b]_{3}) zu schreiben. Diese Schreibweise vereinfacht sich noch weiter, wenn wir für [0]_{3}, [1]_{3} und [2]_{3} einfach 0, 1 und 2 schreiben (und dann natürlich modulo 3 rechnen). Die Multiplikation in \overline{R} sieht in dieser Notation so aus:

(a_{1}, b_{1}) · (a_{2}, b_{2}) = (a_{1} a_{2} + b_{1} b_{2}, a_{1} b_{2} + a_{2} b_{1}).

(d) Jedes Ideal von \overline{R} ist insbesondere eine additive Untergruppe von \overline{R}. Um die Ideale zu bestimmen, genügt es also, die additiven Untergruppen zu betrachten, Die ,,triviale” Untergruppe U_{0} = \{(0, 0)\} der Ordnung 1 und die ganze Gruppe \overline{R} der Ordnung 9 sind bekanntlich Ideale. Alle anderen Untergruppen müssen nach dem Satz von Lagrange die Ordnung 3 haben. Es gibt 4 solche Untergruppen,

U_{1} = { (1, 0), (2, 0), (0, 0) }, U_{3} = { (1, 1), (2, 2), (0, 0) },
U_{2} = { (0, 1), (0, 2), (0, 0) }, U_{4} = { (1, 2), (2, 1), (0, 0) },

und jede dieser Untergruppen ist genau dann ein Ideal, wenn \overline{R}·U_{i} ⊆ U_{i} gilt.

Wegen (1, 1)·(1, 0) = (1, 1) und (1, 1)·(0, 1) = (1, 1) ist \overline{R}·U_{1} ⊈ U_{1} und \overline{R}·U_{2} ⊈ U_{2}. Andererseits gilt (a, b)·(c, c) = (ac + bc, ac + bc) und (a, b)·(c, −c) = (ac − bc, −(ac − bc)) für alle a, b, c ∈ ℤ_{3} und damit \overline{R}·U_{3} ⊆ U_{3} und \overline{R}·U_{4} ⊆ U_{4}.

\overline{R} hat also genau die 4 Ideale U_{0}, U_{3}, U_{4} und \overline{R}.

9. Übung zur Vorlesung ”Diskrete Strukturen“ (H. Pahlings) SS 01

Lösung zu Aufgabe 33 (a).

Gegeben sind die simultanen Kongruenzen

x ≡ 1 mod 4, x ≡ 2 mod 5, x ≡ 3 mod 7.

Da die drei Zahlen 4, 5 und 7 paarweise teilerfremd sind, gibt es nach dem chinesischen Restsatz eine Lösung und wir können sie berechnen, indem wir dem (konstruktiven) Beweis dieses Satzes folgen. Benutzen wir dabei die Bezeichnungen aus der Vorlesung, d. h., schreiben wir die gegebenen Kongruenzen in der Form x ≡ a_{i} mod q_{i} und setzen wir m = q_{1}q_{2}q_{3} sowie q′_{i} = \frac{m}{q_{i}}, so erhalten wir

a_{1} = 1, a_{2} = 2, a_{3} = 3,

q_{1} = 4, q_{2} = 5, q_{3} = 7, m = 140,
q′_{1} = 35, q′_{2} = 28, q′_{3} = 20.

Man sieht leicht (oder berechnet mit dem euklidischen Algorithmus)

1 = 9·4 + (−1)·35 = (−11)·5 + 2·28 = 3·7 + (−1)·20.

Schreiben wir dafür wieder wie in der Vorlesung jeweils 1 = y_{i} q_{i} + z_{i} q′_{i}, so erhalten wir

z_{1} = −1, z_{2} = 2, z_{3} = −1

und daraus schließlich

[x]_{m} = [∑_{i=1}^{3} a_{i} q′_{i} z_{i}]_{m} = [ 1·35·(−1) + 2·28·2 + 3·20·(−1) ]_{140} = [17]_{140}.

Also löst jede Zahl der Form x = 140 z +17 mit z ∈ ℤ die gegebenen simultanen Kongruenzen.

Lösung zu Aufgabe 33 (b).

Es sei jetzt der Zeitpunkt t_{0} = 0 min. Nach Voraussetzung geben die Sender jeweils zu den Zeitpunkten

t_{1} = 5 n_{1} − 1 min, t_{2} = 7 n_{2} − 4 min und t_{3} = 11 n_{3} − 10 min

Signale ab (n_{1}, n_{2}, n_{3} ∈ ℤ). Gesucht ist der erste Zeitpunkt t ≥ 0, für den die drei simultanen Kongruenzen

t ≡ −1 mod 5, t ≡ −4 mod 7, t ≡ −10 mod 11

gelten. Wir lösen diese Aufgabe ganz analog zur Aufgabe 28 (a) und erhalten der Reihe nach a_{1} = −1, a_{2} = −4, a_{3} = −10,

q_{1} = 5, q_{2} = 7, q_{3} = 11, m = 385,
q′_{1} = 77, q′_{2} = 55, q′_{3} = 35.
1 = 31·5 + (−2)·77 = 8·7 + (−1)·55 = (−19)·11 + 6·35.
z_{1} = −2, z_{2} = −1, z_{3} = 6

und daraus schließlich

[t]_{m} = [∑_{i=1}^{3} a_{i} q′_{i} z_{i}]_{m} = [ (−1)·77·(−2) + (−4)·55·(−1) + (−10)·35·6 ]_{385} = [−1726]_{385}.

Gesucht ist die kleinste positive Zahl aus [−1726]_{385}, das ist t = 199. Also werden die drei Sender in drei Stunden und 19 Minuten zum ersten Mal wieder alle gleichzeitig ein Signal geben.

Hausaufgaben

Aufgabe 35. Bestimmen Sie alle n ∈ ℕ mit φ(n) = 4 und untersuchen Sie, für welche dieser n die prime Restklassengruppe ℤ_{n}^{∗} zyklisch ist. Welche der Gruppen ℤ_{n}^{∗} mit φ(n) = 4 sind isomorph? Geben Sie jeweils explizit einen Isomorphismus an. Aufgabe 36. [Vordiplomklausur-Aufgabe September 2000.]

(a) Es sei φ die eulersche φ-Funktion. Bestimmen Sie φ(2000).

(b) Bestimmen Sie diejenige ganze Zahl x mit 0 ≤ x ≤ 1999, die folgende Kongruenz erfüllt: (123)^{802} ≡ x mod 2000.

Aufgabe 37. Es sei K = ℤ_{2}[x] /fℤ_{2}[x] mit f = x^{4} +x^{3} +x^{2} +x+1 und G die multiplikative Gruppe von K.

(a) Geben Sie mindestens vier erzeugende Elemente von G an in der Form g = [ a_{0} + a_{1}x + a_{2}x^{2} + a_{3}x^{3} ]_{f} mit a_{i} ∈ ℤ_{2}.

(b) Zeigen Sie: Ist G = ⟨g⟩, so ist auch G = ⟨g^{2}⟩.

Aufgabe 38. Es sei G die Symmetriegruppe eines Quadrats, also die Gruppe aller Drehungen und Spiegelungen, die das Quadrat in sich überführen.

(a) Geben Sie alle Untergruppen von G an and machen Sie eine Skizze, aus der die Inklusionen ersichtlich sind.

(b) Welche Untergruppen sind Normalteiler? Hinweis: Benutzen Sie, dass das Produkt von zwei Spiegelungen eine Drehung ist.

Hinweis. Beachten Sie, das für die Teilnahme an der Schein- bzw. Test-Klausur am 13. 7. eine Anmeldung bis zum 2. 7. erforderlich ist.

Lösung zu Aufgabe 38 (a).

1  23 4

Das abgebildete Quadrat mit den Ecken 1, 2, 3, 4 besitzt offensichtlich acht verschiedene Symmetrieabbildungen, nämlich die Spiegelung an der Mittelhalbierenden der Kanten \overline{12} und \overline{34}, die Spiegelung an der Mittelhalbierenden der Kanten \overline{14} und \overline{23}, die Spiegelungen an den Diagonalen \overline{13} bzw. \overline{24}, die Drehungen im Uhrzeigersinn um den Mittelpunkt des Quadrats um 90^{∘}, 180^{∘} und 270^{∘} und schließlich die identische Abbildung, die alle Ecken fest lässt. Die Symmetriegruppe G hat also acht Elemente. Bezeichnen wir diese in der obigen Reihenfolge mit σ_{1}, σ_{2}, τ_{1}, τ_{2}, ϱ, ϱ^{2}, ϱ^{3} und ι und schreiben wir sie als jeweils in Form der von ihnen bewirkten Permutation der Ecken, so erhalten wir

\begin{aligned}σ_{1} & = & (1, 2)(3, 4), & τ_{1} & = & (2, 4), & ϱ & = & (1, 2, 3, 4), & ϱ^{3} & = & (1, 4, 3, 2), \\ σ_{2} & = & (1, 4)(2, 3), & τ_{2} & = & (1, 3), & ϱ^{2} & = & (1, 3)(2, 4), & ι & = & (1). \end{aligned}

(a) Jedes Element aus G erzeugt eine zyklische Untergruppe von G. Auf diese Weise erhalten wir schon einmal die Untergruppen

\begin{aligned}U_{1} & = & ⟨ι⟩ & = & \{ι\}, \\ U_{2} & = & ⟨σ_{1}⟩ & = & \{σ_{1}, ι\}, \\ U_{3} & = & ⟨σ_{2}⟩ & = & \{σ_{2}, ι\}, \\ U_{4} & = & ⟨τ_{1}⟩ & = & \{τ_{1}, ι\}, \\ U_{5} & = & ⟨τ_{2}⟩ & = & \{τ_{2}, ι\}, \\ U_{6} & = & ⟨ϱ^{2}⟩ & = & \{ϱ^{2}, ι\}, \\ U_{7} & = & ⟨ϱ⟩ & = & ⟨ϱ^{3}⟩ = \{ϱ, ϱ^{2}, ϱ^{3}, ι\} \end{aligned}

der Ordnungen 1, 2, 2, 2, 2, 2 und 4. Da jede Gruppe der Ordnung 2 zyklisch ist, haben wir damit insbesondere schon alle Untergruppen der Ordnung 2 gefunden. Nach dem Satz von Lagrange können jetzt also nur noch Untergruppen der Ordnung 4 fehlen. Eine solche Untergruppe der Ordnung 4 darf weder ϱ noch ϱ^{3} enthalten, da sie sonst schon gleich U_{7} wäre. Sie muss daher mindestens zwei Spiegelungen enthalten. Deren Produkt ist dann eine Drehung (da die Ecken nach zwei Spiegelungen wieder im Uhrzeigersinn nummeriert sind), und zwar eine von ι verschiedene Drehung, da die Spiegelungen verschieden sind. Also ist jede der noch fehlenden Untergruppen das Erzeugnis einer Spiegelung und der Drehung ϱ^{2}. Das ergibt zwei neue Untergruppen

\begin{aligned}U_{8} & = & ⟨σ_{1}, ϱ^{2}⟩ & = & ⟨σ_{2}, ϱ^{2}⟩ & = & \{σ_{1}, σ_{2}, ϱ^{2}, ι\}, \\ U_{9} & = & ⟨τ_{1}, ϱ^{2}⟩ & = & ⟨τ_{2}, ϱ^{2}⟩ & = & \{τ_{1}, τ_{2}, ϱ^{2}, ι\} \end{aligned}

der Ordnung 4, und weitere kann es dann nicht mehr geben. Die folgende Skizze zeigt die gegenseitigen Inklusionen der Untergruppen.

[figure: G; U_{8}; U_{7}; U_{9}; U_{2}; U_{3}; U_{6}; U_{4}; U_{5}; U_{1}]

Lösung zu Aufgabe 38 (b).

(b) Die triviale Untergruppe U_{1} und G selbst sind natürlich Normalteiler von G. Aber auch die Untergruppen der Ordnung 4 sind normal in G, denn für sie gilt jeweils [G:U_{i}] = 2 und deshalb U_{i}g = U_{i} = gU_{i} für alle g ∈ U_{i} und U_{i}g = G \ U_{i} = gU_{i}, für alle g ∈ G \ U_{i}. Die Untergruppe U_{6} ist ebenfalls ein Normalteiler, denn es ist g^{−1}ϱ^{2}g = ϱ^{2} ∈ U_{6} und g^{−1}ιg = ι ∈ U_{6} und für alle g ∈ G. Andererseits sind die Untergruppen U_{2} bis U_{5} keine Normalteiler, denn wie man leicht anschaulich sieht (oder nachrechnet) ist ϱ^{−1}σ_{i}ϱ ∉ ⟨σ_{i}⟩ und ϱ^{−1}τ_{i}ϱ ∉ ⟨τ_{i}⟩ für i ∈ {1, 2}.

Bemerkung: Die Gruppe G aller Spiegelungen und Drehungen eines Quadrats wird im Allgemeinen als ”Diedergruppe“ D_{8} bezeichnet.

Lösung zu Aufgabe 35.

Ist n ∈ ℕ mit φ(n) = 4 und ist n = ∏_{i=1}^{s} p_{i}^{r_{i}} die Zerlegung von n in ein Produkt von paarweise teilerfremden Primzahlpotenzen, so ist φ(n) = ∏_{i=1}^{s}(p_{i}−1)p_{i}^{r_{i}−1}. Also kann n keinen Primteiler größer als 5 und kein Quadrat einer ungeraden Primzahl enthalten, d. h., n hat die Form n = 2^{a} 3^{b} 5^{c} mit a ∈ ℕ_{0} und b, c ∈ {0, 1}. Mit einer kleinen Fallunterscheidung ergibt sich: Ist b = c = 0, so ist n = 8. Ist b = 1, so ist n = 12. Ist c = 1, so ist n = 5 oder n = 10. Für den zweiten Teil der Aufgabe betrachten wir zunächst die beiden Restklassengruppen ℤ_{5}^{∗} und ℤ_{10}^{∗}. Wegen [2]_{5}^{2} ≠ [1]_{5} und [3]_{10}^{2} ≠ [1]_{10} sind die Ordnungen von [2]_{5} und [3]_{10} größer als 2 und damit (als Teiler von 4) gleich 4. Daraus folgt: ℤ_{5}^{∗} und ℤ_{10}^{∗} sind beide zyklisch und die Abbildung ℤ_{5}^{∗} → ℤ_{10}^{∗} mit [2]_{5}^{i} ↦ [3]_{10}^{i} für i ∈ {0, 1, 2, 3} ist ein Isomorphismus. In ℤ_{8}^{∗} und ℤ_{12}^{∗} sind alle Quadrate gleich [1]_{8} bzw. [1]_{12}, diese beiden Gruppen sind also nicht zyklisch. Man sieht (etwa durch Nachrechnen), dass jede bijektive Abbildung von ℤ_{8}^{∗} nach ℤ_{12}^{∗}, die [1]_{8} auf [1]_{12} abbildet, ein Isomorphismus ist.

Lösung zu Aufgabe 36.

(a) Es ist 2000 = 2^{4}·5^{3}, also φ(2000) = (2 − 1)·2^{3}·(5 − 1)·5^{2} = 800.

(b) Es ist 123 = 3 · 41, also 1 ∈ ggT(123, 2000). Nach dem Satz von Euler gilt daher 123^{800} = 123^{φ(2000)} ≡ 1 mod 2000. Die gesuchte Zahl x ist demnach die kleinste positive ganze Zahl mit x ≡ 123^{2} = 15129 mod 2000 . Das ist offensichtlich x = 1129.

Lösung zu Aufgabe 37.

Gegeben sind der Ring K = ℤ_{2}[x] /fℤ_{2}[x] mit f = x^{4} + x^{3} + x^{2} + x + 1 und die multiplikative Gruppe G von K. Wegen Grad f = 4 hat K 16 Elemente. Nach Aufgabe 27 ist f irreduzibel. Also ist K ein Körper und alle von 0 verschiedenen Elemente aus K sind invertierbar. Somit ist |G| = 15, und jedes Element von G hat eine Ordnung, die ein Teiler von 15 ist.

(a) Setzen wir etwa g = [ x^{3} + x]_{f}, so ist g^{3} = [ x]_{f} ≠ [1]_{f} und g^{5} = [ x^{3} + x^{2} ]_{f} ≠ [1]_{f} und damit ord (g) ∉ {1, 3, 5}. Also ist ord (g) = 15 und ⟨g⟩ = G. Die sämtlichen Erzeugenden von G sind dann gerade alle Potenzen von g mit zu 15 teilerfremden Exponenten, also

\begin{aligned}g & = & [ x^{3} + x]_{f}, & g^{8} & = & [ x^{2} + x + 1 ]_{f}, \\ g^{2} & = & [ x^{2} + x]_{f}, & g^{11} & = & [ x^{3} + x^{2} + x]_{f}, \\ g^{4} & = & [ x^{3} + x + 1 ]_{f}, & g^{13} & = & [ x^{2} + 1 ]_{f}, \\ g^{7} & = & [ x^{3} + 1 ]_{f}, & g^{14} & = & [ x + 1 ]_{f}. \end{aligned}

(b) Es ist zu zeigen: Ist G = ⟨g⟩, so ist auch G = ⟨g^{2}⟩. Die Behauptung folgt mit Satz 2 aus §8 der Vorlesung sofort aus ord (g) = |G| = 15 und 1 ∈ ggT (2, 15).

Hausaufgaben

Aufgabe 39.

Es seien p_{1}, …, p_{k} Primzahlen mit p_{i} ≡ 1 mod 4 und q ein Primteiler von 4(p_{1} ⋯ p_{k})^{2} + 1. Zeigen Sie, dass −1 ein Quadrat in ℤ_{q} ist, und folgern Sie daraus, dass es unendlich viele Primzahlen gibt, die kongruent 1 modulo 4 sind.

Aufgabe 40.

Berechnen Sie die Anzahl N_{n}(2) der irreduziblen Polynome f ∈ ℤ_{2}[x] vom Grad n für 1 ≤ n ≤ 10. Geben Sie für jedes dieser n näherungsweise \frac{N_{n}(2)}{A_{n}(2)} an, wobei A_{n}(2) die Anzahl aller Polynome f ∈ ℤ_{2}[x] vom Grad n bezeichne.

Aufgabe 41.

Es sei

H = [ \begin{matrix}1 & 1 & 0 & 1 & 0 & 0 & 1 \\ 0 & 0 & 0 & 1 & 1 & 0 & 1 \\ 1 & 0 & 1 & 1 & 0 & 0 & 1 \\ 0 & 0 & 0 & 0 & 0 & 1 & 1 \end{matrix} ]

und C = { c ∈ ℤ_{2}^{7} | H ·c^{T} = 0 }. Was ist |C| und was ist die Minimaldistanz von C? Wie würden Sie v = [ 0, 0, 0, 1, 1, 1, 1 ] korrigieren, d. h., welches c ∈ C hat minimalen Hamming-Abstand von v?

Aufgabe 42.

Professor Schlaumeier und seine Frau geben eine Party, an der außer ihnen noch fünf weitere Ehepaare teilnehmen. Bei der Begrüßung geben einige Leute einander die Hand, aber natürlich nicht Ehepartner untereinander. Am Schluss der Party fragt der Professor alle anderen, wie vielen Leuten sie jeweils die Hand gegeben haben, und er erhält elf verschiedene Antworten. Wie viele Gäste hat Frau Schlaumeier mit Handschlag begrüßt?

Hinweis. Wegen des Hochschulsportfests am 11. 7. können wir die Aufgaben dieses Blattes nicht zur üblichen Zeit am Mittwoch Nachmittag besprechen. Wir bieten deshalb einen Ersatztermin dafür an, nämlich Dienstag, den 10. 7., um 8.15 Uhr in Hörsaal I.

Hinweis. Die Aufgaben auf diesem Übungsblatt sind ein Angebot an alle, die sich vor der Vordiplomklausur am 7. September noch etwas mit Graphentheorie beschäftigen wollen. Darüberhinaus bieten wir in der vorlesungsfreien Zeit drei Diskussionsstunden an, und zwar am Freitag, dem 24. August, am Dienstag, dem 28. August, und am Montag, dem 3. September, jeweils um 10.00 Uhr im Hörsaal I. Dort können insbesondere die unten stehenden Aufgaben besprochen werden. Wer die Scheinklausur bestanden, aber die Hausaufgabenbedingung um höchstens 4 Punkte verfehlt hat, kann diese Bedingung noch nachträglich durch eine sinnvolle Bearbeitung einer entsprechenden Anzahl der neuen Aufgaben erfüllen und damit den Übungsschein erwerben. Die Abgabe der Lösungen (im Geschäftszimmer des Lehrstuhls) muss dazu allerdings vor der ersten Diskussionsstunde, also bis zum 24. August um 10.00 Uhr erfolgen.

Hausaufgaben

Aufgabe 43.

Ist G = (V, E) ein nummerierter Graph und ist V = {v_{1}, …, v_{n}}, so heißt (d (v_{1}), …, d (v_{n})) \underline{Gradfolge} von G.

(a) Gibt es einen Graphen mit Gradfolge i) (4, 3, 2, 2, 1), ii) (3, 3, 3, 1), iii) (5, 5, 3, 3, 2, 2, 2) ?

(b) Zeigen Sie: Ist d_{1} ≥ ⋯ ≥ d_{n} (mit d_{i} ∈ ℕ), so gibt es einen Graphen mit Gradfolge (d_{1}, …, d_{n}) genau dann, wenn es einen mit Gradfolge (d_{2}−1, …, d_{d_{1}+1}−1, d_{d_{1}+2}, …, d_{n}) gibt.

Aufgabe 44.

Ist G = (V, E) ein Graph, so heißt \overline{G} = (V, \binom{V}{2}\ E) \underline{Komplementärgraph} zu G. Man nennt G \underline{selbst-komplementär}, wenn G ≅ \overline{G} ist. Zeigen Sie, dass für einen selbst-komplementären Graphen G = (V, E) die Kongruenz |V | ≡ 0 oder |V | ≡ 1 mod 4 gilt, und bestimmen Sie alle diese Graphen mit n ≤ 8 Knoten.

Aufgabe 45.

(a) Skizzieren Sie den Baum, der durch den Prüfercode (2, 2, 2, 3, 9, 3, 3) gegeben ist.

(b) Es sei d_{1}, …, d_{n} eine Folge natürlicher Zahlen mit ∑_{i=1}^{n} d_{i} = 2 n − 2. Zeigen Sie, dass die

Anzahl der Bäume auf V = \{1, …, n\} mit d (i) = d_{i} gerade \frac{(n − 2)!}{(d_{1} − 1)! ⋯ (d_{n} − 1)!} ist.

Aufgabe 46.

Zeigen Sie: Ein planarer Graph, in dem es keinen Kreis der Länge 3 gibt, besitzt einen Knoten v vom Grad d (v) ≤ 3.

Übung zur Vorlesung ,,Diskrete Strukturen“ (SS 01)

Prof. Dr. H. Pahlings

Präsenzaufgaben für die Übungsstunde am 26. 4. 01

Aufgabe P1. Zeigen Sie (mit dem Schubfachprinzip): Jede Teilmenge M ⊆ {1, … 9} mit |M| = 6 enthält zwei Zahlen, deren Summe 10 ist.

Aufgabe P2. Es sei

σ = ( \begin{matrix}1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 \\ 9 & 3 & 10 & 6 & 8 & 1 & 2 & 7 & 4 & 5 \end{matrix} ) ∈ S_{10}.

(a) Schreiben Sie σ als Produkt von ziffernfremden Zyklen.

(b) Zeigen Sie: Sind σ_{1}, σ_{2} ziffernfremde Zyklen, so ist σ_{1}σ_{2} = σ_{2}σ_{1}.

(c) Berechnen Sie σ^{−1}, σ^{4}, σ^{12}, σ^{123}.

Aufgabe P3. Schreiben Sie alle Elemente von S_{4} als Produkte von ziffernfremden Zyklen und als Produkte von Transpositionen (Zweierzyklen).

Aufgabe P4. Zeigen Sie:

(a)  ∑_{k=0}^{n} ( \begin{matrix}n \\ k \end{matrix} )^{2} = ( \begin{matrix}2n \\ n \end{matrix} ) ,

(b)  ∑_{k=1}^{n} k ( \begin{matrix}n \\ k \end{matrix} )^{2} = n ( \begin{matrix}2n − 1 \\ n − 1 \end{matrix} ) .

Diskrete Strukturen (H. Pahlings) SS 2001

Präsenzaufgaben am 3. 5. 2001

Aufgabe P5. Wie viele ungerade Zahlen in {1, …, 100} sind weder durch 3 noch durch 5 teilbar? . Aufgabe P6. An einem Institut sind 10 Professoren und 4 Professorinnen. Wie viele verschiedene paritätisch besetzte Kommissionen mit 4 Mitgliedern kann man bilden? Aufgabe P7. Welche der folgenden Gleichungen sind richtig?

( \begin{matrix}n \\ k \end{matrix} ) = ( \begin{matrix}n \\ k − 1 \end{matrix} ) + ( \begin{matrix}n \\ k − 2 \end{matrix} ) für n ≥ k ≥ 2 . . . . . . . . . . . . . . . . □ Ja □ Nein
( \begin{matrix}n + 1 \\ k \end{matrix} ) = ( \begin{matrix}n \\ k \end{matrix} ) + ( \begin{matrix}n \\ k − 1 \end{matrix} ) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . □ Ja □ Nein
( \begin{matrix}m + n \\ k \end{matrix} ) = ∑_{l=0}^{k} ( \begin{matrix}m \\ k − l \end{matrix} ) ( \begin{matrix}n \\ l \end{matrix} ) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .□ Ja □ Nein
∑_{k=0}^{n} S_{n,k} = 2^{n} . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . □ Ja □ Nein
∑_{k=0}^{n} s_{n,k} = n! . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . □ Ja □ Nein

Aufgabe P8. Es sei |M| = 4 und |N| = 3. Die Anzahl der injektiven Abbildungen f: N → M ist . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . der surjektiven Abbildungen f: N → M ist . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . der surjektiven Abbildungen f: M → N ist . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . der surjektiven Abbildungen f: M → M ist . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . der Äquivalenzrelationen auf N ist . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . der surjektiven Abbildungen f: M → ∅ ist . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . aller Abbildungen f: ∅ → M ist . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Aufgabe P9.

Es seien σ = ( \begin{matrix}1 & 2 & 3 & 4 & 5 & 6 \\ 4 & 5 & 1 & 3 & 6 & 2 \end{matrix} ) und τ = ( \begin{matrix}1 & 2 & 3 & 4 & 5 & 6 \\ 3 & 6 & 1 & 5 & 2 & 4 \end{matrix} ) Permutationen aus S_{6}.

Die Zyklendarstellung von σ ist . . . . . . . . . . . . . . . . . . Die Zyklendarstellung von τ ist . . . . . . . . . . . . . . . . . . Die Zyklendarstellung von σ ∘ τ ist . . . . . . . . . . . . . . . Die Zyklendarstellung von σ^{2} ist . . . . . . . . . . . . . . . . . Die Zyklendarstellung von τ^{−1} ist . . . . . . . . . . . . . . . . Welches ist das kleinste n ∈ ℕ mit τ^{n} = (1) ? . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

Diskrete Strukturen (H. Pahlings) SS 2001

Präsenzaufgaben am 10. 5. 2001

Aufgabe P10. Welche der folgenden formalen Potenzreihen sind invertierbar?

∑_{n=0}^{∞} x^{n} . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . □ Ja □ Nein
∑_{n=0}^{∞} n!x^{n} . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . □ Ja □ Nein

x + x^{2} . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . □ Ja □ Nein

∑_{n=0}^{∞} n^{n!}x^{n} . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .□ Ja □ Nein

Aufgabe P11. Welche der folgenden Aussagen über formale Potenzreihen sind richtig?

Ist A = A(x) = ∑_{n=0}^{∞} a_{n}x^{n} ∈ K[[x]], so ist

A(x^{2}) = ∑_{n=0}^{∞} a_{n}x^{2n} ∈ K[[x]] . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . □ Ja □ Nein
A(x + 1) = ∑_{n=0}^{∞} a_{n}(x + 1)^{n} ∈ K[[x]] . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . □ Ja □ Nein
x^{3}A(x) = ∑_{n=3}^{∞} a_{n+3}x^{n} ∈ K[[x]] . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . □ Ja □ Nein
(A(x))^{2} = ∑_{n=0}^{∞} a_{n}^{2}x^{n} ∈ K[[x]] . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . □ Ja □ Nein
(A(x))^{−1} = ∑_{n=0}^{∞} a_{n}x^{−n} ∈ K[[x]] . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . □ Ja □ Nein
D(A(x)) = ∑_{n=0}^{∞} a_{n−1}x^{n} ∈ K[[x]] . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . □ Ja □ Nein

aus D(A(x)) = 0 folgt A = c ∈ K (A ist eine Konstante) . . . . . . . . . . . □ Ja □ Nein

Aufgabe P12. Wie viele verschiedene Möglichkeiten gibt es, einen Betrag von n (z. B. 50) Euro in 1- und 2-Euromünzen auszuzahlen?

Diskrete Strukturen (H. Pahlings) SS 2001

Präsenzaufgaben am 17. 5. 2001

Aufgabe P13. Gibt es A ∈ ℚ[[x]] mit A^{2} = ∑_{n=0}^{∞} n! x^{n}? . . . . . . . . . . . . . . . . . . . . . . . . . . . . .□ Ja □ Nein Gibt es für jeden Körper K ein A ∈ K[[x]] mit A^{2} = 1 + x^{2} ? . . . . . . . □ Ja □ Nein Gibt es A ∈ 𝔽_{2}[[x]] mit A^{2} = 1 + x? . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . □ Ja □ Nein Gilt in 𝔽_{2}[[x]] die Gleichung (∑_{i=0}^{∞} a_{i}x^{i})^{2} = ∑_{i=0}^{∞} a_{i}x^{2i}? . . . . . . . . . . . . . . □ Ja □ Nein Aufgabe P14. Ist f = ∑_{i=0}^{n} a_{i}x^{i} ∈ K[x] mit a_{n} ≠ 0, so gilt für das reflektierte Polynom f^{R} von f:

f^{R} = ∑_{i=0}^{n} a_{i}x^{n−i}, . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . □ Ja □ Nein

f^{R} = ∑_{i=0}^{n} a_{n−i}x^{i}, . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . □ Ja □ Nein

f^{R} = ∑_{i=0}^{n} a_{n−i}x^{n−i}, . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . □ Ja □ Nein

f^{R} = x^{n} ∑_{i=0}^{n} a_{i}x^{i}, . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .□ Ja □ Nein

f^{R} = x^{n} ∑_{i=0}^{n} a_{i}x^{−i}, . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . □ Ja □ Nein

(f^{R})^{R} = f. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . □ Ja □ Nein Aufgabe P15. Für alle n ∈ ℕ und α ∈ ℂ gilt

\binom{α}{n} = \binom{α − 1}{n − 1} + \binom{α − 1}{n}, . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .□ Ja □ Nein

\binom{α}{n} = \binom{α}{α − n}, . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . □ Ja □ Nein

α^{n} = ∑_{k=0}^{n} S_{n,k} k!\binom{α}{k}, . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .□ Ja □ Nein

\binom{α}{n} = 0 für n > α. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .□ Ja □ Nein

Präsenzaufgaben am 31. 5. 2001

Aufgabe P16. (ℕ_{0}, +, −, 0, ·, 1) ist ein Ring . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . □ Ja □ Nein (ℤ, +, −, 0) ist eine Gruppe . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . □ Ja □ Nein (ℝ_{>0}, ·,^{−1}, 1) ist eine Gruppe . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . □ Ja □ Nein ℤ[\sqrt{5}] = \{a + b\sqrt{5} | a, b ∈ ℤ\} ist Unterring von ℝ . . . . . . . . . . . . . . . . . . .□ Ja □ Nein {f ∈ ℚ[x] | f = 0 oder Grad f ist gerade} ist Unterring von ℚ[x] … □ Ja □ Nein

Aufgabe P17. Die Relation ∼, definiert durch a ∼ b genau dann wenn a + b ∈ 2ℤ, ist eine Kongruenzrelation auf ℤ, . . . . . . . . . . . . . . . . . . . . . . . □ Ja □ Nein a − 4b ∈ 3ℤ, ist eine Kongruenzrelation auf ℤ, . . . . . . . . . . . . . . . . . . . . . .□ Ja □ Nein Grad a = Grad b, ist eine Kongruenzrelation auf ℚ[x], . . . . . . . . . . . . . . □ Ja □ Nein a(0) = b(0), ist eine Kongruenzrelation auf ℚ[x], . . . . . . . . . . . . . . . . . . . □ Ja □ Nein a − b ∈ ℚ, ist eine Kongruenzrelation auf ℝ, . . . . . . . . . . . . . . . . . . . . . . . □ Ja □ Nein

Aufgabe P18. Ist K ein Körper und f, g ∈ K[x], so gilt: f = g ⟺ f(a) = g(a) für alle a ∈ K . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . □ Ja □ Nein f ist in K[x] invertierbar ⟺ f(a) ≠ 0 für alle a ∈ K . . . . . . . . . . . . . .□ Ja □ Nein Grad(f ·g) = Grad f · Grad g . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . □ Ja □ Nein {f ∈ K[x] | f(1) = 0} ⊴ K[x] . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .□ Ja □ Nein {f ∈ K[x] | Grad f ≤ 3} ⊴ K[x] . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . □ Ja □ Nein

Aufgabe P19. In ℤ gilt: 2 ∈ ggT(2, 0) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . □ Ja □ Nein In ℤ gilt: aus 1 = ya + zb mit a, b, y, z ∈ ℤ folgt 1 ∈ ggT(a, b) . . . . . .□ Ja □ Nein In ℤ[x] gilt: 2 ∈ ggT(2x, 2x^{2} + 2x) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .□ Ja □ Nein Ist R ein Ring und 1 ∈ I ⊴ R, so ist I = R . . . . . . . . . . . . . . . . . . . . . . . . . □ Ja □ Nein

{∑_{i=3}^{∞} a_{i}x^{i} | a_{i} ∈ ℝ} ⊴ ℝ[[x]] . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . □ Ja □ Nein

Aufgabe P20. Wie viele Elemente hat ℤ/6ℤ? . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

Wie viele Elemente hat ℤ_{2}[x] / (x^{2} + 1)ℤ_{2}[x] ? . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

Wie viele Lösungen hat die Gleichung x^{2} + y^{2} + 4 z = 3 in ℤ? . . . . . . . . . . . . . . . . . . . . . . .

Präsenzaufgaben am 21. 6. 2001

Aufgabe P21. R sei ein kommutativer Ring. Sind a, b Einheiten (a, b ∈ R^{∗}), so ist ab Einheit. . . . . . . . . . . . . . . . . . . . □ Ja □ Nein Ist ab Einheit, so sind a und b Einheiten. . . . . . . . . . . . . . . . . . . . . . . . . . . □ Ja □ Nein Ist a + b Einheit, so sind a und b Einheiten. . . . . . . . . . . . . . . . . . . . . . . . .□ Ja □ Nein

Aufgabe P22. 35 ist ein Teiler von 6^{2n} − 1 für alle n ≥ 1 . . . . . . . . . . . . . . . . . . . . . . . . . .□ Ja □ Nein

Aufgabe P23. Es sei f = x^{4} + x ∈ ℤ_{2}[x]. Wie viele Elemente hat ℤ_{2}[x]/fℤ_{2}[x] ? . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . ℤ_{2}[x]/fℤ_{2}[x] ist ein Körper. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .□ Ja □ Nein Es sei α = [x + 1]_{f}. Was ist α^{4} ? . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

Aufgabe P24. Es sei K ein Körper und f ∈ K[x]. Ist Grad f > 1, so ist f irreduzibel genau dann wenn f keine Nullstelle in K hat.

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . □ Ja □ Nein

Ist Grad f = 1, so ist f irreduzibel. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . □ Ja □ Nein Ist Grad f = 0, so ist f irreduzibel. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . □ Ja □ Nein Ist Grad f = 2 und f(a) ≠ 0 für alle a ∈ K, so ist f irreduzibel. . . . . □ Ja □ Nein Ist K = ℂ, so ist f irreduzibel genau dann wenn Grad f = 1. . . . . . . .□ Ja □ Nein

Aufgabe P25. Ist (G, · ,^{−1} , 1) eine Gruppe und a, b ∈ G, so ist (a·b)^{−1} = a^{−1}·b^{−1}. . □ Ja □ Nein (ℤ_{n}, +, −, 0) ist für alle n ∈ ℕ eine zyklische Gruppe. . . . . . . . . . . . . . . □ Ja □ Nein (ℤ_{n}^{∗}, · ,^{−1} , 1) ist für alle n ∈ ℕ eine zyklische Gruppe. . . . . . . . . . . . . . . . □ Ja □ Nein Hat eine Gruppe G nur 2 Untergruppen, so ist G zyklisch. . . . . . . . . . □ Ja □ Nein

Präsenzaufgaben am 28. 6. 2001

Aufgabe P26. Es sei G eine Gruppe und |G| = m ∈ ℕ und g ∈ G. Die Abbildung G → G, h ↦ g·h ist bijektiv. . . . . . . . . . . . . . . . . . . . . . . . □ Ja □ Nein Zu jedem Teiler d von m gibt es ein Element der Ordnung d in G…□ Ja □ Nein Hat g die Ordung d, so gilt d | m. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . □ Ja □ Nein Ist m eine Primzahl, so ist G zyklisch. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . □ Ja □ Nein Ist m = 15 und g^{3} ≠ 1 und g^{5} ≠ 1, so ist G zyklisch. . . . . . . . . . . . . . . . □ Ja □ Nein Ist ∼ eine Äquivalenzrelation auf G, so ist [1]_{∼} Untergruppe von G. □ Ja □ Nein Ist ∼ eine Kongruenzrelation auf G, so ist [1]_{∼} Normalteiler von G. □ Ja □ Nein Ist φ: G → H ein Gruppenhomomorphismus, so ist Kern(φ) ⊴ G… □ Ja □ Nein

Aufgabe P27. Für alle m ∈ ℕ, a ∈ ℤ gilt a^{φ(m)} ≡ a mod m. . . . . . . . . . . . . . . . . . . . . . . . □ Ja □ Nein Für alle n ∈ ℕ gilt 70 | 101^{6n} − 1. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . □ Ja □ Nein Für alle n ∈ ℕ gilt 70 | 1001^{6n} − 1. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . □ Ja □ Nein Für welche m ∈ ℕ ist φ(m) ungerade? . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

Aufgabe P28. Zu jedem m ∈ ℕ gibt es eine Gruppe G mit |G| = m. . . . . . . . . . . . . . . □ Ja □ Nein Es gibt eine Gruppe mit genau zwei Elementen der Ordnung 5. . . . . □ Ja □ Nein Eine Untergruppe einer zyklischen Gruppe ist stets zyklisch. . . . . . . . □ Ja □ Nein Ein homomorphes Bild einer zyklischen Gruppe ist stets zyklisch… □ Ja □ Nein

Aufgabe P29. Es sei G = (ℤ_{20}, +) und H = { [8n]_{20} | n ∈ ℤ }. H ist Untergruppe von G. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . □ Ja □ Nein Was ist |H|? . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Wie viele erzeugende Elemente hat H? . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Was ist [G:H] ? . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Es ist [2]_{20} + H = [6]_{20} + H. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . □ Ja □ Nein

Präsenzaufgaben am 5. 7. 2001

Aufgabe P30. Es sei p eine Primzahl und n ∈ ℕ. Dann ist ℤ_{p^{n}} ein Körper, . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . □ Ja □ Nein ist ℤ_{p}[x]/(x^{n} − 1) ein Körper, . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . □ Ja □ Nein gibt es einen Körper mit p^{n} Elementen, . . . . . . . . . . . . . . . . . . . . . . . . . . . . □ Ja □ Nein gibt es genau ein irreduzibles Polynom f ∈ ℤ_{p}[x] vom Grad n. . . . . . □ Ja □ Nein

Aufgabe P31. Die Anzahl der normierten irreduziblen Polynome vom Grad 3 in ℤ_{3}[x] ist . . . . . . . . . . .

Aufgabe P32. Ist f ∈ ℤ_{p}[x] irreduzibel mit Grad f = d und n ∈ ℕ, so gilt: wenn f | (x^{n} − 1), so gilt d | n, . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . □ Ja □ Nein wenn f | (x^{p^{n}−1} − 1), so gilt d | n, . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . □ Ja □ Nein

Aufgabe P33. Es sei C der Code über ℤ_{2} mit Generatormatrix G(C) = [ \begin{matrix}1 & 1 & 1 & 0 & 0 \\ 0 & 1 & 1 & 1 & 0 \\ 0 & 0 & 1 & 1 & 1 \end{matrix} ]. Dann gilt:

C ist ein zyklischer Code, . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . □ Ja □ Nein die Minimaldistanz von C ist 3, . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . □ Ja □ Nein dim C = 3. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .□ Ja □ Nein

Aufgabe P34. Wie viele zyklische Codes C der Länge n = 3 gibt es über ℤ_{2} (d. h. C ⊆ ℤ_{2}^{3}) ? . . . . . . Was sind ihre Dimensionen? . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Was sind ihre Minimaldistanzen? . . . . . . . . . . . . . . . . . . . . . . . . . . . .

Präsenzaufgaben am 12. 7. 2001

Aufgabe P35. Wie viele Ideale hat der Ring ℤ_{2}[x] /(x^{3} + 1) ? . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

Aufgabe P36. Ist G = (V, E) ein Graph mit |V | ≥ 2, so gilt: Es gibt stets v_{i}, v_{j} ∈ V mit v_{i} ≠ v_{j} und d(v_{i}) = d(v_{j}). . . . . . . . . . . . . . . □ Ja □ Nein Ist ∑_{v∈V} d(v) < |V |, so ist G nicht zusammenhängend. . . . . . . . . . . . . . . . □ Ja □ Nein

Aufgabe P37. In einer Gruppe von 15 Personen kennt jede Person höchstens 3 andere. Wie viele Paare von Personen, die sich gegenseitig kennen, kann es in dieser Gruppe höchstens geben? …

Aufgabe P38. Ist G = (V, E) ein nummerierter Graph mit Adjazenzmatrix A ∈ ℤ^{n×n} und Inzidenzmatrix B ∈ ℤ^{n×m} und V = { v_{1}, …, v_{n} }, so ist der Grad d(v_{i}) die Summe der Einträge der i-ten Spalte von A, . . . . . . . . . . . . . . . . . . . . □ Ja □ Nein die Summe der Einträge der i-ten Spalte von B, . . . . . . . . . . . . . . . . . . . .□ Ja □ Nein die Summe der Einträge der i-ten Zeile von A, . . . . . . . . . . . . . . . . . . . . . □ Ja □ Nein die Summe der Einträge der i-ten Zeile von B. . . . . . . . . . . . . . . . . . . . . . □ Ja □ Nein

Aufgabe P39. Ist G = (V, E) ein Graph, so gilt |V | ≤ |E|. . . . . . . . . . . . . . . . . . . . . . . . . □ Ja □ Nein Ist G = (V, E) ein Graph, so gilt |E| ≤ |V |^{2}. . . . . . . . . . . . . . . . . . . . . . . . □ Ja □ Nein Der vollständige Graph K_{6} hat 15 Kanten. . . . . . . . . . . . . . . . . . . . . . . . . . □ Ja □ Nein Der vollständige Graph K_{6} hat einen 4-regulären induzierten Teilgraphen. □ Ja □ Nein Es gibt einen 3-regulären Graphen mit 5 Knoten. . . . . . . . . . . . . . . . . . . □ Ja □ Nein

Name: Matrikelnummer:

Klausur zur Vorlesung Diskrete Strukturen (13. 7. 2001)

Professor Dr. H. Pahlings, Lehrstuhl D für Mathematik, RWTH Aachen

Ankreuzteil

Aufgabe A1. Es seien s_{n,k} und S_{n,k} die Stirlingzahlen 1. bzw. 2. Art. Dann gilt:

(1) S_{n,k} = S_{n−1,k−1} + k·S_{n−1,k} für 1 ≤ k ≤ n. . . . . . . . . . . . . . . . . . . . . . . . . . . □ Ja □ Nein

(2) ∑_{k=0}^{n} s_{n,k} = 2^{n}. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . □ Ja □ Nein

(3) Was ist S_{4,2}? . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

Aufgabe A2. Ist A = ∑_{n=0}^{∞} a_{n}x^{n} ∈ ℚ[[x]] eine formale Potenzreihe, so ist:

(1) A^{2} = ∑_{n=0}^{∞} a_{n}^{2}x^{n} . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . □ Ja □ Nein

(2) x^{2}A = ∑_{n=2}^{∞} a_{n−2}x^{n} . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . □ Ja □ Nein

(3) A genau dann in ℚ[[x]] invertierbar, wenn a_{0} = 1 ist . . . . . . . . . . . . . . . . □ Ja □ Nein

Aufgabe A3. Ist K ein Körper und f ∈ K[x] mit Grad f ≥ 1, so gilt:

(1) Gibt es kein c ∈ K mit (x + c) | f, so ist f irreduzibel. . . . . . . . . . . . . . .□ Ja □ Nein

(2) Ist K[x] /f K[x] ein Körper, so ist f irreduzibel. . . . . . . . . . . . . . . . . . . . . □ Ja □ Nein

(3) x^{3} + x + 1 ∈ ℤ_{2}[x] ist irreduzibel. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .□ Ja □ Nein

Aufgabe A4.

(1) Wie viele Elemente hat ℤ/9 ℤ? . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

(2) ℤ/9 ℤ ist ein Körper. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . □ Ja □ Nein

(3) Wie viele Elemente hat ℤ_{3}[x] /(x^{2} − 1) ℤ_{3}[x] ? . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

(4) ℤ_{3}[x] /(x^{2} − 1) ℤ_{3}[x] ist ein Körper. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . □ Ja □ Nein

Aufgabe A5. Es sei C der Code über ℤ_{2} mit der Generatormatrix G = [ \begin{matrix}1 & 1 & 1 & 0 & 0 \\ 0 & 1 & 1 & 1 & 0 \\ 0 & 0 & 1 & 1 & 1 \end{matrix} ].

(1) Was ist die Dimension von C? . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

(2) C ist zyklisch. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . □ Ja □ Nein

(3) Die Minimaldistanz von C ist 3. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . □ Ja □ Nein

Aufgabe A6. Gibt es einen Graphen G = (V, E) mit |V | ≤ 5 und

(1) ∑_{v∈V} d(v) = 9 ? . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .□ Ja □ Nein

(2) ∑_{v∈V} d(v) = 22 ? . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .□ Ja □ Nein

(3) Adjazenzmatrix A mit A^{2} = [ \begin{matrix}1 & 0 & 0 \\ 0 & 1 & 0 \\ 0 & 0 & 1 \end{matrix} ]? . . . . . . . . . . . . . . . . . . . . . . . . . □ Ja □ Nein

Rechenaufgaben ohne Begründung

Aufgabe R1. (7 Punkte)

(1) Wie viele injektive Abbildungen f: {1, 2} → {1, 2, 3, 4} gibt es? . . . . . . . . . . . . . . . . . . . . . .

(2) Wie viele surjektive Abbildungen f: {1, 2, 3, 4} → {1, 2, 3} gibt es? . . . . . . . . . . . . . . . . . . .

(3) Wie viele injektive Abbildungen f: {1, 2, 3, 4} → {1, 2, 3, 4} gibt es? . . . . . . . . . . . . . . . . . . Aufgabe R2. (4 Punkte) Es seien die Permutationen a = (1 2 5) (3 6 7 8 4) und c = ( \begin{matrix}1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 \\ 7 & 5 & 3 & 8 & 1 & 4 & 2 & 6 \end{matrix} ) aus S_{8} gegeben.

(1) Die Zyklendarstellung von c ist . . . . . . . . . . . . . . . . . . . . . .

(2) Die Ordnung von a ist . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

(3) Die Zyklendarstellung von a^{3} ist . . . . . . . . . . . . . . . . . . . .

(4) Die Zyklendarstellung von a^{3001} ist . . . . . . . . . . . . . . . . . . Aufgabe R3. (4 Punkte) Berechnen Sie einen größten gemeinsamen Teiler d der Zahlen 532 und 434 und stellen Sie ihn in der Form d = a · 532 + b · 434 mit a, b ∈ ℤ dar. . . . . . . . . . . . Aufgabe R4. (8 Punkte)

(1) Es sei φ die eulersche φ-Funktion. Berechnen Sie φ(60). . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

(2) Wie viele Einheiten (invertierbare Elemente) hat der Ring ℤ/60 ℤ? . . . . . . . . . . . . . . . . . .

(3) Bestimmen Sie die kleinste Zahl n ∈ ℕ_{0} mit n ≡ 7^{162} mod 60. . . . . . . . . . . . . . . . . . . . . . . . . Aufgabe R5. (6 Punkte)

(1) Die Anzahl der irreduziblen Teiler von x^{2^{5}} − x ∈ ℤ_{2}[x] ist . . . . . . . . . . . . . . . . . . . . . . . . . . .

(2) Die Anzahl der irreduziblen Polynome vom Grad 5 über ℤ_{2} ist . . . . . . . . . . . . . . . . . . . . . . . Aufgabe R6. (5 Punkte) Wie viele Ideale hat der Ring ℤ_{2}[x] /(x^{5} + 1) ℤ_{2}[x] ? . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

Aufgaben mit Lösungsweg

Aufgabe L1. (8 Punkte) Die Folge (a_{n})_{n∈ℕ_{0}} sei rekursiv definiert durch a_{0} = 0, a_{1} = 2 und a_{n} = −a_{n−1} + 2 a_{n−2} für alle n ≥ 2. Bestimmen Sie mit Hilfe der erzeugenden Funktion die explizite Darstellung der Folgenglieder a_{n}. Aufgabe L2. (6 Punkte) Geben Sie explizit einen Isomorphismus ψ: ℤ_{220} → ℤ_{4} × ℤ_{5} × ℤ_{11} an und berechnen Sie

ψ( [135]_{220}), ψ( [187]_{220}) und ψ( [135·187]_{220}).

Benutzen Sie dies, um [135]_{220} · [187]_{220} in ℤ_{220} auszurechnen.

Zur Organisation der Übungen ,,Diskrete Strukturen” (SS 01)

Prof. Dr. H. Pahlings

Die Aufgabenblätter für die Übungsaufgaben werden in der Regel jeweils freitags um 10.00 Uhr im Lehrstuhl ausgelegt. Die Lösungen erwarten wir dann anderthalb Wochen später am Montag bis 12.00 Uhr im Übungskasten des Lehrstuhls. In der darauf folgenden Diskussionsstunde am Mittwoch um 17.30 Uhr werden dann einige der Aufgaben besprochen, soweit die Zeit nicht für die Diskussion von Fragen zur Vorlesung gebraucht wird. In der Übungsstunde am Donnerstag können, wenn nötig, noch einige weitere Fragen zu den Hausaufgaben diskutiert werden. Ansonsten sollen die Übungsstunden im Wesentlichen dem Üben des Vorlesungsstoffes anhand neuer Präsenzaufgaben dienen.

Eine Ausnahme von diesem Zeitplan ist die erste Übungsserie, die in der Vorlesungsstunde am Mittwoch, dem 18. 4., ausgegeben wird und die bis zum Mittwoch, dem 25. 4., um 14.00 Uhr zu bearbeiten ist.

Da für eine sinnvolle Übungsstunde 45 Minuten etwas wenig sind, werden wir statt der eigentlich vorgesehenen dreizehn Übungsstunden nur zehn Übungsstunden ansetzen, die dann aber jeweils 60 Minuten dauern, nämlich donnerstags von 15.45 bis 16.45 Uhr (vier Gruppen) bzw. von 17.30 bis 18.30 Uhr (drei Gruppen). Die drei Gruppen mit der späteren Anfangszeit sind insbesondere für diejenigen Teilnehmer gedacht, bei denen sich sonst eine Überschneidung mit anderen Veranstaltungen ergibt. Die Termine der zehn Übungsstunden sind: 26. 4., 3. 5., 10. 5., 17. 5., 31. 5., 21. 6.,

28. 6., 5. 7., 12. 7. und 19. 7..

Die Einteilung in die Übungsgruppen erfolgt durch Eintragen in die sieben Übungsgruppenlisten während der Vorlesung am Freitag, dem 20. 4.. Wir empfehlen, dass Sie sich schon vorher überlegen, wer mit wem zusammen in derselben Gruppe sein möchte und wer diese Namen dann gegebenenfalls geschlossen in eine der Listen einträgt.

Die erste Diskussionsstunde findet am Mittwoch, dem 25. 4., statt.

Am Freitag, dem 13. 7., findet um 15.30 Uhr eine zweistündige Schein-Klausur statt. Obwohl der Übungsschein im Fach Diskrete Strukturen für das Studium der Informatik nicht vorgeschrieben ist, ist sein Erwerb doch eine gute Übung für die nachfolgende Vordiplom-Klausur. Wir empfehlen deshalb dringend die Teilnahme an den Übungen und an der Schein-Klausur.

Einen Übungsschein erhält, wer am Ende des Semesters

(1) 50 % der Hausaufgaben ”sinnvoll“ bearbeitet und

(2) die Schein-Klausur bestanden hat.

Mit eventuellen weiteren Fragen zur Organisation von Vorlesung und Übungen können Sie sich im Lehrstuhl D für Mathematik an Dr. Felsch, Raum 222, wenden.

Literatur zur Vorlesung

M. Aigner: Diskrete Mathematik. Vieweg, 3. Aufl. 1999. N. Biggs: Discrete Mathematics. Clarendon Press, Oxford 1989. R. Graham, D. Knuth, O. Patashnik: Concrete Mathematics. Addison Wesley, 2. Aufl. 2000. A. Steger: Diskrete Strukturen I, Springer, 2001.