Lösungen der Übungsaufgaben - Springer978-3-8348-9941-5/1.pdf · 1 (n+lf, 2 1+2+3+...+(n+l)~(n+lXD+2)f2. Lösungen der Übungsaufgaben 3 6n Punkte aufdem Rand. 215 4 Induktionsverankerung:

Lösungen der Übungsaufgaben

Kapitell

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 Schubfachprinzip mindestens zwei aus derselben Kategorie.(b) Wenn er zwei graue Socken bekommen will, so muss er im schlimmsten Fall 22Socken 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 unterteilen. Teilt man 10 Punkte (Objekte) auf diese 9 Teilquadrate (Kategorien) auf, sogibt es nach dem Schubfachprinzip ein Teilquadrat, das mindestens zwei Punkte enthält. Den größten Abstand, den zwei Punkte in einem Quadrat der Seitenlänge 1 habenkönnen, ist die Länge der Diagonale, also nach dem Satz des Pythagoras .Ji.

3 Einen Würfel der Kantenlänge 2 kann man in 2·2·2 = 8 kleine Würfel der Kantenlänge1 unterteilen. Teilt man 9 Punkte auf diese 8 Würfel auf, so gibt es nach dem Schubfachprinzip einen Würfel, der mindestens 2 Punkte enthält. Der Abstand dieser zweiPunkte kann höchstens so groß sein wie die Raumdiagonale, also J12 +12+12 =J3 .

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

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

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

7 Siehe 1.1 "Gleiche Anzahl von Bekannten". Man muss lediglich die Relation "ist bekannt mit" durch die Relation "stößt an mit" ersetzen.

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

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

10 Wir teilen die elfnatürlichen Zahlen in folgende fiinfKategorien Ko, Kl> ...,~ ein:• In Ko 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 ~ kommen diejenigen Zahlen, die bei Division durch 5 den Rest 4 ergeben.

A. Beutelspacher, Marc-A. Zschiegner, Diskrete Mathematikfür Einsteiger, DOI 10.1007/978-3-8348-9941-5, © Vieweg+Teubner Verlag | Springer Fachmedien Wiesbaden GmbH 2011

212 Lösungen der Übungsaufgaben

Das verallgemeinerte Schubfachprinzip sagt jetzt (da 11 > 2 . 5 ist), dass es eine Kategorie mit drei Objekten gibt. Es gibt also drei Zahlen, die bei Division durch 5 denselben Rest ergeben. Wenn wir die Differenz je zweier dieser Zahlen bilden, ,,hebtsich der Rest weg", die Differenz ist daher durch 5 teilbar.

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

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 mindestenseine Kategorie, in der mindestens zwei Objekte liegen. Die Summe zweier geraderZahlen ist gerade, die Summe zweier ungerader Zahlen ist ebenfalls gerade. Der Mittelpunkt zwischen zwei Punkten (Xl, Yl)und (X2, Y2) ist

(Xl +X2 Yl +Y2)

2 ' 2Da beide Zähler gerade sind, wenn beide Punkte in der gleichen Kategorie liegen, sindsie 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 inacht Kategorien aufteilen: nämlich die vier Kategorien aus Aufgabe 12, jeweils mit "zgerade" 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 YKoordinate den Rest 0, 1 oder 2 haben. Dies ergibt die neun Kategorien (3 Möglichkeiten für x mal 3 Möglichkeiten für y), auf die wir die 10 Punkte aufteilen. Nach demSchubfachprinzip enthält eine Kategorie mindestens zwei Punkte. Die x-Koordinatendieser Punkte ergeben bei Division durch 3 also den gleichen Rest. Die Zahl XI + 2X2ist dann ohne Rest durch 3 teilbar. Dasselbe gibt für die y-Koordinaten bzw. die ZahlYl + 2Y2. Dann sind die Koordinaten des Punktes

(Xl +2X2 Yl +2Y2)

3 ' 3 '

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

15 Schubfachprinzip: Die Objekte sind die 9 natürlichen Zahlen. Diese werden in 8 Kategorien 1<0, KI, ..., Ks eingeteilt:• 1<0 enthält diejenigen Zahlen, die Vielfache von 9 sind,• K1 enthält die Zahlen, die bei Division durch 9 den Rest I ergeben,


• K2enthält die Zahlen, die bei Division durch 9 den Rest 2 ergeben,

•

213

• Ks 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 Zahlendurch 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). Daes 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 {I, 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. Insbesondere 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 ergibtsich zwangsläufig folgende Teilabdeckung, die in der Mitte ein 2x2-Quadrat frei lässt,

das nicht überdeckt werden kann.

r--

- -I

2 Wenn moder n durch 4 teilbar ist, so kann man das Schachbrett nach Satz 2.2.1 kom

plett mit 4xl-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

214

gilt. N..m SlItz 2.2.1 kann man die ersten4b Spaltenkomplett mit 4x1-Dominodeinen'I1berdecke:n. EbeDso köJmeIl von den res1liehen 2 Spelten die obersten 4a Zeilell mit4)(1-Dmnino!ltllimm. iiberdeckt wmden.. Obris: bleibt ein 2lC2-Fe1d, das mit dmn 2lC2Steinilberdecll:t werdenkann.

3 Ein Springer spriDgt abwechBelDd von einem lChwarzen Feld zu einem weißen Feldund umgekehrt, erreicht also jeweils nach 2 Spriingen wieder ein Feld der g1eichIInFarbe.Um wiede:r auf seiD Awlgangsfe1d zurOckzukehren. musser folglich eine geradeAnzahl von Zügen durchfiihren.

4 Ein Tmm. wechelt bei jedm:Bewegung stindig die Farbe _ Feldes. Um jedes Feld

genau. eiDmal zu erreichen. muss er sm Ende auf einemFeld std1eD, du eine andereFarbe alt das Startfeld hat. Er kann dahm: nicht von einem.Eekfeld in die pgmriiberliegendeEekegelangen, da diese beidenFelder die gleicheFllbe besitzen.

5 Fürzwei Quadrate gibt es llIIr eine Möglichkeit zusammen'llJbingen. Ein dritte. Quad

llIt kann auf zwei Arten~ wsden (1II1twMIlr all" in einm: Reihe odm: mitKniek.). Fllr vier Quadrategibt es danndie dargestellten Möglichkeiten

6 Die zwölfPentomiDos sind

7 Die Strategie des erIItlln Spielers besteht darin, dass er ein zweites Irnuz diagona1 __ben sein mte8 Kreuz setzt (und ZWllr auf die entgegengeseIzt Seite, wo dl::r zweiteSpieler - ev&IIltuell-1I&Iin entes Knmzgemacht hat). DIIIIII. bleibenibm lIOWOhl für das

dritte ab aum :6lrdas~ KreuzjeweilszweiMöglichkeiten, VOll denen der Gegnerimmer nur eine verllindem kann. Auf diese Weise hat der ersteSpiek:r ßBCh vier Zü.......",....

I Wrr betraehten einen AUIlsclmitt von 4 Reihen und 82 Spalten IW!I dem Gitter. JedeSpalte diese. AusschDittIhat vier Gitterpunkte. Vier Pullk1c kllm1en aufgenau 34

- 81venchiedme Arten gefärbt werden (fiir jedm Punkt hat man drei Farben zur VIIdiigung). Da es 82 Spalten gibt, gibt es mindest:eDs zweiSpalten mit derse1ben FarbaDordnung. In jeder FlIlblJIlImllllmg gibt CI aber zwei Punkte, die gleich gefirbt lIind.Man nehme diesePunktc in denbeiden Spalten. Diese bilden ein Redrteck mit gleieb-

-"""""KapI""

1 (n+lf,

2 1+2+3+ ...+(n+l) ~(n+lXD+2)f2.


3 6n Punkte auf dem Rand.

215

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 2° - 1 Zügen umgeschichtet werden kann.

Induktionsbehauptung: Dann gilt die Aussage auch für n + 1, d. h. für einen Turm mitn + 1 Scheiben gibt es eine Lösung mit 2°+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 2° - 1 Züge. Nun hat man die größte Scheibe freigelegt. Diese Scheibe kannman 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 benötigt man dafür 2° - 1 Züge . Das bedeutet, dass wir insgesamt

(2° - 1) + 1 + (2° - 1) = 2 . 2° - 1 = 2°+1- 1

Züge benötigt haben.

S Sie brauchen 264- 1 = 18446744073709551615 Sekunden. Das sind 584942417355

Jahre!

6 Induktionsbasis: Sei n = 1. Durch Aufteilung mit nur einem Kreis entstehen nur zweiLä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

k b 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 kb ... , kn entstanden ist. Nach Induktionsvoraussetzung 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+l liegt, wechselt die Farbe. Dadurchentsteht 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 ausdem 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örensowohl 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 vertauschtwerden.

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

+ 2n-3+ 2n-1

+ 3 +

+5

2n-5

+

+

+ 2n-1

+2n

n-Zn

+ 2n + 2n + + 2n

Aus 2·(1 + 3 + 5 + ... + (2n-1)) = n-Zn folgt die Behauptung.

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

+ q + q2 + + qn

-( 9 + g2 + + gD + gn+1 )

+ 0 + 0 + + 0 qD+l

1- qD+l

Aus S - q-S = (1 - q) . S = 1 - qn+1 folgt: S = 1_ qD+l . Durch Multiplikation mit a1-q

folgt die gesuchte Summenformel.

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

1 + 2 + 4 + ... + 2 n + 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 = (n1pn+I + 2. Dann gilt

1·2 + 2.22 + 3.23 + 4.24 + ... + n·2n + (n + 1)-2n+1

= (n - 1pn+1 + 2 + (n + 1pn+1 = 2n·2n+1 + 2 = n·2n+2 + 2.

12 Induktionsbasis: Die Formel gilt fürn = 1, denn e = t·1·(1 +1)·(2 ·1+1).Induktionsschritt: Für ein n ~ 1 gelte 12+ 22+ 32+ ... + n2= tn ·(n + 1).(2n + 1). Danngilt

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

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

= t(n+1)·(n+2) ·(2n+3)= t(n+1)·(n+2) ·(2·(n+1)+1) .

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

217

14 Siehe Satz 3.2.6.

15 Induktionsbasis: Die Behauptung gilt für n = 1, denn i-I = 6.Induktionsschritt: Für ein n ~ 1 sei 70

- 1 = 6·k mit einer natürlichen Zahl k. Dann ist

70+1_1 =7.70-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). Dieersten 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 fnviele Arten. Wir bezeichnen die Anzahl der Möglichkeiten, die n-te Stufezu erreichen, mit Sn. Die erste Stufe erreicht der Briefträger nur auf eine Weise. Ebenso gibt es für die zweite Stufe nur eine Möglichkeit, also gilt SI = S2 = I. Um die(n+2)-te Stufe zu erreichen, gibt es zwei prinzipiell verschiedene Möglichkeiten. Imersten Fall kommt der Briefträger von der (n+1)-ten Stufe her, auf die er auf So+1 Möglichkeiten gelangt sein kann. Im zweiten Fall kommt er in einem Doppelschritt von dern-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 = fo•

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

19 Es gilt

M = M+m <:::> M2

= M+m <:::> (M)2 = M+I <:::> (M)2 _ M_l =0.m M m m m m m

Diese quadratische Gleichung hat die Lösungen

M = 1±.J5m 2

Da M die größere Teilstrecke ist, ist folgt Mim = cp.

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+ ... + 60 = f20+1. Dann gilt


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

fCn+1)+2 = fn+3 = fn+1 + fn+2 = fn+1 + fn + fn_1 + ... + fl + 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

IS " E I= IS I+ IEI-I S u E I= 55 + 60 -I S u E I~ 55 + 60 - 80 = 35,

denn IS u EI:::; 80 (Anzahl alles Hörer) . Also ist IS " E I~ 35.

2 (a) Für jeden Buchstaben gibt es 26 Möglichkeiten, insgesamt also 26·26·26 = 263 =

17576 Möglichkeiten.(b) Aufhttp://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 lOS = 100000 Möglichkeiten.

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

6 Für die erste Stelle gibt es 9 Möglichkeiten (1, 2, ..., 9), für die zweite dann ebenfallsnoch 9 (0, 1,2, ..., 9, ausgenommen die Ziffer der ersten Stelle), für die dritte 8 und fürdie 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 I F I =

42.103.000 und I M I = 82.259.500 - 42.103 .000 = 40.156.500. Die Anzahl aller verschiedengeschlechtlichen Paare ist dann

8

9

IF x M I= IF 1·1 M I= 1690709119500000.

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

Die Menge sei M = {mi, mr, ..., mn} . Wir ordnen jeder Teilmenge T von M wie folgteine binäre Folge {bi, b2, ..., bs} zu: Es gilt b,= 1, falls m, E T ist, sonst gilt b, = O. Dadiese Zuordnung eineindeutig (bijektiv) ist, gibt es genau so viele Teilmengen wie binäre Folgen, also 2n

•

(lOJ 1O! (42J 42! (47J= - = 252 = -- = 42-41/2 = 861 = 52251400851 .5 5!·5! '40 2!·401 ' 11

Lösungen der Übungsaufgaben 219

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

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

11 (a) (l;J = 45.

(b)Aus (~J = 55fo1gtn= 11.

(c) Wegen (I;J < 50 < (121J

kann die Behauptung nicht stimmen .

12 Es klingelt (~J - m mal.

13 Auf der Party befinden sich 4 Paare und 4 Singles : Die 4 Paare stoßen (~J - 4 = 24

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

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

nomialzahl (:J. Da diese die Anzahl der k-elementigen Teilmengen einer n-elemen-

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

•

15 Wegen (n;lJ = (n+1)n/2 kann man die Dreieckszahlen in der dritten "Spalte" des

Pascalsehen Dreiecks finden.

16 Wie betrachten eine Menge M mit n Elementen und wollen aus dieser eine kelementige Teilmenge auswählen. Nach Defmition der Binomialzahlen gibt es dafiir

genau (:J 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 ( n J Möglichkeiten.n-k

17 Es gibt (m: nJ Möglichkeiten, den Punkt rechts oben zu erreichen.

18 Nach Satz 4.2.5 gibt es (12+77

-IJ = 31824 Möglichkeiten.

19 Esgilt n! < n! ~3!.(n-3)!<2! . (n - 2) ! ~ 3 < n - 2 ~ 5 < n.2!-(n-2)! 3!-(n-3)!


20 Am Pascalsehen Dreieck erkennt man, dass die Binomialzahlen "in der Mitte" amgröß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 (nJ - n! - n·(n-l)! - n (n-1Jk - k!-(n-k)! - k·(k-l)!-(n-l-(k-1))! - k' k-l .

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: nurnoch eine Möglichkeit. Das ergibt insgesamt 8·7·6·5-4·3·2·1 = 8! = 40320 Möglichkeiten.

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 aufbeiden Seiten ergibt sich n . Ig(8) ~ Ig(1000000). Auflösen nach n ergibtn ~ Ig(1000000) / Ig(8) ~ 6,64. Es werden also mindestens 7 Schlitze benötigt.

26 IAuBuCuDI = lAI + IBI + lcl + IDI-IAnBI-IAncl-IAnDI-IBncl-IBnDI-lcnDI+ IAnBncl + IAnBnDI + IAnCnDI + IBnCnDI-IAnBnCnDI.

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

a(lO) = 10! _ 10! + 10! _ 10! + 10! _ 1O! + 1O! _ 10! + 10! _ 10! + 1O!1! 2! 3! 4! 5! 6! 7! 8! 9! 1O!

= 3628800 - 3628800 + 1814400 - 604800 + 151200 - 30240

+ 5040 -720 +90 -10 + 1 = 1334961.

28 Offensichtlich gilt a(l) = 0 und a(2) = 1. O. B. d. A. bestehe die n-elementige Mengeaus den Zahlen von 1 bis n. Bei einer fixpunktfreien Permutation darf die 1 nicht aufsich selbst abgebildet werden, für sie gibt es also genau n-I mögliche Plätze. Wenndie 1 auf Platz Nr. x abgebildet wird (x 'cl: 1), dann wird das Element x entweder aufPlatz Nr. 1 abgebildet oder nicht. Für den ersten Fall gibt es genau a(n-2) Möglichkeiten, denn alle Elemente außer 1 und x können beliebig fixpunktfrei permutiert werden.Für den zweiten Fall gibt es a(n-l) Möglichkeiten, denn alle Elemente außer 1 könnenfixpunktfrei permutiert werden. Insgesamt folgt, dass es (n - l) ·(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


<XI = IZ I+ ID I+ IFI = 51 + 34 + 21 = 106

<X2 = IZ (] D I + IZ (] F I + ID (] F I = 17 + 11 + 7 = 35

<X3 = IZ(]D(]FI =4

Nach Satz 4.3 .1 können wir die gesuchte Anzahl wie folgt berechnen:

30

221

n

<p(n)

21

3

242

54

6

27

68

49 10 11 12 13

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) = p - 1.

32 Nach Aufgabe 33 gilt: <p(2a) = 2a- 2a-1 = 2a-I'(2 - 1) = 2a-l.

33 Eine PrimzaWpotenz pa ist nur zu Vielfachen von p nicht teilerfremd. Es gibt pa-I

Vielfache von p, die kleiner oder gleich pa sind: I-p, 2·p, ..., pa.l.p. Daher gilt: <p(pa) =pa_pa-I .

34 Wenn p und q verschiedene PrimzaWen sind, gilt <p(p.q) = (p -1)-(q -1).

KapitelS

1 Aus a l b und b I a folgt b = qia und a = q2b mit ganzen Zahlen ql und q2. Einsetzen

ergibt die Gleichung folgt b = qia = qlq2b. Daraus folgt b = 0 oder 1 = qlq2. Da qi und

q2 ganze Zahlen sind, folgt ql = q2 = 1 oder ql = q2 = -1, also a = ±b.

2 Induktionsbasis: Die Aussage gilt für n = 0, denn aus 0 = 6 . 0 folgt 6 I O.

Induktionsschritt: Für ein n ~ 0 sei n3- n = ö-kmit einer natürlichen Zahl k. Dann ist

(n + 1)3- (n + 1) = n3+ 3n2+ 3n + 1 - n - 1 = n 3- 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* < Ia I.

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* > O. Danngilt

b = a·(-q*) -r* = a(-q*=F1) + (I a I-r*) =: aq + r.

Dabei setzen wir r := Ia 1- r* und q:= -q* - 1 falls a > 0 ist. Falls a < 0 gilt, setzenwir q := -q* + 1. Wegen 0 < r* < 1a 1 gilt dann r> 0 und r < I a I. Damit ist dieBehauptung bewiesen.

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

5 (a) n+l mod n = 1, n2mod n = 0, 2n+5 mod n = 5 mod n, 3n+6 mod n = 6 mod n, 4n-lmodn= n-1.(b) (n+2) mod (n+1) = 1, (2n+2) mod (n+1) = 0, (n 2+1) mod (n+1) = 2, (n2)mod (n+1)=1.(c)(n+1)2 mod n = 1, (n+1)IOOO mod n = 1, (n-li mod n = 1, (n_l)IOOOI mod n = n-1.(d) (n+l)nmod n = 0, n3 + 2n2+ 4 modn = 4 mod4, (2n+2)(n+1) modn= 2 modn, n!modn=O.

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

I~

I~-,/

1/I~

(b) Bei b = a genügt ein Zug, bei b = 2a benötigt man zwei Züge und für b = 2a+1werden 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 (ab)(a + b) = 11 ist. Da 11 eine Primzahl ist, muss einer der Faktoren gleich 1 und derandere gleich 11 sein. Die Lösung dieses Gleichungssystems ist a = 6 und b = 5. Diegesuchten Quadratzahlen sind also 36 und 25.(b) Wir suchen Lösungen der Gleichung a2- b2= (a - b)(a + b) = 1001. Für die Faktoren 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 + 2, 2n+ 1 = 2·n + 1, 2 = 1·2 + O. Also giltggt(2n+3, 2n+!) = 1.

11 Induktionsbasis: Die Aussage gilt für n = I, denn ggT(fI, f3)= ggT(I, 2) = 1.

Induktionsschritt: Für ein n ~ I gelte ggT(fn, fn+2) = 1. Wir führen die ersten Schrittedes euklidischen Algorithmus durch :

fn+3= fn+!·1 + fn+2, fn+! = fn+2·O + fn+h fn+2= fn+!·1 + fn.

Nach Satz 5.3.1 folgt ggT(fn+3, fn+t} = ggT(fn+h fn+2) = ggT(fn+!, fn)= 1.

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

gibt sich fn2mod fn+! = 0 - (_l)n = (_I)n+!.

(b) Aus fn·fnmod fn+1= ±1 ergibt sich, dass entweder fn oder -fn die Inverse von fnist.

13 Der erweiterte euklidische Algorithmus liefert

1 = 1234'(-17) + 567-37.

14 (1010101Oh = 170, (2002)11 = 2664, (ABCDh6 = 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 ersetztwerden.

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 ergibtsich die Quersumme 25 + a, also a = 2. Also sind 19296 und 19692 durch 36 teilbar.

18 Die ZaWen 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 = O. Die Zahlen sind durch 9 teilbar, wenn ihre Quer

summe 2a + 2b durch 9 teilbar ist. Da a die Werte von I 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 dieQuersumme 18 gibt es mehrere Möglichkeiten: 1188,2277,3366,4455,5544,6633,

7722,8811,9900.

19 Es sei z = lln·12n + lln_I·12n-1 + ... + al·121 + ao·120 eine natürliche Zahl, die im

Zwölfersystem die Darstellung (llnlln-l...alao) hat. Bei Division von z durch 12 ergibt

sich der Rest ao. Daraus ergeben sich folgenden Regeln für i E {12, 6,4,3, 2}: z istgenau 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 letzten 2 (3, 4, ...) Ziffern gebildete Zahl durch 4 (8, 16, ...) teilbar ist:


= I02.(ak_I·1Ok-3 + ak-2·1Qk-4 + + a2·100) + al·1 0 1 + ao.100

= lO3.(ak_l·lOk-4 + ak_2·IQk-S + + a3'lOO) + a2·102 + al·IO l + ao'lOO

= lO4.(ak_l·lOk-S + ak_2·IQk--6 + + a4'lOO) + a3·103 + a2·102 + al ·IO I + ao' lOO

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

n - ao= ak-l ·bk-I + ak_2·bk-2 + ... + aj -b!

durch t teilbar. Folglich gilt n - ao == 0 (mod t), also n == ao (mod t).(b) Da t ein Teiler von b-l ist, teilt tauch bLI = (b-l)(b+l), bLI = (b-1)(b2+b+1) ,..., bk-LI = (b-1)(bk-2 + ... + b + I), also auch

ak_dbk-LI) + ak_2·(bk-LI) + ... + al ·(bLI)

= ak_l·bk-1 + ak_2·bk-2 + ... + al ·b l + ao·bO- (ak-I + ak-2 + ... + al + ao)

=n-Q(n).

22 Es gilt:

(b + 1)(b2s - b2s-1 + b2s-2- b2s-3± ...+ b2- b + I)

= b2s+1 _ b2s + b2s-1 _ b2s-2± ... + b3_ b2+ b

+ b2s _ b2s-1 + b2s-2 +... _ b3 + b2- b + I

=b2s+1 + 1.

23 (a) Die Quersumme einer solchen Zahl ist 0 + I + 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 sieschreiben als

lOOOOOa + 10000b + lOOOa + lOOb + 10a + b

= 10lOlOa + 1010lb = 10lOl·(IOa + 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-..alao, so ergibt sich nach dem Anhängen

des Spiegelbildes die Zahl ak-1-..alaoaoal...ak-1- Die alternierende Quersumme dieserZahl 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 vonPrimzahlpotenzen schreiben:

n= p~l . p~' ..... p~' .


Wir wählen zwei weitere Primzahlen p* und q*, die unter den Primzahlen PI> P2, ..., Psnicht vorkommen. Dann sind die Zahlen a = P*' p~' ..... p~. und b = q*. p~l nicht durchn 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 Primzahl.

27 Angenommen, es gibt nur endlich viele Primzahlen PI> P2, ..., ps. Wir betrachten dieZahl

n = pI 'pr ... 'Ps - 1.

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

28 Seien [al und [b] zwei verschiedene Restklassen modulo n. Wir müssen zeigen, dass

[al und [b] disjunkt sind. Sei x ein Element aus [b], das heißt x "" b (mod n), Angenommen, x wäre auch ein Element von [al, 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 [al und [b] gleich, ein Widerspruch.(b) Es ist klar, dass jede ganze Zahl z in der Restklasse [z] enthalten ist. Angenommen, z wäre in einer weiteren Restklasse [a] 'f. [z] enthalten. Dann gilt z "" a (mod n),woraus z - a"" 0 (mod n) bzw. n I z - a folgt. Dann gilt nach Satz 5.7.1 aber [al = [z],ein Widerspruch.

29 Die Multiplikationstafeln von Zr,und Zl2 sehen wie folgt aus.

[0] [I] [2] [3]

[0] [0] [0] [0] [0]

[1] [0] [1] [2] [3]

[2] [0] [2] [4] [6]

[3] [0] [3] [6] [2]

[4] [0] [4] [1] [5]

[5] [0] [5] [3] [1]

[6] [0] [6] [5] [4]

[4] [5]

[0] [0]

[4] [5]

[1] [3]

[5] [1]

[2] [6]

[6] [4]

[3] [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]

~ ~ ~ 00 ~ ~ 00 ~ ~ 00 ~ ~ 00[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]

00 ~ 00 ~ ~ 00 ~ ~ 00 ~ ~ 00 ~

[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: ur' = [1], [2rl = [4],[3rl = [5], [6r1 = [6] und umgekehrt.(b) In Zl2 sind nur die Elemente [1], [5], [7] und [11] invertierbar, und zwar sind sie zusich selbst invers.

30 In ZlOl gilt [2rl= 51, or' = 34 und [50r1

= 99.

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

Kapitel 6

1 Sei (aj, a2, ..., !ln-I> lln) ein Codewort. Dann ist k = al + a2 + ... + !ln eine gerade Zahl .Angenommen auch (al> ..., llj', ..., an)mit llj ':f= llj wäre ein Codewort. Dann wäre auchk' = al + ...+ llj' + ... + Bn eine gerade Zahl. Dann wäre auch die Differenz k' - k = llj'

-llj eine gerade Zahl. Da llj ' und llj aus der Menge {O, I} sind, folgt llj' -llj = 0, alsollj' = llj. Dies widerspricht der Annahme.

2 (a) C = {ala2a384asa6a7as8.9110 teilt al + 3a2 + a3+ 384+ ... + 3as + 8.9}, C ist also einParitä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 teilerfremd zu 10 sind. Allerdings erkennt er Vertauschungsfehler nicht, wenn sich die vertauschten Ziffern um 5 unterscheiden. Zum Beispiel sind sowohl 169 828 013 als auch

619828013 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 189828 047 Codewörter. Br erkennt auch nicht alle Vertauschungsfehler:Zum Beispiel sind sowohl 189828091 als auch 189828901 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 BAN ala2a33.4asli6a7ag mit 8 Stellen wird das Prüfsymbol agso bestimmt, dass

3'al + l'a2 + 3'a3 + 1'3.4 + 3'as + l-a, + 3'a7 + l-a, durch 10 teilbar ist. Bei einer BANala2a334asli6a7agll9alOallaI2a13 mit 13 Stellen wird das Prüfsymbol a13 so bestimmt, dass

l-a, + 3'a2 + l 'a3+ 3'34 + + 3'a12+ l'a13 durch 10 teilbar ist. Bs sei ala2a3... eine gül-tige BAN und al ...8;-I8;'8;+1 die BAN mit einem Binzelfehler an der Stelle i, also 8;' :ft

ar, Dann gibt es zwei Fälle:

(1.) Die Ziffer aj bzw. a,' wird mit dem Faktor 1 gewichtet. Dann ist die Differenz derbeiden gewichteten BAN gerade 8; - 8;' . Da 8; und 8;' Ziffern von 0 bis 9 sein können,

kann die Differenz a, - a,' Werte von -9 bis 9 annehmen. Der einzige Wert in diesem

Bereich, der modulo 10 keinen Rest, also keinen Unterschied in der Prüfziffer ergebenwürde, ist die Differenz O. Die tritt aber nur dann auf, wenn 8;= 8;' gilt. Somit wird ein

Binzelfehler erkannt.

(2.) Die Ziffer 8; bzw. 8;' wird mit dem Faktor 3 gewichtet. Dann ist die Differenz derbeiden gewichteten BAN gerade 38; - 38;' = 3(8; - 8;'). Da 8; und 8;' Ziffern von 0 bis 9

sein können, kann die Differenz 3(aj - an Werte von -27 bis 27 annehmen. Modulo10 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 8;= 8;' gilt. Somit wird ein Binzelfehler erkannt.

6 (a) 9 783406 418716 ist eine korrekte BAN, denn als gewichtete Quersumme ergibtsich 110, also eine ZehnerzaW.

(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 ala2a3... eine gültige EAN . Vertauscht man zwei Ziffern aj und ak (mit i:ft k), somuss man zwei Fälle unterscheiden:

(I .) Die Ziffern a, 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 gewichtetenSumme, 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 8; und ak werden mit unterschiedlichen Gewichten versehen (zum Bei

spiel aj mit 1 und ak mit 3). Dann erhält man als Differenz der gewichteten Summen

38; + ak- 8; - 3ak = 28; - 2ak = 2(8; - ak). Da 8; 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 10Differenzen, die modulo 10 keinen Unterschied ergeben , also nicht entdeckt werden.Die Differenz 0 ist dabei harmlos, da dann a, und ak gleich sind. Die Differenzen ±10bedeuten aber, dass sich die Ziffern a; und ak um 5 unterscheiden, eine Vertauschungder beiden Ziffern aber nicht erkannt wird.Der EAN-Code erkennt also Vertauschungsfehler höchstens von Ziffern mit unterschiedlichen Gewichten und auch nur dann, wenn sich die beiden vertauschten Ziffernnicht um 5 unterscheiden. Beispiel: 12345670 hat die gewichtete Summe 60, aber62345170 hat die gewichtete Summe 70, ist also ebenfalls eine Zehnerzahl.

8 (a) 3 - 282 - 87144 - X ist keine korrekte ISBN, denn die gewichtete Quersumme ist243, also keine Elferzahl. Das korrekte Prüfsymbol ist 9.(b) 3 - 528 - 06783 -7 ist eine korrekte ISBN, denn als gewichtete Quersumme ergibtsich die ElferzahlllO = 10· 11.

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

10 Sei ala2a3.... ~alO eine ISBN. Dann ist

lO·al + 9·a2 + 8·a3 + 7·a4 + 6·as + 5·a6 + 4·a7 + 3·ag + 2·a9 + l·alO

eine durch 11 teilbare Zahl. Durch Vertauschen der 2. und der 5. Stelle entsteht die

Folge alasa314a21l6...alO. Wir können a2* as voraussetzen, denn sonst wäre die Vertauschung belanglos. Angenommen, auch dies wäre ein Codewort. Dann müsste auch

lO·al + 9·as + 8·a3 + 7·a4 + 6·a2 + 5·a6 + 4·a7 + 3·ag + 2·a9 + l·alO

eine durch l l teilbare Zahl sein. Zusammen folgt mit 5.1.1, dass l l auch die Diffe

renz 9·a2 + 6·as - (9·as + 6·a2) = 3(a2 - as) teilen muss. Da 3 teilerfremd zu 11 ist,folgt, dass ll ein Teiler von a2 - as sein muss. Da a2 und as beide zwischen 0 und9 liegen, ist die Differenz a2 - as eine Zahl zwischen -9 und +9. Die einzige durch11 teilbare Zahl in diesem Bereich ist aber O. Daher muss al = a2 sein. Dieser Widerspruch 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 erkannt. Zum Beispiel wäre 1 2345 67 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 (g], g2' ..., gJ ein Codewort eines Gruppencodes mit Kontrollsymbol c und Per

mutationen 1t1> 1t2, .... , 1tn. Das heißt , dass 1tl(gl)·1t2(g2)· ... ·1tn(gn) = c ist. Bei der Übertragung möge ein Fehler an der i-ten Stelle passiert sein, es wird also der Vektor

(gI> ..., hi> ..., gJ mit hj "* gj empfangen. Wenn dieser Vektor auch ein Codewort wäre, dann müsste 1tl(gl)- ... . 1tj(hj)' ....1tn(gJ = c = 1tl(gl)- ... . 1tj(gj)' ... ·1tn(gJ gelten.Indem man von rechts der Reihe nach mit 1tn(gJ-1

, 1tn-l(gn-2rl, ..., 1tj+1(gj+1rl und


von links mit 1t1(glr1, 1t2(g2rl, ... ·1tj_l(gj_Ir l multipliziert, erhält man schließlich1tj(hJ = 1tj(gj). Da Permutationen injektiv sind, folgt hj = gj, ein Widerspruch.

13 Aus 1tj(x)= 1tj(x') folgt gjX = g.x' . Da gj E Zq*,also invertierbar ist, führt die Multiplikation mit gj-l auf x = x' . Also ist die Abbildung 1tj injektiv und daher als Abbildung einer endlichen Menge in sich auch bijektiv. Also ist die Abbildung 1tj: Zq~ Zqmit x ~ x . gi eine Permutation von Zq. Die Multiplikation mit Gewichten kann manalso auch als Permutation auffassen. Jeder Paritätscode mit Gewichten gj E Zq* ist daher auch ein Code mit Permutationen über der Gruppe (Zq,+).

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

e-a = e-Ig-x) = (e-gj -x = g·x = a.

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

34567 8

3 1 268 7

34567 8

3 8 064 1

345 678

345 678

16 Individuelle Lösung.

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

1t1(2) = 7, 1t2(5) = 9, 1t

3(3) = 6, ..., 1t1o(5) = 9,

so ergibt sich 7969963069. Mit Hilfe der Verknüpfungstabelle der Diedergruppekö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 Element ist. Daher ist die Prüfziffer gleich 2 und die gesamte Banknotennununer lautetG N 3 0 7 6 6 0 3 N 2.

18 Die zwei Ziffempaare (glO, gll), deren Vertauschung nicht bemerkt würde, sind (1,8)und (4, 7), denn es gilt


Kapitel 7

1 Individuelle Lösung.

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

3 DIESER TEXT IST NICHT MEHR GEHEIM.

4 lAMAMAN.

5 Als Hilfe sind hier die häufigsten Buchstaben des Geheimtextes: q, a, 1, 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 betrachtenmüssen. Entsprechend schreiben wir den Text von oben nach unten in Spalten, wobeidie Zeilen- und die Spaltenzahl Teiler von 60 sind. Bei fünf Spalten erhalten wir denfolgenden Klartext: Ich wusste, dass diese Transpositionschiffre leicht zu knacken ist!

8 Lösung: IST DAS EIN GUTER ALGORITHMUS?

9 MFBTVCNCDKMG.

10 Mit dem Schlüsselwort BUBRO ergibt sich der folgende Klartext:Den hoechsten Organisationsstand erfuhr die Kryptologie in Venedig, wo sie in Formeiner staatlichen Buerotaetigkeit ausgeuebt wurde. Es gab Schluessel-Sekretaere, dieihr Buero im Dogenpalast hatten und fuer ihre Taetigkeit rund zehn Dukaten im Monatbekamen. Es wurde dafuer gesorgt, dass sie waehrend ihrer Arbeit nicht gestoert wurden. Sie durften ihre Bueros aber auch nicht verlassen, bevor sie eine gestellte Aufgabe geloest hatten.

11 .W orum geht es bei der jüngsten Aufregung um Echelon und die Spionage der Vereinigten Staaten gegen europäische Wirtschaftsunternehmen? Fangen wir mit ein paaroffenen Worten von amerikanischer Seite an. Ja, meine kontinentaleuropäischenFreunde, wir haben euch ausspioniert. Und es stimmt, wir benutzen Computer, um Daten nach Schlüsselwörtern zu durchsuchen. Aber habt ihr euch auch nur für einen Augenblick gefragt, wonach wir suchen? Der jüngste Bericht des Europäischen Parlaments über Echelon, verfasst von dem britischen Journalisten Duncan Campbell, hatzornige Beschuldigungen der Kontinentaleuropäer ausgelöst. Der US-Geheimdienst,heißt es, stehle Spitzentechnologie europäischer Unternehmen, um sie - man höre undstaune - zur Verbesserung der eigenen Konkurrenzfähigkeit an amerikanische Unternehmen 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 Handvoll Gebiete technologisch überlegen sind. Aber, um es so behutsam wie möglich zuformulieren: Die Anzahl dieser Gebiete ist sehr, sehr gering . Die meiste europäischeTechnologie lohnt den Diebstahl einfach nicht. Richtig , meine kontinentalen Freunde ,wir haben euch ausspioniert, weil ihr mit Bestechung arbeitet. Die Produkte eurer Unternehmen sind oftmals teurer oder technologisch weniger ausgereift als die eurer amerikanischen Konkurrenten, manchmal sogar beides . Deshalb bestecht ihr so oft. DieKomplizenschaft eurer Regierungen geht sogar so weit, dass Bestechungsgelder inmehreren europäischen Staaten noch immer steuerlich absetzbar sind."

12 (a) HFGSCFEBYFFTTXNQHFG.~)QXVHCAMDMZSffiCBYDPM.

(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 beioder nicht. Dementsprechend gibt es bei n Zellen 2° Möglichkeiten, ein lineares Schieberegister 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 mussdiesen 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 gewesen sein. Die Rückkopplungskoeffizienten Ci bestimmen wir wie folgt. Für den Inhalt der linken Zelle, der nacheinander 0,0,0, 1, 1 sein muss, gilt- nach einem Takt: 0 = Cs • 1 + C4 • 0 + C3 • 0 + C2 • 0 + CI • 0,- nach zwei Takten: 0 = Cs • 0 + C4 • 1 + C3 • 0 + C2 • 0 + CI • 0,- nach drei Takten: 0 = Cs • 0 + C4 • 0 + C3 • 1 + C2 • 0 + CI • 0,- nach vier Takten: I = Cs • 0 + C4 • 0 + C3 • 0 + C2 • I + CI • 0,- nach fünf Takten: I = Cs • 1 + C4 • 0 + C3 • 0 + C2 • 0 + CI • 1.

Dieses lineare Gleichungssystem hat die Lösung CI = 1, C2 = 1, C3 = 0, C4 = 0, Cs =0, indie Summe gehen also nur die ersten beiden Zellen ein.


~Cl~~-.

18 Aus P = 23 und q = 37 können wir n = pq = 851 und cp(n) = (p -I)(q - I) = 792 be

rechnen. Als zu cp teilerfremde Zahl wählen wir zum Beispiel e = 17. Damit könnenwir die Nachricht m = 537 zu c = m"mod n = 53i7 mod 851 = 220 verschlüsseln, Der

erweiterte euklidische Algorithmus ergibt als Lösung von ed mod cp = I den privatenSchlüsseld = 233. Damit können wir c = 220 wieder entschlüsseln: Cd mod n = 220 233

mod 851 = 537 = m.

19 (a) Es ergibt sich n = pq = 33. Wir verschlüsseln jeden codierten Buchstaben m, = 13,

1,20,8,5, 13, 1,20,9,11 einzeln zu Ci = m{ mod n = 19, I, 14, 17,26,19, I, 14,3,

11. Dies entspricht der Buchstabenfolge "SANQZSANCK".(b) Mit cp = (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 Cid mod n = 7, 21, 20. Dies entspricht dem Wort "GUT".

20 Sei i eine natürliche Zahl mit 1 :s; i :s; 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

(pJ p! p .(p-I)!i i!·(p-i)! = i!·(p-i)!

eine natürliche Zahl ist, teilt der Nenner i!·(p - i)! den Zähler p.(p - I)!. Da der Nen

ner teilerfremd zu p ist, muss er (p - I)! teilen. Also gilt (p - I)! = k . i!·(p - i)! mit ei

ner natürlichen Zahl k. Daraus folgt

(~J =k · p.

21 (a) Da m l 6 = «(m2i )2i gilt , benötigt man 4 Multiplikationen.

(b) Wegen m2l = m I6·m4·m benötigt man nach (a) 4 +2 = 6 Multiplikationen.(c) Die Idee ist, m wiederholt zu quadrieren und dann geeignete Terme zu multiplizieren. Diesen Square-and-Multiply-Algorithmus zur Berechnung von md mit höchstens

2 · [ld(d)] Multiplikationen kann man wie folgt formulieren:(I.) Setze z := I und c := x (dabei speichert z die Zwischenergebnisse und c enthält diePotenzen 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.).


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

22 Aus den beiden Gleichungen n = p.q = 14803 und cp(n) = (p - I) . (q - I) = 14560folgt durch Eliminieren von q die Gleichung (p - 1) . (14803/p - 1) = 14560. Ausmultiplizieren ergibt 14803 - p - l4803/p + 1 = 14560. Zusammenfassen und Multiplikation mit p liefert die quadratische Gleichung 0 = p2- 244p + 14803. Diese hat die Lö

sungen PI = 131 und P2= 113. Dementsprechend sind ql = 113 und q2= 131.

KapitelS

1 Alle Graphen mit genau vier Ecken sind die folgenden (von Permutationen derEcken 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 mitzwei Farben färben, so dass es am Ende aufgeht. Bei ungerader Länge müsste die letzte Ecke die gleiche Farbe wie die erste Ecke bekommen; dadurch hätten zwei benachbarte Ecken die gleiche Farbe.

4 Ein Graph ist genau dann bipartit, wenn er nur Kreise gerader Länge hat. Wir betrachten einen bipartiten Graphen mit der Partition {EI, E2}. In jedem Kreis müssen sichdann Ecken aus EI und E2 abwechseln. Dann muss die Anzahl der Ecken im Kreis gerade sein.

Seien umgekehrt alle Kreise gerade. Sei eo eine beliebige Ecke. Sei EI die Menge aller Ecken, die einen ungeraden kürzesten Abstand zu eo haben, und sei E2 dieMenge aller Ecken, die einen geraden kürzesten Abstand zu eo haben. Dann ist {EI,E2} eine Bipartition. Denn: Angenommen, es gibt eine Kante von EI nach EI (odervon ~ nach E2.Diese würde einen ungeraden Kreis schließen.

5 Wir betrachten eine beliebige Ecke Co mit einer ihrer anschließenden Kanten ko. Sei eldie andere Ecke von ko. Da el mindestens den Grad 2 hat, gibt es eine weitere Kante kldurch er. Usw. Da der Graph nur endlich viele Ecken besitzt, kommen wir irgendwarman einer Ecke ej an, an der wir schon waren, das heißt Cj= Cimit i < j . Darm ist die besuchte Kantenfolge von ei bis ej ein Kreis.

6 In Kapitel 1.2 haben wir bewiesen : In jeder Gruppe von mindestens zwei Personengibt es zwei, die die gleiche Anzahl von Bekannten innerhalb dieser Gruppe haben.Wir übertragen diesen Satz auf einfache Graphen, indem wir Ecken mit Personen undKanten mit der Bekanntsheitsre1ation identifizieren. Die Anzahl der Bekannten einerPerson 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 gleichen Grad haben.

7 Die Graphen mit 1:1:;;; 2 setzen sich aus Kreisen und Pfaden (Wege mit paarweise verschiedenen Ecken) zusammen.

8 (a) Bei diesem Verfahren werden bei jedem Durchgang durch eine Ecke zwei Kantenverbraucht, außer beim Start in der Anfangsecke. Würde das Verfahren in einer Eckegeraden Grades enden, die nicht die Anfangsecke ist, so wären an dieser schon geradzahlig 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 desVerfahrens.(b) Beim Start in einer Ecke ungeraden Grades wird eine Kante verbraucht und esbleiben noch geradzahlig viele Kanten übrig. Bei jedem Durchgang durch die Anfangsecke werden zwei Kanten verbraucht. Wenn überhaupt, bleiben also immer geradzahlig viele Kanten übrig, so dass man stets aus der Anfangsecke wieder herauskommt.

9 (b) Ja, denn jede Ecke hat einen geraden Grad.(c) Zum Beispiel: links oben anfangen, dann waagerecht nach rechts gehen und imZick-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 K" (mit ungeradem n) nach folgender Regel in einem Zug zeichnen: "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 Uhrzeigersinn 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.

~------~el

(b) Der Graph ist nicht eulersch, da nicht alle Ecken einen geraden Grad haben: DieEcke el hat Grad 1 und die Ecke e3hat Grad 5.(c) Da es genau zwei Ecken mit ungeradem Grad gibt, besitzt der Graph eine offene

eulersche Linie : el - e2- e3- el - e4- e3- e2- e4- e3.

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


geraden Grad. Umgekehrt: Sei G ein eulerscher Graph. Wir beweisen die Behauptungdurch Induktion nach der Anzahl der Kanten von G. Da G eulersch ist, besitzt G einenKreis. Man entferne die Kanten dieses Kreises . Jede Komponente des so erhaltenenGraphen 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 immernoch zusammenhängend, ein Widerspruch zur Minimalität.

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

18 Es genügt , eine Kante (gestrichelt eingezeichnet) aus Ks 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 dieUngleichung 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

Lm(L);;::4g.LGebiet

Da jede Kante höchstens zwei Gebiete trennt, ist

Lm(L)~2m.LGebiet

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 X(G) = 4.

25 Siehe zum Beispiel http://www.matheprisma.delModule/4FP/SeitelO.htm.

26 X(G) =4.

27 Der Baum, der nur aus einer Ecke besteht, hat die chromatische Zahl 1. Jeder Baummit 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 wirauf diese Weise abwechselnd mit den beiden Farben sämtliche Ecken färben.

28 Die Nwnmerierung auf der linken Seite führt zu 2 (= X) Farben, die auf der rechtenSeite zu 4 (= L1+I) Farben.

4~38 7

5 6

1 2

8rgJ54 2

7 6

1 3

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 manjeweils 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) Kt; hat die folgenden fiinfFaktoren:

----

(b) Ks hat sieben Faktoren.

31 Der vollständige Graph K2n hat n - I Faktoren.


32 Da der Graph Kn,n regulär und bipartit ist, besitzt er eine Kantenfärbung mit 1:1 = nFarben. Die Menge F, aller Kanten der Farbe i ist dann ein Faktor. Kn,n hat also n Faktoren .

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 X'(G) = 3 gelten, aber es ist X'(G) = 4.

Kapitel 9

1 Ein gerichteter hamiltonscher Pfad ist beispielsweise

2 Angenommen, es gibt keine Quelle. Sei eo eine Ecke. Da eo keine Quelle ist, gibt esmindestens eine Kante ko, die zu eo hinzeigt. Sei el die Anfangsecke von ko. Da auchel keine Quelle ist, gibt es mindestens eine Kante kI, die zu el hinzeigt. Sei e2 die Anfangsecke von kl. Falls e2= eo ist, enthält der Graph einen gerichteten Kreis. Anderenfalls gibt es mindestens eine weitere Kante k2, die zu e2 hinzeigt. Sei e3 die Anfangsecke von k2. Falls e3 = eo oder e3 = el ist, enthält der Graph einen gerichteten Kreis.Usw. Da der Graph nur endlich viele Ecken hat, muss irgendwann eine gerichteteKante kn eine der Ecken eo, .... Co-I als Anfangsecke haben . Dann enthält der Graph einen 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 Eingangsgrade jede Kante genau einmal gezählt. Die Summen sind also beide gleich derSumme aller Kanten.

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

(deg+(e))2 = (n - li - 2(n - I)deg-(e) + (deg-(e))2.

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

~)deg+(e))2 = ~)n-l)2 -2(n-1)Ldeg-(e)+ L(deg-(e))2ceR ceR ceR ceR


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

der vorherigen Aufgabe), also gleich (~J = n(n2-1) . Damit folgt

L(deg+(e))2 =n .(n-l)2 -2(n-l) n(n-l) +L(deg-(e))2_ 2 _

<:> L(deg+(e))2 = L(deg-(e))2 .ceE ceE

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

1 2

6tr--t--~--+-~ 3

6 Sei G ein zusammenhängender gerichteter Graph, der einen gerichteten eulerschenKreis enthält. Sei e eine beliebige Ecke von G. Der gerichtete eu1ersche Kreis durchquert die Ecke e einige Male, sagen wir a mal. Dabei läuft er genau a mal in die Eckehinein und kommt genau a mal aus ihr heraus . Da jede gerichtete Kante genau einmalim eu1erschenKreis enthalten ist, folgt deg'(e) = a = deg'Te).

7 Da ip die kleinste aller Zahlen c(k) - f(k) (falls keine Vorwärtskante ist) und f(k) (fallskeine Rückwärtskante ist) ist, wird bei Addition von ip weder auf den Vorwärtskantendie Kapazitätsbeschränkung verletzt noch treten bei Subtraktion auf den Rückwärtskanten negative Werte von f auf. Da ip auf allen Vorwärtskanten von P addiert und allen Rückwärtskanten subtrahiert wird, ist außerdem die Flusserhaltung der innerenEcken gewährleistet. Da der Pfad P genau eine Vorwärtskante, die von der Quelleausgeht, enthält, wird durch Addition von ip auf dieser Kante der Wert des Flusses genau um ipvergrößert.

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


q s

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

6 --&--'-'A,~"@' ® 9q &:---!....~.';.,''''''li''~(1)~.. __1_-- s

(J) 5 (1),-~ 3 @ <S;l,/

8 ,/'5

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 minimalenSchnitts voll ausgenutzt, also gilt fl(k) = c(k) = f2(k) fiir 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, diemit den Quellen qj, ..., q, bzw. mit den Senken SI, ... , St über Kanten mit unendlichgroßer Kapazität verbunden werden. Durch diese unendlich großen Kapazitäten beeinträchtigen diese zusätzlichen Ecken und Kanten den Fluss nicht.

14 Aus einem Pfad in einem ungerichteten Graphen kann man einen gerichteten Pfaderhalten, indem man alle Kanten des Pfades in der gleichen Richtung orientiert. Dasheißt, wenn der ungerichtete Pfad die Kanten {eo, ed, {eI, e2}, ... besitzt, so erhält dergerichtete Pfad die Kanten (eo, el), (e-, e2), ... Umgekehrt kann man aus einem gerichteten Pfad einem ungerichteten machen, indem man auf die Orientierung verzichtet.

Das bedeutet, aus jeder gerichteten Kante (Ci, ej) wird die ungerichtete {e., ej}. Da in


einem gerichteten Graphen alle Ecken paarweise verschieden sind, enthält auch derungerichtete 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 dannauch 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 enach e*. Dabei bedeutet disjunkt, dass die Wege keine Kanten gemeinsam haben. Mitdiesen Definitionen kann man den Satz von Menger auch für ungerichtete Graphen Gbeweisen. Dazu muss man lediglich den assoziierten Graphen von G betrachten undauf diesen den Satz von Menger für gerichtete Graphen anwenden.

16 Die minimale trennende Kantenmenge von Ö' besteht genau aus den gerichteten Kanten (e(1), e(2»,die aus den Ecken e der minimalen trennenden Eckenmenge von Ö ent

standen sind.

Kapitel 10

1 Die Kommutativgesetze x A y = YA x und x v y = y v x folgen aus

x Y XAy yAX xvy yvx

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 A (y A z) = (x A y) A z und x v (y v z) = (x v y) v z, sowiedas zweite Distributivgesetz x A (y V z) = (x A y) V (x A z) folgen aus dieser Tabelle:

x y Z XA (x Ay) xv (x vy) XA (x Ay) V

(y A z) AZ (yv z) vz (yv z) (x Az)

0 0 0 0 0 0 0 0 0

0 0 I 0 0 1 1 0 0

0 1 0 0 0 1 I 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 A X= x, 0 v x = x und x A -,x = 0, x v -,x = 1 folgen aus

x -,x XA-,X Xv-,x lAX Ovx

0 1 0 1 0 0

1 0 0 1 1 1

2 Derdua1eSatziauret

(x A (x V y)) V (y Al) = ((x A (x V y)) V y) A ((x A (x V y)) v 1).

3 (a) Beweis mit Hilfe einer Wahrheitstabelle:

241

x Y XAY XV (XAY) (x V (x A y)) (x V (x AY)) ((x V (x A y)) A y)A (yv 0) AY V ((x V (x AY)) A 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 v (x A Y), so folgt die Äquivalenz der Ausdrücke aus dem Distributivgesetz: Z A (y V 0) = (z Ay) V (z A 0).

4 Beweis durch vollständige Induktion nach der Anzahl der Operatoren (A, v , -,):

Induktionsanfang: Enthält B keinen Operator, so ist B die Nullfunktion, die Identitätoder die Einsfunktion. Diese Funktionen erfüllen trivialerweise die Behauptung, denn

OD = 1 = -,0, xD= X= -,(-,x), 1D= 0 =-,1.

Induktionsannahme: Die Behauptung gelte fiir alle booleschen Ausdrücke mit höchstens m Operatoren (m ~ 0).

Induktionsschluss: Zu zeigen ist, dass die Behauptung fiir alle booleschen Ausdrücke

mit m + 1 Operatoren gilt. Jeden solchen Ausdruck kann man als

BI(e\, ..., en) A B2(e\, ..., en), BI(e\, ..., en) v B2(e\, ..., en) oder -,BI(e\, ..., en)

schreiben, wobei BI und B2 Ausdrücke mit höchstens m Operatoren sind . Jede dieser

drei Formen erfiillt die Behauptung, denn mit der Definition der Dualität, mit der In

duktionsannahme und mit den Regeln von De Morgan folgt :

(BI(e\, ..., en) A B2(el, ..., en))D = BID(e\, ..., en) v Bl(e\, ..., en)

= -,BI(-,e\, ..., -,en) v -,B2(-,e\, ..., -,en) = -,(BI(-,e\, ..., -,en) A B2(-,el, ..., -,en) ) ,

(BI(e\, ..., en) v B2(el' ..., en))D = BID(e\, ..., en) A Bl(e\, ..., en)

= -,BI(-,e\, ..., -,en) A -,B2(-,e\, ..., -,en) = -,(BI(-,e\, ..., -,en) v B2(-,el, ..., -,en) ) ,


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

5 Das zweite Absorptionsgesetz ergibt sich aus Satz 10.1.1 wie folgt

x v (x AY) = (x A 1) v (x AY) = XA(1 v Y) = XA 1 = x.

Das zweite Idempotenzgesetz folgt aus Satz 10.1.1 durch

x A x = (x Ax) V0 = (x A x) V (x A....,x) = x A(x v ....,x) = x A I = x;

6 Aus x A Y= 0 und x v Y= 1 folgt nach 10.1.1und 10.1.3

....,X = ....,X v 0 = ....,X v (x Ay) = (-,x v x) A (-,x Vy) = 1 A(-,x V y)

= (x v y) A (-,x Vy) = (x A ....,x) v y = 0 v y = y.

7 Beweis des Involutionsgesetzes ....,(....,x) = x:

x ....,X ....,(-,x)

0 1 0

1 0 1

Beweis der Gesetze von de Morgan ....,(x Ay) = ....,X v ....,y und ....,(x v y) = ....,X A ....,y:

x y ....,(x AY) ....,xv....,y ....,(x Vy) ....,XA....,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 sichdie 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

""'(Xl AX2 A ... AXnA Xn+l) = ""'(Xl AX2 A ... Axn) V"",Xn+l= "",Xl V "",X2 V ... V ""'XnV ""'Xn+1 und

"",(Xl v X2 V ... V x, V Xn+l) = "",(Xl V X2 V ... V xn)A"",Xn+l= "",Xl A "",X2 A ... A""'XnA ....,Xn+l .

9 Nach Wien.

10 Andreas und Christian kommen zu Besuch.

11 Möglichst einfache Ausdrücke für die zweistelligen booleschen Funktionen aus Bild10.3 sind:


f1(x, y) = 0

f2(X, y) = XA Y

f3(X, y) = XA -.y

f4(x, y) =xfs(x, y) = -.x AY

f6(X, y) = y,

f7(x, y) = (x v y) A-.(x Ay)

fs(x, y) = x v y

f9(X, y) = -.(x v y)

flO(X, y) = (x A y) V -.(x v y)

fll(x, y) =-.y

f12(X, y) = x v -.y

f13(x, y) = -.x

f14(X, y) = -.x v y

f1S(x, y) = -.(x Ay)

f16(X, y) = I

243

12 (x vyv z) A(x vyv-.z) A (-.x vyv z) A(-.x vyv -.z) A(-.x v-.yv z)

13 (-.x A-.y A -.z) V (-.x AYAz) V (x A-.y A -.z) V (x A -.y Az) V (x AYAz)

14 Das KV-Diagramm des Ausdrucks hat folgendes Aussehen :

c-.c ,-A-, -.c

-.a 1 I

I I

I I I

-.a

~

d

Zusammenfassen benachbarter Einser zu drei Blöcken ergibt die vereinfachte Form(-.a A-.b Ac) v (a A-.d) v (a Ab x -.c).

15 Bei fünf Variablen können 32 VolIkonjunktionen auftreten. Diese 32 Plätze kann manin einem Quader anordnen, der aus zwei übereinander liegenden 4 x 4 großen Ebenenzusammengesetzt 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 deren Negation. Bei der Vereinfachung von Ausdrücken sollen auch solche VolIkonjunktionen als benachbart gelten, die im Quader übereinander liegen.

16 Sei feine dreistellige boolesche Funktion mit der Eigenschaft, dass der Funktionswertnegiert wird, wenn genau eine Eingangsvariable negiert wird. Es ist klar, dass es genau zwei derartige Funktionen gibt, da man f(0, 0, 0) E {O, I} wählen kann . Für dieWahl f(O, 0, 0) = 0 kannman die Wahrheitstafel wie folgt sukzessive aufbauen:

x Y Z f(x, y, z)

0 0 0 0

0 0 I I

244

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) v (...,x /\ Y/\ ...,z) v (x /\...,y /\ ...,z) V (x /\ Y/\ z).

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

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

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

x-e----l

z-+-.--i

f(x, y, z)

19 Für die Summe s und den Übertrag ü des Halbaddierers kann man folgendes schreiben, 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 dieLampe mit f(x, y, z) (1 = leuchtet, 0 = leuchtet nicht). Es ergibt sich folgende Wertetabelle.

x y z f(x, y, z)

0 0 0 1


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

245

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

f(x, y, z) = (-,x /\ -,y /\ -,z) v (-,x /\ Y/\ z) V (x /\ -,y /\ z) V (x /\ Y/\ -,z).

Dieser Tenn lässt sich mit dem KV-Verfahrennicht mehr vereinfachen, da sich keineEinser zu Blöcken zusammenfassenlassen.(c) Die zugehörige Gatterschaltung ist in folgender Abbildungdargestellt.

x-e_-(]

Y-.-.-az -H~:L----l

f(x, y, z)

21 Zunächst stellenwir die Wertetabelleder gesuchtenFunktion f auf.

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

0 0 0 0 0

0 0 0 1 0

0 0 1 0 0

0 0 1 1 0

0 1 0 0 0

0 1 0 1 0

0 1 1 0 0

0 1 1 1 1

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

1 0 0 0 0

1 0 0 1 0

1 0 1 0 0

1 0 1 1 1

1 1 0 0 0

1 1 0 1 1

1 1 1 0 1

1 1 1 1 1


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

f(x, y, z) = (-,w 1\ X 1\ Y1\ z) V (w 1\ -,x 1\ Y1\ z) V (w 1\ X 1\ -,y 1\ z)

V (w 1\ X 1\ Y1\ -,z) V (w 1\ X 1\ Y1\ z).

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

y-,y ~ -,y

-,w

-,w

1

I I I

I

~~

z -,zEs können vier Zweierblöcke gebildet werden, die Vereinfachung lautet daher

f(w, x, y, z) = (w 1\ X 1\ z) V (w 1\ Y1\ z) V (w 1\ X 1\ y) V (x 1\ Y1\ z),

Die zugehörige Gatterschaltung ist in folgender Abbildung dargestellt.

w-.----iX-+tI~--1

y-+-t......--1Z--H-h

f(w, x, y, z)

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 I 0 0

0 I 0 I 0

I 0 0 0 I

1 1 1 0 0

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


23 Wie beim Halbaddierer bezeichnen wir die beiden Ausgänge mit s (fiir 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 I 0 0 I

0 I I I 0

I 0 0 0 I

I 0 I I 0

1 1 0 I 0

I I I I I

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

ü = (...,x 1\ Y1\ z) V (x 1\ ...,y 1\ z) V (x 1\ Y1\ ...,z) v (x 1\ Y1\ z),

S = (--,x1\ ...,y 1\ z) V (--,x 1\ Y1\ ...,z) v (x 1\ ...,y 1\ ...,z)v (x 1\ Y1\ z).

Der Ausdruck fiir s lässt sich nicht weiter vereinfachen. Für ü erhält man mit Hilfe eines KV-Diagramms den vereinfachten Ausdruck ü = (x 1\ y) V (y 1\ z) V (x 1\ z). Es ergibt sich folgende Schaltung.

X-._-<aY -t-+-----iz--H -L~

s(X, Y, z)

ü(X, Y, z)


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

X----j

y----j

Z----j

ü

I-;;-:------s

25 Die beiden vierstelligen Binärzahlen seien X3X2XlXound Y3Y2YlYO. Das abgebildete Pa

ralleladdierwerk liefert die Summe dieser Zahlen als fiinfstellige Binärzahl Z4Z3Z2ZtZO.

Xo

Xl

X2

X3 Zo

Zt

Z2Yo

YlZ3

Y2 Z4

Y3

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

altemierende 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 Zahlensysterus 72

Baum 144

Bemoulli, 1. (1654-1705) 33

Bemoullische 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

Binomialzahlcn 48

- explizite Formel 50

- Rekursionsformel 49

bipartitcr Graph 138

Bipartition 138

Blätter 147

Blockchiffre 126

Boolesche Algebra 193

boolesche Funktion 194

boolcschc Operatoren 191

cCäsar, G. J. (100 - 44 v. Chr.) 113

Cäsar-Codc 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 Groppen 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

Diedergmppe 103

Dirichlet, L. (1805 - 1859) 1

A. Beutelspacher, Marc.-A. Zschiegner, Diskrete Mathematikfür Einsteiger, DOI 10.1007/978-3-8348-9941-5, © Vieweg+Teubner Verlag | Springer Fachmedien Wiesbaden GmbH 2011

250

disjunkt 45, 182

Disjunktion 191

disjunktive Nonnalfonn 196

Distributivgesetze 192

Division mit Rest 65

Dominosteine

- ax I-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

EinzeIfehler 94

Electronic Code Book Mode 127

Empfänger 112

Endecke 145,163

endliche Menge 45

Entsch1ü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

eulerscheq>-Funktion 61, 130

Eulersche Polyederforme1 149

Eulersche Zahl 59

eulerscherGraph 141

eulerscherKreis 141

F

Faktor 157

Faktorisie:rung 158

Faktorisie:rungsproblem 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

Fiinffarbensatz (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ßsehePrimzahlen 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


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. 1. (1861 - 1955) 152

Heesch, H. (1906 - 1995) 152

Hexadezimalsystem 73

Hexadezimalzahl 73

Höhe eines binären Baums 147

I

Idempotenzgesetze 193

Implikation 195

lnduktion 27

- lnduktionsbasis 27

- Induktionsschritt 27

- Induktionsverankerung 27

- lnduktionsvoraussetzung 27

- Prinzip der vollständigen Induktion 27

- Prinzip der vollständigen Induktion

(allgemein) 33

inkongruent 67

Inkrement 176

innere Ecke 169

innerlich disjunktcs Wegesystem 185

lnvolutionsgesetz 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 Norrna1forrn 198

Kontrollzeichen 94

Kreis 139

Kryptoanalyse 115

Kryptographie 111

KV-Diagrarnm 199

L

Landkarten schwarz-weiß 34

Länge eines Kreises 139

leere Menge 48

Lemma von Bezout 69

Leonardo von Pisa 36

lineare Komplexität 126

lineares Schieberegister 124

Logarithmus dualis 147

logische Schaltungen 202

251

252

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

Meziriac, 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üsse1ung 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

natiirliche Zahlen 63

natiirlicher Logarithmus 80

Negation 191

Nettofluss 172

Netzwerk 169

neutrales Element 192

Nicht-Operator 191

Norma1form 196

NOR-Verknüpfung 195

Nullfluss 170

ooffene culcrschc 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

Produktforme1 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

Rarnsey, F. P. (1903 -1930) 4

Rarnscy-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


Rückwärtskante 175

sSatz 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

- mxn-Schachbrett 15

Schieberegister 124

Schlüssel 114

Schlüsselwort 116

Schnitt 172

Schubfachprinzip I

- unendliches 7

- verallgemeinertes 7

Sender 112

Senke 163

Shrinking Generator 126

Sieb des Eratosthenes 78

Siebformel 54

Signatureigenschaft 129

Signaturschema 129

Snnpson-Identiilit 40

Skyta1a 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

253

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

vVereinfachen 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

Vigenere, Blaise de 116

Vigcnere-Codc 116

Vigenere-Quadrat 117

visuelle Kryptographie 121

Volladdierer 206

Volldisjunktion 198

Vollkonjunktion 196

vollständige Induktion 27

vollständiger Graph 138

Vorwärtskante 175

254

wWeehselwegnahme 69

Weg 139

Wegesystern 182, 185

Wert eines Flusses 171

Wohldefinicrtheit 85

Wurzel 147

xXOR-Vcrknüpfung 195


zZ 63

Zahlendarstellung 72

Zählen 45

Zahlensystem 72

Zahlentheorie 63

Ziffern 72

Z. 84

z.. 89

zugrundeliegender Graph 165

zulässige Färbung 34

zusammenhängender Graph 139

Documents

Lösungen der Übungsaufgaben - Springer978-3-8348-9941-5/1.pdf · 1 (n+lf, 2 1+2+3+...+(n+l)~(n+lXD+2)f2. Lösungen der Übungsaufgaben 3 6n Punkte aufdem Rand. 215 4 Induktionsverankerung: