Lösungen der Übungsaufgaben978-3-8348-9182... · 2017-08-27 · Lösungen der Übungsaufgaben...

Lösungen der Übungsaufgaben

Kapitel 1

1 Wir teilen die Socken in drei Kategorien ein: graue, braune und schwarze. (a) Wenn der Professor vier Socken aus seiner Kiste nimmt, so sind nach dem Schub-fachprinzip mindestens zwei aus derselben Kategorie. (b) Wenn er zwei graue Socken bekommen will, so muss er im schlimmsten Fall 22 Socken ziehen, denn die ersten 20 könnten alle braun oder schwarz sein.

2 Ein Quadrat der Seitenlänge 3 kann man in 9 kleine Quadrate der Seitenlänge 1 unter-teilen. Teilt man 10 Punkte (Objekte) auf diese 9 Teilquadrate (Kategorien) auf, so gibt es nach dem Schubfachprinzip ein Teilquadrat, das mindestens zwei Punkte ent-hält. Den größten Abstand, den zwei Punkte in einem Quadrat der Seitenlänge 1 haben können, ist die Länge der Diagonale, also nach dem Satz des Pythagoras 2 .

3 Einen Würfel der Kantenlänge 2 kann man in 2 2 2 = 8 kleine Würfel der Kantenlänge 1 unterteilen. Teilt man 9 Punkte auf diese 8 Würfel auf, so gibt es nach dem Schub-fachprinzip einen Würfel, der mindestens 2 Punkte enthält. Der Abstand dieser zwei Punkte kann höchstens so groß sein wie die Raumdiagonale, also 3111 222 .

4 hmhm = 28. Teilt man 28 Punkte auf 3 3 3 = 27 kleine Würfel auf, so enthält mindes-tens einer davon zwei Punkte, die höchstens den Abstand der Raumdiagonale haben.

5 Wir unterteilen das Dreieck in vier gleichseitige Dreiecke der Seitenlänge ½. Verteilen wir fünf Punkte auf diese 4 kleinen Dreiecke, so enthält ein Dreieck mindestens zwei Punkte. Diese beiden Punkte können höchstens den Abstand ½ haben.

6 hmhm = ¼. Man unterteilt das Dreieck in 16 gleichseitige Dreiecke der Seitenlänge ¼.

7 Siehe 1.1 „Gleiche Anzahl von Bekannten“. Man muss lediglich die Relation „ist be-kannt mit“ durch die Relation „stößt an mit“ ersetzen.

8 32. Da jeder Springer beim Ziehen auf ein Feld der anderen Farbe wechselt, kann man 32 Springer zum Beispiel auf die weißen Felder stellen.

9 Mehr als die Hälfte muss auf Feldern gleicher Farbe stehen, also ...

10 Wir teilen die elf natürlichen Zahlen in folgende fünf Kategorien K0, K1, ..., K4 ein: In K0 kommen diejenigen Zahlen, die Vielfache von 5 sind, in K1 kommen diejenigen Zahlen, die bei Division durch 5 den Rest 1 ergeben, in K2 kommen diejenigen Zahlen, die bei Division durch 5 den Rest 2 ergeben, in K3 kommen diejenigen Zahlen, die bei Division durch 5 den Rest 3 ergeben, in K4 kommen diejenigen Zahlen, die bei Division durch 5 den Rest 4 ergeben.

212 Lösungen der Übungsaufgaben

Das verallgemeinerte Schubfachprinzip sagt jetzt (da 11 > 2 5 ist), dass es eine Kate-gorie mit drei Objekten gibt. Es gibt also drei Zahlen, die bei Division durch 5 den-selben Rest ergeben. Wenn wir die Differenz je zweier dieser Zahlen bilden, „hebt sich der Rest weg“, die Differenz ist daher durch 5 teilbar.

11 Wir verteilen die Türme der Reihe nach. Erste Spalte: 8 Möglichkeiten, zweite Spalte: nur noch 7 Möglichkeiten, dritte Spalte: noch 6 Möglichkeiten, ... achte Spalte: nur noch eine Möglichkeit. Das ergibt insgesamt 8 7 6 5 4 3 2 1 = 8! = 40320 Möglichkei-ten.

12 Betrachten wir die x- und die y-Koordinaten der Punkte. Es gibt vier Kategorien: x gerade, y gerade; x gerade, y ungerade; x ungerade, y gerade; x ungerade, y ungerade;

Es gibt fünf Objekte (Punkte). Nach dem Schubfachprinzip gibt es daher mindestens eine Kategorie, in der mindestens zwei Objekte liegen. Die Summe zweier gerader Zahlen ist gerade, die Summe zweier ungerader Zahlen ist ebenfalls gerade. Der Mit-telpunkt zwischen zwei Punkten (x1, y1) und (x2, y2) ist

2yy,

2xx 2121

Da beide Zähler gerade sind, wenn beide Punkte in der gleichen Kategorie liegen, sind sie durch zwei teilbar und die Koordinaten des Mittelpunktes sind ganzzahlig.

13 hmhm = 9. Denn die neun Punkte kann man je nach ihren x-, y- und z-Koordianten in acht Kategorien aufteilen: nämlich die vier Kategorien aus Aufgabe 12, jeweils mit „z gerade“ und „z ungerade“. Der Rest folgt analog zu Aufgabe 12.

14 Bei einer ganzzahligen Division durch 3 können sowohl die x- als auch die y-Koordinate den Rest 0, 1 oder 2 haben. Dies ergibt die neun Kategorien (3 Möglich-keiten für x mal 3 Möglichkeiten für y), auf die wir die 10 Punkte aufteilen. Nach dem Schubfachprinzip enthält eine Kategorie mindestens zwei Punkte. Die x-Koordinaten dieser Punkte ergeben bei Division durch 3 also den gleichen Rest. Die Zahl x1 + 2x2 ist dann ohne Rest durch 3 teilbar. Dasselbe gibt für die y-Koordinaten bzw. die Zahl y1 + 2y2. Dann sind die Koordinaten des Punktes

3y2y,

3x2x 2121 ,

der die Strecke im Verhältnis 2:1 teilt, ganzzahlig.

15 Schubfachprinzip: Die Objekte sind die 9 natürlichen Zahlen. Diese werden in 8 Kate-gorien K0, K1, ..., K8 eingeteilt: K0 enthält diejenigen Zahlen, die Vielfache von 9 sind, K1 enthält die Zahlen, die bei Division durch 9 den Rest 1 ergeben,

Lösungen der Übungsaufgaben 213

K2 enthält die Zahlen, die bei Division durch 9 den Rest 2 ergeben, . . . K8 enthält die Zahlen, die bei Division durch 9 den Rest 8 ergeben.

Dann ist jede Zahl in mindestens einer dieser 8 Kategorie enthalten. Nach dem Schub-fachprinzip gibt es eine Kategorie mit zwei Objekten. Das bedeutet: Es gibt zwei Zah-len, die bei Division durch 9 denselben Rest ergeben. Wenn wir die Differenz dieser Zahlen bilden, „hebt sich der Rest weg”. D.h.: Wenn man die Differenz dieser Zahlen durch 9 teilt, geht diese ohne Rest auf. Mit anderen Worten: Die Differenz ist durch 9 teilbar.

16 Wir haben 1000 Objekte (natürliche Zahlen) und 8 Kategorien (Reste von 0 bis 7). Da es mehr Objekte als Kategorien sind, gibt es wieder mindestens eine Kategorie mit mindestens zwei Objekten. D.h. es gibt zwei Zahlen, die den gleichen Rest haben. Die Differenz dieser beiden Zahlen ist dann ohne Rest durch 8 teilbar.

17 Unter je n + 1 natürlichen Zahlen gibt es mindestens zwei, deren Differenz durch n teilbar ist.

18 Gegenbeispiel: In der Menge {1, 2, 6, 7, 11, 12} gibt es keine zwei Zahlen, deren Summe durch 5 teilbar ist.

Kapitel 2

1 Wenn es eine Überdeckung geben sollte, dann muss jedes Eckfeld überdeckt sein. Ins-besondere muss das Feld links unten überdeckt sein; o. B. d. A. liegt der entsprechen-de Dominostein waagrecht. Dann müssen die beiden Felder rechts neben diesem Stein durch zwei senkrecht stehende Steine abgedeckt sein. Notwendigerweise müssen dann über diesen zwei senkrechten Steinen zwei waagrechte Steine liegen. Links neben die-sen beiden Dominosteinen müssen zwei senkrechte Steine liegen. Insgesamt ergibt sich zwangsläufig folgende Teilabdeckung, die in der Mitte ein 2 2-Quadrat frei lässt, das nicht überdeckt werden kann.

2 Wenn m oder n durch 4 teilbar ist, so kann man das Schachbrett nach Satz 2.2.1 kom-plett mit 4 1-Dominosteinen überdecken. Seien m und n durch 2 aber nicht durch 4 teilbar. Dann gibt es natürliche Zahlen a und b, so dass m = a 4 + 2 und n = b 4 + 2


gilt. Nach Satz 2.2.1 kann man die ersten 4b Spalten komplett mit 4 1-Dominosteinen überdecken. Ebenso können von den restlichen 2 Spalten die obersten 4a Zeilen mit 4 1-Dominosteinen überdeckt werden. Übrig bleibt ein 2 2-Feld, das mit dem 2 2-Stein überdeckt werden kann.

3 Ein Springer springt abwechselnd von einem schwarzen Feld zu einem weißen Feld und umgekehrt, erreicht also jeweils nach 2 Sprüngen wieder ein Feld der gleichen Farbe. Um wieder auf sein Ausgangsfeld zurückzukehren, muss er folglich eine gerade Anzahl von Zügen durchführen.

4 Ein Turm wechselt bei jeder Bewegung ständig die Farbe des Feldes. Um jedes Feld genau einmal zu erreichen, muss er am Ende auf einem Feld stehen, das eine andere Farbe als das Startfeld hat. Er kann daher nicht von einem Eckfeld in die gegenüber-liegende Ecke gelangen, da diese beiden Felder die gleiche Farbe besitzen.

5 Für zwei Quadrate gibt es nur eine Möglichkeit zusammenzuhängen. Ein drittes Quad-rat kann auf zwei Arten angehängt werden (entweder alle in einer Reihe oder mit Knick). Für vier Quadrate gibt es dann die dargestellten Möglichkeiten.

6 Die zwölf Pentominos sind

7 Die Strategie des ersten Spielers besteht darin, dass er sein zweites Kreuz diagonal ne-ben sein erstes Kreuz setzt (und zwar auf die entgegengesetzte Seite, wo der zweite Spieler eventuell sein erstes Kreuz gemacht hat). Dann bleiben ihm sowohl für das dritte als auch für das vierte Kreuz jeweils zwei Möglichkeiten, von denen der Gegner immer nur eine verhindern kann. Auf diese Weise hat der erste Spieler nach vier Zü-gen gewonnen.

8 Wir betrachten einen Ausschnitt von 4 Reihen und 82 Spalten aus dem Gitter. Jede Spalte dieses Ausschnitts hat vier Gitterpunkte. Vier Punkte können auf genau 34 = 81 verschiedene Arten gefärbt werden (für jeden Punkt hat man drei Farben zur Verfü-gung). Da es 82 Spalten gibt, gibt es mindestens zwei Spalten mit derselben Farban-ordnung. In jeder Farbanordnung gibt es aber zwei Punkte, die gleich gefärbt sind. Man nehme diese Punkte in den beiden Spalten. Diese bilden ein Rechteck mit gleich-farbigen Ecken.

Kapitel 3

1 (n + 1)2.

2 1 + 2 + 3 + ... + (n + 1) = (n + 1)(n + 2)/2.


3 6n Punkte auf dem Rand.

4 Induktionsverankerung: Die Aussage gilt für n = 1 Scheibe, denn um eine Scheibe umzuschichten, benötigt man 21 – 1 = 2 – 1 = 1 Zug. Induktionsannahme: Es gibt ein n 1, so dass ein Turm mit n Scheiben in 2n – 1 Zü-gen umgeschichtet werden kann. Induktionsbehauptung: Dann gilt die Aussage auch für n + 1, d. h. für einen Turm mit n + 1 Scheiben gibt es eine Lösung mit 2n+1 – 1 Zügen. Induktionsschritt: Wir betrachten zunächst die oberen n Scheiben des n + 1 Scheiben hohen Turms. Um diese n Scheiben umzuschichten, benötigt man nach Induktionsan-nahme 2n – 1 Züge. Nun hat man die größte Scheibe freigelegt. Diese Scheibe kann man in einem Zug umsetzen. Schließlich schichtet man noch den Turm der kleineren n Scheiben auf die umgesetzte (n + 1)-te Scheibe. Wieder nach Induktionsannahme be-nötigt man dafür 2n – 1 Züge. Das bedeutet, dass wir insgesamt

(2n – 1) + 1 + (2n – 1) = 2 · 2n – 1 = 2n+1 – 1

Züge benötigt haben.

5 Sie brauchen 264 – 1 = 18446744073709551615 Sekunden. Das sind 584942417355 Jahre!

6 Induktionsbasis: Sei n = 1. Durch Aufteilung mit nur einem Kreis entstehen nur zwei Länder, die man mit schwarz und weiß verschiedenen färben kann. Induktionsschritt: Die Behauptung gelte für n Kreise. Wir müssen zeigen, dass sie dann auch für n + 1 Kreise gilt. Dazu betrachten wir eine beliebige Landkarte, die durch Zeichnen von n + 1 Kreisen k1, k2, ... , kn+1 entstanden ist. Lassen wir die Gerade kn+1 außer Betracht, so haben wir eine Landkarte, die nur durch die n Kreise k1, ... , kn entstanden ist. Nach In-duktionsvoraussetzung ist diese Landkarte mit den Farben schwarz und weiß zulässig färbbar. Jetzt fügen wir den (n+1)-ten Kreis wieder ein. Dabei entstehen neue Länder, und wir müssen einen Teil der Länder umfärben. Wir färben das Innere des (n+1)-ten Kreises um: Jedes Land, das innerhalb von kn+1 liegt, wechselt die Farbe. Dadurch entsteht eine zulässige Färbung.

7 Induktionsbasis: Sei n = 3. Natürlich kann man die Ecken eines Dreiecks mit drei ver-schiedenen Farben färben. Induktionsschritt: Die Behauptung gelte für ein beliebiges n-Eck. Wir müssen zeigen, dass sie dann auch für ein (n+1)-Eck gilt. Dazu betrachten wir ein beliebiges trianguliertes (n+1)-Eck. Sei d eine Diagonale aus dem Inneren der Triangulierung. Dann zerlegt d das (n+1)-Eck in zwei triangulierte Vielecke L und R mit jeweils weniger als n Ecken. Nach Induktionsvoraussetzung sind beide Vielecke L und R mit drei Farben färbbar. Die beiden Ecken von d gehören sowohl zu L als auch zu R. Falls diese Ecken bei den Färbungen von L und R ver-


schiedene Farben erhalten haben, müssen die Farben von L entsprechend vertauscht werden.

8 Wir wenden den Trick von Gauß auf die ersten n ungeraden Zahlen an:

1 + 3 + 5 + ... + 2n–1

+ 2n–1 + 2n–3 + 2n–5 + ... + 1

= 2n + 2n + 2n + ... + 2n

= n 2n

Aus 2 (1 + 3 + 5 + ... + (2n–1)) = n 2n folgt die Behauptung.

9 Der Trick besteht darin, dass wir von der Summe S = 1 + q + q2 + ... + qn ihr q-faches abziehen, also S – q S bilden:

1 + q + q2 + ... + qn

– ( q + q2 + ... + qn + qn+1 )

= 1 + 0 + 0 + ... + 0 – qn+1

= 1 – qn+1

Aus S – q S = (1 – q) S = 1 – qn+1 folgt: S = q1

q1 1n

. Durch Multiplikation mit a

folgt die gesuchte Summenformel.

10 Induktionsbasis: Die Formel gilt für n = 1, denn 1 + 2 = 22 – 1. Induktionsschritt: Für ein n 1 gelte 1 + 2 + 4 + ... + 2n = 2n+1 – 1. Dann gilt

1 + 2 + 4 + ... + 2n + 2n+1 = 2n+1 – 1 + 2n+1 = 2n+2 – 1.

11 Induktionsbasis: Die Formel gilt für n = 1, denn 1 2 = (1 – 1) 21+1 + 2. Induktionsschritt: Für ein n 1 gelte 1 2 + 2 22 + 3 23 + 4 24 + ... + n 2n = (n – 1) 2n+1 + 2. Dann gilt

1 2 + 2 22 + 3 23 + 4 24 + ... + n 2n + (n + 1) 2n+1 = (n – 1) 2n+1 + 2 + (n + 1) 2n+1 = 2n 2n+1 + 2 = n 2n+2 + 2.

12 Induktionsbasis: Die Formel gilt für n = 1, denn 12 = )112()11(161 .

Induktionsschritt: Für ein n 1 gelte 12 + 22 + 32 + ... + n2 = )1n2()1n(n61 . Dann

gilt

12 + 22 + 32 + ... + n2 + (n + 1)2 = )1n2()1n(n61 + (n + 1)2

)1n(61 [2n2 + n + 6(n + 1)] = )1n(6

1 [2n2 + 7n + 6] = )3n2()2n()1n(6

1 = )1)1n(2()2n()1n(61 .

13 Induktionsbasis: Die Ungleichung gilt für n = 5, denn 25 = 32 > 25 = 52.


Induktionsschritt: Für ein n 5 gelte 2n > n2. Dann gilt

2n+1 = 2 2n > 2 n2 = n2 + n2 > n2 + 4n (denn n > 4) = n2 + 2n + 2n > n2 + 2n + 1 = (n + 1)2

14 Siehe Satz 3.2.6.

15 Induktionsbasis: Die Behauptung gilt für n = 1, denn 71 – 1 = 6. Induktionsschritt: Für ein n 1 sei 7n – 1 = 6 k mit einer natürlichen Zahl k. Dann ist

7n+1 – 1 = 7 7n – 1 = 7 (6k + 1) – 1 = 42k + 6 = (7k + 1) 6

ebenfalls durch 6 teilbar.

16 Nein (144 + 233 322), nein, nein, nein (die Simpson-Identität gilt jeweils nicht). Die ersten 40 Fibonacci-Zahlen lauten: 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181, 6765, 10946, 17711, 28657, 46368, 75025, 121393, 196418, 317811, 514229, 832040, 1346269, 2178309, 3524578, 5702887, 9227465, 14930352, 24157817, 39088169, 63245986, 102334155.

17 Auf genau fn viele Arten. Wir bezeichnen die Anzahl der Möglichkeiten, die n-te Stufe zu erreichen, mit sn. Die erste Stufe erreicht der Briefträger nur auf eine Weise. Eben-so gibt es für die zweite Stufe nur eine Möglichkeit, also gilt s1 = s2 = 1. Um die (n+2)-te Stufe zu erreichen, gibt es zwei prinzipiell verschiedene Möglichkeiten. Im ersten Fall kommt der Briefträger von der (n+1)-ten Stufe her, auf die er auf sn+1 Mög-lichkeiten gelangt sein kann. Im zweiten Fall kommt er in einem Doppelschritt von der n-ten Stufe her, auf die er auf sn Arten gelangt sein kann. Insgesamt gibt es also sn+2 = sn+1 + sn Möglichkeiten, auf die (n+2)-te Stufe zu gelangen. Es folgt sn = fn.

18 Eine Drohne hat in der n-ten Vorfahrensgeneration genau fn Vorfahren, nämlich fn–1 weibliche und fn–2 männliche. Eine Königin entspricht im Kaninchenproblem einem gebärfähigen, eine Drohne einem nicht-gebärfähigen Paar.

19 Es gilt

mM =

MmM

mM2

= mM 2

mM = 1

mM

2

mM – 1

mM = 0.

Diese quadratische Gleichung hat die Lösungen

mM =

251

Da M die größere Teilstrecke ist, ist folgt M/m =

20 Induktionsbasis: Die Formel gilt für n = 1, denn 1 + f2 = 1 + 1 = 2 = f3 = f2+1. Induktionsschritt: Für ein n 1 gelte 1 + f2 + f4 + f6 + ... + f2n = f2n+1. Dann gilt

1 + f2 + f4 + f6 + ... + f2n + f2(n+1) = f2n+1 + f2(n+1) = f2n+1 + f2n+2 = f2n+3 = f2(n+1)+1.


21 Induktionsbasis: Die Formel gilt für n = 1, denn f1+2 = f3 = 2 = 1 + 1 = f1 + 1. Induktionsschritt: Für ein n 1 gelte fn+2 = fn + fn–1 + . . . + f1 + 1. Dann gilt

f(n+1)+2 = fn+3 = fn+1 + fn+2 = fn+1 + fn + fn–1 + ... + f1 + 1.

Kapitel 4

1 Es sei S die Menge der Studentinnen und E die Menge der Erstsemester. Dann ist S E die Menge der Studentinnen im ersten Semester. Nach der Summenformel gilt

| S E | = | S | + | E | – | S E | = 55 + 60 – | S E | 55 + 60 – 80 = 35,

denn | S E | 80 (Anzahl alles Hörer). Also ist | S E | 35.

2 (a) Für jeden Buchstaben gibt es 26 Möglichkeiten, insgesamt also 26 26 26 = 263 = 17576 Möglichkeiten. (b) Auf http://www.world-airport-codes.com sind derzeit 9528 Codes aufgelistet.

3 Es gibt 4 2 10 3 = 240 Möglichkeiten. Dafür braucht man 240 Monate, also 20 Jahre.

4 Für jede Ziffer gibt es 10 Möglichkeiten, insgesamt also 105 = 100000 Möglichkeiten.

5 Bei zwei 3-stelligen Zahlenschlössern gibt es nur 103 + 103 = 2000 Möglichkeiten, bei einem 6-stelligen jedoch 106 = 1000000.

6 Für die erste Stelle gibt es 9 Möglichkeiten (1, 2, ..., 9), für die zweite dann ebenfalls noch 9 (0, 1, 2, ..., 9, ausgenommen die Ziffer der ersten Stelle), für die dritte 8 und für die vierte 7. Insgesamt gibt es also nur noch 9 9 8 7 = 4536 Möglichkeiten (statt 9 10 10 10 = 9000, wenn er nichts verraten hätte).

7 Es sei F die Menge der Frauen und M die Menge der Männer. Dann gilt | F | = 42.103.000 und | M | = 82.259.500 – 42.103.000 = 40.156.500. Die Anzahl aller ver-schiedengeschlechtlichen Paare ist dann

| F M | = | F | | M | = 1690709119500000.

Wenn es gleich viele Männer wie Frauen gäbe, wäre | F | = | M | = 82.259.500 / 2 = 41.129.750. Dann gäbe es mehr Paare: | F M | = | F | | M | = 1691656335062500.

8 Die Menge sei M = {m1, m2, ..., mn}. Wir ordnen jeder Teilmenge T von M wie folgt eine binäre Folge {b1, b2, ..., bn} zu: Es gilt bi = 1, falls mi T ist, sonst gilt bi = 0. Da diese Zuordnung eineindeutig (bijektiv) ist, gibt es genau so viele Teilmengen wie binäre Folgen, also 2n.

9 5

10 =

!5!5!10 = 252,

4042

= !40!2

!42 = 42 41/2 = 861, 1147

= 52251400851.


10 Es gibt 7 Dominos mit gleichen Zahlen (0-0, 1-1, ..., 6-6) und 27

= 21 Dominos mit

verschiedenen Zahlen. Insgesamt gibt es also 28 Stück.

11 (a) 2

10 = 45.

(b) Aus 2n

= 55 folgt n = 11.

(c) Wegen 2

10 < 50 <

211

kann die Behauptung nicht stimmen.

12 Es klingelt 2m

– m mal.

13 Auf der Party befinden sich 4 Paare und 4 Singles: Die 4 Paare stoßen 28

– 4 = 24

mal miteinander an, die 4 Singles stoßen mit 11 + 10 + 9 + 8 = 38 anderen Leuten an.

14 Im Pascalschen Dreieck findet man in der (n+1)-ten Zeile an (k+1)-ten Stelle die Bi-

nomialzahl kn

. Da diese die Anzahl der k-elementigen Teilmengen einer n-elemen-

tigen Menge angibt, ist die Zeilensumme gleich der Anzahl aller Teilmengen einer n-elementigen Menge. Nach Satz 4.1.4 ist diese Anzahl gleich 2n.

15 Wegen 2

1n = (n+1)n/2 kann man die Dreieckszahlen in der dritten „Spalte“ des

Pascalschen Dreiecks finden.

16 Wie betrachten eine Menge M mit n Elementen und wollen aus dieser eine k-elementige Teilmenge auswählen. Nach Definition der Binomialzahlen gibt es dafür

genau kn

Möglichkeiten. Andererseits kann man eine solche Teilmenge auch da-

durch auswählen, dass man die restlichen n – k Elemente von M auswählt. Dafür gibt

es kn

n Möglichkeiten.

17 Es gibt n

nm Möglichkeiten, den Punkt rechts oben zu erreichen.

18 Nach Satz 4.2.5 gibt es 7

1712 = 31824 Möglichkeiten.

19 Es gilt )!2n(!2

!n < )!3n(!3

!n 3! (n – 3)! < 2! (n – 2)! 3 < n – 2 5 < n.


20 Am Pascalschen Dreieck erkennt man, dass die Binomialzahlen „in der Mitte“ am größten sind, also für gerades n bei k = n / 2 und für ungerades n bei k = (n 1) / 2.

21 Der Term a2bc3d4 hat den Koeffizienten 12600.

22 Ja, es gilt 1,000110000 > 2.

23 kn

= )!kn(!k

!n = ))!1k(1n()!1k(k

)!1n(n = 1k1n

kn .

24 Wir verteilen die Türme der Reihe nach. Erste Spalte: 8 Möglichkeiten, zweite Spalte: nur noch 7 Möglichkeiten, dritte Spalte: noch 6 Möglichkeiten, ... achte Spalte: nur noch eine Möglichkeit. Das ergibt insgesamt 8 7 6 5 4 3 2 1 = 8! = 40320 Möglichkei-ten.

25 Wenn es n Schlitze gibt, von denen jeder 8 mögliche Tiefen haben kann, kann man 8n verschiedene Schlüssel herstellen. Es soll also 8n 1000000 gelten. Durch Logarith-mieren auf beiden Seiten ergibt sich n lg(8) lg(1000000). Auflösen nach n ergibt n lg(1000000) / lg(8) 6,64. Es werden also mindestens 7 Schlitze benötigt.

26 A B C D = A + B + C + D – A B – A C – A D – B C – B D – C D + A B C + A B D + A C D + B C D – A B C D .

27 Wir nummerieren die Briefe und die Umschläge mit 1, 2, 3, ..., 10, wobei der Um-schlag i genau der sein soll, der zu Brief Nr. i gehört. Jedes Eintüten der Briefe ist eine Permutation der Menge {1, 2, 3, ..., 10}. Eine Aktion, bei der kein Brief im rich-tigen Umschlag ist, entspricht einer Permutation ohne Fixpunkte. Nach Satz 4.3.4 ist die Anzahl der Permutationen einer 10-elementigen Menge ohne Fixpunkt gleich

a(10) = 10! !1!10 +

!2!10

!3!10 +

!4!10

!5!10 +

!6!10

!7!10 +

!8!10

!9!10 +

!10!10

= 3628800 – 3628800 + 1814400 – 604800 + 151200 – 30240 + 5040 – 720 + 90 – 10 + 1 = 1334961.

28 Offensichtlich gilt a(1) = 0 und a(2) = 1. O. B. d. A. bestehe die n-elementige Menge aus den Zahlen von 1 bis n. Bei einer fixpunktfreien Permutation darf die 1 nicht auf sich selbst abgebildet werden, für sie gibt es also genau n 1 mögliche Plätze. Wenn die 1 auf Platz Nr. x abgebildet wird (x 1), dann wird das Element x entweder auf Platz Nr. 1 abgebildet oder nicht. Für den ersten Fall gibt es genau a(n 2) Möglichkei-ten, denn alle Elemente außer 1 und x können beliebig fixpunktfrei permutiert werden. Für den zweiten Fall gibt es a(n 1) Möglichkeiten, denn alle Elemente außer 1 können fixpunktfrei permutiert werden. Insgesamt folgt, dass es (n 1) (a(n 2) + a(n 1)) fixpunktfreie Permutationen gibt.

29 Es seien Z, D und F die Mengen aller Vielfachen der Zahlen 2, 3 bzw. 5. Ferner sei


1 = | Z | + | D | + | F| = 51 + 34 + 21 = 106

2 = Z D + Z F + D F = 17 + 11 + 7 = 35

3 = Z D F = 4

Nach Satz 4.3.1 können wir die gesuchte Anzahl wie folgt berechnen:

1 – 2 + 3 = 106 – 35 + 4 = 75

30 n 1 2 3 4 5 6 7 8 9 10 11 12 13 (n) 1 1 2 2 4 2 6 4 6 4 10 4 12

31 Da jede Primzahl p nur durch 1 und sich selbst teilbar ist, ist sie zu den Zahlen 1 bis p 1 teilerfremd. Es gilt daher (p) = p – 1.

32 Nach Aufgabe 33 gilt: (2a) = 2a – 2a–1 = 2a–1 (2 – 1) = 2a–1.

33 Eine Primzahlpotenz pa ist nur zu Vielfachen von p nicht teilerfremd. Es gibt pa 1 Vielfache von p, die kleiner oder gleich pa sind: 1 p, 2 p, ..., pa-1 p. Daher gilt: (pa) = pa – pa–1.

34 Wenn p und q verschiedene Primzahlen sind, gilt (p q) = (p – 1) (q – 1).

Kapitel 5

1 Aus a b und b a folgt b = q1a und a = q2b mit ganzen Zahlen q1 und q2. Einsetzen ergibt die Gleichung folgt b = q1a = q1q2b. Daraus folgt b = 0 oder 1 = q1q2. Da q1 und q2 ganze Zahlen sind, folgt q1 = q2 = 1 oder q1 = q2 = –1, also a = b.

2 Induktionsbasis: Die Aussage gilt für n = 0, denn aus 0 = 6 0 folgt 6 | 0. Induktionsschritt: Für ein n 0 sei n3 – n = 6 k mit einer natürlichen Zahl k. Dann ist

(n + 1)3 – (n + 1) = n3 + 3n2 + 3n + 1 – n – 1 = n3 – n + 3n2 + 3n = 6 k + 3n(n + 1)

ebenfalls durch 6 teilbar, denn das Produkt n(n + 1) aus einer Zahl und ihrem Nach-folger ist durch 2, also 3n(n + 1) durch 6 teilbar.

3 Zu zeigen: Wenn die Aussage für positives b gilt, dann gilt sie auch für negatives b. Wir setzen voraus, dass die Aussage für positives b gilt. Sei b negativ. Dann ist –b positiv, und es gibt q* und r* mit

–b = aq* + r* und 0 r* < a .

Indem wir beide Seiten mit –1 multiplizieren, erhalten wir

b = a ( q*) – r*.


Wenn r* = 0 ist, haben wir bereits eine Darstellung gefunden. Sei also r* > 0. Dann gilt

b = a ( q*) – r* = a( q* 1) + ( a – r*) =: aq + r.

Dabei setzen wir r := a – r* und q := q* 1 falls a > 0 ist. Falls a < 0 gilt, setzen wir q := q* + 1. Wegen 0 < r* < a gilt dann r > 0 und r < a . Damit ist die Behauptung bewiesen.

4 217 mod 23 = 10, 11111 mod 37 = 11, 123456789 mod 218 = 119

5 (a) n+1 mod n = 1, n2 mod n = 0, 2n+5 mod n = 5 mod n, 3n+6 mod n = 6 mod n, 4n–1 mod n = n–1. (b) (n+2) mod (n+1) = 1, (2n+2) mod (n+1) = 0, (n2+1) mod (n+1) = 2, (n2) mod (n+1) = 1. (c) (n+1)2 mod n = 1, (n+1)1000 mod n = 1, (n–1)2 mod n = 1, (n–1)10001 mod n = n – 1. (d) (n+1)n mod n = 0, n3 + 2n2 + 4 mod n = 4 mod 4, (2n+2)(n+1) mod n = 2 mod n, n! mod n = 0.

6 (a) Drei Beispiele mit unterschiedlichen Seitenlängen:

(b) Bei b = a genügt ein Zug, bei b = 2a benötigt man zwei Züge und für b = 2a+1 werden 3a Züge gebraucht.

7 Die gesuchte Zahl ist 43.

8 (a) Wegen a2 b2 = (a b)(a + b) suchen wir Zahlen a und b, für die das Produkt (a b)(a + b) = 11 ist. Da 11 eine Primzahl ist, muss einer der Faktoren gleich 1 und der andere gleich 11 sein. Die Lösung dieses Gleichungssystems ist a = 6 und b = 5. Die gesuchten Quadratzahlen sind also 36 und 25. (b) Wir suchen Lösungen der Gleichung a2 b2 = (a b)(a + b) = 1001. Für die Fakto-ren a b und a + b gibt es mehrere Möglichkeiten, denn 1001 ist gleich

1 1001 = 7 143 = 11 91 = 13 77.

Die ersten beiden Faktoren a b = 1 und a + b = 1001 führen zur Lösung (a, b) = (501, 500). Die weiteren Faktoren ergeben die Lösungen (75, 68), (51, 40), (45, 32).

9 ggT(123456789, 987654321) = 9.


10 Die aufeinander folgenden ungeraden Zahlen seien 2n+3 und 2n+1. Der euklidische Algorithmus liefert dann: 2n+3 = (2n+1) 1 + 2, 2n+1 = 2 n + 1, 2 = 1 2 + 0. Also gilt ggt(2n+3, 2n+1) = 1.

11 Induktionsbasis: Die Aussage gilt für n = 1, denn ggT(f1, f3) = ggT(1, 2) = 1. Induktionsschritt: Für ein n 1 gelte ggT(fn, fn+2) = 1. Wir führen die ersten Schritte des euklidischen Algorithmus durch:

fn+3 = fn+1 1 + fn+2, fn+1 = fn+2 0 + fn+1, fn+2 = fn+1 1 + fn.

Nach Satz 5.3.1 folgt ggT(fn+3, fn+1) = ggT(fn+1, fn+2) = ggT(fn+1, fn) = 1.

12 (a) Aus der Simpson-Identität (Satz 3.4.3) folgt fn2 = fn+1 fn 1 ( 1)n. Modulo fn+1 er-

gibt sich fn2 mod fn+1 = 0 ( 1)n = ( 1)n+1.

(b) Aus fn fn mod fn+1= 1 ergibt sich, dass entweder fn oder fn die Inverse von fn ist.

13 Der erweiterte euklidische Algorithmus liefert

1 = 1234·( 17) + 567·37.

14 (10101010)2 = 170, (2002)11 = 2664, (ABCD)16 = 43981.

15 2007 = (11111010111)2 = (31012)5 = (1565)11 = (7D7)16.

16 Damit die Quersumme durch 9 teilbar ist, muss das Fragezeichen durch eine 3 ersetzt werden.

17 Die Zahl 19a9b muss durch 4 und durch 9 teilbar sein. Daher müssen sowohl die letz-ten beiden Ziffern durch 4 (also b = 2 oder b = 6) als auch die Quersumme durch 9 teilbar sein. Für b = 2 ergibt sich die Quersumme 21 + a, also a = 6. Für b = 6 ergibt sich die Quersumme 25 + a, also a = 2. Also sind 19296 und 19692 durch 36 teilbar.

18 Die Zahlen müssen durch 9 und durch 11 teilbar sein. Sie sind durch 11 teilbar, wenn die alternierende Quersumme durch 11 teilbar ist. Dies ist für Zahlen der Form „aabb“ immer erfüllt, denn a – a + b – b = 0. Die Zahlen sind durch 9 teilbar, wenn ihre Quer-summe 2a + 2b durch 9 teilbar ist. Da a die Werte von 1 bis 9 und b die Werte von 0 bis 9 annehmen kann, kommen als Quersummen nur die Zahlen 18 und 36 in Frage. Für die Quersumme 36 ergibt sich a = b = 9, also 9999 als gesuchte Zahl. Für die Quersumme 18 gibt es mehrere Möglichkeiten: 1188, 2277, 3366, 4455, 5544, 6633, 7722, 8811, 9900.

19 Es sei z = an 12n + an–1 12n–1 + ... + a1 121 + a0 120 eine natürliche Zahl, die im Zwölfersystem die Darstellung (anan–1...a1a0) hat. Bei Division von z durch 12 ergibt sich der Rest a0. Daraus ergeben sich folgenden Regeln für i {12, 6, 4, 3, 2}: z ist genau dann durch i teilbar, wenn die Endstelle durch i teilbar ist.

20 Da 102 durch 4, 103 durch 8, 104 durch 16, ... teilbar ist, erkennt man an folgenden Darstellungen, dass n genau dann durch 4 (8, 16, ...) teilbar ist, wenn die aus den letz-ten 2 (3, 4, ...) Ziffern gebildete Zahl durch 4 (8, 16, ...) teilbar ist:


n = ak–1 10k–1 + ak–2 10k–2 + ... + a1 101 + a0 100

= 102 (ak–1 10k–3 + ak–2 10k–4 + ... + a2 100) + a1 101 + a0 100

= 103 (ak–1 10k–4 + ak–2 10k–5 + ... + a3 100) + a2 102 + a1 101 + a0 100

= 104 (ak–1 10k–5 + ak–2 10k–6 + ... + a4 100) + a3 103 + a2 102 + a1 101 + a0 100

21 (a) Da b durch t teilbar ist, ist auch die Zahl

n a0 = ak–1 bk–1 + ak–2 bk–2 + ... + a1 b1

durch t teilbar. Folglich gilt n a0 0 (mod t), also n a0 (mod t). (b) Da t ein Teiler von b–1 ist, teilt t auch b2–1 = (b–1)(b+1), b3–1 = (b–1)(b2+b+1), ..., bk–1–1 = (b–1)(bk–2 + ... + b + 1), also auch

ak–1 (bk–1–1) + a k–2 (bk–2–1) + ... + a1 (b1–1) = ak–1 bk–1 + ak–2 bk–2 + ... + a1 b1 + a0 b0 (ak–1 + ak–2 + ... + a1 + a0)

= n – Q(n).

22 Es gilt:

(b + 1)(b2s b2s 1 + b2s 2 b2s 3 ... + b2 b + 1) = b2s+1 b2s + b2s 1 b2s 2 ... + b3 b2 + b

+ b2s b2s 1 + b2s 2 ... b3 + b2 b + 1 = b2s+1 + 1.

23 (a) Die Quersumme einer solchen Zahl ist 0 + 1 + 2 + 3 + 4 + 5 + 6 + 7 + 8 + 9 = 45, also durch 9 teilbar. Nach Korollar 5.5.6 ist dann auch die Zahl selbst durch 9 teilbar. (b) Wenn die Zahl im Dezimalsystem die Darstellung „ababab“ hat, so kann man sie schreiben als

100000a + 10000b + 1000a + 100b + 10a + b = 101010a + 10101b = 10101 (10a + b ).

Da 10101 (= 7 1443) durch 7 teilbar ist, ist es die Zahl „ababab“ ebenfalls. (c) Hat die ursprüngliche Zahl die Form ak 1...a1a0, so ergibt sich nach dem Anhängen des Spiegelbildes die Zahl ak 1...a1a0a0a1...ak 1. Die alternierende Quersumme dieser Zahl ist gleich 0, denn jede Ziffer geht einmal mit positivem und einmal mit negati-vem Vorzeichen ein. Nach Korollar 5.5.9 ist die Zahl dann durch 11 teilbar.

24 Wenn n keine Primzahl ist, dann kann man n nach Satz 5.6.5 eindeutig als Produkt von Primzahlpotenzen schreiben:

n = 1e1p 2e

2p ... sesp .


Wir wählen zwei weitere Primzahlen p* und q*, die unter den Primzahlen p1, p2, ..., pS nicht vorkommen. Dann sind die Zahlen a = p* 2e

2p ... sesp und b = q* 1e

1p nicht durch n teilbar, wohl aber das Produkt ab = p* q* n.

25 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 197, 199.

26 Für x = 40 ergibt sich 402 + 40 + 41 = 40 (40+1) + 41 = 41 41, also keine Primzahl. Für x = 41 ergibt sich 412 + 41 + 41 = 41 (41+1) + 41 = 43 41, ebenfalls keine Prim-zahl.

27 Angenommen, es gibt nur endlich viele Primzahlen p1, p2, ..., pS. Wir betrachten die Zahl

n = p1 p2 ... pS – 1.

Nach Hilfssatz 5.6.1 gibt es eine Primzahl pi (i {1, 2, ..., s}) mit pi n. Außerdem ist n+1 das Produkt aller Primzahlen und wird daher ebenfalls von pi geteilt. Nach Hilfssatz 5.1.1 folgt aus pi n und pi n+1, dass gilt pi (n+1) – n, also pi 1. Dies ist ein Widerspruch, da pi größer als 1 ist.

28 Seien [a] und [b] zwei verschiedene Restklassen modulo n. Wir müssen zeigen, dass [a] und [b] disjunkt sind. Sei x ein Element aus [b], das heißt x b (mod n). Ange-nommen, x wäre auch ein Element von [a], das heißt x a (mod n). Dann wäre a b (mod n). Das bedeutet, a b wäre durch n teilbar. Nach Satz 5.7.1 wären dann die beiden Restklassen [a] und [b] gleich, ein Widerspruch. (b) Es ist klar, dass jede ganze Zahl z in der Restklasse [z] enthalten ist. Angenom-men, z wäre in einer weiteren Restklasse [a] [z] enthalten. Dann gilt z a (mod n), woraus z a 0 (mod n) bzw. n | z a folgt. Dann gilt nach Satz 5.7.1 aber [a] = [z], ein Widerspruch.

29 Die Multiplikationstafeln von Z7 und Z12 sehen wie folgt aus.

[0] [1] [2] [3] [4] [5] [6] [0] [0] [0] [0] [0] [0] [0] [0] [1] [0] [1] [2] [3] [4] [5] [6] [2] [0] [2] [4] [6] [1] [3] [5] [3] [0] [3] [6] [2] [5] [1] [4] [4] [0] [4] [1] [5] [2] [6] [3] [5] [0] [5] [3] [1] [6] [4] [2] [6] [0] [6] [5] [4] [3] [2] [1]


[0] [1] [2] [3] [4] [5] [6] [7] [8] [9] [10] [11]

[0] [0] [0] [0] [0] [0] [0] [0] [0] [0] [0] [0] [0] [1] [0] [1] [2] [3] [4] [5] [6] [7] [8] [9] [10] [11] [2] [0] [2] [4] [6] [8] [10] [0] [2] [4] [6] [8] [10] [3] [0] [3] [6] [9] [0] [3] [6] [9] [0] [3] [6] [9] [4] [0] [4] [8] [0] [4] [8] [0] [4] [8] [0] [4] [8] [5] [0] [5] [10] [3] [8] [1] [6] [11] [4] [9] [2] [7] [6] [0] [6] [0] [6] [0] [6] [0] [6] [0] [6] [0] [6] [7] [0] [7] [2] [9] [4] [11] [6] [1] [8] [3] [10] [5] [8] [0] [8] [4] [0] [8] [4] [0] [8] [4] [0] [8] [4] [9] [0] [9] [6] [3] [0] [9] [6] [3] [0] [9] [6] [3] [10] [0] [10] [8] [6] [4] [2] [0] [10] [8] [6] [4] [2] [11] [0] [11] [10] [9] [8] [7] [6] [5] [4] [3] [2] [1]

(a) In Z7 sind alle Elemente außer der 0 invertierbar, es gilt: [1] 1 = [1], [2] 1 = [4], [3] 1 = [5], [6] 1 = [6] und umgekehrt. (b) In Z12 sind nur die Elemente [1], [5], [7] und [11] invertierbar, und zwar sind sie zu sich selbst invers.

30 In Z101 gilt [2] 1 = 51, [3] 1 = 34 und [50] 1 = 99.

31 Dass Zn* abgeschlossen bezüglich der Multiplikation ist, wurde in Satz 5.7.8 gezeigt. Das neutrale Element ist 1 Zn*. Nach Definition von Zn* hat jedes Element ein mul-tiplikatives Inverses. Da nach Satz 5.7.6 in Zn das Assoziativgesetz der Multiplikation gilt, gilt es erst recht in Zn*.

Kapitel 6

1 Sei (a1, a2, ..., an–1, an) ein Codewort. Dann ist k = a1 + a2 + ... + an eine gerade Zahl. Angenommen auch (a1, ..., ai’, ..., an) mit ai’ ai wäre ein Codewort. Dann wäre auch k’ = a1 + ... + ai’ + ... + an eine gerade Zahl. Dann wäre auch die Differenz k’ – k = ai’ – ai eine gerade Zahl. Da ai’ und ai aus der Menge {0, 1} sind, folgt ai’ – ai = 0, also ai’ = ai. Dies widerspricht der Annahme.

2 (a) C = {a1a2a3a4a5a6a7a8a9 | 10 teilt a1 + 3a2 + a3 + 3a4 + ... + 3a8 + a9}, C ist also ein Paritätscode der Länge 9 zur Basis 10 mit dem Gewichten 1 und 3. (b) Nach Korollar 6.2.4 erkennt dieser Code alle Einzelfehler, da alle Gewichte teiler-fremd zu 10 sind. Allerdings erkennt er Vertauschungsfehler nicht, wenn sich die ver-tauschten Ziffern um 5 unterscheiden. Zum Beispiel sind sowohl 169 828 013 als auch 619 828 013 Codewörter.


3 Der Code erkennt nicht alle Einzelfehler, da zum Beispiel die Ziffern 1 und 4 bei ihrer Gewichtung mit 3 zur gleichen Quersumme führen. So sind etwa sowohl 189 828 017 als auch 189 828 047 Codewörter. Er erkennt auch nicht alle Vertauschungsfehler: Zum Beispiel sind sowohl 189 828 091 als auch 189 828 901 erlaubte Codewörter. In-sofern ist der Code aus Aufgabe 2 besser.

4 Nach Korollar 6.2.4 muss g teilerfremd zur Basis des Codes sein. Bei der Basis 12 kommen daher nur die Gewichte 1, 5, 7 oder 11 in Frage.

5 Bei einer EAN a1a2a3a4a5a6a7a8 mit 8 Stellen wird das Prüfsymbol a8 so bestimmt, dass 3·a1 + 1·a2 + 3·a3 + 1·a4 + 3·a5 + 1·a6 + 3·a7 + 1·a8 durch 10 teilbar ist. Bei einer EAN a1a2a3a4a5a6a7a8a9a10a11a12a13 mit 13 Stellen wird das Prüfsymbol a13 so bestimmt, dass 1·a1 + 3·a2 + 1·a3 + 3·a4 + ... + 3·a12 + 1·a13 durch 10 teilbar ist. Es sei a1a2a3... eine gül-tige EAN und a1...ai–1ai’ai+1... die EAN mit einem Einzelfehler an der Stelle i, also ai’ ai. Dann gibt es zwei Fälle: (1.) Die Ziffer ai bzw. ai’ wird mit dem Faktor 1 gewichtet. Dann ist die Differenz der beiden gewichteten EAN gerade ai – ai’. Da ai und ai’ Ziffern von 0 bis 9 sein können, kann die Differenz ai – ai’ Werte von –9 bis 9 annehmen. Der einzige Wert in diesem Bereich, der modulo 10 keinen Rest, also keinen Unterschied in der Prüfziffer ergeben würde, ist die Differenz 0. Die tritt aber nur dann auf, wenn ai = ai’ gilt. Somit wird ein Einzelfehler erkannt. (2.) Die Ziffer ai bzw. ai’ wird mit dem Faktor 3 gewichtet. Dann ist die Differenz der beiden gewichteten EAN gerade 3ai – 3ai’ = 3(ai – ai’). Da ai und ai’ Ziffern von 0 bis 9 sein können, kann die Differenz 3(ai – ai’) Werte von –27 bis 27 annehmen. Modulo 10 würden die Differenzen –20, –10, 0, 10 und 20 keinen Rest ergeben. Der einzige Wert, der in diesem Bereich aber angenommen werden kann, ist die Differenz 0, da als Differenzen nur Vielfache von 3 in Frage kommen. Die Differenz 0 tritt aber nur dann auf, wenn ai = ai’ gilt. Somit wird ein Einzelfehler erkannt.

6 (a) 9 783406 418716 ist eine korrekte EAN, denn als gewichtete Quersumme ergibt sich 110, also eine Zehnerzahl. (b) 4000 6542 ist keine korrekte EAN, denn als gewichtete Quersumme ergibt sich 49, also keine Zehnerzahl. Die korrekte EAN wäre 4000 6543.

7 Es sei a1a2a3... eine gültige EAN. Vertauscht man zwei Ziffern ai und ak (mit i k), so muss man zwei Fälle unterscheiden: (1.) Die Ziffern ai und ak werden mit dem gleichen Gewicht (also entweder beide mit 1 oder beide mit 3) gewichtet. Dann erhält man keinen Unterschied in der gewichteten Summe, also keinen Unterschied in der Prüfziffer. Der Vertauschungsfehler wird also nicht erkannt. Beispiel: 12345670 hat die gewichtete Summe 60, aber auch 32145670 und 14325670 haben die gewichtete Summe 60. (2.) Die Ziffern ai und ak werden mit unterschiedlichen Gewichten versehen (zum Bei-spiel ai mit 1 und ak mit 3). Dann erhält man als Differenz der gewichteten Summen 3ai + ak – ai – 3ak = 2ai – 2ak = 2(ai – ak). Da ai und ak Ziffern von 0 bis 9 sein können,


gibt es für diese Differenz mögliche Werte von –18 bis 18. Dabei sind –10, 0 und 10 Differenzen, die modulo 10 keinen Unterschied ergeben, also nicht entdeckt werden. Die Differenz 0 ist dabei harmlos, da dann ai und ak gleich sind. Die Differenzen ±10 bedeuten aber, dass sich die Ziffern ai und ak um 5 unterscheiden, eine Vertauschung der beiden Ziffern aber nicht erkannt wird. Der EAN-Code erkennt also Vertauschungsfehler höchstens von Ziffern mit unter-schiedlichen Gewichten und auch nur dann, wenn sich die beiden vertauschten Ziffern nicht um 5 unterscheiden. Beispiel: 12345670 hat die gewichtete Summe 60, aber 62345170 hat die gewichtete Summe 70, ist also ebenfalls eine Zehnerzahl.

8 (a) 3 – 282 – 87144 – X ist keine korrekte ISBN, denn die gewichtete Quersumme ist 243, also keine Elferzahl. Das korrekte Prüfsymbol ist 9. (b) 3 – 528 – 06783 – 7 ist eine korrekte ISBN, denn als gewichtete Quersumme ergibt sich die Elferzahl 110 = 10 11.

9 Der ISBN-Code ist ein Paritätscode der Länge 10 zur Basis 11 mit den Gewichten 10, 9, 8, ..., 1. Da alle Gewichte teilerfremd zu 11 sind, folgt nach Korollar 6.2.4, dass der ISBN-Code alle Einzelfehler erkennt.

10 Sei a1a2a3.... a9a10 eine ISBN. Dann ist

10 a1 + 9 a2 + 8 a3 + 7 a4 + 6 a5 + 5 a6 + 4 a7 + 3 a8 + 2 a9 + 1 a10

eine durch 11 teilbare Zahl. Durch Vertauschen der 2. und der 5. Stelle entsteht die Folge a1a5a3a4a2a6...a10. Wir können a2 a5 voraussetzen, denn sonst wäre die Ver-tauschung belanglos. Angenommen, auch dies wäre ein Codewort. Dann müsste auch

10 a1 + 9 a5 + 8 a3 + 7 a4 + 6 a2 + 5 a6 + 4 a7 + 3 a8 + 2 a9 + 1 a10

eine durch 11 teilbare Zahl sein. Zusammen folgt mit 5.1.1, dass 11 auch die Diffe-renz 9 a2 + 6 a5 – (9 a5 + 6 a2) = 3(a2 – a5) teilen muss. Da 3 teilerfremd zu 11 ist, folgt, dass 11 ein Teiler von a2 – a5 sein muss. Da a2 und a5 beide zwischen 0 und 9 liegen, ist die Differenz a2 – a5 eine Zahl zwischen –9 und +9. Die einzige durch 11 teilbare Zahl in diesem Bereich ist aber 0. Daher muss a1 = a2 sein. Dieser Wi-derspruch zeigt, dass der ISBN-Code Vertauschungen der 2. und 5. Stelle 100%ig er-kennt.

11 Ersetzt man eine Ziffer durch eine andere mit Abstand 7, so wird der Fehler nicht er-kannt. Zum Beispiel wäre 1 2 3 4 5 6 7 8 9 0 (mit der gewichteten Quersumme 210) korrekt, aber 8 2 3 4 5 6 7 8 9 0 (mit der gewichteten Quersumme 280) ebenfalls.

12 Sei (g1, g2, ..., gn) ein Codewort eines Gruppencodes mit Kontrollsymbol c und Per-mutationen 1, 2, ...., n. Das heißt, dass 1(g1) 2(g2) ... n(gn) = c ist. Bei der Ü-bertragung möge ein Fehler an der i-ten Stelle passiert sein, es wird also der Vektor (g1, ..., hi, ..., gn) mit hi gi empfangen. Wenn dieser Vektor auch ein Codewort wä-re, dann müsste 1(g1) ... i(hi) ... n(gn) = c = 1(g1) ... i(gi) ... n(gn) gelten. Indem man von rechts der Reihe nach mit n(gn)–1, n–1(gn–2)–1, ..., i+1(gi+1)–1 und


von links mit 1(g1)–1, 2(g2)–1, ... i–1(gi–1)–1 multipliziert, erhält man schließlich i(hi) = i(gi). Da Permutationen injektiv sind, folgt hi = gi, ein Widerspruch.

13 Aus i(x) = i(x’) folgt gix = gix’. Da gi Zq*, also invertierbar ist, führt die Multi-plikation mit gi

–1 auf x = x’. Also ist die Abbildung i injektiv und daher als Abbil-dung einer endlichen Menge in sich auch bijektiv. Also ist die Abbildung i: Zq Zq mit x x gi eine Permutation von Zq. Die Multiplikation mit Gewichten kann man also auch als Permutation auffassen. Jeder Paritätscode mit Gewichten gi Zq* ist da-her auch ein Code mit Permutationen über der Gruppe (Zq, +).

14 Wenn in jeder Zeile und Spalte der Verknüpfungstafel jedes Element genau einmal vorkommt, so sind für alle Elemente g und h die Gleichungen g x = h und x g = h ein-deutig lösbar. Sei g ein Element der Menge und sei e die Lösung von x g = g, das heißt, es gelte e g = g. Wir zeigen nun, dass e das neutrale Element ist, das heißt, dass dann für jedes Element a gilt e a = a. Sei also a ein beliebiges Element und sei x die Lösung von g x = a. Dann folgt mit Hilfe der Assoziativität

e a = e (g x) = (e g) x = g x = a.

Aus der Lösbarkeit von x a = e folgt außerdem, dass es für jedes Element a ein inver-ses Element gibt. Damit sind alle Gruppenaxiome erfüllt.

15 3 = 72534061989876543210

, 4 = 07862135499876543210

,

5 = 10937568249876543210

, 6 = 51460839729876543210

,

7 = 85231964079876543210

, 8 = 98765432109876543210

,

9 = 1, 10 = 2, 11 = 3.

16 Individuelle Lösung.

17 Wir übersetzen die Buchstaben zunächst in Ziffern und erhalten 2 5 3 0 7 6 6 0 3 5. Wenden wir die Permutationen i auf die jeweils i-te Stelle an,

1(2) = 7, 2(5) = 9, 3(3) = 6, ..., 10(5) = 9,

so ergibt sich 7 9 6 9 9 6 3 0 6 9. Mit Hilfe der Verknüpfungstabelle der Diedergruppe können wir das Produkt dieser Zahlen berechnen. Es ergibt sich

7 * 9 * 6 * 9 * 9 * 6 * 3 * 0 * 6 * 9 = 3.

Wiederum aus der Verknüpfungstabelle entnehmen wir, dass 2 das zu 3 inverse Ele-ment ist. Daher ist die Prüfziffer gleich 2 und die gesamte Banknotennummer lautet G N 3 0 7 6 6 0 3 N 2.

18 Die zwei Ziffernpaare (g10, g11), deren Vertauschung nicht bemerkt würde, sind (1, 8) und (4, 7), denn es gilt


2(1) 8 = 8 8 = 0 = 4 1 = 2(8) 1,

2(4) 7 = 7 7 = 0 = 1 4 = 2(7) 4.

Kapitel 7

1 Individuelle Lösung.

2 VENI VEDI VICI („Ich kam, ich sah, ich siegte.“)

3 DIESER TEXT IST NICHT MEHR GEHEIM.

4 I AM A MAN.

5 Als Hilfe sind hier die häufigsten Buchstaben des Geheimtextes: q, a, l, c, d, x.

6 Machen Sie das!

7 Der Text hat 60 Zeichen und endet mit einem Ausrufezeichen, was darauf hin deutet, dass wir nur Teiler von 60 als Abstand der Klartextbuchstaben voneinander betrachten müssen. Entsprechend schreiben wir den Text von oben nach unten in Spalten, wobei die Zeilen- und die Spaltenzahl Teiler von 60 sind. Bei fünf Spalten erhalten wir den folgenden Klartext: Ich wusste, dass diese Transpositionschiffre leicht zu knacken ist!

8 Lösung: IST DAS EIN GUTER ALGORITHMUS?

9 MFBTVCJVCDKMG.

10 Mit dem Schlüsselwort BUERO ergibt sich der folgende Klartext: Den hoechsten Organisationsstand erfuhr die Kryptologie in Venedig, wo sie in Form einer staatlichen Buerotaetigkeit ausgeuebt wurde. Es gab Schluessel-Sekretaere, die ihr Buero im Dogenpalast hatten und fuer ihre Taetigkeit rund zehn Dukaten im Monat bekamen. Es wurde dafuer gesorgt, dass sie waehrend ihrer Arbeit nicht gestoert wur-den. Sie durften ihre Bueros aber auch nicht verlassen, bevor sie eine gestellte Aufga-be geloest hatten.

11 „Worum geht es bei der jüngsten Aufregung um Echelon und die Spionage der Verei-nigten Staaten gegen europäische Wirtschaftsunternehmen? Fangen wir mit ein paar offenen Worten von amerikanischer Seite an. Ja, meine kontinentaleuropäischen Freunde, wir haben euch ausspioniert. Und es stimmt, wir benutzen Computer, um Da-ten nach Schlüsselwörtern zu durchsuchen. Aber habt ihr euch auch nur für einen Au-genblick gefragt, wonach wir suchen? Der jüngste Bericht des Europäischen Parla-ments über Echelon, verfasst von dem britischen Journalisten Duncan Campbell, hat zornige Beschuldigungen der Kontinentaleuropäer ausgelöst. Der US-Geheimdienst, heißt es, stehle Spitzentechnologie europäischer Unternehmen, um sie - man höre und staune - zur Verbesserung der eigenen Konkurrenzfähigkeit an amerikanische Unter-nehmen weiterzugeben. Liebe europäische Freunde, kommt bitte auf den Boden der


Tatsachen zurück. Es stimmt zwar, dass die Europäer den Amerikanern auf einer Hand voll Gebiete technologisch überlegen sind. Aber, um es so behutsam wie möglich zu formulieren: Die Anzahl dieser Gebiete ist sehr, sehr gering. Die meiste europäische Technologie lohnt den Diebstahl einfach nicht. Richtig, meine kontinentalen Freunde, wir haben euch ausspioniert, weil ihr mit Bestechung arbeitet. Die Produkte eurer Un-ternehmen sind oftmals teurer oder technologisch weniger ausgereift als die eurer a-merikanischen Konkurrenten, manchmal sogar beides. Deshalb bestecht ihr so oft. Die Komplizenschaft eurer Regierungen geht sogar so weit, dass Bestechungsgelder in mehreren europäischen Staaten noch immer steuerlich absetzbar sind.“

12 (a) HFGSCFEBYFFTTXNQHFG. (b) QXVHCAMDMZSJECBYDPM. (c) Individuelle Lösung.

13 Addition modulo 2 liefert den Schlüssel 111111.

14 Für jede der n Zellen gibt es zwei Möglichkeiten: Entweder sie trägt zur Summe bei oder nicht. Dementsprechend gibt es bei n Zellen 2n Möglichkeiten, ein lineares Schie-beregister zusammenzustellen.

15 Die gesuchten linearen Schieberegister mit maximalen Perioden sind die folgenden:

16 Nein, denn die Folge beginnt mit vier Nullen. Ein Schieberegister der Länge 4 muss diesen Nullzustand jedoch immer beibehalten, sobald er einmal aufgetreten ist.

17 Damit die Folge mit 00001 beginnen kann, muss 1, 0, 0, 0, 0 der Anfangszustand ge-wesen sein. Die Rückkopplungskoeffizienten ci bestimmen wir wie folgt. Für den In-halt der linken Zelle, der nacheinander 0, 0, 0, 1, 1 sein muss, gilt

nach einem Takt: 0 = c5 1 + c4 0 + c3 0 + c2 0 + c1 0, nach zwei Takten: 0 = c5 0 + c4 1 + c3 0 + c2 0 + c1 0, nach drei Takten: 0 = c5 0 + c4 0 + c3 1 + c2 0 + c1 0, nach vier Takten: 1 = c5 0 + c4 0 + c3 0 + c2 1 + c1 0, nach fünf Takten: 1 = c5 1 + c4 0 + c3 0 + c2 0 + c1 1.

Dieses lineare Gleichungssystem hat die Lösung c1 = 1, c2 = 1, c3 = 0, c4 = 0, c5 =0, in die Summe gehen also nur die ersten beiden Zellen ein.

1 1 1

0 00 0

1

0 00 01 0


18 Aus p = 23 und q = 37 können wir n = pq = 851 und (n) = (p 1)(q 1) = 792 be-rechnen. Als zu teilerfremde Zahl wählen wir zum Beispiel e = 17. Damit können wir die Nachricht m = 537 zu c = me mod n = 53717 mod 851 = 220 verschlüsseln. Der erweiterte euklidische Algorithmus ergibt als Lösung von ed mod = 1 den privaten Schlüssel d = 233. Damit können wir c = 220 wieder entschlüsseln: cd mod n = 220233 mod 851 = 537 = m.

19 (a) Es ergibt sich n = pq = 33. Wir verschlüsseln jeden codierten Buchstaben mi = 13, 1, 20, 8, 5, 13, 1, 20, 9, 11 einzeln zu ci = mi

e mod n = 19, 1, 14, 17, 26, 19, 1, 14, 3, 11. Dies entspricht der Buchstabenfolge „SANQZSANCK“. (b) Mit = (p 1)(q 1) = 20 liefert der erweiterte euklidische Algorithmus den ge-heimen Schlüssel d = 7. Damit entschlüsseln wir die einzelnen Buchstabencodes ci = 13, 21, 14 separat zu ci

d mod n = 7, 21, 20. Dies entspricht dem Wort „GUT“.

20 Sei i eine natürliche Zahl mit 1 i p 1. Da p eine Primzahl ist, ist p teilerfremd zu allen Zahlen, die kleiner sind als p. Insbesondere ist p teilerfremd zu allen Zahlen 1, 2, ..., i, also auch zu i! und zu (p i)!. Da die Binomialzahl

)!ip(!i)!1p(p

)!ip(!i!p

ip

eine natürliche Zahl ist, teilt der Nenner i! (p i)! den Zähler p (p 1)!. Da der Nen-ner teilerfremd zu p ist, muss er (p 1)! teilen. Also gilt (p 1)! = k i! (p i)! mit ei-ner natürlichen Zahl k. Daraus folgt

ip

= k p.

21 (a) Da m16 = (((m2)2)2)2 gilt, benötigt man 4 Multiplikationen. (b) Wegen m21 = m16 m4 m benötigt man nach (a) 4 + 2 = 6 Multiplikationen. (c) Die Idee ist, m wiederholt zu quadrieren und dann geeignete Terme zu multiplizie-ren. Diesen Square-and-Multiply-Algorithmus zur Berechnung von md mit höchstens 2 [ld(d)] Multiplikationen kann man wie folgt formulieren: (1.) Setze z := 1 und c := x (dabei speichert z die Zwischenergebnisse und c enthält die Potenzen von x). (2.) Wenn d durch 2 teilbar ist, dann quadriere c, teile d ganzzahlig durch 2 (d := d div 2) und beginne wieder mit (2.). (3.) Wenn d nicht durch 2 teilbar ist, dann quadriere c, teile d ganzzahlig durch 2 (d := n div 2), multipliziere z mit c (z := z c) und gehe zu (2.).

0 00 0

c2 c1

1


(4.) Führe dieses Verfahren solange durch, bis d = 0 ist. Das Endergebnis steht dann in der Variablen c.

22 Aus den beiden Gleichungen n = p q = 14803 und (n) = (p – 1) (q – 1) = 14560 folgt durch Eliminieren von q die Gleichung (p – 1) (14803/p – 1) = 14560. Ausmul-tiplizieren ergibt 14803 – p – 14803/p + 1 = 14560. Zusammenfassen und Multiplika-tion mit p liefert die quadratische Gleichung 0 = p2 – 244p + 14803. Diese hat die Lö-sungen p1 = 131 und p2 = 113. Dementsprechend sind q1 = 113 und q2 = 131.

Kapitel 8

1 Alle Graphen mit genau vier Ecken sind die folgenden (von Permutationen der Ecken abgesehen):

2 Km,n hat m + n Ecken und m n Kanten.

3 Nur dann, wenn der Kreis gerade Länge hat, kann man seine Ecken abwechselnd mit zwei Farben färben, so dass es am Ende aufgeht. Bei ungerader Länge müsste die letz-te Ecke die gleiche Farbe wie die erste Ecke bekommen; dadurch hätten zwei benach-barte Ecken die gleiche Farbe.

4 Ein Graph ist genau dann bipartit, wenn er nur Kreise gerader Länge hat. Wir betrach-ten einen bipartiten Graphen mit der Partition {E1, E2}. In jedem Kreis müssen sich dann Ecken aus E1 und E2 abwechseln. Dann muss die Anzahl der Ecken im Kreis ge-rade sein. Seien umgekehrt alle Kreise gerade. Sei e0 eine beliebige Ecke. Sei E1 die Men-ge aller Ecken, die einen ungeraden kürzesten Abstand zu e0 haben, und sei E2 die Menge aller Ecken, die einen geraden kürzesten Abstand zu e0 haben. Dann ist {E1, E2} eine Bipartition. Denn: Angenommen, es gibt eine Kante von E1 nach E1 (oder von E2 nach E2. Diese würde einen ungeraden Kreis schließen.

5 Wir betrachten eine beliebige Ecke e0 mit einer ihrer anschließenden Kanten k0. Sei e1 die andere Ecke von k0. Da e1 mindestens den Grad 2 hat, gibt es eine weitere Kante k1 durch e1. Usw. Da der Graph nur endlich viele Ecken besitzt, kommen wir irgendwann an einer Ecke ej an, an der wir schon waren, das heißt ej = ei mit i < j. Dann ist die be-suchte Kantenfolge von ei bis ej ein Kreis.

6 In Kapitel 1.2 haben wir bewiesen: In jeder Gruppe von mindestens zwei Personen gibt es zwei, die die gleiche Anzahl von Bekannten innerhalb dieser Gruppe haben. Wir übertragen diesen Satz auf einfache Graphen, indem wir Ecken mit Personen und Kanten mit der Bekanntsheitsrelation identifizieren. Die Anzahl der Bekannten einer Person entspricht dann dem Grad der zugehörigen Ecke. Wir erhalten den Satz: In je-


dem einfachen Graphen (mit mindestens zwei Ecken) gibt es zwei Ecken, die den glei-chen Grad haben.

7 Die Graphen mit 2 setzen sich aus Kreisen und Pfaden (Wege mit paarweise ver-schiedenen Ecken) zusammen.

8 (a) Bei diesem Verfahren werden bei jedem Durchgang durch eine Ecke zwei Kanten verbraucht, außer beim Start in der Anfangsecke. Würde das Verfahren in einer Ecke geraden Grades enden, die nicht die Anfangsecke ist, so wären an dieser schon gerad-zahlig viele Kanten verbraucht worden und es wäre noch mindestens eine Kante übrig, um aus der Ecke wieder herauszulaufen. Dies wäre ein Widerspruch zum Ende des Verfahrens. (b) Beim Start in einer Ecke ungeraden Grades wird eine Kante verbraucht und es bleiben noch geradzahlig viele Kanten übrig. Bei jedem Durchgang durch die An-fangsecke werden zwei Kanten verbraucht. Wenn überhaupt, bleiben also immer ge-radzahlig viele Kanten übrig, so dass man stets aus der Anfangsecke wieder heraus-kommt.

9 (b) Ja, denn jede Ecke hat einen geraden Grad. (c) Zum Beispiel: links oben anfangen, dann waagerecht nach rechts gehen und im Zick-Zack-Muster zurück gehen usw.

10 Der Graph Km,n ist genau dann eulersch, wenn n und m gerade sind.

11 Allgemein kann man Kn (mit ungeradem n) nach folgender Regel in einem Zug zeich-nen: „Gehe zunächst einmal außen herum und danach im Uhrzeigersinn immer zur nächsten Ecke, zu der noch keine Kante führt.“ Wenn die Ecken von K7 im Uhrzeiger-sinn nummeriert sind, liefert dieses Verfahren folgenden eulerschen Weg: 1, 2, 3, 4, 5, 6, 7, 1, 3, 5, 7, 2, 4, 6, 1, 4, 7, 3, 6, 2, 5, 1.

12 (a) Der zugehörige planare Graph sieht wie folgt aus.

(b) Der Graph ist nicht eulersch, da nicht alle Ecken einen geraden Grad haben: Die Ecke e1 hat Grad 1 und die Ecke e3 hat Grad 5. (c) Da es genau zwei Ecken mit ungeradem Grad gibt, besitzt der Graph eine offene eulersche Linie: e1 – e2 – e3 – e1 – e4 – e3 – e2 – e4 – e3.

13 Sei die Kantenmenge von G eine Vereinigung disjunkter Kreise. Da jede Ecke eines Kreises den Grad 2 hat, hat auch jede Ecke der Vereinigung von disjunkten Kreisen

e1

e2

e3

e4


geraden Grad. Umgekehrt: Sei G ein eulerscher Graph. Wir beweisen die Behauptung durch Induktion nach der Anzahl der Kanten von G. Da G eulersch ist, besitzt G einen Kreis. Man entferne die Kanten dieses Kreises. Jede Komponente des so erhaltenen Graphen G* ist eulersch, also nach Induktion eine Vereinigung disjunkter Kreise.

14 Es gibt folgende sechs Bäume mit sechs Ecken:

15 Die Behauptung folgt aus den Aufgaben 27 und 29.

16 Sei G ein minimal zusammenhängender Graph. Angenommen, G enthält einen Kreis. Dann könnte man aus dem Kreis eine Kante entfernen und der Graph wäre immer noch zusammenhängend, ein Widerspruch zur Minimalität.

17 Sei G ein Baum. Da je zwei Ecken eines Baums durch einen Kantenzug verbunden sind, führt das Einfügen einer weiteren Kante zu einem geschlossenen Kantenzug, also einem Kreis. Sei umgekehrt G ein maximal kreisloser Graph. Dann enthält G keinen Kreis, ist also ein Baum.

18 Es genügt, eine Kante (gestrichelt eingezeichnet) aus K5 zu entfernen:

19 Es genügt, die gestrichelte Kante zu entfernen. Eine planare Darstellung wäre dann:

20 (a) g = 1, (b) m = 8, (c) n = 9.

21 Mit n = 4 Ecken, m = 6 Kanten und g = 4 Gebieten gilt n – m + g = 4 – 6 + 4 = 2.

22 Nein. Schauen Sie sich den Beweis von 8.4.2 noch mal an. Angenommen, es gäbe nur eine Ecke vom Grad 5, dann hätten alle anderen einen Grad größer gleich 6. In die Ungleichung eingesetzt ergibt sich ein Widerspruch.


23 Wenn der Graph keine Dreiecke enthält, dann gilt für die Anzahl m(L) der Kanten um ein Gebiet L die Abschätzung m(L) 4. Ist g die Anzahl aller Gebiete, so folgt

.g4)L(mGebietL

Da jede Kante höchstens zwei Gebiete trennt, ist

.m2)L(mGebietL

Zusammen folgt 2m 4g bzw. m 2g. Mit der Eulerschen Polyederformel n – m + g = 2 ergibt sich m 2g = 4 2n + 2m, also 2n 4 m.

24 Der Graph aus Aufgabe 21 hat G) = 4.

25 Siehe zum Beispiel http://www.matheprisma.de/Module/4FP/Seite10.htm.

26 G) = 4.

27 Der Baum, der nur aus einer Ecke besteht, hat die chromatische Zahl 1. Jeder Baum mit mehr als einer Ecke hat chromatische Zahl 2. Letzteres kann man sich wie folgt klar machen. Wir färben ein Ecke mit der ersten Farbe, dann alle Ecken, die mit ihr verbunden sind, mit der zweiten Farbe. Da ein Baum keine Kreise enthält, können wir auf diese Weise abwechselnd mit den beiden Farben sämtliche Ecken färben.

28 Die Nummerierung auf der linken Seite führt zu 2 (= ) Farben, die auf der rechten Seite zu 4 (= +1) Farben.

29 Ein Graph ist genau dann bipartit, wenn man seine Ecken so in zwei Klassen untertei-len kann, dass benachbarte Ecken zu unterschiedlichen Klassen gehören. Färbt man jeweils die Ecken einer Klasse gleich, so erhält man eine Eckenfärbung mit zwei Far-ben, so dass benachbarte Ecken unterschiedliche Farben haben.

30 (a) K6 hat die folgenden fünf Faktoren: (b) K8 hat sieben Faktoren.

31 Der vollständige Graph K2n hat n 1 Faktoren.

1 2

3 4

5 6

7 8

1 3

5 8

7 6

2 4


32 Da der Graph Kn,n regulär und bipartit ist, besitzt er eine Kantenfärbung mit = n Farben. Die Menge Fi aller Kanten der Farbe i ist dann ein Faktor. Kn,n hat also n Fak-toren.

33 Der Petersen-Graph ist regulär, alle Ecken haben den Grad 3. Wäre er faktorisierbar, so hätte er 3 Faktoren und es müsste ’(G) = 3 gelten, aber es ist ’(G) = 4.

Kapitel 9

1 Ein gerichteter hamiltonscher Pfad ist beispielsweise

2 Angenommen, es gibt keine Quelle. Sei e0 eine Ecke. Da e0 keine Quelle ist, gibt es mindestens eine Kante k0, die zu e0 hinzeigt. Sei e1 die Anfangsecke von k0. Da auch e1 keine Quelle ist, gibt es mindestens eine Kante k1, die zu e1 hinzeigt. Sei e2 die An-fangsecke von k1. Falls e2 = e0 ist, enthält der Graph einen gerichteten Kreis. Anderen-falls gibt es mindestens eine weitere Kante k2, die zu e2 hinzeigt. Sei e3 die Anfangs-ecke von k2. Falls e3 = e0 oder e3 = e1 ist, enthält der Graph einen gerichteten Kreis. Usw. Da der Graph nur endlich viele Ecken hat, muss irgendwann eine gerichtete Kante kn eine der Ecken e0, ..., en-1 als Anfangsecke haben. Dann enthält der Graph ei-nen gerichteten Kreis.

3 Da jede gerichtete Kante genau eine Anfangsecke und genau eine Eingangsecke hat, wird sowohl bei der Summe aller Ausgangsgrade als auch bei der Summe der Ein-gangsgrade jede Kante genau einmal gezählt. Die Summen sind also beide gleich der Summe aller Kanten.

4 Da der zugrundeliegende Graph eines Turniers vollständig ist, gilt für jede Ecke e deg+(e) + deg (e) = n 1, wobei n die Anzahl aller Ecken ist. Umformen und Quadrie-ren dieser Gleichung führt zu deg+(e) = (n 1) deg (e) bzw.

(deg+(e))2 = (n 1)2 2(n 1)deg (e) + (deg (e))2.

Bilden wir nun die Summe über alle n Ecken, so erhalten wir

Ee

2

Ee Ee

2

Ee

2 ))e((deg)e(deg)1n(2)1n())e((deg


Die Summe über alle Eingangsgrade ist gleich der Anzahl aller Kanten (vgl. Lösung

der vorherigen Aufgabe), also gleich 2

)1n(n2n

. Damit folgt

Ee

22

Ee

2 ))e((deg2

)1n(n)1n(2)1n(n))e((deg

Ee

2

Ee

2 ))e((deg))e((deg .

5 Ein gerichteter hamiltonscher Pfad ist zum Beispiel 1 5 6 2 3 4.

6 Sei G ein zusammenhängender gerichteter Graph, der einen gerichteten eulerschen Kreis enthält. Sei e eine beliebige Ecke von G. Der gerichtete eulersche Kreis durch-quert die Ecke e einige Male, sagen wir a mal. Dabei läuft er genau a mal in die Ecke hinein und kommt genau a mal aus ihr heraus. Da jede gerichtete Kante genau einmal im eulerschen Kreis enthalten ist, folgt deg+(e) = a = deg (e).

7 Da iP die kleinste aller Zahlen c(k) f(k) (falls k eine Vorwärtskante ist) und f(k) (falls k eine Rückwärtskante ist) ist, wird bei Addition von iP weder auf den Vorwärtskanten die Kapazitätsbeschränkung verletzt noch treten bei Subtraktion auf den Rückwärts-kanten negative Werte von f auf. Da iP auf allen Vorwärtskanten von P addiert und al-len Rückwärtskanten subtrahiert wird, ist außerdem die Flusserhaltung der inneren Ecken gewährleistet. Da der Pfad P genau eine Vorwärtskante, die von der Quelle ausgeht, enthält, wird durch Addition von iP auf dieser Kante der Wert des Flusses ge-nau um iP vergrößert.

8 Die folgende Abbildung zeigt fett gedruckt einen f-ungesättigten Baum, der nicht mehr weiter wachsen kann. Der abgebildete Fluss f ist daher maximal. Der zugehörige minimale Schnitt (X, X ) ist gestrichelt eingezeichnet. Es gilt wf = c(X, X ) = 7.

1 2

3

4 5

6


9 Die folgende Abbildung zeigt fett gedruckt einen f-ungesättigten Baum, der nicht mehr weiter wachsen kann. Der abgebildete Fluss f ist daher maximal. Der zugehörige minimale Schnitt (X, X ) ist gestrichelt eingezeichnet. Es gilt wf = c(X, X ) = 18.

10 Folgender Fluss im Netzwerk aus der vorherigen Aufgabe ist ebenfalls maximal.

11 Nach Satz 9.2.6 werden bei jedem maximalen Fluss die Kapazitäten des minimalen Schnitts voll ausgenutzt, also gilt f1(k) = c(k) = f2(k) für alle Kanten k des Schnitts. Wie man am Beispiel des Nullflusses leicht sehen kann, gilt die Umkehrung nicht.

13 Man kann eine neue „Superquelle“ q und eine neue „Supersenke“ s hinzufügen, die mit den Quellen q1, ..., qs bzw. mit den Senken s1, ..., st über Kanten mit unendlich großer Kapazität verbunden werden. Durch diese unendlich großen Kapazitäten beein-trächtigen diese zusätzlichen Ecken und Kanten den Fluss nicht.

14 Aus einem Pfad in einem ungerichteten Graphen kann man einen gerichteten Pfad er-halten, indem man alle Kanten des Pfades in der gleichen Richtung orientiert. Das heißt, wenn der ungerichtete Pfad die Kanten {e0, e1}, {e1, e2}, ... besitzt, so erhält der gerichtete Pfad die Kanten (e0, e1), (e1, e2), ... Umgekehrt kann man aus einem gerich-teten Pfad einem ungerichteten machen, indem man auf die Orientierung verzichtet. Das bedeutet, aus jeder gerichteten Kante (ei, ej) wird die ungerichtete {ei, ej}. Da in

q s

4

16

5

3

1

5

3 2

4

5

s q

6 3 6

3 6

7

9

4 5

8 3 5

s q

6 3 6

3 6

7

9

4 5

8 3 5


einem gerichteten Graphen alle Ecken paarweise verschieden sind, enthält auch der ungerichtete Graph keine mehrfach vorkommenden Ecken.

15 Eine Kantenmenge T trennt die Ecken e und e* eines (ungerichteten) Graphen G, wenn der Teilgraph G \ T keinen Weg von e nach e* enthält. Die Menge T heißt dann auch e und e* trennende Kantenmenge. Eine Menge T von Ecken heißt e und e* trennende Eckenmenge, wenn der Teilgraph G \ T keinen Weg von e nach e* enthält. Ein Wegesystem von e nach e* ist eine Menge von paarweise disjunkten Wegen von e nach e*. Dabei bedeutet disjunkt, dass die Wege keine Kanten gemeinsam haben. Mit diesen Definitionen kann man den Satz von Menger auch für ungerichtete Graphen G beweisen. Dazu muss man lediglich den assoziierten Graphen von G betrachten und auf diesen den Satz von Menger für gerichtete Graphen anwenden.

16 Die minimale trennende Kantenmenge von G besteht genau aus den gerichteten Kan-ten (e(1), e(2)), die aus den Ecken e der minimalen trennenden Eckenmenge von G ent-standen sind.

Kapitel 10

1 Die Kommutativgesetze x y = y x und x y = y x folgen aus

x y x y y x x y y x

0 0 0 0 0 0

0 1 0 0 1 1

1 0 0 0 1 1

1 1 1 1 1 1

Die Assoziativgesetze x (y z) = (x y) z und x (y z) = (x y) z, sowie das zweite Distributivgesetz x (y z) = (x y) (x z) folgen aus dieser Tabelle:

x y z x (y z)

(x y) z

x (y z)

(x y) z

x (y z)

(x y) (x z)

0 0 0 0 0 0 0 0 0

0 0 1 0 0 1 1 0 0

0 1 0 0 0 1 1 0 0

0 1 1 0 0 1 1 0 0

1 0 0 0 0 1 1 0 0

1 0 1 0 0 1 1 1 1

1 1 0 0 0 1 1 1 1

1 1 1 1 1 1 1 1 1


Die Gesetze 1 x = x, 0 x = x und x x = 0, x x = 1 folgen aus

x x x x x x 1 x 0 x

0 1 0 1 0 0

1 0 0 1 1 1

2 Der duale Satz lautet

(x (x y)) (y 1) = ((x (x y)) y) ((x (x y)) 1).

3 (a) Beweis mit Hilfe einer Wahrheitstabelle:

x y x y x (x y) (x (x y)) (y 0)

(x (x y)) y

((x (x y)) y) ((x (x y)) 0)

0 0 0 0 0 0 0

0 1 0 0 0 0 0

1 0 0 1 0 0 0

1 1 1 1 1 1 1

(b) Setzt man z = x (x y), so folgt die Äquivalenz der Ausdrücke aus dem Dis-tributivgesetz: z (y 0) = (z y) (z 0).

4 Beweis durch vollständige Induktion nach der Anzahl der Operatoren ( , , ): Induktionsanfang: Enthält B keinen Operator, so ist B die Nullfunktion, die Identität oder die Einsfunktion. Diese Funktionen erfüllen trivialerweise die Behauptung, denn

0D = 1 = 0, xD = x = ( x), 1D = 0 = 1.

Induktionsannahme: Die Behauptung gelte für alle booleschen Ausdrücke mit höchs-tens m Operatoren (m 0). Induktionsschluss: Zu zeigen ist, dass die Behauptung für alle booleschen Ausdrücke mit m + 1 Operatoren gilt. Jeden solchen Ausdruck kann man als

B1(e1, ..., en) B2(e1, ..., en), B1(e1, ..., en) B2(e1, ..., en) oder B1(e1, ..., en)

schreiben, wobei B1 und B2 Ausdrücke mit höchstens m Operatoren sind. Jede dieser drei Formen erfüllt die Behauptung, denn mit der Definition der Dualität, mit der In-duktionsannahme und mit den Regeln von De Morgan folgt:

(B1(e1, ..., en) B2(e1, ..., en))D = B1D(e1, ..., en) B2

D(e1, ..., en) = B1( e1, ..., en) B2( e1, ..., en) = (B1( e1, ..., en) B2( e1, ..., en)),

(B1(e1, ..., en) B2(e1, ..., en))D = B1D(e1, ..., en) B2

D(e1, ..., en) = B1( e1, ..., en) B2( e1, ..., en) = (B1( e1, ..., en) B2( e1, ..., en)),

( B1(e1, ..., en))D = B1D(e1, ..., en) = ( B1( e1, ..., en)).


Nach vollständiger Induktion folgt, dass die Behauptung für beliebige boolesche Aus-drücke gilt.

5 Das zweite Absorptionsgesetz ergibt sich aus Satz 10.1.1 wie folgt

x (x y) = (x 1) (x y) = x (1 y) = x 1 = x.

Das zweite Idempotenzgesetz folgt aus Satz 10.1.1 durch

x x = (x x) 0 = (x x) (x x) = x (x x) = x 1 = x;

6 Aus x y = 0 und x y = 1 folgt nach 10.1.1 und 10.1.3

x = x 0 = x (x y) = ( x x) ( x y) = 1 ( x y) = (x y) ( x y) = (x x) y = 0 y = y.

7 Beweis des Involutionsgesetzes ( x) = x:

x x ( x)

0 1 0

1 0 1

Beweis der Gesetze von de Morgan (x y) = x y und (x y) = x y:

x y (x y) x y (x y) x y

0 0 1 1 1 1

0 1 1 1 0 0

1 0 1 1 0 0

1 1 0 0 0 0

8 Beweis durch vollständige Induktion nach n: Induktionsanfang: Die Behauptung gilt trivialerweise für n = 1. Für n = 2 ergeben sich die Gesetze von de Morgan. Induktionsannahme: Die Behauptung gelte für eine natürliche Zahl n 2. Induktionsschluss: Nach Induktionsannahme gilt die Behauptung dann auch für n+1, denn

(x1 x2 ... xn xn+1) = (x1 x2 ... xn) xn+1 = x1 x2 ... xn xn+1 und

(x1 x2 ... xn xn+1) = (x1 x2 ... xn) xn+1 = x1 x2 ... xn xn+1.

9 Nach Wien.

10 Andreas und Christian kommen zu Besuch.

11 Möglichst einfache Ausdrücke für die zweistelligen booleschen Funktionen aus Bild 10.3 sind:


f1(x, y) = 0 f9(x, y) = (x y) f2(x, y) = x y f10(x, y) = (x y) (x y) f3(x, y) = x y f11(x, y) = y f4(x, y) = x f12(x, y) = x y f5(x, y) = x y f13(x, y) = x f6(x, y) = y, f14(x, y) = x y f7(x, y) = (x y) (x y) f15(x, y) = (x y) f8(x, y) = x y f16(x, y) = 1

12 (x y z) (x y z) ( x y z) ( x y z) ( x y z)

13 ( x y z) ( x y z) (x y z) (x y z) (x y z)

14 Das KV-Diagramm des Ausdrucks hat folgendes Aussehen:

Zusammenfassen benachbarter Einser zu drei Blöcken ergibt die vereinfachte Form ( a b c) (a d) (a b c).

15 Bei fünf Variablen können 32 Vollkonjunktionen auftreten. Diese 32 Plätze kann man in einem Quader anordnen, der aus zwei übereinander liegenden 4 4 großen Ebenen zusammengesetzt ist. Jede Ebene besteht aus einem KV-Diagramm für vier Variablen (siehe Abbildung 10.6). Die untere Ebene gehört zur fünften Variable, die obere zu de-ren Negation. Bei der Vereinfachung von Ausdrücken sollen auch solche Vollkon-junktionen als benachbart gelten, die im Quader übereinander liegen.

16 Sei f eine dreistellige boolesche Funktion mit der Eigenschaft, dass der Funktionswert negiert wird, wenn genau eine Eingangsvariable negiert wird. Es ist klar, dass es ge-nau zwei derartige Funktionen gibt, da man f(0, 0, 0) {0, 1} wählen kann. Für die Wahl f(0, 0, 0) = 0 kann man die Wahrheitstafel wie folgt sukzessive aufbauen:

x y z f(x, y, z)

0 0 0 0

0 0 1 1

1 1

1 1

1 1 1

b

b

a

a

a

d d

ccc


0 1 0 1

0 1 1 0

1 0 0 1

1 0 1 0

1 1 0 0

1 1 1 1

Aus der Tabelle können wir die disjunktive Normalform ablesen:

f(x, y, z) = ( x y z) ( x y z) (x y z) (x y z).

Anhand der Tabelle können wir uns davon überzeugen, dass f(x, y, z) = x y z gilt, wobei das Zeichen die XOR-Verknüpfung bezeichnen soll. Die zweite mögliche Funktion ist g(x, y, z) = f(x, y, z).

17 Die Schaltungen folgen unmittelbar aus den definierenden booleschen Ausdrücken (siehe Funktionen f7, f10 bzw. f14 in Kapitel 10.2).

18 Realisierung der 2-aus-3-Schaltung nur mit NAND-Bausteinen:

19 Für die Summe s und den Übertrag ü des Halbaddierers kann man folgendes schrei-ben, woraus sich die Schaltung in NOR-Technik direkt ergibt:

ü = NOR(NOR(x, 0), NOR(y, 0)), s = NOR(NOR(NOR(NOR(NOR(x, 0), 0), NOR(y, 0)),

NOR(NOR(x, 0), NOR(NOR(y, 0), 0))), 0).

20 (a) Wir bezeichnen die Schalter mit x, y und z (1 = geschlossen, 0 = offen) und die Lampe mit f(x, y, z) (1 = leuchtet, 0 = leuchtet nicht). Es ergibt sich folgende Werteta-belle.

x y z f(x, y, z)

0 0 0 1

&

&

&

& f(x, y, z)

x

y

z


0 0 1 0

0 1 0 0

0 1 1 1

1 0 0 0

1 0 1 1

1 1 0 1

1 1 1 0

(b) Aus der Tabelle können wir die disjunktive Normalform ablesen:

f(x, y, z) = ( x y z) ( x y z) (x y z) (x y z).

Dieser Term lässt sich mit dem KV-Verfahren nicht mehr vereinfachen, da sich keine Einser zu Blöcken zusammenfassen lassen. (c) Die zugehörige Gatterschaltung ist in folgender Abbildung dargestellt.

21 Zunächst stellen wir die Wertetabelle der gesuchten Funktion f auf.

w x y z f(w, x, y, z) w x y z f(w, x, y, z)

0 0 0 0 0 1 0 0 0 0

0 0 0 1 0 1 0 0 1 0

0 0 1 0 0 1 0 1 0 0

0 0 1 1 0 1 0 1 1 1

0 1 0 0 0 1 1 0 0 0

0 1 0 1 0 1 1 0 1 1

0 1 1 0 0 1 1 1 0 1

0 1 1 1 1 1 1 1 1 1

&

&

&

1 f(x, y, z)

x y z

&


Aus der Tabelle können wir die disjunktive Normalform ablesen:

f(x, y, z) = ( w x y z) (w x y z) (w x y z) (w x y z) (w x y z).

Zur Vereinfachung tragen wir diese Funktion in ein KV-Diagramm ein.

Es können vier Zweierblöcke gebildet werden, die Vereinfachung lautet daher

f(w, x, y, z) = (w x z) (w y z) (w x y) (x y z).

Die zugehörige Gatterschaltung ist in folgender Abbildung dargestellt.

22 Bei x = y ist a = 1, bei x < y zeigt b = 1 und bei x > y ist c = 1.

x y a(x, y) b(x, y) c(x, y) 0 0 1 0 0 0 1 0 1 0 1 0 0 0 1 1 1 1 0 0

Die Schaltung ergibt sich direkt aus den aus der Tabelle folgenden booleschen Aus-drücken a(x, y) = ( a b) (a b), b(x, y) = a b, c(x, y) = a b.

x

x

w

w

w

z z

yyy

1

1 1 1

1

&

&

&

1 f(w, x, y, z)

w x y

&

z


23 Wie beim Halbaddierer bezeichnen wir die beiden Ausgänge mit s (für Summe) und ü (für Übertrag). Die Wertetabelle hat folgende Gestalt.

x y z ü s 0 0 0 0 0 0 0 1 0 1 0 1 0 0 1 0 1 1 1 0 1 0 0 0 1 1 0 1 1 0 1 1 0 1 0 1 1 1 1 1

Für beide Ausgänge lesen wir die disjunktive Normalform aus der Tabelle ab:

ü = ( x y z) (x y z) (x y z) (x y z), s = ( x y z) ( x y z) (x y z) (x y z).

Der Ausdruck für s lässt sich nicht weiter vereinfachen. Für ü erhält man mit Hilfe ei-nes KV-Diagramms den vereinfachten Ausdruck ü = (x y) (y z) (x z). Es er-gibt sich folgende Schaltung.

&

&

&

1 s(x, y, z)

x y z

&

&

&

&

1 ü(x, y, z)


24 Mit den Halbaddierern Ha 1 und Ha 2 ergibt sich die Volladdiererschaltung wie folgt.

25 Die beiden vierstelligen Binärzahlen seien x3x2x1x0 und y3y2y1y0. Das abgebildete Pa-ralleladdierwerk liefert die Summe dieser Zahlen als fünfstellige Binärzahl z4z3z2z1z0.

Ha1

Ha2

1 ü

x

z

y

ü1

ü2

s2 s

s1

z3

ü3

ü0

Ha

Va1

x0

x2

x1

z0

z1

ü1

Va2

Va3

y0

y3

y1

z2

x3

y2

z0

z2

z1

z3 ü2 z4

Stichwortverzeichnis

A

Absolutbetrag 64 Absorptionsgesetze 193 Addierwerk 206 Advanced Encryption Standard 127 AES 127 Algorithmus 114 Algorithmus zum Finden eines maximalen

Flusses 178 Alphabet 94 alternierende Quersumme 76 Anfangsecke 163 Angreifer 112 Apel, K. (geb. 1932) 152 Äquivalenzfunktion 195 Assoziativgesetz 192 assoziierter gerichteter Graph 188 asymmetrische Kryptographie 129 Ausfluss 170 Ausgangsgrad 163 Aussage 28 Auswahlen mit Wiederholungen 53 Auswahlen ohne Wiederholung 53 Authentizität 111

B

b-adische Darstellung 72 Basis eines Zahlensystems 72 Baum 144 Bernoulli, J. (1654 1705) 33 Bernoullische Ungleichung 32 binäre Folge 47 binärer Baum 147 binäres Schieberegister 124 Binärsystem 73 Binärzahl 73

Binet-Formel 38 Binomialsatz 52 Binomialzahlen 48

explizite Formel 50 Rekursionsformel 49

bipartiter Graph 138 Bipartition 138 Blätter 147 Blockchiffre 126 Boolesche Algebra 193 boolesche Funktion 194 boolesche Operatoren 191

C

Cäsar, G. J. (100 44 v. Chr.) 113 Cäsar-Code 113 Cayley, A. (1821 1895) 152 chromatische Zahl 153 chromatischer Index 156 Cipher Block Chaining Mode 127 Cliquen und Anticliquen 3 Code 94 Code der ehemaligen deutschen Geldscheine 103 Codes über Gruppen 101 Codewörter 94 Codieren 93

D

Darstellung einer Zahl zu einer Basis 72 Data Encryption Standard 127 Dedekind, R. (1831 – 1916) 8 DES 127 Descartes, R. (1596 1650) 46 Dezimalsystem 73 Dezimalzahl 73 Diedergruppe 103 Dirichlet, L. (1805 - 1859) 1

250 Stichwortverzeichnis

disjunkt 45, 182 Disjunktion 191 disjunktive Normalform 196 Distributivgesetze 192 Division mit Rest 65 Dominosteine

a 1-Dominosteine 15 Dreieckszahlen 29 dual 193 Dualität 193 Durchschnitt 45

E

EAN-Code 108 Ecken 137, 163 eckenzusammenhängend 186 Eckenzusammenhangszahl 186 einfacher gerichteter Graph 164 Einfluss 170 Eingangsgrad 163 Einzelfehler 94 Electronic Code Book Mode 127 Empfänger 112 Endecke 145, 163 endliche Menge 45 Entschlüsselung 112 Eratosthenes von Kyrene (284 200 v. Chr.) 78 erweiterter euklidischer Algorithmus 70 Euklid (ca. 300 v. Chr.) 69 Euklidischer Algorithmus 68 Euler, L. (1707 1783) 59, 140 eulersche -Funktion 61, 130 Eulersche Polyederformel 149 Eulersche Zahl 59 eulerscher Graph 141 eulerscher Kreis 141

F

Faktor 157 Faktorisierung 158 Faktorisierungsproblem 132

Fakultät 28 Färbung 153 Färbungsmethoden 11 fehlererkennender Code 93 Fehlererkennung 93 Feistel-Chiffre 127 Fermatsche Primzahlen 77 f-gesättigter Pfad 175 Fibonacci 36 Fibonacci-Zahlen 37 Fixpunkt einer Permutation 57 Fluss 170 Flusserhaltung 170 Freimaurer-Code 113 Fünffarbensatz (Heawood, 1890) 154 f-ungesättigter Baum 178 f-ungesättigter Pfad 175

G

Gatter 202 Gauß, C. F. (1777 1855) 30, 67 Gaußklammer 147 Gaußsche Primzahlen 77 Gebiet 149 Geheimhaltung 111 Geheimtext 112 geometrische Reihe 32 gerichtete Kanten 163 gerichteter eulerscher Kreis 187 gerichteter Graph 163 gerichteter hamiltonscher Pfad 166 gerichteter Kantenzug 164 gerichteter Kreis 165 gerichteter Pfad 165 gerichteter Weg 165 geschlossener gerichteter Kantenzug 165 geschlossener Kantenzug 139 Gesetze von de Morgan 193 Gewinnverhinderungsstrategie 20 ggT 67 Gitterpunkte 22

Stichwortverzeichnis 251

goldener Schnitt 40 Grad einer Ecke 140 Graph 137 Graphentheorie 137 Greedy-Algorithmus 153 größter gemeinsamer Teiler 67 Gruppe 89 Gruppencode 101 Gruppencode mit Permutationen 102 Guthrie, F. (1831 1899) 151

H

Haken, W. (geb. 1928) 152 Halbaddierer 205 Hamilton, W. R. (1805 1865) 151 Hauptsatz der elementaren Zahlentheorie 81 Heawood, P. J. (1861 1955) 152 Heesch, H. (1906 1995) 152 Hexadezimalsystem 73 Hexadezimalzahl 73 Höhe eines binären Baums 147

I

Idempotenzgesetze 193 Implikation 195 Induktion 27

Induktionsbasis 27 Induktionsschritt 27 Induktionsverankerung 27 Induktionsvoraussetzung 27 Prinzip der vollständigen Induktion 27 Prinzip der vollständigen Induktion

(allgemein) 33 inkongruent 67 Inkrement 176 innere Ecke 169 innerlich disjunktes Wegesystem 185 Involutionsgesetz 193 Inzidenz 137 ISBN-Code 99 isolierte Ecke 140

K

Kanten 137 Kantenfärbung 156 Kantenzug 139 kantenzusammenhängend 184 Kantenzusammenhangszahl 184 Kapazität 169 Kapazität eines Schnitts 172 Kapazitätsbeschränkung 170 Kapazitätsfunktion 169 Karnaugh und Veitch, Verfahren von 199 kartesisches Produkt 46 Kasiski-Test 118 Kempe, A. B. (1849 1922) 152 Kerckhoffs, Prinzip von 114 Klartext 112 Kleiner Satz von Fermat 130 Knoten 137 Kommutativgesetz 192 Komplement 170 Komponente 46 kongruent 67 Königsberger Brückenproblem 140 Konjunktion 191 konjunktive Normalform 198 Kontrollzeichen 94 Kreis 139 Kryptoanalyse 115 Kryptographie 111 KV-Diagramm 199

L

Landkarten schwarz-weiß 34 Länge eines Kreises 139 leere Menge 48 Lemma von Bézout 69 Leonardo von Pisa 36 lineare Komplexität 126 lineares Schieberegister 124 Logarithmus dualis 147 logische Schaltungen 202


M

Mächtigkeit 45 maximaler Fluss 174 maximaler Grad 153 Maximum-Fluss-Minimum-Schnitt-Satz (Ford

und Fulkerson, 1956) 177 Menger, K. (1902 1985) 183 Mersennesche Primzahlen 78 Méziriac, C.-G. Bachet de (1581 1638) 70 minimale trennende Mengen 182 minimaler Schnitt 174 Modul 83 modulare Arithmetik 82 modulare Inverse 71 modulo 67 monoalphabetische Verschlüsselung 115 monochromatisch 18

monochromatische Rechtecke 18 Morgan, Augustus de (1806 1871) 151 Museumsproblem 21

N

N 63 NAND- und NOR-Technik 203 NAND-Verknüpfung 195 natürliche Zahlen 63 natürlicher Logarithmus 80 Negation 191 Nettofluss 172 Netzwerk 169 neutrales Element 192 Nicht-Operator 191 Normalform 196 NOR-Verknüpfung 195 Nullfluss 170

O

offene eulersche Linie 143 öffentlicher Schlüssel 129 One-Time-Pad 123

P

Paritätscode 94 Paritätscode mit Gewichten 96 Pascalsches Dreieck 50 Pentominos 24 Permutation 56 planarer Graph 148 plättbarer Graph 148 polyalphabetische Chiffre 116 Polybios (ca. 200 120 v. Chr.) 112 Polybios-Code 112 Potenzmenge 48 Primzahl 77 Primzahlsatz 80 Prinzip von Kerckhoffs 114 privater Schlüssel 129 Problem der falschen Münze 145 Produkt von Restklassen 87 Produktformel 46 Prüfziffer 94 pseudozufällige Folgen 123 Public-Key-Eigenschaft 129 Public-Key-Kryptographie 129 Public-Key-Verschlüsselungsschema 129

Q

Quelle 163 Quersumme 75

R

Ramsey, F. P. (1903 – 1930) 4 Ramsey-Theorie 4 Realisierung von booleschen Funktionen 204 regulärer Graph 158 Relation 164 Repräsentanten 83 Restklasse 83 revidierter Fluss 176 Rijndael 128 RSA-Algorithmus 130 Rückkopplungskoeffizient 124

Stichwortverzeichnis 253

Rückwärtskante 175

S

Satz von Brooks 154 Satz von Euler 130 Satz von König 157 Satz von Kuratowski 151 Satz von Menger 183 Satz von Vizing 157 Schachbrett 11

m n-Schachbrett 15 Schieberegister 124 Schlüssel 114 Schlüsselwort 116 Schnitt 172 Schubfachprinzip 1

unendliches 7 verallgemeinertes 7

Sender 112 Senke 163 Shrinking Generator 126 Sieb des Eratosthenes 78 Siebformel 54 Signatureigenschaft 129 Signaturschema 129 Simpson-Identität 40 Skytala 133 Square-and-Multiply-Algorithmus 135 Statistische Analyse 115 steganographisch 111 Stellenwertsystem 72 Strichcode 101 Stromchiffre 122 Summe von Restklassen 85 Summenformel 45 Symmetrie 103 symmetrische Gruppe 56 symmetrisches Verschlüsselungsverfahren 114

T

teilbar 6

Teilbarkeit 63 Teilbarkeitsregeln 74 Teilen 63 teilerfremd 6, 69 Teilmenge 48 Tetrisfiguren 24 transitiv 167 trennende Eckenmenge 184 trennende Kantenmenge 181 triangulieren 21 Triple-DES 128 Turm von Hanoi 41 Turnier 165

U

Überdeckung des Schachbretts mit Dominosteinen 11

unknackbare Codes 120

V

Vereinfachen von booleschen Ausdrücken 199 Vereinigung 45 Verfahren von Karnaugh und Veitch 199 Verschlüsselungseigenschaft 129 Vertauschungsfehler 95 Vielfaches 63 Vielfachsummendarstellung 69 Vierfarbenproblem 151 Vierfarbensatz (Apel und Haken, 1976) 154 Vigenère, Blaise de 116 Vigenère-Code 116 Vigenère-Quadrat 117 visuelle Kryptographie 121 Volladdierer 206 Volldisjunktion 198 Vollkonjunktion 196 vollständige Induktion 27 vollständiger Graph 138 Vorwärtskante 175


W

Wechselwegnahme 69 Weg 139 Wegesystem 182, 185 Wert eines Flusses 171 Wohldefiniertheit 85 Wurzel 147

X

XOR-Verknüpfung 195

Z

Z 63 Zahlendarstellung 72 Zählen 45 Zahlensystem 72 Zahlentheorie 63 Ziffern 72 Zn 84 Zn* 89 zugrundeliegender Graph 165 zulässige Färbung 34 zusammenhängender Graph 139

Date post:	13-Feb-2020
Category:	Documents
Upload:	others
View:	4 times
Download:	0 times

Lösungen der Übungsaufgaben978-3-8348-9182... · 2017-08-27 · Lösungen der Übungsaufgaben...

Documents