View
222
Download
0
Category
Preview:
Citation preview
Was ist Diskrete Mathematik � und wozu?
Christian Krattenthaler
Fakultät für Mathematik, Universität Wien
Christian Krattenthaler Diskrete Mathematik
Was ist Diskrete Mathematik?
diskret . . . 1) unau�ällig, unaufdringlich (Brockhaus)
Diskrete Mathematik ist die Mathematik, die sich im Hintergrundhält.
/∖/∖/∖/∖/∖/∖/∖/∖/∖/∖/∖/∖/∖/∖/∖/∖/∖/∖/∖/∖/∖/∖/∖
Christian Krattenthaler Diskrete Mathematik
Was ist Diskrete Mathematik?
diskret . . .
1) unau�ällig, unaufdringlich (Brockhaus)
Diskrete Mathematik ist die Mathematik, die sich im Hintergrundhält.
/∖/∖/∖/∖/∖/∖/∖/∖/∖/∖/∖/∖/∖/∖/∖/∖/∖/∖/∖/∖/∖/∖/∖
Christian Krattenthaler Diskrete Mathematik
Was ist Diskrete Mathematik?
diskret . . . 1) unau�ällig, unaufdringlich (Brockhaus)
Diskrete Mathematik ist die Mathematik, die sich im Hintergrundhält.
/∖/∖/∖/∖/∖/∖/∖/∖/∖/∖/∖/∖/∖/∖/∖/∖/∖/∖/∖/∖/∖/∖/∖
Christian Krattenthaler Diskrete Mathematik
Was ist Diskrete Mathematik?
diskret . . . 1) unau�ällig, unaufdringlich (Brockhaus)
Diskrete Mathematik ist die Mathematik, die sich im Hintergrundhält.
/∖/∖/∖/∖/∖/∖/∖/∖/∖/∖/∖/∖/∖/∖/∖/∖/∖/∖/∖/∖/∖/∖/∖
Christian Krattenthaler Diskrete Mathematik
Was ist Diskrete Mathematik?
diskret . . . 1) unau�ällig, unaufdringlich (Brockhaus)
Diskrete Mathematik ist die Mathematik, die sich im Hintergrundhält.
/∖/∖/∖/∖/∖/∖/∖/∖/∖/∖/∖/∖/∖/∖/∖/∖/∖/∖/∖/∖/∖/∖/∖
Christian Krattenthaler Diskrete Mathematik
Was ist Diskrete Mathematik?
diskret . . . 1) unau�ällig, unaufdringlich (Brockhaus)
2) taktvoll, rücksichtsvoll (Brockhaus)
Diskrete Mathematik ist die Mathematik, die von auÿerordentlichdiskreten Personen betrieben wird.
/∖/∖/∖/∖/∖/∖/∖/∖/∖/∖/∖/∖/∖/∖/∖/∖/∖/∖/∖/∖/∖/∖/∖
Christian Krattenthaler Diskrete Mathematik
Was ist Diskrete Mathematik?
diskret . . . 1) unau�ällig, unaufdringlich (Brockhaus)2) taktvoll, rücksichtsvoll (Brockhaus)
Diskrete Mathematik ist die Mathematik, die von auÿerordentlichdiskreten Personen betrieben wird.
/∖/∖/∖/∖/∖/∖/∖/∖/∖/∖/∖/∖/∖/∖/∖/∖/∖/∖/∖/∖/∖/∖/∖
Christian Krattenthaler Diskrete Mathematik
Was ist Diskrete Mathematik?
diskret . . . 1) unau�ällig, unaufdringlich (Brockhaus)2) taktvoll, rücksichtsvoll (Brockhaus)
Diskrete Mathematik ist die Mathematik, die von auÿerordentlichdiskreten Personen betrieben wird.
/∖/∖/∖/∖/∖/∖/∖/∖/∖/∖/∖/∖/∖/∖/∖/∖/∖/∖/∖/∖/∖/∖/∖
Christian Krattenthaler Diskrete Mathematik
Was ist Diskrete Mathematik?
diskret . . . 1) unau�ällig, unaufdringlich (Brockhaus)2) taktvoll, rücksichtsvoll (Brockhaus)
Diskrete Mathematik ist die Mathematik, die von auÿerordentlichdiskreten Personen betrieben wird.
/∖/∖/∖/∖/∖/∖/∖/∖/∖/∖/∖/∖/∖/∖/∖/∖/∖/∖/∖/∖/∖/∖/∖
Christian Krattenthaler Diskrete Mathematik
Was ist Diskrete Mathematik?
diskret . . . 1) unau�ällig, unaufdringlich (Brockhaus)2) taktvoll, rücksichtsvoll (Brockhaus)
3) 4 nicht zusammenhängend
Christian Krattenthaler Diskrete Mathematik
Was ist Diskrete Mathematik?
diskret . . . 1) unau�ällig, unaufdringlich (Brockhaus)2) taktvoll, rücksichtsvoll (Brockhaus)3) 4 nicht zusammenhängend
Christian Krattenthaler Diskrete Mathematik
Was ist Diskrete Mathematik?
diskret . . . 1) unau�ällig, unaufdringlich (Brockhaus)2) taktvoll, rücksichtsvoll (Brockhaus)3) 41 nicht zusammenhängend
Ggt.: kontinuierlich (Brockhaus)
14 = MathematikChristian Krattenthaler Diskrete Mathematik
Was ist Diskrete Mathematik?
diskret . . . 1) unau�ällig, unaufdringlich (Brockhaus)2) taktvoll, rücksichtsvoll (Brockhaus)3) 41 nicht zusammenhängend
Ggt.: kontinuierlich (Brockhaus)
14 = MathematikChristian Krattenthaler Diskrete Mathematik
Was ist Diskrete Mathematik?
diskret kommt von lateinisch discretus, das Partizip Perfekt vondiscernere.
Letzteres bedeutet absondern, unterscheiden, trennen.Es ist also das Gegenteil von kontinuierlich, oder synonym: stetig.
De�nition
Die Funktion f ist stetig im Punkt x genau dann, wenn für alleε > 0 ein δ > 0 existiert, sodass für alle x0 mit |x − x0| < δ dieUngleichung |f (x)− f (x0)| < ε gilt.
Christian Krattenthaler Diskrete Mathematik
Was ist Diskrete Mathematik?
diskret kommt von lateinisch discretus, das Partizip Perfekt vondiscernere.Letzteres bedeutet absondern, unterscheiden, trennen.
Es ist also das Gegenteil von kontinuierlich, oder synonym: stetig.
De�nition
Die Funktion f ist stetig im Punkt x genau dann, wenn für alleε > 0 ein δ > 0 existiert, sodass für alle x0 mit |x − x0| < δ dieUngleichung |f (x)− f (x0)| < ε gilt.
Christian Krattenthaler Diskrete Mathematik
Was ist Diskrete Mathematik?
diskret kommt von lateinisch discretus, das Partizip Perfekt vondiscernere.Letzteres bedeutet absondern, unterscheiden, trennen.Es ist also das Gegenteil von kontinuierlich, oder synonym: stetig.
De�nition
Die Funktion f ist stetig im Punkt x genau dann, wenn für alleε > 0 ein δ > 0 existiert, sodass für alle x0 mit |x − x0| < δ dieUngleichung |f (x)− f (x0)| < ε gilt.
Christian Krattenthaler Diskrete Mathematik
Was ist Diskrete Mathematik?
diskret kommt von lateinisch discretus, das Partizip Perfekt vondiscernere.Letzteres bedeutet absondern, unterscheiden, trennen.Es ist also das Gegenteil von kontinuierlich, oder synonym: stetig.
De�nition
Die Funktion f ist stetig im Punkt x genau dann, wenn für alleε > 0 ein δ > 0 existiert, sodass für alle x0 mit |x − x0| < δ dieUngleichung |f (x)− f (x0)| < ε gilt.
Christian Krattenthaler Diskrete Mathematik
Was ist Diskrete Mathematik?
diskret kommt von lateinisch discretus, das Partizip Perfekt vondiscernere.Letzteres bedeutet absondern, unterscheiden, trennen.Es ist also das Gegenteil von kontinuierlich, oder synonym: stetig.
Christian Krattenthaler Diskrete Mathematik
Was ist Diskrete Mathematik?
stetig: diskret:
Christian Krattenthaler Diskrete Mathematik
Was ist Diskrete Mathematik?
stetig: diskret:
Christian Krattenthaler Diskrete Mathematik
Was ist Diskrete Mathematik?
stetig: diskret:
Christian Krattenthaler Diskrete Mathematik
Was ist Diskrete Mathematik?
Diskrete Mathematik beschäftigt sich nicht mitDi�erentialrechnung, Integralrechnung, Di�erentialgleichungen,Integralgleichungen, Kurven, Flächen, kontinuierlichen Bewegungenund Prozessen, . . .
Christian Krattenthaler Diskrete Mathematik
Erwartungen, die ich enttäuschen werde
Industrie- und Wirtschaftsprobleme, und wie DiskreteMathematik diese löst
Christian Krattenthaler Diskrete Mathematik
Erwartungen, die ich enttäuschen werde
Industrie- und Wirtschaftsprobleme, und wie DiskreteMathematik diese löst
Christian Krattenthaler Diskrete Mathematik
Mathematik lässt sich nicht auf eine Hilfswissenschaft derWirtschaft, Industrie, Physik, . . . reduzieren,ja sie muss sich hüten, auf eine solche reduziert zu werden, in ihremeigenen Interesse, aber insbesondere auch im Interesse ihrerAnwendungen!
Christian Krattenthaler Diskrete Mathematik
Nicht weil es nützlich, weil es interessant ist, will man verstehen!
(Rudolf Taschner)
Christian Krattenthaler Diskrete Mathematik
Mathematik lässt sich nicht auf eine Hilfswissenschaft
. . .ja sie muss sich hüten, auf eine solche reduziert zu werden, in ihremeigenen Interesse, aber insbesondere auch im Interesse ihrerAnwendungen!
Christian Krattenthaler Diskrete Mathematik
Der (geistige) Vater der heute verwendeten Internetverschlüsselungist Leonhard Euler!
Ron Rivest, Adi Shamir, Len Adleman erfanden dieRSA-Verschlüsselung.Aber die verwendete Mathematik stammt ausschlieÿlich von Euler,aus einer Zeit, wo nicht nur die Worte ,,Kryptographie� und,,Internet� völlig unbekannt waren . . .
Christian Krattenthaler Diskrete Mathematik
Der (geistige) Vater der heute verwendeten Internetverschlüsselungist Leonhard Euler!Ron Rivest, Adi Shamir, Len Adleman erfanden dieRSA-Verschlüsselung.
Aber die verwendete Mathematik stammt ausschlieÿlich von Euler,aus einer Zeit, wo nicht nur die Worte ,,Kryptographie� und,,Internet� völlig unbekannt waren . . .
Christian Krattenthaler Diskrete Mathematik
Der (geistige) Vater der heute verwendeten Internetverschlüsselungist Leonhard Euler!Ron Rivest, Adi Shamir, Len Adleman erfanden dieRSA-Verschlüsselung.Aber die verwendete Mathematik stammt ausschlieÿlich von Euler,aus einer Zeit, wo nicht nur die Worte ,,Kryptographie� und,,Internet� völlig unbekannt waren . . .
Christian Krattenthaler Diskrete Mathematik
Erwartungen, die ich enttäuschen werde
Industrie- und Wirtschaftsprobleme, und wie DiskreteMathematik diese löst
Einblicke in neue eigene Resultate
Christian Krattenthaler Diskrete Mathematik
Erwartungen, die ich enttäuschen werde
Industrie- und Wirtschaftsprobleme, und wie DiskreteMathematik diese löst
Einblicke in neue eigene Resultate
Christian Krattenthaler Diskrete Mathematik
Satz
Die Anzahl der Multiketten x1 ≤ x2 ≤ · · · ≤ xl−1 im Poset der
m-teilbaren nichtkreuzenden Partitionen assoziiert zur
Spiegelungsgruppe vom Typ Dn mit Rang(xi ) = s1 + s2 + · · ·+ si ,
i = 1, 2, . . . , l − 1, ist durch
2
(n − 1
s1
)(m(n − 1)
s2
)· · ·
(m(n − 1)
sl
)+m
l∑j=2
(n − 1
s1
)(m(n − 1)
s2
)· · ·
(m(n − 1)− 1
sj − 2
)· · ·
(m(n − 1)
sl
)
+
(n − 2
s1 − 2
)(m(n − 1)
s2
)· · ·
(m(n − 1)
sl
)gegeben, wo s1 + s2 + · · ·+ sl = n.
Christian Krattenthaler Diskrete Mathematik
Erwartungen, die ich enttäuschen werde
Industrie- und Wirtschaftsprobleme, und wie DiskreteMathematik diese löst
Einblicke in neue eigene Resultate
Christian Krattenthaler Diskrete Mathematik
Wieviele?
Wieviele Lottotipps gibt es 6 aus 45?
� ��� ��� ��� ��� ��� ��↑
45 Möglichkeiten
Also insgesamt:
45 · 44 · 43 · 42 · 41 · 406 · 5 · 4 · 3 · 2 · 1
= 8145060.
Christian Krattenthaler Diskrete Mathematik
Wieviele?
Wieviele Lottotipps gibt es 6 aus 45?
� ��� ��� ��� ��� ��� ��↑
45 Möglichkeiten
Also insgesamt:
45 · 44 · 43 · 42 · 41 · 406 · 5 · 4 · 3 · 2 · 1
= 8145060.
Christian Krattenthaler Diskrete Mathematik
Wieviele?
Wieviele Lottotipps gibt es 6 aus 45?
� ��� ��� ��� ��� ��� ��
↑45 Möglichkeiten
Also insgesamt:
45 · 44 · 43 · 42 · 41 · 406 · 5 · 4 · 3 · 2 · 1
= 8145060.
Christian Krattenthaler Diskrete Mathematik
Wieviele?
Wieviele Lottotipps gibt es 6 aus 45?
� ��� ��� ��� ��� ��� ��↑
45 Möglichkeiten
Also insgesamt:
45 · 44 · 43 · 42 · 41 · 406 · 5 · 4 · 3 · 2 · 1
= 8145060.
Christian Krattenthaler Diskrete Mathematik
Wieviele?
Wieviele Lottotipps gibt es 6 aus 45?
13� ��� ��� ��� ��� ��� ��
↑44 Möglichkeiten
Also insgesamt:
45 · 44 · 43 · 42 · 41 · 406 · 5 · 4 · 3 · 2 · 1
= 8145060.
Christian Krattenthaler Diskrete Mathematik
Wieviele?
Wieviele Lottotipps gibt es 6 aus 45?
13� ��� ��� ��� ��� ��� ��↑
44 Möglichkeiten
Also insgesamt:
45 · 44 · 43 · 42 · 41 · 406 · 5 · 4 · 3 · 2 · 1
= 8145060.
Christian Krattenthaler Diskrete Mathematik
Wieviele?
Wieviele Lottotipps gibt es 6 aus 45?
13� ��34� ��� ��� ��� ��� ��
↑43 Möglichkeiten
Also insgesamt:
45 · 44 · 43 · 42 · 41 · 406 · 5 · 4 · 3 · 2 · 1
= 8145060.
Christian Krattenthaler Diskrete Mathematik
Wieviele?
Wieviele Lottotipps gibt es 6 aus 45?
13� ��34� ��� ��� ��� ��� ��
↑43 Möglichkeiten
Also insgesamt:
45 · 44 · 43 · 42 · 41 · 406 · 5 · 4 · 3 · 2 · 1
= 8145060.
Christian Krattenthaler Diskrete Mathematik
Wieviele?
Wieviele Lottotipps gibt es 6 aus 45?
13� ��34� ��
10� ��� ��� ��� ��
↑42 Möglichkeiten
Also insgesamt:
45 · 44 · 43 · 42 · 41 · 406 · 5 · 4 · 3 · 2 · 1
= 8145060.
Christian Krattenthaler Diskrete Mathematik
Wieviele?
Wieviele Lottotipps gibt es 6 aus 45?
13� ��34� ��
10� ��� ��� ��� ��↑
42 Möglichkeiten
Also insgesamt:
45 · 44 · 43 · 42 · 41 · 406 · 5 · 4 · 3 · 2 · 1
= 8145060.
Christian Krattenthaler Diskrete Mathematik
Wieviele?
Wieviele Lottotipps gibt es 6 aus 45?
13� ��34� ��
10� ��41� ��� ��� ��
↑41 Möglichkeiten
Also insgesamt:
45 · 44 · 43 · 42 · 41 · 406 · 5 · 4 · 3 · 2 · 1
= 8145060.
Christian Krattenthaler Diskrete Mathematik
Wieviele?
Wieviele Lottotipps gibt es 6 aus 45?
13� ��34� ��
10� ��41� ��� ��� ��
↑41 Möglichkeiten
Also insgesamt:
45 · 44 · 43 · 42 · 41 · 406 · 5 · 4 · 3 · 2 · 1
= 8145060.
Christian Krattenthaler Diskrete Mathematik
Wieviele?
Wieviele Lottotipps gibt es 6 aus 45?
13� ��34� ��
10� ��41� ��
36� ��� ��
↑40 Möglichkeiten
Also insgesamt:
45 · 44 · 43 · 42 · 41 · 406 · 5 · 4 · 3 · 2 · 1
= 8145060.
Christian Krattenthaler Diskrete Mathematik
Wieviele?
Wieviele Lottotipps gibt es 6 aus 45?
13� ��34� ��
10� ��41� ��
36� ��� ��↑
40 Möglichkeiten
Also insgesamt:
45 · 44 · 43 · 42 · 41 · 406 · 5 · 4 · 3 · 2 · 1
= 8145060.
Christian Krattenthaler Diskrete Mathematik
Wieviele?
Wieviele Lottotipps gibt es 6 aus 45?
13� ��34� ��
10� ��41� ��
36� ��23� ��
↑40 Möglichkeiten
Also insgesamt:
45 · 44 · 43 · 42 · 41 · 406 · 5 · 4 · 3 · 2 · 1
= 8145060.
Christian Krattenthaler Diskrete Mathematik
Wieviele?
Wieviele Lottotipps gibt es 6 aus 45?
13� ��34� ��
10� ��41� ��
36� ��23� ��
Also insgesamt:
45 · 44 · 43 · 42 · 41 · 40
↑40 Möglichkeiten
Christian Krattenthaler Diskrete Mathematik
Wieviele?
Wieviele Lottotipps gibt es 6 aus 45?
13� ��34� ��
10� ��41� ��
36� ��23� ��
Also insgesamt:
45 · 44 · 43 · 42 · 41 · 40
↑40 Möglichkeiten
Christian Krattenthaler Diskrete Mathematik
Wieviele?
Wieviele Lottotipps gibt es 6 aus 45?
10� ��13� ��
23� ��34� ��
36� ��41� ��
Also insgesamt:
45 · 44 · 43 · 42 · 41 · 406 · 5 · 4 · 3 · 2 · 1
= 8145060.
↑40 Möglichkeiten
Christian Krattenthaler Diskrete Mathematik
Wieviele?
Wieviele Lottotipps gibt es 6 aus 45?
10� ��13� ��
23� ��34� ��
36� ��41� ��
Also insgesamt:
45 · 44 · 43 · 42 · 41 · 406 · 5 · 4 · 3 · 2 · 1
= 8145060.
↑40 Möglichkeiten
Christian Krattenthaler Diskrete Mathematik
Wieviele?
45 · 44 · 43 · 42 · 41 · 406 · 5 · 4 · 3 · 2 · 1
= 8145060.
Die Wahrscheinlichkeit, den richtigen Tipp zu landen, ist also
1
8145060= 0.000000122774 . . .
Die Wahrscheinlichkeit, das nicht zu tun, ist
1− 1
8145060= 0.999999877226 . . .
Christian Krattenthaler Diskrete Mathematik
Wieviele?
45 · 44 · 43 · 42 · 41 · 406 · 5 · 4 · 3 · 2 · 1
= 8145060.
Die Wahrscheinlichkeit, den richtigen Tipp zu landen, ist also
1
8145060= 0.000000122774 . . .
Die Wahrscheinlichkeit, das nicht zu tun, ist
1− 1
8145060= 0.999999877226 . . .
Christian Krattenthaler Diskrete Mathematik
Wieviele?
45 · 44 · 43 · 42 · 41 · 406 · 5 · 4 · 3 · 2 · 1
= 8145060.
Die Wahrscheinlichkeit, den richtigen Tipp zu landen, ist also
1
8145060= 0.000000122774 . . .
Die Wahrscheinlichkeit, das nicht zu tun, ist
1− 1
8145060= 0.999999877226 . . .
Christian Krattenthaler Diskrete Mathematik
Wieviele?
Wieviele Teilnehmer an einer Ziehung braucht es, dass wenigstenseiner (mit 50% Wahrscheinlichkeit) den richtigen Tipp errät?
0.9999998772265500000 = 0.509026 . . .
Mehr als 5.5 Millionen!
Christian Krattenthaler Diskrete Mathematik
Wieviele?
Wieviele Teilnehmer an einer Ziehung braucht es, dass wenigstenseiner (mit 50% Wahrscheinlichkeit) den richtigen Tipp errät?
0.9999998772265500000 = 0.509026 . . .
Mehr als 5.5 Millionen!
Christian Krattenthaler Diskrete Mathematik
Wieviele?
Wieviele Teilnehmer an einer Ziehung braucht es, dass wenigstenseiner (mit 50% Wahrscheinlichkeit) den richtigen Tipp errät?
0.9999998772265500000 = 0.509026 . . .
Mehr als 5.5 Millionen!
Christian Krattenthaler Diskrete Mathematik
Wieviele?
Die Frage der Abzählung (,,Wieviele?�) taucht nicht nur in derWahrscheinlichkeitsrechnung, sondern in fast allen Gebieten derMathematik auf, sie ist die Grundlage für Laufzeitanalysen vonComputeralgorithmen, für die Analyse von Modellen derStatistischen Physik, um nur einige zu nennen.
Christian Krattenthaler Diskrete Mathematik
Das Wägeproblem
1 2 3 4 5 6
7 8 9 10 11 12
Christian Krattenthaler Diskrete Mathematik
Das Wägeproblem
1 2 3 4 5 6
7 8 9 10 11 12
Christian Krattenthaler Diskrete Mathematik
Das Wägeproblem
1 2
3 4 5 6
7 8
9 10 11 12
Christian Krattenthaler Diskrete Mathematik
Das Wägeproblem
1 2
3 4 5 6
7 8
9 10 11 12
1 2 3
4 5 6
Christian Krattenthaler Diskrete Mathematik
Das Wägeproblem
1 2
3 4 5 6
7 8
9 10 11 12
1 2 3
4 5 6
1 2 3 7
Christian Krattenthaler Diskrete Mathematik
Das Wägeproblem
1 2
3 4 5 6
7 8
9 10 11 12
1 2 3
4 5 6
1 2 3 7
4
5
Christian Krattenthaler Diskrete Mathematik
Das Wägeproblem
Abstrakt:
Zu Beginn gibt es genau 24 Möglichkeiten:Münze 1 ist zu schwer/zu leicht, . . . , Münze 12 ist zu schwer/zuleicht.
Bei jeder Wägung gibt es 3 mögliche Ausgänge.
Strategie: Konstruiere die Wägungen so, dass bei jeder Wägung dieAnzahl der Möglichkeiten (in etwa) gedrittelt wird.
Christian Krattenthaler Diskrete Mathematik
Das Wägeproblem
Abstrakt:
Zu Beginn gibt es genau 24 Möglichkeiten:Münze 1 ist zu schwer/zu leicht, . . . , Münze 12 ist zu schwer/zuleicht.
Bei jeder Wägung gibt es 3 mögliche Ausgänge.
Strategie: Konstruiere die Wägungen so, dass bei jeder Wägung dieAnzahl der Möglichkeiten (in etwa) gedrittelt wird.
Christian Krattenthaler Diskrete Mathematik
Das Wägeproblem
Abstrakt:
Zu Beginn gibt es genau 24 Möglichkeiten:Münze 1 ist zu schwer/zu leicht, . . . , Münze 12 ist zu schwer/zuleicht.
Bei jeder Wägung gibt es 3 mögliche Ausgänge.
Strategie: Konstruiere die Wägungen so, dass bei jeder Wägung dieAnzahl der Möglichkeiten (in etwa) gedrittelt wird.
Christian Krattenthaler Diskrete Mathematik
Das Wägeproblem
Abstrakt:
Zu Beginn gibt es genau 24 Möglichkeiten:Münze 1 ist zu schwer/zu leicht, . . . , Münze 12 ist zu schwer/zuleicht.
Bei jeder Wägung gibt es 3 mögliche Ausgänge.
Strategie: Konstruiere die Wägungen so, dass bei jeder Wägung dieAnzahl der Möglichkeiten (in etwa) gedrittelt wird.
Christian Krattenthaler Diskrete Mathematik
Das Wägeproblem
Also:
Christian Krattenthaler Diskrete Mathematik
Das Wägeproblem
Also:
24
Christian Krattenthaler Diskrete Mathematik
Das Wägeproblem
Also:
24
8 8 8
Christian Krattenthaler Diskrete Mathematik
Das Wägeproblem
Also:
24
8 8 8
3 3 2 3 3 2 3 3 2
Christian Krattenthaler Diskrete Mathematik
Das Wägeproblem
Also:
24
8 8 8
3 3 2 3 3 2 3 3 2
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
Christian Krattenthaler Diskrete Mathematik
Das Wägeproblem
Wie haben wir das gemacht?
1 2
3 4 5 6
7 8
9 10 11 12
Falls links schwerer: 1S, 2S, 3S, 4S, 5S, 6S, 7L, 8L, 9L, 10L,11L, 12L (12 Möglichkeiten)
Christian Krattenthaler Diskrete Mathematik
Das Wägeproblem
Wie haben wir das gemacht?
1 2
3 4 5 6
7 8
9 10 11 12
Falls links schwerer: 1S, 2S, 3S, 4S, 5S, 6S, 7L, 8L, 9L, 10L,11L, 12L (12 Möglichkeiten)
Christian Krattenthaler Diskrete Mathematik
Das Wägeproblem
Wie haben wir das gemacht?
1 2
3 4 5 6
7 8
9 10 11 12
Falls links schwerer: 1S, 2S, 3S, 4S, 5S, 6S, 7L, 8L, 9L, 10L,11L, 12L (12 Möglichkeiten)
Christian Krattenthaler Diskrete Mathematik
Das Wägeproblem
Wie haben wir das gemacht?
1 2
3 4 5 67 8
9 10 11 12
Falls links schwerer: 1S, 2S, 3S, 4S, 5S, 6S, 7L, 8L, 9L, 10L,11L, 12L (12 Möglichkeiten)
Falls links leichter: 1L, 2L, 3L, 4L, 5L, 6L, 7S, 8S, 9S, 10S,11S, 12S (12 Möglichkeiten)
Christian Krattenthaler Diskrete Mathematik
Das Wägeproblem
Wie haben wir das gemacht?
1 2
3 4 5 6
7 8
9 10 11 12
Falls links schwerer: 1S, 2S, 3S, 4S, 5S, 6S, 7L, 8L, 9L, 10L,11L, 12L (12 Möglichkeiten)
Falls links leichter: 1L, 2L, 3L, 4L, 5L, 6L, 7S, 8S, 9S, 10S,11S, 12S (12 Möglichkeiten)
Falls Gleichgewicht: Unmöglich! (0 Möglichkeiten)
Also: 12:12:0 statt 8:8:8. Extrem ungeschickt!Wir hätten etwa Münzen 1,2,3,4 gegen die Münzen 5,6,7,8abwägen sollen.Wenn man es richtig macht, kann man die falsche Münzetatsächlich immer in 3 Wägungen bestimmen.
Christian Krattenthaler Diskrete Mathematik
Das Wägeproblem
Wie haben wir das gemacht?
1 2
3 4 5 6
7 8
9 10 11 12
Falls links schwerer: 1S, 2S, 3S, 4S, 5S, 6S, 7L, 8L, 9L, 10L,11L, 12L (12 Möglichkeiten)
Falls links leichter: 1L, 2L, 3L, 4L, 5L, 6L, 7S, 8S, 9S, 10S,11S, 12S (12 Möglichkeiten)
Falls Gleichgewicht: Unmöglich! (0 Möglichkeiten)
Also:
12:12:0 statt 8:8:8. Extrem ungeschickt!Wir hätten etwa Münzen 1,2,3,4 gegen die Münzen 5,6,7,8abwägen sollen.Wenn man es richtig macht, kann man die falsche Münzetatsächlich immer in 3 Wägungen bestimmen.
Christian Krattenthaler Diskrete Mathematik
Das Wägeproblem
Wie haben wir das gemacht?
1 2
3 4 5 6
7 8
9 10 11 12
Falls links schwerer: 1S, 2S, 3S, 4S, 5S, 6S, 7L, 8L, 9L, 10L,11L, 12L (12 Möglichkeiten)
Falls links leichter: 1L, 2L, 3L, 4L, 5L, 6L, 7S, 8S, 9S, 10S,11S, 12S (12 Möglichkeiten)
Falls Gleichgewicht: Unmöglich! (0 Möglichkeiten)
Also: 12:12:0 statt 8:8:8.
Extrem ungeschickt!Wir hätten etwa Münzen 1,2,3,4 gegen die Münzen 5,6,7,8abwägen sollen.Wenn man es richtig macht, kann man die falsche Münzetatsächlich immer in 3 Wägungen bestimmen.
Christian Krattenthaler Diskrete Mathematik
Das Wägeproblem
Wie haben wir das gemacht?
1 2
3 4 5 6
7 8
9 10 11 12
Falls links schwerer: 1S, 2S, 3S, 4S, 5S, 6S, 7L, 8L, 9L, 10L,11L, 12L (12 Möglichkeiten)
Falls links leichter: 1L, 2L, 3L, 4L, 5L, 6L, 7S, 8S, 9S, 10S,11S, 12S (12 Möglichkeiten)
Falls Gleichgewicht: Unmöglich! (0 Möglichkeiten)
Also: 12:12:0 statt 8:8:8. Extrem ungeschickt!
Wir hätten etwa Münzen 1,2,3,4 gegen die Münzen 5,6,7,8abwägen sollen.Wenn man es richtig macht, kann man die falsche Münzetatsächlich immer in 3 Wägungen bestimmen.
Christian Krattenthaler Diskrete Mathematik
Das Wägeproblem
Wie haben wir das gemacht?
1 2
3 4 5 6
7 8
9 10 11 12
Falls links schwerer: 1S, 2S, 3S, 4S, 5S, 6S, 7L, 8L, 9L, 10L,11L, 12L (12 Möglichkeiten)
Falls links leichter: 1L, 2L, 3L, 4L, 5L, 6L, 7S, 8S, 9S, 10S,11S, 12S (12 Möglichkeiten)
Falls Gleichgewicht: Unmöglich! (0 Möglichkeiten)
Also: 12:12:0 statt 8:8:8. Extrem ungeschickt!Wir hätten etwa Münzen 1,2,3,4 gegen die Münzen 5,6,7,8abwägen sollen.
Wenn man es richtig macht, kann man die falsche Münzetatsächlich immer in 3 Wägungen bestimmen.
Christian Krattenthaler Diskrete Mathematik
Das Wägeproblem
Wie haben wir das gemacht?
1 2
3 4 5 6
7 8
9 10 11 12
Falls links schwerer: 1S, 2S, 3S, 4S, 5S, 6S, 7L, 8L, 9L, 10L,11L, 12L (12 Möglichkeiten)
Falls links leichter: 1L, 2L, 3L, 4L, 5L, 6L, 7S, 8S, 9S, 10S,11S, 12S (12 Möglichkeiten)
Falls Gleichgewicht: Unmöglich! (0 Möglichkeiten)
Also: 12:12:0 statt 8:8:8. Extrem ungeschickt!Wir hätten etwa Münzen 1,2,3,4 gegen die Münzen 5,6,7,8abwägen sollen.Wenn man es richtig macht, kann man die falsche Münzetatsächlich immer in 3 Wägungen bestimmen.
Christian Krattenthaler Diskrete Mathematik
Der erste Hauptsatz der Informationstheorie von Claude
Shannon
Versucht man unter N Möglichkeiten die richtige mit Hilfe von
Tests zu �nden, die k mögliche Ausgänge haben,
dann geht das (im
schlechtesten Fall) nicht schneller als in
logk(N)
Tests.
Beim Wägeproblem: N = 24, k = 3;
log3(24) = 2.89279 . . .
(x = logk(N) ist jene Zahl, sodass kx = N gilt.)
Christian Krattenthaler Diskrete Mathematik
Der erste Hauptsatz der Informationstheorie von Claude
Shannon
Versucht man unter N Möglichkeiten die richtige mit Hilfe von
Tests zu �nden, die k mögliche Ausgänge haben,
dann geht das (im
schlechtesten Fall) nicht schneller als in
logk(N)
Tests.
Beim Wägeproblem: N = 24, k = 3;
log3(24) = 2.89279 . . .
(x = logk(N) ist jene Zahl, sodass kx = N gilt.)
Christian Krattenthaler Diskrete Mathematik
Der erste Hauptsatz der Informationstheorie von Claude
Shannon
Versucht man unter N Möglichkeiten die richtige mit Hilfe von
Tests zu �nden, die k mögliche Ausgänge haben,
dann geht das (im
schlechtesten Fall) nicht schneller als in
logk(N)
Tests.
Beim Wägeproblem: N = 24, k = 3;
log3(24) = 2.89279 . . .
(x = logk(N) ist jene Zahl, sodass kx = N gilt.)
Christian Krattenthaler Diskrete Mathematik
Der erste Hauptsatz der Informationstheorie von Claude
Shannon
Versucht man unter N Möglichkeiten die richtige mit Hilfe von
Tests zu �nden, die k mögliche Ausgänge haben, dann geht das (im
schlechtesten Fall) nicht schneller als in
logk(N)
Tests.
Beim Wägeproblem: N = 24, k = 3;
log3(24) = 2.89279 . . .
(x = logk(N) ist jene Zahl, sodass kx = N gilt.)
Christian Krattenthaler Diskrete Mathematik
Der erste Hauptsatz der Informationstheorie von Claude
Shannon
Versucht man unter N Möglichkeiten die richtige mit Hilfe von
Tests zu �nden, die k mögliche Ausgänge haben, dann geht das (im
schlechtesten Fall) nicht schneller als in
logk(N)
Tests.
Beim Wägeproblem: N = 24, k = 3;
log3(24) = 2.89279 . . .
(x = logk(N) ist jene Zahl, sodass kx = N gilt.)
Christian Krattenthaler Diskrete Mathematik
Der erste Hauptsatz der Informationstheorie von Claude
Shannon
Versucht man unter N Möglichkeiten die richtige mit Hilfe von
Tests zu �nden, die k mögliche Ausgänge haben, dann geht das (im
schlechtesten Fall) nicht schneller als in
logk(N)
Tests.
Beim Wägeproblem: N = 24, k = 3; log3(24) = 2.89279 . . .
(x = logk(N) ist jene Zahl, sodass kx = N gilt.)
Christian Krattenthaler Diskrete Mathematik
Das Wägeproblem
Wir be�nden uns mit dem Wägeproblem mitten in derInformationstheorie, die die theoretischen Grundlagen fürSuchprobleme bereitstellt.
Die Probleme von Datenkompression, von Datensortierung gehörenhier ebenso her, wie der intelligente Aufbau von Datenbankenbeziehungsweise die Entwicklung von e�zienten Algorithmen zurAu�ndung von Daten in Datenbanken.
Christian Krattenthaler Diskrete Mathematik
Das Wägeproblem
Wir be�nden uns mit dem Wägeproblem mitten in derInformationstheorie, die die theoretischen Grundlagen fürSuchprobleme bereitstellt.Die Probleme von Datenkompression, von Datensortierung gehörenhier ebenso her, wie der intelligente Aufbau von Datenbankenbeziehungsweise die Entwicklung von e�zienten Algorithmen zurAu�ndung von Daten in Datenbanken.
Christian Krattenthaler Diskrete Mathematik
Die Brücken von Königsberg
Hier ist Königsberg am Fluss Pregel:
Ist es möglich einen Spaziergang zu unternehmen, der jede Brückegenau einmal passiert und schlussendlich zum Ausgangspunktzurückkehrt?
Christian Krattenthaler Diskrete Mathematik
Die Brücken von Königsberg
Hier ist Königsberg am Fluss Pregel:
Ist es möglich einen Spaziergang zu unternehmen, der jede Brückegenau einmal passiert und schlussendlich zum Ausgangspunktzurückkehrt?
Christian Krattenthaler Diskrete Mathematik
Die Brücken von Königsberg
Hier ist Königsberg am Fluss Pregel:
Ist es möglich einen Spaziergang zu unternehmen, der jede Brückegenau einmal passiert und schlussendlich zum Ausgangspunktzurückkehrt?
Christian Krattenthaler Diskrete Mathematik
Die Brücken von Königsberg
Schematisch:
Christian Krattenthaler Diskrete Mathematik
Die Brücken von Königsberg
Ein Versuch eines ,,Brückenrundganges�:
Christian Krattenthaler Diskrete Mathematik
Die Brücken von Königsberg
Ein Versuch eines ,,Brückenrundganges�:
Christian Krattenthaler Diskrete Mathematik
Die Brücken von Königsberg
Ein Versuch eines ,,Brückenrundganges�:
Christian Krattenthaler Diskrete Mathematik
Die Brücken von Königsberg
Ein Versuch eines ,,Brückenrundganges�:
Christian Krattenthaler Diskrete Mathematik
Die Brücken von Königsberg
Ein Versuch eines ,,Brückenrundganges�:
Christian Krattenthaler Diskrete Mathematik
Die Brücken von Königsberg
Ein Versuch eines ,,Brückenrundganges�:
Christian Krattenthaler Diskrete Mathematik
Die Brücken von Königsberg
Ein Versuch eines ,,Brückenrundganges�:
Hmm . . .
Christian Krattenthaler Diskrete Mathematik
Die Brücken von Königsberg
Ein Versuch eines ,,Brückenrundganges�:
Hmm . . .
Christian Krattenthaler Diskrete Mathematik
Die Brücken von Königsberg
Abstrahieren wir:
Setzen wir in jedes der vier Landstücke einen dicken Punkt,
Christian Krattenthaler Diskrete Mathematik
Die Brücken von Königsberg
Abstrahieren wir:
Setzen wir in jedes der vier Landstücke einen dicken Punkt,
Christian Krattenthaler Diskrete Mathematik
Die Brücken von Königsberg
Abstrahieren wir:
Setzen wir in jedes der vier Landstücke einen dicken Punkt,
und verbinden wir Punkte, falls die entsprechenden Landstückedurch Brücken verbunden sind.
Christian Krattenthaler Diskrete Mathematik
Die Brücken von Königsberg
Abstrahieren wir:
Die neue Aufgabe: Man �nde einen geschlossenen Weg entlang derstrichlierten Linien, die jede strichlierte Linie genau einmal passiert.
sdfsdf sdfsdfs dfB
Christian Krattenthaler Diskrete Mathematik
Die Brücken von Königsberg
Leonhard Eulers Beobachtung:
Wenn wir uns auf einen der dicken Punkte konzentrieren, müssenwir auf einem geschlossenen Weg genauso oft im Punkt ankommen,wie wir ihn verlassen.
Christian Krattenthaler Diskrete Mathematik
Die Brücken von Königsberg
Leonhard Eulers Beobachtung:
Wenn wir uns auf einen der dicken Punkte konzentrieren, müssenwir auf einem geschlossenen Weg genauso oft im Punkt ankommen,wie wir ihn verlassen.
Christian Krattenthaler Diskrete Mathematik
Die Brücken von Königsberg
Leonhard Eulers Beobachtung:
Wenn wir uns auf einen der dicken Punkte konzentrieren, müssenwir auf einem geschlossenen Weg genauso oft im Punkt ankommen,wie wir ihn verlassen.
Christian Krattenthaler Diskrete Mathematik
Die Brücken von Königsberg
Leonhard Eulers Beobachtung:
Wenn wir uns auf einen der dicken Punkte konzentrieren, müssenwir auf einem geschlossenen Weg genauso oft im Punkt ankommen,wie wir ihn verlassen.
Christian Krattenthaler Diskrete Mathematik
Die Brücken von Königsberg
Leonhard Eulers Beobachtung:
Wenn wir uns auf einen der dicken Punkte konzentrieren, müssenwir auf einem geschlossenen Weg genauso oft im Punkt ankommen,wie wir ihn verlassen.
Christian Krattenthaler Diskrete Mathematik
Die Brücken von Königsberg
Leonhard Eulers Beobachtung:
Wenn wir uns auf einen der dicken Punkte konzentrieren, müssenwir auf einem geschlossenen Weg genauso oft im Punkt ankommen,wie wir ihn verlassen.
Christian Krattenthaler Diskrete Mathematik
Die Brücken von Königsberg
Leonhard Eulers Beobachtung:
Wenn wir uns auf einen der dicken Punkte konzentrieren, müssenwir auf einem geschlossenen Weg genauso oft im Punkt ankommen,wie wir ihn verlassen.
Christian Krattenthaler Diskrete Mathematik
Die Brücken von Königsberg
Leonhard Eulers Beobachtung:
Wenn wir uns auf einen der dicken Punkte konzentrieren, müssenwir auf einem geschlossenen Weg genauso oft im Punkt ankommen,wie wir ihn verlassen.
Jeder Punkt muss mit einer geraden Anzahl von strichlierten Linienverbunden sein!
Christian Krattenthaler Diskrete Mathematik
Die Brücken von Königsberg
Leonhard Eulers Beobachtung:
Wenn wir uns auf einen der dicken Punkte konzentrieren, müssenwir auf einem geschlossenen Weg genauso oft im Punkt ankommen,wie wir ihn verlassen.
Jeder Punkt muss mit einer geraden Anzahl von strichlierten Linienverbunden sein!
Christian Krattenthaler Diskrete Mathematik
Die Brücken von Königsberg
Unsere Figur:
Sogar jeder (!) Knoten ist mit einer ungeraden Anzahl vonstrichlierten Linien verbunden.Es kann also so einen Spaziergang nicht geben!
Christian Krattenthaler Diskrete Mathematik
Die Brücken von Königsberg
Unsere Figur:
Sogar jeder (!) Knoten ist mit einer ungeraden Anzahl vonstrichlierten Linien verbunden.
Es kann also so einen Spaziergang nicht geben!
Christian Krattenthaler Diskrete Mathematik
Die Brücken von Königsberg
Unsere Figur:
Sogar jeder (!) Knoten ist mit einer ungeraden Anzahl vonstrichlierten Linien verbunden.Es kann also so einen Spaziergang nicht geben!
Christian Krattenthaler Diskrete Mathematik
Der Satz von Euler
In einer zusammenhängenden Figur, die aus dicken Punkten und
strichlierten Linien besteht, welche dicke Punkte verbinden, gibt es
genau dann einen geschlossenen Weg, der jede Linie genau einmal
passiert, wenn jeder dicke Punkt mit einer geraden Anzahl von
strichlierten Linien verbunden ist.
Christian Krattenthaler Diskrete Mathematik
Der Satz von Euler
In einer zusammenhängenden Figur, die aus dicken Punkten und
strichlierten Linien besteht, welche dicke Punkte verbinden, gibt es
genau dann einen geschlossenen Weg, der jede Linie genau einmal
passiert, wenn jeder dicke Punkt mit einer geraden Anzahl von
strichlierten Linien verbunden ist.
Christian Krattenthaler Diskrete Mathematik
Die Brücken von Königsberg
Die Lösung des Königsberger Brückenproblems wird oft als dieGeburtsstunde der sogenannten Graphentheorie2 bezeichnet.
Und damit ist man in der Netzwerktheorie und insbesondere derkombinatorischen Optimierung.
2Unter Graphen versteht man in diesem Zusammenhang solche Figuren, die
aus dicken Punkten bestehen, die zum Teil durch Linien verbunden sind.Christian Krattenthaler Diskrete Mathematik
Die Brücken von Königsberg
Die Lösung des Königsberger Brückenproblems wird oft als dieGeburtsstunde der sogenannten Graphentheorie2 bezeichnet.
Und damit ist man in der Netzwerktheorie und insbesondere derkombinatorischen Optimierung.
2Unter Graphen versteht man in diesem Zusammenhang solche Figuren, die
aus dicken Punkten bestehen, die zum Teil durch Linien verbunden sind.Christian Krattenthaler Diskrete Mathematik
Ein listiger Streich
�jeu de taquin� (= Neckspiel)
1 2 3 4
5 6 7 8
9 10 11 12
13 14 15
Christian Krattenthaler Diskrete Mathematik
Ein listiger Streich
�jeu de taquin"
1 2 3 4
5 6 7 8
9 10 11 12
13 14 15
Christian Krattenthaler Diskrete Mathematik
Ein listiger Streich
�jeu de taquin" (= Neckspiel)
1 2 3 4
5 6 7 8
9 10 11 12
13 14 15
Christian Krattenthaler Diskrete Mathematik
Ein listiger Streich
�jeu de taquin� (= Neckspiel)
1 2 3 4
5 6 7 8
9 10 11
13 14 15 12
Christian Krattenthaler Diskrete Mathematik
Ein listiger Streich
�jeu de taquin� (= Neckspiel)
1 2 3 4
5 6 7 8
9 10 11
13 14 15 12
Christian Krattenthaler Diskrete Mathematik
Ein listiger Streich
�jeu de taquin� (= Neckspiel)
1 2 3 4
5 6 7 8
9 10 11
13 14 15 12
Christian Krattenthaler Diskrete Mathematik
Ein listiger Streich
�jeu de taquin� (= Neckspiel)
1 2 3 4
5 7 8
9 6 10 11
13 14 15 12
Christian Krattenthaler Diskrete Mathematik
Ein listiger Streich
�jeu de taquin� (= Neckspiel)
1 2 3 4
5 7 8
9 6 10 11
13 14 15 12
Christian Krattenthaler Diskrete Mathematik
Ein listiger Streich
�jeu de taquin� (= Neckspiel)
1 2 4
5 7 3 8
9 6 10 11
13 14 15 12
Christian Krattenthaler Diskrete Mathematik
Ein listiger Streich
�jeu de taquin� (= Neckspiel)
1 2 4
5 7 3 8
9 6 10 11
13 14 15 12
Christian Krattenthaler Diskrete Mathematik
Ein listiger Streich
�jeu de taquin� (= Neckspiel)
1 2 4
5 7 3 8
9 6 10 11
13 14 15 12
Christian Krattenthaler Diskrete Mathematik
Ein listiger Streich
�jeu de taquin� (= Neckspiel)
5 1 2 4
7 3 8
9 6 10 11
13 14 15 12
Christian Krattenthaler Diskrete Mathematik
Ein listiger Streich
�jeu de taquin� (= Neckspiel)
5 1 2 4
9 7 3 8
6 10 11
13 14 15 12
Christian Krattenthaler Diskrete Mathematik
Ein listiger Streich
�jeu de taquin� (= Neckspiel)
5 1 2 4
9 7 3 8
13 6 10 11
14 15 12
Christian Krattenthaler Diskrete Mathematik
Ein listiger Streich
�jeu de taquin� (= Neckspiel)
5 1 2 4
9 7 3 8
13 6 10 11
14 15 12
Christian Krattenthaler Diskrete Mathematik
Ein listiger Streich
�jeu de taquin� (= Neckspiel)
5 1 2 4
9 7 3 8
13 6 10 11
14 15 12
Christian Krattenthaler Diskrete Mathematik
Ein listiger Streich
�jeu de taquin� (= Neckspiel)
5 1 2 4
9 7 3 8
13 6 10 11
14 15 12
Christian Krattenthaler Diskrete Mathematik
Ein listiger Streich
�jeu de taquin� (= Neckspiel)
15 14 13 12
11 10 9 8
7 6 5 4
3 2 1
Christian Krattenthaler Diskrete Mathematik
Ein listiger Streich
15 14 13 12
11 10 9 8
7 6 5 4
3 2 1 16
Christian Krattenthaler Diskrete Mathematik
Ein listiger Streich
15 14 13 12
11 10 9 8
7 6 5 4
3 2 1 16
15 14 13 12 11 10 9 8 7 6 5 4 3 2 1 16
15 14 13 12 11 10 9 8 7 6 5 4 3 2 1 16
−→ Jede Spielsituation entspricht einer bestimmten Anordnung(,,Permutation�) der Zahlen von 1 bis 16.
Christian Krattenthaler Diskrete Mathematik
Ein listiger Streich
15 14 13 12
11 10 9 8
7 6 5 4
3 2 1 16
15 14 13 12 11 10 9 8 7 6 5 4 3 2 1 16
15 14 13 12 11 10 9 8 7 6 5 4 3 2 1 16
−→ Jede Spielsituation entspricht einer bestimmten Anordnung(,,Permutation�) der Zahlen von 1 bis 16.
Christian Krattenthaler Diskrete Mathematik
Ein listiger Streich
15 14 13 12
11 10 9 8
7 6 5 4
3 2 1 16
15 14 13 12 11 10 9 8 7 6 5 4 3 2 1 16
15 14 13 12 11 10 9 8 7 6 5 4 3 2 1 16
−→ Jede Spielsituation entspricht einer bestimmten Anordnung(,,Permutation�) der Zahlen von 1 bis 16.
Christian Krattenthaler Diskrete Mathematik
Ein listiger Streich
15 14 13 12
11 10 9 8
7 6 5 4
3 2 1 16
15 14 13 12 11 10 9 8 7 6 5 4 3 2 1 16
15 14 13 12 11 10 9 8 7 6 5 4 3 2 1 16
−→ Jede Spielsituation entspricht einer bestimmten Anordnung(,,Permutation�) der Zahlen von 1 bis 16.
Christian Krattenthaler Diskrete Mathematik
Ein listiger Streich
Aufgabe:
Bringe die Zahlen
15 14 13 12 11 10 9 8 7 6 5 4 3 2 1 16
durch sukzessives Vertauschen von zwei Zahlen in die richtigeOrdnung
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
Satz
Für eine gegebene Permutation ist die Anzahl der Vertauschungen,
die man benötigt immer eine gerade Anzahl oder immer eine
ungerade Anzahl.
Christian Krattenthaler Diskrete Mathematik
Ein listiger Streich
Aufgabe:Bringe die Zahlen
15 14 13 12 11 10 9 8 7 6 5 4 3 2 1 16
durch sukzessives Vertauschen von zwei Zahlen in die richtigeOrdnung
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
Satz
Für eine gegebene Permutation ist die Anzahl der Vertauschungen,
die man benötigt immer eine gerade Anzahl oder immer eine
ungerade Anzahl.
Christian Krattenthaler Diskrete Mathematik
Ein listiger Streich
Aufgabe:Bringe die Zahlen
15 14 13 12 11 10 9 8 7 6 5 4 3 2 1 16
durch sukzessives Vertauschen von zwei Zahlen in die richtigeOrdnung
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
Satz
Für eine gegebene Permutation ist die Anzahl der Vertauschungen,
die man benötigt immer eine gerade Anzahl oder immer eine
ungerade Anzahl.
Christian Krattenthaler Diskrete Mathematik
Ein listiger Streich
Ordnen wir also
15 14 13 12 11 10 9 8 7 6 5 4 3 2 1 16
durch Vertauschungen:
15 14 13 12 11 10 9 8 7 6 5 4 3 2 1 16
Christian Krattenthaler Diskrete Mathematik
Ein listiger Streich
Ordnen wir also
15 14 13 12 11 10 9 8 7 6 5 4 3 2 1 16
durch Vertauschungen:
15 14 13 12 11 10 9 8 7 6 5 4 3 2 1 16
Christian Krattenthaler Diskrete Mathematik
Ein listiger Streich
Ordnen wir also
15 14 13 12 11 10 9 8 7 6 5 4 3 2 1 16
durch Vertauschungen:
15 14 13 12 11 10 9 8 7 6 5 4 3 2 1 16
Christian Krattenthaler Diskrete Mathematik
Ein listiger Streich
Ordnen wir also
15 14 13 12 11 10 9 8 7 6 5 4 3 2 1 16
durch Vertauschungen:
1 14 13 12 11 10 9 8 7 6 5 4 3 2 15 16
Christian Krattenthaler Diskrete Mathematik
Ein listiger Streich
Ordnen wir also
15 14 13 12 11 10 9 8 7 6 5 4 3 2 1 16
durch Vertauschungen:
1 14 13 12 11 10 9 8 7 6 5 4 3 2 15 16
Christian Krattenthaler Diskrete Mathematik
Ein listiger Streich
Ordnen wir also
15 14 13 12 11 10 9 8 7 6 5 4 3 2 1 16
durch Vertauschungen:
1 14 13 12 11 10 9 8 7 6 5 4 3 2 15 16
Christian Krattenthaler Diskrete Mathematik
Ein listiger Streich
Ordnen wir also
15 14 13 12 11 10 9 8 7 6 5 4 3 2 1 16
durch Vertauschungen:
1 2 13 12 11 10 9 8 7 6 5 4 3 14 15 16
Christian Krattenthaler Diskrete Mathematik
Ein listiger Streich
Ordnen wir also
15 14 13 12 11 10 9 8 7 6 5 4 3 2 1 16
durch Vertauschungen:
1 2 13 12 11 10 9 8 7 6 5 4 3 14 15 16
Christian Krattenthaler Diskrete Mathematik
Ein listiger Streich
Ordnen wir also
15 14 13 12 11 10 9 8 7 6 5 4 3 2 1 16
durch Vertauschungen:
1 2 13 12 11 10 9 8 7 6 5 4 3 14 15 16
Christian Krattenthaler Diskrete Mathematik
Ein listiger Streich
Ordnen wir also
15 14 13 12 11 10 9 8 7 6 5 4 3 2 1 16
durch Vertauschungen:
1 2 3 12 11 10 9 8 7 6 5 4 13 14 15 16
Christian Krattenthaler Diskrete Mathematik
Ein listiger Streich
Ordnen wir also
15 14 13 12 11 10 9 8 7 6 5 4 3 2 1 16
durch Vertauschungen:
1 2 3 12 11 10 9 8 7 6 5 4 13 14 15 16
Christian Krattenthaler Diskrete Mathematik
Ein listiger Streich
Ordnen wir also
15 14 13 12 11 10 9 8 7 6 5 4 3 2 1 16
durch Vertauschungen:
1 2 3 12 11 10 9 8 7 6 5 4 13 14 15 16
Christian Krattenthaler Diskrete Mathematik
Ein listiger Streich
Ordnen wir also
15 14 13 12 11 10 9 8 7 6 5 4 3 2 1 16
durch Vertauschungen:
1 2 3 4 11 10 9 8 7 6 5 12 13 14 15 16
Christian Krattenthaler Diskrete Mathematik
Ein listiger Streich
Ordnen wir also
15 14 13 12 11 10 9 8 7 6 5 4 3 2 1 16
durch Vertauschungen:
1 2 3 4 11 10 9 8 7 6 5 12 13 14 15 16
Christian Krattenthaler Diskrete Mathematik
Ein listiger Streich
Ordnen wir also
15 14 13 12 11 10 9 8 7 6 5 4 3 2 1 16
durch Vertauschungen:
1 2 3 4 11 10 9 8 7 6 5 12 13 14 15 16
Christian Krattenthaler Diskrete Mathematik
Ein listiger Streich
Ordnen wir also
15 14 13 12 11 10 9 8 7 6 5 4 3 2 1 16
durch Vertauschungen:
1 2 3 4 5 10 9 8 7 6 11 12 13 14 15 16
Christian Krattenthaler Diskrete Mathematik
Ein listiger Streich
Ordnen wir also
15 14 13 12 11 10 9 8 7 6 5 4 3 2 1 16
durch Vertauschungen:
1 2 3 4 5 10 9 8 7 6 11 12 13 14 15 16
Christian Krattenthaler Diskrete Mathematik
Ein listiger Streich
Ordnen wir also
15 14 13 12 11 10 9 8 7 6 5 4 3 2 1 16
durch Vertauschungen:
1 2 3 4 5 10 9 8 7 6 11 12 13 14 15 16
Christian Krattenthaler Diskrete Mathematik
Ein listiger Streich
Ordnen wir also
15 14 13 12 11 10 9 8 7 6 5 4 3 2 1 16
durch Vertauschungen:
1 2 3 4 5 6 9 8 7 10 11 12 13 14 15 16
Christian Krattenthaler Diskrete Mathematik
Ein listiger Streich
Ordnen wir also
15 14 13 12 11 10 9 8 7 6 5 4 3 2 1 16
durch Vertauschungen:
1 2 3 4 5 6 9 8 7 10 11 12 13 14 15 16
Christian Krattenthaler Diskrete Mathematik
Ein listiger Streich
Ordnen wir also
15 14 13 12 11 10 9 8 7 6 5 4 3 2 1 16
durch Vertauschungen:
1 2 3 4 5 6 9 8 7 10 11 12 13 14 15 16
Christian Krattenthaler Diskrete Mathematik
Ein listiger Streich
Ordnen wir also
15 14 13 12 11 10 9 8 7 6 5 4 3 2 1 16
durch Vertauschungen:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
Christian Krattenthaler Diskrete Mathematik
Ein listiger Streich
Ordnen wir also
15 14 13 12 11 10 9 8 7 6 5 4 3 2 1 16
durch Vertauschungen:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
Das waren 7 Vertauschungen, eine ungerade Anzahl vonVertauschungen.Daher: Egal wie man es macht, man braucht eine ungerade Anzahlvon Zügen!
Christian Krattenthaler Diskrete Mathematik
Ein listiger Streich
Ordnen wir also
15 14 13 12 11 10 9 8 7 6 5 4 3 2 1 16
durch Vertauschungen:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
Das waren 7 Vertauschungen, eine ungerade Anzahl vonVertauschungen.
Daher: Egal wie man es macht, man braucht eine ungerade Anzahlvon Zügen!
Christian Krattenthaler Diskrete Mathematik
Ein listiger Streich
Ordnen wir also
15 14 13 12 11 10 9 8 7 6 5 4 3 2 1 16
durch Vertauschungen:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
Das waren 7 Vertauschungen, eine ungerade Anzahl vonVertauschungen.Daher: Egal wie man es macht, man braucht eine ungerade Anzahlvon Zügen!
Christian Krattenthaler Diskrete Mathematik
Ein listiger Streich
15 14 13 12
11 10 9 8
7 6 5 4
3 2 1
Aber, wenn am Anfang und am Ende das leere Feld rechts untensein soll, dann geht das nur in einer geraden Anzahl von Zügen!
Christian Krattenthaler Diskrete Mathematik
Ein listiger Streich
15 14 13 12
11 10 9 8
7 6 5 4
3 2 1 •
Aber, wenn am Anfang und am Ende das leere Feld rechts untensein soll, dann geht das nur in einer geraden Anzahl von Zügen!
Christian Krattenthaler Diskrete Mathematik
Ein listiger Streich
15 14 13 12
11 10 9 8
7 6 5 4
3 2 • 1
Aber, wenn am Anfang und am Ende das leere Feld rechts untensein soll, dann geht das nur in einer geraden Anzahl von Zügen!
Christian Krattenthaler Diskrete Mathematik
Ein listiger Streich
15 14 13 12
11 10 9 8
7 6 • 4
3 2 5 1
Aber, wenn am Anfang und am Ende das leere Feld rechts untensein soll, dann geht das nur in einer geraden Anzahl von Zügen!
Christian Krattenthaler Diskrete Mathematik
Ein listiger Streich
15 14 13 12
11 10 • 8
7 6 9 4
3 2 5 1
Aber, wenn am Anfang und am Ende das leere Feld rechts untensein soll, dann geht das nur in einer geraden Anzahl von Zügen!
Christian Krattenthaler Diskrete Mathematik
Ein listiger Streich
15 14 13 12
11 • 10 8
7 6 9 4
3 2 5 1
Aber, wenn am Anfang und am Ende das leere Feld rechts untensein soll, dann geht das nur in einer geraden Anzahl von Zügen!
Christian Krattenthaler Diskrete Mathematik
Ein listiger Streich
15 14 13 12
• 11 10 8
7 6 9 4
3 2 5 1
Aber, wenn am Anfang und am Ende das leere Feld rechts untensein soll, dann geht das nur in einer geraden Anzahl von Zügen!
Christian Krattenthaler Diskrete Mathematik
Ein listiger Streich
15 14 13 12
7 11 10 8
• 6 9 4
3 2 5 1
Aber, wenn am Anfang und am Ende das leere Feld rechts untensein soll, dann geht das nur in einer geraden Anzahl von Zügen!
Christian Krattenthaler Diskrete Mathematik
Ein listiger Streich
15 14 13 12
7 11 10 8
3 6 9 4
• 2 5 1
Aber, wenn am Anfang und am Ende das leere Feld rechts untensein soll, dann geht das nur in einer geraden Anzahl von Zügen!
Christian Krattenthaler Diskrete Mathematik
Ein listiger Streich
15 14 13 12
7 11 10 8
3 6 9 4
2 • 5 1
Aber, wenn am Anfang und am Ende das leere Feld rechts untensein soll, dann geht das nur in einer geraden Anzahl von Zügen!
Christian Krattenthaler Diskrete Mathematik
Ein listiger Streich
15 14 13 12
7 11 10 8
3 6 9 4
2 5 • 1
Aber, wenn am Anfang und am Ende das leere Feld rechts untensein soll, dann geht das nur in einer geraden Anzahl von Zügen!
Christian Krattenthaler Diskrete Mathematik
Ein listiger Streich
15 14 13 12
7 11 10 8
3 6 9 4
2 5 1 •
Aber, wenn am Anfang und am Ende das leere Feld rechts untensein soll, dann geht das nur in einer geraden Anzahl von Zügen!
Christian Krattenthaler Diskrete Mathematik
Ein listiger Streich
Die natürliche Umgebung des jeu de taquin-Spieles gehört zumGebiet der Algebra: Gruppentheorie.
Im konkreten Fall haben wir es mit einer sogenanntenSpiegelungsgruppe oder Coxetergruppe zu tun.
Christian Krattenthaler Diskrete Mathematik
Ein listiger Streich
Die natürliche Umgebung des jeu de taquin-Spieles gehört zumGebiet der Algebra: Gruppentheorie.Im konkreten Fall haben wir es mit einer sogenanntenSpiegelungsgruppe oder Coxetergruppe zu tun.
Christian Krattenthaler Diskrete Mathematik
Statistische Physik
Statistische Physik versucht globale Phänomene zu analysieren, diesich aus lokalen Beschränkungen ergeben.
Christian Krattenthaler Diskrete Mathematik
Statistische Physik
Statistische Physik versucht globale Phänomene zu analysieren, diesich aus lokalen Beschränkungen ergeben.
Christian Krattenthaler Diskrete Mathematik
Statistische Physik
(idealisiertes) Eis:
H
HO
Christian Krattenthaler Diskrete Mathematik
Statistische Physik
(idealisiertes) Eis:
H
HO
Christian Krattenthaler Diskrete Mathematik
Statistische Physik
(idealisiertes) Eis:
H H H H H
H
H
H
H
H
H H H H
H H H H
H H H H
H H H H
H H H H
H H H H
H H H H
H H H H
H H H H
H H H H
O O O O O
O O O O O
O O O O O
O O O O O
O O O O O
Christian Krattenthaler Diskrete Mathematik
Statistische Physik
(idealisiertes) Eis:
H H H H H
H
H
H
H
H
H H H H
H H H H
H H H H
H H H H
H H H H
H H H H
H H H H
H H H H
H H H H
H H H H
O O O O O
O O O O O
O O O O O
O O O O O
O O O O O
Christian Krattenthaler Diskrete Mathematik
Statistische Physik
(idealisiertes) Eis:
P�asterungen!
Christian Krattenthaler Diskrete Mathematik
Statistische Physik
(idealisiertes) Eis:
P�asterungen!
Christian Krattenthaler Diskrete Mathematik
Statistische Physik
Der ,,Arktische Kreis�(Jockush, Propp, Shor)
Christian Krattenthaler Diskrete Mathematik
Statistische Physik
Der ,,Arktische Kreis�(Jockush, Propp, Shor)
Christian Krattenthaler Diskrete Mathematik
Statistische Physik
Der ,,Arktische Kreis�(Cohen, Larsen, Propp)
Christian Krattenthaler Diskrete Mathematik
Statistische Physik
Der ,,Arktische Kreis�(Cohen, Larsen, Propp)
Christian Krattenthaler Diskrete Mathematik
Statistische Physik
(Kenyon, Okounkov)Christian Krattenthaler Diskrete Mathematik
6
3
0
1
1
0
37
26
0
4
3
6
7
7
86
2
45
4
7
15
1
3
9
7
7
3
24
4
4
4
4
6
3
7
3
9
9 5
9
2
4
6
73
1
6
0
6
08
2
00
3
3
6
9
2
6
5
78
0
9
1
5
4 8
3
6 9
1
6
86
7
00
5
8
1
5
7
6
3
2
9
9
8
8
1
1 5
14
4
1
9
3
2
0
2
0
1
3
4
5
9
0
7
4
5
5
1
2
7
40
3
9
9
2
5 2
9
5
4
4
1
5
7
3
2
9
0
9
3
9
6
7
4
4
7
51
6
7
9
4
7
7
9
40
1
6
47
6
9
1
8
5
9 6
8
4
68
9
8
6
7
2
6
4
3
98
2
9
0
1
9
4
6
8
4
4
8
4
3
9
6
8
1
14
2
5
68
5
5
7
0
7
6
4
9
43
3
3
7
5
81
6
8
4
4
5
4
4
5
77
81
0
8
6
6
6
8
3
4
58
8
7
3
7
9
0
6
2
2
9
1
2
6
3
1
5
6
8
4
7
1
7
2
0
8
6
0
61
2
7
9
6
3
111
5
1
11
5
4
9
1
2
6
01
2
5
9
12
Christian Krattenthaler Diskrete Mathematik
8888888
88
88
88
88
888
7777777
666 6
6
6 666
666
5555555
555
555 4
444444 4 4
44
4 4444 3
333333
3 3 3
3 3 3
3 3 3
222222
2 2 2 2 2
1111111
1 1 1
1 1 1
1 1 1
0000000000
0000000
1111111
11111
1
1 1 1
222222
2 2 2 2 2
3333333
3 3 3 3
3333333
4444444
4 4 4
4 4 4
4 4 4
5555555555
5555555
6666666
66666
6
6 6 6
777777
7 7 7 7 7
8888888
9999999
999
999
Christian Krattenthaler Diskrete Mathematik
Recommended