GT 1: Aussagenlogik

Eine wichtige Grundlage der klassischen Logik ist das Prinzip der Zweiwertigkeit: Jede Aussage besitzt einen von genau zwei Wahrheitswerten.
Das bedeutet, dass jede Aussage entweder “wahr” oder “falsch” ist.
Daraus folgt offenbar sofort, dass jede nicht wahre Aussage falsch ist und jede nicht falsche Aussage wahr.
Formal lässt sich das zum Beispiel mit dem Negationsoperator\neg” darstellen:

\neg “wahr” = “falsch” und
\neg “falsch” = “wahr”

Für wahre Aussagen A schreibt und sagt man oft “Es gilt A”, “A gilt”, “A ist wahr”, “A stimmt” oder ähnliches.

Weitere wichtige Operatoren (neben \neg) sind das logische “und” und das logische “oder”, symbolisiert durch
\land bzw. \lor.
So steht

A \land B für die Aussage “A \text{ und } B” und
A \lor B für die Aussage “A \text{ oder } B“.

A \land B ist dabei dann und nur dann wahr, wenn sowohl A als auch B wahre Aussagen sind.
A \lor B ist genau dann wahr, wenn

  • A wahr ist und B falsch ist,
  • A falsch ist und B wahr ist oder
  • A \land B gilt.

    Formal lässt sich diese Tatsache wie folgt ausdrücken.

    A \lor B ~\Longleftrightarrow~ (A \land \neg B) \text{ oder } (\neg A \land B) \text{ oder } (A \land B) bzw.
    A \lor B ~\Longleftrightarrow~ (A \land \neg B) \lor (\neg A \land B) \lor (A \land B).

    Der Äquivalenzpfeil\Longleftrightarrow” bedeutet dabei für zwei Aussagen C und D mit C ~\Longleftrightarrow~ D, dass C genau dann gilt, wenn D gilt.
    C und D haben also denselben Wahrheitswert.

Tabellarisch lassen “\land“, “\lor” und \Longleftrightarrow sich wie folgt definieren:

\begin{tabular}{r|cc}<br />
\ensuremath{\land} & wahr & falsch \\<br />
\hline<br />
wahr & wahr & falsch \\<br />
falsch & falsch & falsch<br />
\end{tabular}

\begin{tabular}{r|cc}<br />
\ensuremath{\lor} & wahr & falsch \\<br />
\hline<br />
wahr & wahr & wahr \\<br />
falsch & wahr & falsch<br />
\end{tabular}

\begin{tabular}{r|cc}<br />
\ensuremath{\Longleftrightarrow} & wahr & falsch \\<br />
\hline<br />
wahr & wahr & falsch \\<br />
falsch & falsch & wahr<br />
\end{tabular}

Dabei sind die Tabellen für eine belibiege zweistellige Verknüpfung “\circ” immer wie folgt aufgebaut:
\begin{tabular}{r|cc}<br />
\ensuremath{\circ} & Aussage \ensuremath{A} \\<br />
\hline<br />
Aussage \ensuremath{B} & \ensuremath{A \circ B}<br />
\end{tabular}

Abkürzend schreibt man dabei oft auch einfach “1″ für “wahr” und “0″ für falsch.
So definieren wir nun noch die Implikation\Rightarrow” bzw. “\Leftarrow“:

\begin{tabular}{r|cc}<br />
\ensuremath{\Rightarrow} & 1 & 0 \\<br />
\hline<br />
1 & 1 & 1 \\<br />
0 & 0 & 1<br />
\end{tabular}
und analog
\begin{tabular}{r|cc}<br />
\ensuremath{\Leftarrow} & 1 & 0 \\<br />
\hline<br />
1 & 1 & 0 \\<br />
0 & 1 & 1<br />
\end{tabular}

Im Gegensatz zu den Verknüpfungen \land, \lor \text{ und } \Longleftrightarrow sind \Rightarrow und \Leftarrow nicht kommutativ (D.h. hier die Tabellen sind nicht symmetrisch. Eine präzisere Definition des Begriffs der Kommutativität wird in einem späteren Artikel dieser Serie gegeben.)

Es gilt (A \circ B) ~\Longleftrightarrow~ (B \circ A), falls \circ eine der drei Verknüpfungen \land, \lor \text{ oder } \Longleftrightarrow ist.
Außerdem gilt (A ~\Rightarrow~ B) ~\Longleftrightarrow~ (B ~\Leftarrow~ A), wie durch die Symbole angedeutet.

Diese vier Behauptungen mit Hilfe der tabellarischen Definitionen nachzuvollziehen sei dem Leser als Verständnisübung überlassen.

Auf zwei weitere wichtige logische Symbole soll in diesem Artikel noch eingegangen werden.
Es handelt sich um den Allquantor \forall und den Existenzquantor \exists.

Der Allquantor bedeutet sprachlich “für alle”, auf ihn folgt immer eine Variable sowie eine davon abhängige Aussage. Sei A(x) eine Aussage, die von x abhängig ist, das heißt eine Aussage über x. Ist A(x) für alle x wahr, so schreibt man dies wie folgt:

\forall x \colon A(x) (sprich: “für alle x gilt A(x)“)

Ähnliches gilt für den Existenzquantor:

\exists x \colon A(x) bedeutet, “es existiert (mindestens) ein x, für das A(x) gilt”.
Die Schreibweise \exists ! x \colon A(x) bedeutet, “es existiert genau ein x, für das A(x) gilt”.

Hängt A(x, y) von zwei Parametern x und y ab, so bedeutet
\forall x \colon \exists y \colon A(x, y) also zum Beispiel, dass sich zu jedem x ein y finden lässt, so dass A(x, y) erfüllt ist.

Definiert man A(x,y) beispielsweise für natürliche Zahlen x und y als x = y, dann gilt die obige Aussage offenbar, denn es gilt

\forall x \colon x = x woraus \forall x \colon \exists y \colon x = y folgt.

Anmerkung: Wir schreiben auch gelegentlich A(x) ~~\forall x anstelle von \forall x \colon A(x), wenn dies nicht zu Verwechselungen führen kann.

Serie: Gruppentheorie

In den nächsten Wochen und Monaten wird eine Artikelserie zum Thema “Gruppentheorie” erscheinen. Die Gruppentheorie ist ein Teilgebiet der Algebra und ist für die gesamte Mathematik fundamental. Eine Gruppe ist eine Struktur, die gewisse Bedingungen erfüllt, so dass einige wichtige Rechenregeln gelten.

Bei der Artikelserie soll es sich um eine Einführung handeln, die sich insbesondere an Leser ohne Vorkenntnisse richtet.
Das Ziel ist es, grundlegende Aspekte der Gruppentheorie verständlich zu vermitteln.
Auf die in der Mathematik notwendige logische Strenge soll und kann dennoch nicht verzichtet werden.

Das inhaltliche Ziel der Artikelserie ist der sogenannte “Satz von Cayley”, ein zugleich wichtiges und überraschendes Resultat über endliche Gruppen. Zur Motivation sei dieser Satz schon jetzt angegeben.

Satz von Cayley
Jede endliche Gruppe G der Ordnung \text{ord} (G) = n \in \mathbb{N} ist isomorph zu einer Untergruppe der symmetrischen Gruppe S_n.

Alle verwendeten Begriffe werden im Laufe der Artikelserie ausreichend erläutert. Auch den anschließenden Beweis des Satzes wird der interessierte Leser nach der Lektüre nachvollziehen können.

Die Artikel dieser Serie im Überblick:

  1. Teil 1: Aussagenlogik
  2. Teil 2: Mengenlehre
  3. Teil 3: Abbildungen
  4. Teil 4: Verknüpfungen
  5. Teil 5: Gruppen
  6. . . .

Die Liste wird bis zum Ende der Artikelserie gegebenenfalls ergänzt oder strukturellen Änderungen unterzogen und soll lediglich einen Einblick in (und einen Überblick über) die Themen ermöglichen.

Erweiterung des Lemmas von Bézout

Nach einiger Zeit komme ich nun (endlich) mal wieder dazu, einen Artikel hier zu veröffentlichen.
Diesmal handelt es sich um einen Beweis einer Erweiterung von Bézouts Lemma,
den ich vor einigen Wochen fand, als ich mich mit einer Aufgabe aus der zweiten Runde des Bundeswettbewerbs Mathematik rumschlug.

Ich hoffe, einen zwar recht kurzen aber dennoch interessanten Artikel geschrieben haben zu können.

Neben der nicht mehr ganz so anschaulichen Formulierung gibt es eine weitere Besonderheit:
Diesmal steht der Artikel als PDF-Datei zum Download zur Verfügung:
http://mathe.florian-severin.de/downloads/bezout.pdf

Viel Spaß damit!

Turm von Hanoi

Turm von HanoiVon mathegenius inspiriert möchte ich nun, wie dort angekündigt einige Überlegungen zum Turm von Hanoi anstellen und vorführen.
Wer die Legende noch nicht kennt, sollte sich diesen Artikel (von mathegenius) ansehen.
Etwas verallgemeinert werde ich in diesem Artikel Überlegungen für beliebig viele Scheiben anstellen, nicht nur für die ursprünglichen 64.
Eine Frage, die sich stellt ist natürlich die nach der Anzahl der nötigen Schritte.
Diese Frage wollen wir zunächst für einige wenige Scheiben beantworten, und dann verallgemeinern.

Wir benennen die drei Stapelplätze dafür zunächst mit A, B und C. Auf dem Platz A liegen die Scheiben in der Ausgangsposition, Ziel soll es sein, sie auf den Platz B zu verlegen. Die Scheiben seien mit 1 bis n benannt, je kleiner die Ziffer dabei ist, desto kleiner sei auch die Scheibe.

Für eine Scheibe ist die Lösung trivial, trotzdem sei sie hier genannt:
Man verschiebt einfach die Scheibe von A nach B.
Wir benötigen einen Schritt.

Auch zwei Scheiben sollten noch kein Problem darstellen:
A --> C
A --> B
C --> B

Dafür brauchen wir drei Schritte.

An die Aufgabe, einen Turm aus drei Scheiben zu verschieben wollen wir systematischer herangehen.
Wie machen wir das?
Naja, wenn wir es irgendwie schaffen könnten, die untere, größte Scheibe auf den Platz B zu befördern, hätten wir unser Problem reduziert. Nun müssten nur noch die beiden Scheiben von A nach B verschoben werden – die Lösung dafür haben wir schon.
Also gut, wir haben den Plan, die große Scheibe auf Platz B zu bringen. Was müssen wir dazu tun? Klar, der Platz B darf nicht belegt sein. Außerdem muss die große Scheibe zum Bewegen frei sein. Wohin mit den Scheiben 1 und 2?
Hm, Glück gehabt, Platz C ist noch nicht benutzt in unserem Gedankenspiel!
Das einzige, was noch zu erledigen ist, ist nun also, die beiden kleineren Scheiben auf Platz C zu verlegen.
Auch das ist aber nicht schwierig – wie man zwei Scheiben verschiebt wissen wir schließlich.
Aber funktionieren auch alle unsere Schritte, ist zwischendurch vielleicht doch ein Platz belegt, den wir vergessen haben?
Versuchen wir einfach mal, alles zusammen zu puzzeln.

  1. Verschiebe die beiden oberen Scheiben nach C.
    Das geht in jedem Fall, wir ignorieren einfach die unterste Scheibe und führen dann unsere Lösung für zwei Scheiben durch – wobei natürlich C statt B zu benutzen ist.
  2. Lege die große Scheibe von A nach B.
    Das geht auch, schließlich liegen die anderen beiden Scheiben auf C.
  3. Verschiebe die beiden Scheiben von C nach B.
    Auch das funktioniert wieder, mit der Lösung für zwei Scheiben.

Wieviele Verschiebungen benötigen wir nun dafür?
Für den ersten Schritt sind es drei, wie wir zuvor herausgefunden haben.
Der zweite Schritt ist nur eine einzige Verschiebung.
Und der dritte Schritt ist wieder eine Bewegung von zwei Scheiben, benötigt also insgesamt ebenfalls drei einzelne Verschiebungen.
Zusammen macht das also sieben Züge.

Aber mit vier Scheiben wird es vielleicht etwas kniffliger. Schließlich können die vier Scheiben ja auch einen Platz mehr blockieren – oder?
Probieren wir einfach mal das gleiche System aus, wie bei drei Scheiben:

  1. Verschiebe die drei oberen Scheiben von A nach C.
    Hm. Das ist lösbar, haben wir ja schon gesehen.
    Wir benötigen sieben Verschiebungen.
  2. Verschiebe die vierte Scheibe auf Platz B.
    Auch das ist möglich, die anderen Scheiben liegen ja auf Platz C. Machbar in einer einzigen Bewegung.
  3. Zum Abschluss, verschiebe die drei Scheiben, die auf C zwischengelagert waren auch nach B.
    Das kostet wiederum sieben Schritte.

Insgesamt brauchen wir also 2 \cdot 7 + 1 = 15 Züge.

Das sollte erstmal reichen. Jetzt versuchen wir noch, das Prinzip ganz allgemein zu beschreiben.
Dabei wollen wir auch sofort herausfinden, wie viele Züge nötig sind.
Führen wir dafür erstmal eine Benennung ein:
Sei also S(n) die Anzahl der Schritte, die benötigt werden, um n Scheiben zu verschieben.

Nun stellen wir uns vor, wir haben einen Turm aus n Scheiben. Für n = 1 geben wir die triviale Lösung vor, alle weiteren Fälle wollen wir jetzt induktiv lösen.
Dazu nehmen wir an, dass wir den Wert von S(n - 1) kennen. Auch wie wir die n - 1 Scheiben von einem Platz auf den anderen verschieben setzen wir als bekannt voraus.

Jetzt soll es aber auch losgehen, wir beschreiben unser Verfahren:

  1. Wir schieben mit dem bekannten Verfahren für n - 1 Scheiben die obersten Scheiben von Platz A nach C.
    Dafür benötigen wir genau S(n - 1) Schritte.
  2. Wir legen die größte, gewissermaßen die “neue”, Scheibe auf Platz B.
    Das kostet eine einzige Verschiebung.
  3. Nun bewegen wir den hohen Stapel von C nach B, wofür wiederum S(n - 1) Züge nötig sind.

Damit haben wir aus der Lösung für n - 1 Scheiben eine Lösung für n Scheiben erhalten!
Weil wir die (schnellste) Lösung für n = 1 schon kennen, finden wir also auch eine Zugfolge, um 2 Scheiben zu bewegen.
Daraus entwickeln wir dann den Weg für 3 Scheiben, woraus wiederum derjenige mit 4 Scheiben gefunden wird.
So geht es immer weiter, ad infinitum.
Großartig, wir können nun also den Turm von Hanoi lösen, und das für beliebig viele Scheiben!

Auch die Anzahl können wir bestimmen. Schließlich gilt, wie wir gerade gesehen haben, S(n) = 2 \cdot S(n - 1) + 1.
Daraus kann man S(n) = 2^n - 1 finden. Dass dieser Wert tatsächlich stimmt, ist noch etwas einfacher zu zeigen, als ihn herzuleiten; nämlich mit unserer Induktion.
Denn:
S(n) = 2 \cdot S(n - 1) + 1 = 2 \cdot (2^{n-1} - 1) + 1 = 2^n - 2 + 1 = 2^n - 1

Also ist diese Formel tatsächlich richtig.

Für die in der Legende genannten 64 Scheiben benötigt man daher S(64) = 2^{64} - 1 = 18.446.744.073.709.551.615 \approx 18 \cdot 10^{18} Verschiebungen.
Würde für jeden Zug eine Sekunde benötigt, so dauerte das Unterfangen (falls es nicht pausiert würde) etwa 584.942.417.355 Jahre an. Das entspricht den auch von mathegenius genannten 5,8 Milliarden Jahrhunderten [bis zum Ende des Universums ;)].
Unvorstellbar!

Das Geburtstagsparadoxon

Geburtstagstorte
Wieder einmal ein Artikel über paradox Erscheinendes aus der (kombinatorischen) Wahrscheinlichkeitsrechnung: Das sogenannte “Geburtstagsparadoxon”.

Beim Geburtstagsparadoxon geht es um die – erstaunlich hohe – Wahrscheinlichkeit, dass bei einer vorher festgelegten (zufälligen) Menge von mehreren Personen mindestens zwei von ihnen am selben Tag ihren Geburtstag feiern.

Um die Fehleinschätzung zu demonstrieren: Was glauben Sie, ab welcher Personenzahl diese Wahrscheinlichkeit 50% übersteigt? 100 Personen? 366? Oder gar über 500?*

Falsch! Bereits bei 23 Personen liegt die Wahrscheinlichkeit für einen Doppelgeburtstag bei 50,73%! Das glauben Sie nicht? Nun gut, gehen wir der Sache auf den Grund.

Recht einfach ist es, wenn wir einfach alle Personen der Reihe nach durchgehen und jedes Mal aufs Neue die Wahrscheinlichkeit dafür berechnen, dass unter den bisher betrachteten Personen ein Doppelgeburtstag liegt. Anschließend verallgemeinern wir diese Vorgehensweise und erhalten eine Formel für die Berechnung der Wahrscheinlichkeit bei einer gegebenen Zahl n von Personen. Also gut:

Eine Person: Es kann kein Doppelgeburtstag auftreten, es ist egal, wann die erste Person ihren Geburtstag feiert.

Zwei Personen: Nur zu \frac{1}{365} tritt ein Doppelgeburtstag auf, nämlich genau dann, wenn die 2. Person NICHT an einem der bereits “vergebenen” Tage Geburtstag hat, es bleiben also 1-(\frac{364}{365}) = \frac{1}{365} \approx 0,27\%

Drei Personen: Wie schon bei Person Nummer zwei erläutert tritt KEIN Doppelgeburtstag genau dann auf, wenn Person drei ihren Geburtstag weder mit der ersten, noch mit der zweiten Person teilt. Das ist in (\frac{364}{365} \cdot \frac{363}{365}) = 99,18\% der Fälle so. Übrig bleiben 1-(\frac{364}{365} \cdot \frac{363}{365}) = 0,82\% FÜR einen Doppelgeburtstag. Noch immer sehr niedrig.

Vier Personen: Führen wir das gleiche Muster fort: 1-(\frac{364}{365} \cdot \frac{363}{365} \cdot \frac{362}{365}) \approx 1,64\%. Eine Verdopplung immerhin.

Fünf Personen: 1-(\frac{364}{365} \cdot \frac{363}{365} \cdot \frac{362}{365} \cdot \frac{361}{365}) \approx 2,71\%. Allzu rasant scheint der Wert ja nicht zu steigen.

Sechs Personen: 1-(\frac{364}{365} \cdot \frac{363}{365} \cdot \frac{362}{365} \cdot \frac{361}{365} \cdot \frac{360}{365}) \approx 4,05\%.
… Um es nicht allzu langwierig zu machen springen wir nun direkt zu 20 Personen:

20 Personen: 1-(\frac{364}{365} \cdot \frac{363}{365} \cdot \ldots \cdot \frac{346}{365}) \approx 41,14\%

21 Personen: 1-(\frac{364}{365} \cdot \ldots \cdot \frac{345}{365}) \approx 44,37\%

22 Personen: 1-(\frac{364}{365} \cdot \ldots \cdot \frac{344}{365}) \approx 47,57\%

23 Personen: 1-(\frac{364}{365} \cdot \ldots \cdot \frac{344}{365}) \approx 50,73\%

Erstaunlich. Mal wieder.

Für interessierte sei auch noch die Formel genannt, mit der sich die Wahrscheinlichkeit für einen Doppelgeburtstag unter n Personen berechnen lässt:

P(n) = 1 - \frac{365!}{(365 - n)! \cdot 365^n}

Die Werte sind allerdings nur theoretisch – in der Praxis ist die Wahrscheinlichkeit sogar noch etwas größer.
Das liegt vor allem daran, dass die Geburtstage selten gleichmäßig über das Jahr verteilt sind.So gibt es eine deutliche Tendenz für die Sommermonate.


(*) Bereits bei 135 Personen rundet mein Sage auf 100%, bei einer Genauigkeit von zehn Nachkommastellen.

Rätsel: Kopfrechnen

Im “PatzBlatt”, der Zeitschrift der Einzelmeisterschaften der Schachjugend NRW, fand sich letzte Woche folgendes Rätsel.

Man kombiniere die Zahlen 1, 5, 6 und 7 in beliebieger Reihenfolge mit den Grundrechenarten um als Ergebnis 21 zu erhalten. Klammern setzen ist natürlich erlaubt. Wie geht das?

Die theoretisch durchaus interessante Lösung habe ich mit Hilfe eines Python-Skripts gefunden. Nach einigem “Kopfrechnen” und logischen Schlüssen darauf zu stoßen ist aber mit Sicherheit eleganter und wertvoller. Wenngleich das nicht ganz einfach ist möchte ich euch diese Knobelei nicht vorenthalten.

Viel Spaß beim Kopfzerbrechen!

Das Königsberger Brückenproblem

Rücken Sie Ihre Sitzgelegenheit zurecht, machen Sie es sich bequem, seien Sie bereit für eine virtuelle Zeitreise; wir begeben uns zurück ins 18. Jahrhundert.

Wir befinden uns jetzt im damaligen Königsberg (heute Kaliningrad). Nach einem gemütlichen Spaziergang durch die Stadt kommen wir schließlich an den Pregel. Wir überqueren eine der sieben Brücken und stehen inmitten der sogenannten Kneiphof-Insel.

Ein älterer Mann kommt auf uns zu und bietet eine Wette: “Schaffen Sie es, jede der sieben Brücken genau einmal zu passieren und am Ende wieder hier an ihrem Ausgangspunkt zu landen? Ich biete einen Reichstaler.” (Anm.: Kaufkraft im 18.Jh etwa 15€)

Lageskizze der Königsberger Brücken

Lageskizze der Königsberger Brücken

Sollten Sie diese Wette annehmen?

Natürlich nicht! Es ist unmöglich, einen solchen Weg zu finden. Doch warum? Und wie lässt sich das beweisen? (Diese beiden Fragen hängen oft eng miteinander zusammen.)

Setzen wir zur Auflösug unseren Stadtrundgang fort. Wir kommen zu einem kleinen Haus, irgendwo in Königsberg. Es ist das Haus Leonhard Eulers, einer der größten Mathematiker der Geschichte. Euler war es, der unsere Fragen im Jahre 1736 beantworten konnte.

Dazu tat er etwas für die Mathematik seiner Zeit noch recht ungewöhnliches: Er ließ die genauen Details des Brückenplans weg und untersuchte nur ihre Struktur, die Beziehung der Wege untereinander. Die genauen Maße der Wege waren uninteressant.

So wandelte Euler das praktische Problem um in eines der Graphentheorie, dessen Anfang heute bei diesen Entdeckungen Eulers gesehen wird. Er verwandte neue Begriffe, die “Knoten” und die “Kanten”, die zusammen einen Graphen bilden.

Graph der Königsberger Brücken

Die Knoten sind dabei die vier zu erreichenden Teile der Stadt; die Kanten als Verbindungen zwischen den Knoten stellen unsere Brücken dar.

Gesucht ist nun ein Weg, der bei demselben Knoten beginnt und endet und dabei jede Kante genau einmal benutzt.

Wir sehen schnell, dass an jedem der Knoten eine ungerade Anzahl von Kanten liegt (man spricht von einem ungeraden Grad der Knoten). Ein Knoten, der zugleich Start- und Endknoten unserer Reise ist, müsste allerdings einen geraden Grad besitzen, ansonsten muss mindestens eine Brücke zweimal überquert werden. Das ist uns jedoch nicht erlaubt, wir können also keinen solchen Weg finden.

(Für eine sehr gut gestaltete nähere Erläuterung des Themas siehe http://www.matheprisma.uni-wuppertal.de/Module/Koenigsb/)

Primzahlen mit über 10 Millionen Dezimalstellen

Soeben las ich in Günter Zieglers Blog, dass vor kurzem vom GIMPS-Projekt zwei Primzahlen mit jeweils weit über 10 Millionen Dezimalstellen gefunden worden sind.

Der technische Fortschritt macht selbst bei solchen Riesen nicht halt, und trotzdem gibt es noch immer keine Möglichkeit, Primzahlen in irgendeiner Weise exakt berechnen zu können. Durch (kluges) Ausprobieren finden wir neue, immer größere Primzahlen, doch irgendeine Regel oder Ordnung lässt sich nicht erkennen.

Scheinbar zufällig liegen diese Grundbausteine der Arithmetik chaotisch verteilt in der unendlichen Menge der  Zahlen. Seit über 2000 Jahren kennen wir sie, seit über 2000 Jahren sind sie eines der größten Rätsel, seit über 2000 Jahren sträuben sie sich gegen jeden Versuch einer exakten Darstellung.

Faszinierend!

(Inspiriert auch von “Die Musik der Primzahlen” (oder als Taschenbuch) von Marcus du Sautoy)

Paradoxes Fahrrad-Rätsel

Fahrrad

Stellen Sie sich vor, Sie nehmen an einem Fahrrad-Rennen teil. Die Strecke besteht aus zwei Runden irrelevanter Länge, eine davon haben Sie bereits absolviert. Bisher beträgt Ihre Durchschnittsgeschwindigkeit 20 km/h, Sie hatten sich aber vorgenommen, nach dem gesamten Rennen mit einer durchschnittlichen Geschwindigkeit von 40km/h ins Ziel zu gelangen.

Wie schnell müssen Sie also nun in der zweiten Runde fahren, um diese Wunsch-Gesamtgeschwindigkeit zu erreichen?

Plausibel erscheinen zunächst 60km/h.

Doch ganz so einfach ist es natürlich nicht. In Wahrheit können Sie das Rennen gar nicht mehr mit der gewünschten Durchschnittsgeschwindigkeit von 40km/h beenden! Egal, wie kräftig Sie in die Pedale treten, eine Gesamt-Durchschnittsgeschwindigkeit von 40km/h zu erreichen ist unmöglich!

Warum? Nunja, für die erste Hälfte der Strecke benötigten Sie 20km/h. Wenn wir die Streckenlänge mit s bezeichnen gilt also für die benötigte Zeit t = \frac{1}{2}s : 20 \text{km/h} = \frac{1}{40}\text{km/h} \cdot s. Um das Ziel mit einer Geschwindigkeit von 40km/h zu erreichen, müssten Sie für die beiden Runden zusammen jedoch ebenfalls t = s : 40\text{km/h} = \frac{1}{40}\text{km/h} \cdot s benötigen; die zweite Runde müssten Sie also in 0 Sekunden absolvieren, was nicht nur praktisch unmöglich ist!

Genau so verhält es sich natürlich, wenn Sie bereits 99 von 100 Runden mit einer Geschwindigkeit von 99km/h gefahren sind und 100km/h erreichen möchten.

Warum gewinne ich nicht im Lotto?

In diesem Artikel werden wir der Frage auf den Grund gehen. Dazu lernen wir zunächst die Begriffe der Fakultät und des Binomialkoeffizienten kennen, die beide aus der Kombinatorik stammen. Grob gesagt beschäftigt sich die Kombinatorik damit, Dinge abzuzählen. Oft geht es um Anordnungen von Dingen (populäres Beispiel: die möglichen Ziehungen der Lottozahlen bzw. -kugeln). Damit hängt die Kombinatorik teilweise eng mit der Wahrscheinlichkeitsrechnung zusammen, wie es z.B. in dem Artikel über PIN-Nummern zu erkennen ist.

Fakultät

Mithilfe der Fakultät kann man z.B. die Permutationen abzählen, die Anzahl der Vertauschungen einer bestimmen Anzahl von Objekten. Dazu zunächst ein Beispiel: Wir wollen die Anzahl aller Anordnungen berechnen, die es bei 5 Personen gibt, die auf 5 Stühle “verteilt” werden sollen. Gehen wir das Ganze einmal durch: Für die erste Person stehen uns alle 5 Stühle zur Verfügung. Die zweite Person müssen wir auf einen der verbleibenden 4 Stühle setzen. Es ergeben sich also {5} \cdot 4 = {20} Möglichkeiten für zwei Personen. Für jede weitere Person gibt es immer genau einen Stuhl weniger, auf dem die Person Platz nehmen kann, als die Person zuvor zur Auswahl hatte. Man erhält also {5} \cdot (5-1) \cdot (5-2) \cdot (5-3) \cdot (5-4) = 5 \cdot 4 \cdot 3 \cdot 2 \cdot 1 = 5 \cdot 4 \cdot 3 \cdot 2 = {120} Möglichkeiten. Genau dieses Produkt nennt man “Fakultät von 5″ und schreibt 5{!}. Allgemein definieren wir die Fakultät von n, n! als  n \cdot (n-1) \cdot (n-2) \cdot ... \cdot 3 \cdot 2 \cdot 1 = n \cdot (n-1) \cdot (n-2) \cdot \ldots \cdot 3 \cdot 2 . Die Größe der Fakultät einer Zahl steigt sehr rasant an und schon bei 3-stelligen Zahlen benötigt ein (durchschnittlicher) Computer längere Zeit zur Berechnung. Dem erwähnten Problem der Anordnungen von Lottozahlen lässt sich so allerdings nicht auf die Schliche kommen, da nur 6 aus 49 Kugeln insgesamt ausgewählt werden und die Reihenfolge außerdem irrelevant ist.

Der Binomialkoeffizient

Der mitdenkende Leser erkennt vielleicht schon, wie dieses Problem zu umgehen ist. Zunächst überlegen wir uns, wie viele Möglichkeiten es gibt, 6 aus 49 Kugeln auszuwählen. Wir gehen so vor, wie oben bei Berechnung der Fakultät: Für die erste Kugel, die gezogen wird, gibt es 49 Möglichkeiten, für die zweite noch 48, für die dritte 47 und so weiter… Insgesamt ergibt sich  {49} \cdot 48 \cdot 47 \cdot 46 \cdot 45 \cdot 44 = \frac{49!}{43!} = \frac {49!}{(49-6)!} Allerdings haben wir die Reihenfolge der Ziehungen der Kugeln noch nicht berücksichtigt, dass heißt jede mögliche Kombination kommt mehrmals vor. Genauer gesagt: In jeder möglichen Anordnung. Um die richtige Zahl der möglichen Ziehungen (ohne Relevanz der Reihenfolge) zu erhalten, müssen wir den Wert also noch durch die Anzahl der Anordnungen teilen. Das ist genau 6!, wie oben erläutert. Also ist die Zahl der möglichen Ziehungen beim Lotto genau \frac {49!}{(49-6)!6!} = \frac {49!}{(6!(49-6)!} Wie bereits oben angedeutet genau das der Binomialkoeffizient , sprich “49 über 6″. Allgemein ist \binom{n}{k} = \frac{n!}{(n-k)!k!} (gilt nur für natürliche Zahlen n, k was bei “alltäglichen” Abzählaufgaben jedoch meist erfüllt ist) Um die Wahrscheinlichkeit zu erhalten, mit der man ein Lottospiel gewinnt muss man nun noch den Kehrwert dieser Gesamtzahl der möglichen Ziehungen bilden, also den Anteil der eigenen ausgewählten Kombination an der Gesamtzahl berechnen: \frac {1}{\binom{49}{6}} = \frac{1}{\frac{49!}{43!\cdot6!}} = \frac{43!\cdot6!}{49!} = \frac{1}{13983816} \approx 0{,}00000715 \% , was sehr sehr gering ist.

Selbst wenn man 14 Millionen verschiedenene Lottoscheine abgeben würde befände sich darunter im Durchschnitt nur ein einziger mit “6 Richtigen”. Und darum gewinnen Sie nicht im Lotto. (Wer schon einmal im Lotto gewonnen hat und diese Aussage somit aus persönlicher Erfahrung widerlegen kann ist natürlich herzlich eingeladen, dies in einem Kommentar zu tun.)