Zufallsbit

In der letzten "Schlag den Raab"-Ausgabe wurde ein Spiel gespielt, das mich fasziniert hat. Es geht so:

Der erste Spieler würfelt mit einem Würfel. Ist es eine Zahl von 1-5, wird diese auf sein Punktekonto addiert und er darf nochmal würfeln. Ist es aber eine 6, verliert er alle Punkte wieder und der zweite Spieler ist dran. Man kann jederzeit aufhören zu würfeln, solange man keine 6 bekommt, dann werden die bisher erreichten Punkte auf ein Gesamtpunktekonto gutgeschrieben und der Gegner ist dran. Wer zuerst 50 Gesamtpunkte hat, ist der Sieger. 

Zum Beispiel könnte das Spiel so laufen:

Spieler 1: 1,5,6 (Gesamt: 0)

Spieler 2: 4,4, Aufhören (Gesamt: 8)

Spieler 1: 2,1, Aufhören (Gesamt: 3)

Spieler 2: 3,6 (Gesamt: 8)

usw.

Die Frage die ich mir sofort gestellt habe: Ab welcher Punktzahl lohnt es sich, aufzuhören? Natürlich würde man kaum mit einem Punkt an den Gegner abgeben, aber man würde auch nicht einfach drauflos würfeln, bis man seine 50 Punkte zusammen hat, denn die Wahrscheinlichkeit, dabei einmal eine 6 zu würfeln und alles wieder zu verlieren ist sehr hoch. Nun bin ich aber relativ schwach darin, das passende Wahrscheinlichkeitsmodell für solche Dinge zu finden. Selbst wenn ich eins finde, bin ich mir immer noch wahnsinnig unsicher, ob es das richtige war und ob damit nicht vielleicht die ganze Rechnung falsch ist. Viel besser bin ich darin, einfach ein Programm zu schreiben, das mir das Ganze simuliert.

Source

In dem Programm definiere ich einen "Cutoff", also eine Grenze, wo die virtuellen Spieler aufhören würden zu würfeln. Cutoff 10 bedeutet, dass der Spieler aufhört, sobald er >= 10 Punkte erreicht. Für jeden möglichen Cutoff habe ich dann jeweils 100.000 Spieler simuliert und das Ergebnis war.. nun ja.. interessant. Grafik gefällig?

Das Ergebnis überrascht mich ehrlich gesagt. Zwischen Cutoff 7 und 30 ist es relativ egal, was man macht, immer braucht man im Schnitt 8-9 Würfelnrunden um die 50 Punkte zu erreichen. Das macht irgendwie auch Sinn, denn bei Cutoff 25 bräuchte man ja nur zwei erfolgreiche Runden um zu gewinnen, aber bei Cutoff 7 ist die Wahrscheinlichkeit durch eine 6 gekillt zu werden entsprechend kleiner. Trotzdem läuft das irgendwie gegen meine Intuition, dass eine so breite Spanne von Cutoffs die gleichen Werte hat. Wenn jemand tatsächlich Ahnung von Mathematik hat und mir das erklären könnte, wäre ich sehr dankbar.

Hinter der Uni liegt ein großer Parkplatz. Hinter diesem Parkplatz steht ein Studentenwohnheim, in dem ein Freund von mir wohnt. Wenn ich ihn besuchen will, muss ich von einer Ecke des Parkplatzes zur anderen. Etwa so:

Man könnte natürlich einfach den Gehweg benutzen:

Aber das wäre nicht nur sehr langweilig, sondern auch rasend ineffizient. Die Wegkosten sind natürlich a*b. Die optimale Route kann man eigentlich nur nachts gehen, wenn der Parkplatz leer ist.

Der optimale Weg wäre natürlich genau die Diagonale und damit nach Pythagoras (und meinetwegen noch der Dreicksungleichung) . Dieser Weg geht aber leider nicht immer, weil der Parkplatz tagsüber mit Autos voll steht. Deshalb nehme ich notgedrungen diesen Weg:

Da stellt sich einem chronisch gelangweilten Informatiker natürlich die Frage: Wie viel verliere ich dabei an Optimalität? Die Abmessungen habe ich persönlich vorgenommen (und sah dabei ganz schön blöd aus, wie ich zwischen den Autos einen Fuß vor den anderen setzte und leise mitzählte).

Außerdem gibt es genau 17 solcher Parkinseln c und 17 Zwischenräume d, nicht nur 6 wie auf dem Bild suggeriert. Zeit für Mathematik.

Ich muss die Strecke b überbrücken während ich bei d diagonal gehe. Für die Anschaulichkeit sortiere ich das Problem mal in etwas Äquivalentes um:

 Der Winkel in dem ich gehen muss um von rechts nach links zu kommen ist bzw. , also . In meinem Fall wäre das .

Das ist zu meiner Überraschung und Freude ziemlich nahe an den optimalen 45°. Den kleinen Unterschied bezichtige ich einfach mal als Messfehler. Damit ist der Rest der Rechnung auch noch wahnsinnig einfach, denn der gesamte diagonale Weg ist damit . Der vertikale Weg addiert sich einfach zu 17*10m=170m und der Gesamtweg ist damit etwa 340m.

Vergleichen mit dem optimalen Weg von ist das immer noch ein zu 92% optimaler Weg. Was mich sehr glücklich macht.

In einem Anfall von Langeweile und weil "Sur3" in den Kommentaren des ersten Beitrages zum Monty Hall Problem immer noch nicht glaubt, dass es besser ist zu wechseln, habe ich eben ein kurzes (und echt hässliches) Python-Skript zusammengehackt, das eben dieses Problem simuliert.

Die Ergebnisse bei 100.000 Durchläufen:

% python montyhall.py

Switch Win: 66597

Switch Lose: 33403

No Switch Win: 33382

No Switch Lose: 66618

Conclusive proof :)

Im letzten Beitrag über die Statik ging es um das Gleichgewicht der Kräfte. Die Quintessenz war, dass es bei Statik um starre Systeme geht und daher die Summe der Kräfte in alle Richtungen gleich null sein muss. Mit dieser Bedingung kann man zwei Gleichungen aufstellen und Dinge berechnen. Insbesondere ging es dabei um Auflager, was sich grob mit "Befestigungen" übersetzen lässt. Diese waren nötig, weil wir verhindern müssen, dass sich das System bewegen kann. Wir haben aber auch gesehen, dass in dem betrachteten 2D-System eine Gleichung fehlte, um die drei Unbekannten zu berechnen. Diese Gleichung ergibt sich aus den Momenten.



Momente treten auf, wenn sich irgendetwas infolge einer äußeren Kraft um eine Achse drehen würde. Wenn ihr einen Stift an einem Ende fest haltet und an der anderen Seite von oben drückt, dann würde sich der Stift um die Einspannung (die festhaltenden Finger) drehen. Vielleicht hilft dieses Bild ja bei der Vorstellung:

Wenn man hier gemäß dem roten Vektor auf den Balken drücken würde, "dreht" sich der Balken um den die untere Ecke der Einspannung und wirkt deshalb eine Kraft auf den oberen Kontaktpunkt. Das ist auch ganz intuitiv, dieses Verhalten würde man so erwarten. Das hilft uns jetzt weiter, denn genau wie die Summe der Kräfte, muss auch die Summe aller Momente in einem statischen System gleich Null sein, einfach weil sich das System nicht bewegen, also auch nicht drehen darf. Das gibt uns eine dritte Gleichung, mit der wir jetzt endlich ein einfaches statisches System zuende rechnen können.

Sicher haben alle schon einmal vom Hebelgesetz gehört. Demnach bewirken äußere Kräfte ein Moment, und zwar multipliziert mit dem Hebelarm. Einzelmomente allerdings haben keinen Hebelarm, das gilt wirklich nur für Momente verursachende äußere Kräfte. Das bedeutet auch, dass man sich, um Momente zu berechnen, irgendeinen Punkt wählen muss, um "den man drehen lässt". Welcher Punkt das ist, ist egal, das Ergebnis bleibt gleich. Beispiel:

Dieses Auflager ganz links nennt man auch "feste Einspannung" und nimmt sowohl vertikale und horizontale Kräfte als auch Momente auf. Man kann sich das buchstäblich als einen in die Wand geschlagenen Nagel vorstellen. Um auszurechnen, welche Kräfte an der Wand wirken benutzt man die drei Gleichgewichtsbedingungen:

1. Summe der horizontalen Kräfte ist null:

2. Summe der vertikalen Kräfte ist null:

3. Summe der Momente ist null. Hier drehen wir um die Einspannung (Punkt A). Die postitive Drehrichtung ist im Uhrzeigersinn:

Die Wand muss also ein Moment von - 20 kNm (Kraft mal Hebelarm) auffangen, verursacht durch die äußere Kraft. Zur Veranschaulichung von Momenten kann eventuell auch dieses Applet hilfreich sein.

Man kann übrigens wie erwähnt auch ohne Probleme z.B. um das Ende des Balkens drehen:

Man beachte, dass mit 2 multipliziert werden muss, weil es sich hier um ein von Kräften verursachtes Moment mit Hebelarm handelt. hingegen ist ein Einzelmoment und hat keinen Hebelarm. Zum Schluss können wir uns ja nochmal das System aus dem letzten Beitrag angucken:

Beim letzten Mal hatten wir schon festgestellt, aber jetzt können wir auch um den linken unteren Punkt A drehen um B zu bekommen. Die horizontale Länge des Systems nenne ich L, die eigentliche Größe ist egal, denn die Länge kürzt sich hier raus:

So weit, so einfach. Was aber, wenn es in diesem System z.B. noch ein gäbe? Wir hätten ein großes Problem, denn die Summe der Horizontalen würde zwei Unbekannte beinhalten. Man kann ebenfalls nicht um A oder B drehen, denn hätte keinen Hebelarm bezüglich A und umgekehrt, beide Unbekannten würden also raus fallen. Das Problem ist, dass das Gesamtsystem eine Unbekannte mehr als Gleichgewichtsbedingungen hat, das System ist statisch unbestimmt. Die Lösung ist Thema in nächsten Beitrag, kurz gesagt muss man dem System gezielt Unbekannte entziehen indem man Gelenke einfügt.

Good news everyone! Die lange, langsam peinliche inhaltslose Zeit dieses Blogs ist beendet. Das ganze Zeug was ich in den letzten Wochen gelernt habe wird ab jetzt offiziell hier verwurstet. Es geht um Technische Mechanik, genauer gesagt um Statik. Dazu müssen wir erstmal klären, was das genau ist.

Nun, Objekte in der realen Welt ("statische Systeme") werden ja irgendwie belastet. Jemand steht auf einer Brücke, Wind pustet seitlich gegen ein Haus, Schnee drückt auf ein Dach oder die Erdanziehung zieht ein Objekt nach unten. In der Realität wird also jedes System mindestens von der Erdanziehung belastet. Die Technische Mechanik fragt sich im Allgemeinen, wie eine Kraft auf ein System wirkt. Die Statik im Speziellen fragt sich, wie eine Kraft auf ein starres (unbewegliches) System wirkt. Dafür darf das System natürlich keinerlei Freiheitsgrade haben. Nehmen wir als Beispiel den Schreibtisch an dem ich gerade sitze. Wenn ich von der Seite drücken würde, würde er sich verschieben. Wenn ich aber von oben drücke, würde der Boden, auf dem die Tischbeine stehen, die Kraft auffangen (oder besser gesagt: entgegenwirken). Ich habe hier also ein kinematisches (bewegliches) System und das ist nicht das Thema. Die Statik würde annehmen, dass der Schreibtisch z.B. an der Wand fest angebracht ist, sich also nicht verschieben kann.

Um ein statisches System zu bekommen, muss also in jeder möglichen Richtung eine Befestigung bestehen. Das nennt man dann "Auflager". Damit das ganze hier aber nicht zu sehr ausartet, beschränken wir uns auf 2D-Systeme und vergessen ab jetzt die y-Achse. Das ist nur eine verhältnismäßig kleine Einschränkung, alles was wir hier besprechen funktioniert genau so in 3D, nur da wird es schnell unübersichtlich und unnötig kompliziert. Ein Schreibtisch als statisches 2D-System ausgedrückt, wo ich oben drauf drücke sähe damit so aus:

Dazu gibt es einige Dinge zu sagen. Zunächst ginge der Tisch natürlich in y-Richtung weiter, wir haben aber wie gesagt jetzt eine Art seitliche Sicht um die Dinge zu vereinfachen. Der Nullpunkt ist ab jetzt immer ganz unten links und die x-Richtung geht nach rechts, die z-Richtung nach oben. Der rote Pfeil ist natürlich die Kraft, die auf den oberen Bereich wirkt. Die beiden dreieckigen Dinger unten sind die eben erwähnten Auflager. Das linke Auflager kann Kräfte in x- und z-Richtung aufnehmen, wärend das rechte nur Kräfte in z-Richtung aufnehmen kann. Daher auch der kleine Strich unter dem Auflager, den kann man ganz physisch als "Boden" auffassen wärend das Auflager darüber in x-Richtung verschieblich ist.

Es ist also so, dass der Tisch auf dem Boden steht, denn beide Tischbeine können vertikale Kräfte von oben aufnehmen, zudem ist das linke Tischbein unten noch "an der Wand befestigt", damit wir hier ein statisches System bekommen.

Um jetzt irgendetwas berechnen zu können bringt man die entgegenwirkenden Kräfte, die vom Boden ausgehen, am System an. Wenn wir diese ausrechnen, wissen wir welche Kräfte an den Stellen auftreten, wo der Tisch auf dem Boden steht bzw. verankert ist. Das können wir machen, weil wir ja wissen, dass das System unbeweglich ist. Es muss also so sein, dass alle vertikalen Kräfte zusammen und alle horizontalen Kräfte zusammen gleich Null sind. Wenn wären, wären ja die Kräfte, die von unten kommen größer als die von oben kommenden, da System würde sich entsprechend verbotenerweise bewegen. Damit haben wir zwei Gleichungen:

und .

Die Summe aller Kräfte in einer Richtung ist immer gleich Null. Damit:



1)

(die obere Kraft zeigt nach unten, in negative z-Richtung und hat damit ein negatives Vorzeichen)



2)

Man beachte, dass es egal ist, in welche Richtung ich die Auflagerkäfte anzeichne. Ich hätte auch alle umgekehrt Zeichnen können, das einzige was sich geändert hätte, wäre das Vorzeichen. Und das ist nicht weiter schlimm, worauf ich im nächsten Beitrag eingehen werde.

Mit diesen beiden Gleichungen sind wir nicht besonders viel weiter gekommen. Wir haben festgestellt, dass ist, was wir auch wohl einfach erraten hätten, denn wo keine horizontale äußere Kraft wirkt, muss auch keine entgegen halten. Wir haben immer noch zwei Variablen, aber nur eine Gleichung. Nötig ist eine weitere Gleichung und woher die kommt, darum gehts dann im nächsten Beitrag.

P.S.: Natürlich wird sich heraus stellen, dass . Eine Kraft die in der Mitte angreift, verteilt sich gleichmäßig auf beide Auflager. Wäre ja auch schlimm, wenn sich so einfache Systeme schon nicht-intuitiv verhalten würden.

Wer ins Casino geht und sich (wie ich) als erstes fragt, bei welchem Spiel er mathematisch die besten Chancen hat zu gewinnen, landet zu meiner großen Verwunderung ziemlich oft bei Roulette. Das hat zumindest eine kurze, wenig repräsentative Umfrage in meinem Bekanntenkreis ergeben. Oft mit einem Zusatz wie "Wenn man mal so etwas wie Poker ignoriert".

Zunächst kommt es bei Poker drauf an, mit welchen Einsätzen man spielt. Casinos halten von jedem Pot einen kleinen Teil ein, das so genannte "Rake". Wenn der Einsatz klein ist, übersteigt der Rake oft die möglichen Gewinne. Also verliert man hier auch über die Zeit, außer man hat einen deutlichen spielerischen Vorteil gegenüber seinen Gegnern.

Aber zurück zum Roulette. Ich vermute, die Entscheidung für dieses Spiel basiert darauf, dass es nur eine einzige Zahl gibt, wo die Bank gewinnt (die Null). Dem gegenüber stehen die gaaaanzen, vielen Zahlen auf der Roulette-Scheibe, bei der die Bank nichts gewinnt. Deshalb glaubt man wohl, der Bankenvorteil müsse verschwindend gering sein. Die Gewinnquoten sind so allerdings so berechnet, als ob es die Null nicht gäbe. Das heißt, die Quote sind für alle einfachen Einsätze minimal zu klein oder konkret: Im Schnitt gewinnt die Bank bei allen einfachen Einsätzen 1,35%.

Beim Baccara ist es sogar noch schlechter. Wenn der Spieler oder die Bank gewinnt ist der Bankvorteil bei 1%, im Falle eines Unentscheidens jedoch knappe 15%. Das kommt zwar nur in 10% der Fälle vor, ist deswegen trotzdem nicht gerade vorteilhaft für den Spieler. Auch Let it Ride-Poker hat etwa 2% Bankvorteil. Zum Vergleich: Deutsches Lotto hat eine Ausschüttungsquote von 50%. Wenn man also für 120 Millionen alle möglichen Reihen tippt, beträgt die Gewinnerwartung lächerliche 60 Millionen. Nach 2 Monaten Lottospiel hat man damit aus 120 Millionen Euro einen fünfstelligen Betrag gemacht.

Der Champion unter den spielerfreundlichen Casinospielen ist Blackjack. Der Vorteil der Bank besteht, weil der Spieler zuerst dran ist. Wenn man über 21 kommt, hat die Bank automatisch gewonnen, auch wenn sie unter normalen Umständen ebenfalls über 21 gekommen wäre. Dieser Vorteil ist aber trotzdem gering, weil der Spieler schließlich auch eine Karte der Bank sieht und außerdem weiß, dass die Bank mindestens 17 erreichen muss. Sieht der Spieler also eine 4 bei der Bank, ist es oft gut, einfach auch mit 12 Punkten keine Karte mehr zu nehmen. Die Chance ist nämlich ganz gut, dass die zweite Karte der Bank 10 Punkte wert ist. Und mit 14 Punkten steht wiederum die Chance gut, dass die Bank noch eine hohe Karte erwischt und über 21 kommt.

Der Bankvorteil ist damit bei Blackjack unter 0,5%, zumindest bei mathematisch perfektem Spiel. Ist natürlich blöd wenn Blackjack einem überhaupt gar keinen Spaß macht. So wie mir.

Letztens habe ich mit Freunden Poker gespielt und länger über eine Entscheidung nachgedacht. Weil ich auf Nachfrage erklären musste, was pot odds sind und wie man sie berechnet, kann ich das hier auch nochmal tun.

Pot odds kommen ins Spiel, wenn man noch keine fertige Hand hat. Zum Beispiel hat man ein kleineres Päärchen (4,4 z.B.) und der Flop hat drei höhere Karten. Da kann man davon ausgehen, dass jemand mindestens ein höheres Paar hat und man eine dritte vier braucht, um die Hand zu gewinnen.

Oder man sitzt auf einem flush oder straight draw und braucht noch eine Karte. Wenn der Gegner setzt, stellt sich die Frage, ob es sich mathematisch rechnet, zu callen und einen eventuell großen Pot zu gewinnen oder ob die Wahrscheinlichkeit zu klein zum callen ist.

Dazu zählen wir zunächst die outs. Das sind Karten, die kommen könnten um deine Hand zu einer starken Hand zu machen. Sagen wir, du hättest 7,9 beides Karo. Auf dem Flop kommen 6,10,K, davon die letzten beiden Karo. Da liegt also ein flush draw und einen inside straight draw. Da wären zunächst alle restlichen Karo, die einen flush machen würden. Das sind 2,3,4,5,6,8,J,Q,A, also 9 outs. Dazu kommen drei achten, die eine straight machen würden. Die 8 Karo haben wir vorher schon gezählt, die zählt jetzt nicht mehr. Insgesamt hast du damit 12 outs. Übrigens: Vorsicht bei einem flush. Wenn noch viele Gegner im Spiel sind, ist möglicherweise 7,9 nicht der höchste flush. Da geht man gerne mal pleite mit.

Die Formel für "nach dem Flop" ist jetzt: 2 * outs * restliche Karten + 2. Das "+2" ist auf 1 anzupassen, wenn man nur die odds für eine Karte ausrechnet. Siehe weiter unten.

Bei uns also:  2 * 12 * 2 + 2 = 50% Chance, dass man auf Turn oder River eine starke Hand bekommt. Das hört sich jetzt ganz gut an, kann aber je nach Qualität des Gegner schwierig werden. Gute Gegner könnten nach dem Turn wieder wetten, deshalb rechnen wir lieber die Chance nur für den Turn aus: 2*12+1=25%

Jetzt schauen wir uns an, was wir mit diesen odds callen könnten. Sagen wir, der Pot ist 250$ und der Gegner hat nach dem Flop 40$ gewettet. Man multipliziert die odds mit der Pot-Größe (inklusive der Wette des Gegners!). Dabei sind natürlich "25%" als 0.25 zu verstehen. 0.25 * 290= 72.5. Soviel könnten wir also guten gewissens callen, da der Gegner nur 40$ gewettet hat, wäre hier ein call angebracht.

Harald fragt per Mail:

"(...) aber wieso ist denn 1+1=2? axiome gut und schön, aber was wenn ich einfach 1+1=3 sage?(...)"

Tja Harald, natürlich kannst du einfach 1+1=3 sagen, aber was hättest du damit grundlegend anders gemacht als bei 1+1=2? Es ist doch so, es scheint relativ natürlich, dass man eine unendliche Menge von Zahlen hat, wobei alle unterschiedlich groß sind und die eine der Nachfolger der nächsten ist. In unserer Welt ist das eben 1,2,3,4... usw. Die Zwei ist definiert als der Nachfolger der Eins. Die drei ist wiederum der Nachfolger des Nachfolgers der Eins. Anders gesagt: Sei succ(n) die Funktion, die jeweils den Nachfolger der Zahl n angibt. D.h. succ(n)=n+1.

Dann ist 2=succ(1), 3=succ(succ(1)), 4=succ(succ(succ(1))) usw. Und an dieser Stelle könnte ich Haralds Idee umsetzen und sagen 3=succ(1), damit wäre die Drei an die Stelle der Zwei gerückt. Aber was kommt dann an der dritten Stelle, da ist ja jetzt ein Platz frei. Wie wärs mit der Zwei? Und auf einmal macht die ganze Diskussion keinen Sinn mehr. Es wird klar, das Konzept der natürlichen Zaheln ist universell, so ziemlich jede Kultur in jedem Universum dürfte ein solches Konzept erfinden. Wie man die einzelnen Zahlen jedoch bezeichnet ist völlig egal, wenn man die zweite Zahl im System mit "3" bezeichnen will, nur zu, das ändert nichts. Dann wäre 3+3=4 und 3*3=4, dafür würde die Zwei jetzt den Platz der Drei einnehmen.

Und so ähnlich lässt sich diese Argumentation mit allen Axoimen durchführen. Es ist relativ egal, wie man Teile der Axiome bezeichnet, denn sie stellen alle "Basiskonzepte" der Natur dar, deren Eigenschaften sich nicht so leicht wie die Bezeichnungen wegdiskutieren lassen. Gerade das ist ja das schöne an Mathematik.

Ich beschäftige mich gerne mit Metamathematik, beziehungsweise mit den Grenzen, Axiomen und Implikationen von Mathematik an sich. Und das vielleicht wichtigste Ergebnis aus dem Bereich überhaupt ist der so genannte Gödelsche Unvollständigkeitssatz. Kurt Gödel war einer der Besten überhaupt (und wäre einen eigenen Eintrag an sich wert), und hat nachgewiesen, dass Mathematik so seine inhärenten Probleme hat.

Man muss wissen, dass Mathematik nicht immer so streng formalisiert war. In Eulers Zeiten gleichte ein Beweis eher einem philosophischen Gedankengang, denn man hatte schlicht keine einheitliche Notation und Techniken um die Dinge streng formal zeigen zu können. Irgendwann kam Hilbert auf die Idee, die Mathematik streng axiomatisch aufzubauen. Das bedeutet, man definiert eine Hand voll Axiome (das sind "atomare Weisheiten", z.B. 1+1=2) und kann damit im Prinzip alle mathematischen Sätze überhaupt herleiten. Im Endeffekt könnte man damit einen Computer füttern, der einfach logisch aus den Axiomen folgert, so lange bis alle Sätze da stehen.

Nun, das könnte man, wenn Kurt Gödel nicht 1931 bewiesen hätte, dass das nicht möglich ist. Er betrachtete "hinreichend mächtige Systeme", das sind solche, die zumindest natürliche Zahlen beinhalten. Natürlich könnte man die natürlichen Zahlen anders definieren, wichtig ist nur, dass man eine abzählbar unendliche Menge Zahlen hat (außerdem benötigt der Beweis ein paar arithmetische Operationen). Dann ist das System entweder unvollständig oder widersprüchlich. Ziemlich ernüchternd, aber wahr.

Weitere Einsichten liefert der Beweis: Gödel sagte, jeder aus dem System ableitbare Satz bekäme eine Nummer. Nun gibt es eine Nummer, die mehr oder weniger für den mathematischen Satz "Nicht ableitbar" steht. Wäre nun genau dieser Satz aus dem System ableitbar, dann gäbe es einen Wiederspruch, denn der Satz an sich sagt ja aus, dass er nicht ableitbar ist, wie sollte das dann gehen?

Die andere Möglichkeit ist, dass der Satz gemäß seiner Aussage nicht aus dem System abgeleitet werden kann, dann wäre die Sache wieder Widerspruchsfrei, aber dann ließen sich nicht mehr alle Sätze ableiten, denn es gäbe diese eine Nummer, die per Definition zum System gehört, aber nicht ableitbar ist. Das ist jetzt natürlich sehr vage formuliert, und auf Bedarf (Mail oder Kommentar reicht), würde ich das hier etwas mathematischer formulieren. Die Idee dahinter sollte aber klar geworden sein.

Welche Konsequenzen ergeben sich daraus? Nun, die bessere Wahl ist vermutlich ein unvollständiges System. Andernfalls könnte man nicht auf die Richtigkeit der Ergebnisse vertrauen, denn es gäbe da irgendwo einen Widerspruch, der genau deinen Beweis zerstören könnte. Unser mathematisches System scheint zu den Unvollständigen zu gehören, denn es gibt unentscheidbare Sätze. Einen Widerspruch in unseren Axiomen hat man dagegen bisher noch nicht gefunden.

Interessanterweise ist der Gedankengang der gleiche, wie der den man benutzt um das Halteproblem zu zeigen. Das Halteproblem sagt aus, dass es allgemein nicht entscheidbar ist, ob ein Programm (oder eine Turingmaschine) überhaupt irgendwann stoppt, geschwiege denn das richtige Ergebnis zu liefern. Das versetzte der automatischen Programmverifikation einen Schlag, denn es damit war gezeigt, dass man keine Hoffnung haben kann, jemals alle Programme automatisch auf Richtigkeit überprüfen zu können.

Viele meiner Suchanfragen lassen vermuten, dass einige Informatikstudenten im ersten Semester händeringend nach Beispielen suchen, wie man mit der O-Notation umgeht. Ich werde hier ein Beispiel durchrechnen, in der Hoffnung dass es jemandem hilft. Lasst doch ein Kommentar da wenn das der Fall ist ;)

Also, neben der informellen Beschreibung der O-Notation gibt es natürlich auch den streng formalen Weg. Zunächst nehme ich mir mal den Bubble-Sort heraus und kopiere den Pseudocode von Wikipedia:

prozedur bubbleSort( A : Liste sortierbarer Elemente ) definiert als:
  n := Länge( A ) - 1
  wiederhole
    vertauscht := falsch
    für jedes i in 0 bis n wiederhole:
      falls A[ i ] > A[ i + 1 ] dann
        vertausche( A[ i ], A[ i + 1 ] )
        vertauscht := wahr
      falls ende
    für ende
    n := n - 1
  während vertauscht
prozedur ende

Jetzt analysieren wir, wie man diesen Algorithmus bezüglich der O-Notation klassifizieren muss. Zunächst einigen wir uns darauf, dass wir nur Zuweisungen, Additionen und Vertauschungen (was ja auch nur Zuweisungen sind) als Rechenschritt zählen. Alles andere kostet natürlich auch Zeit, macht aber verhältnismäßig wenig aus.

Also los: Zeile zwei ist eine Zuweisung, das ist ein Rechenschritt. Alles was zwischen Zeile drei und  zwölf steht  wird wiederholt, und zwar so lange bis das Array sortiert ist. Wann ist das im schlimmsten Fall passiert? Natürlich wenn das Array umgekehrt sortiert ist. Denn dann muss das vorderste Element nach hinten und umgekehrt. Da Bubble-Sort immer nur direkte Nachbarn vertauscht, muss jedes Element also ganz durchgeschoben werden. Also weiter, das erste Element muss also ganz nach hinten, braucht dafür n Durchläufe der "für"-Schleife. Pro einen solchen Durchlauf brauchen wir einen Vergleich, eine Vertauschung und eine Zuweisung. Wir sind also im Moment bei . Dann wird noch das n heruntergezählt und dann wird die "wiederhole"-Schleife durchlaufen. Das passiert auch n-Mal in unserem worst-case.

Da bekommen wir also und damit . Gut, wie erwartet ist das eine quadratische Laufzeit, bleibt nur noch formal zu zeigen dass das auch wirklich ist. Dafür ist natürlich zunächst die formale Definition nötig, die sieht so aus:

Da steht also folgendes: Es gibt eine Funktion g, die schneller oder gleich schnell als unsere Funktion f wächst. Dazu multiplizieren wir noch eine Konstante c dran, die wir uns für den Beweis wählen können. Plastischer wirds erst, wenn ich das mal eben für das Beispiel durchführe.

Jetzt muss ich nur noch ein c und ein finden, für das die obige Gleichung gilt, dann gilt es auch für alle größeren n und der Beweis ist geführt. Dafür dividiere ich aber erst durch , dann wird es einfacher:

Ich wähle und c=5, die Gleichung ist erfüllt und es ist leicht zu sehen, dass sie auch erfüllt bleibt, wenn das n größer wird. Ab dem bleibt die Bubble-Sort Funktion also immer im -Bereich, Beweisende.

Ich bin im echten Leben eine äußerst schweigsame Person und wenn ich mal in irgendeiner Gesellschaft bin, fühlt sich immer irgendwann jemand genötigt, mir irgendwelche Fragen zu stellen. Ich würde präferieren einfach da zu sitzen und zu zu hören, aber das funktioniert so gut wie nie. Also erzähle ich ein paar Dinge von dem, was ich so mache und für was ich mich interessiere. Und weil man als normaler Mensch die Konversation nach einer Frage nicht einfach so abbricht, stellen die meisten dann Folgefragen, woraufhin ich etwas ins Detail gehe und 1-2 Dinge aus der Mathematik anschneide die mich besonders interessieren. Und jetzt kommt dann normalerweise die Frage "Und wofür braucht man das alles?".

An dieser Stelle bin ich immer leicht genervt. Ich frage ja auch nicht nach der Daseinsberechtigung des Berufes meines Gesprächspartners. Trotzdem habe ich natürlich immer ein paar Beispiele parat, die einfach genug sind damit sie der Durschnittsmensch versteht, aber schwierig genug um kurz drüber nachdenken zu müssen. Eins davon ist das Drei-Ziegen-Problem...

Du bist in einem Quiz und hast drei Türen vor dir. Hinter einer Tür befindet sich ein Hauptpreis, hinter den beiden anderen eine Niete. Du musst eine Tür wählen. Wenn du den Hauptpreis triffst, öffnet der Showmaster zufällig eine andere Tür und präsentiert die Niete, deine Tür bleibt verschlossen. Wenn du eine Niete triffst, öffnet der Showmaster die Tür mit der anderen Niete dahinter.

Jetzt darfst du entscheiden, ob du bei deiner Tür bleibst oder die verbliebene wählst. Sollte man wechseln?

Jetzt überlegen die meisten kurz und fühlen sich dann besonders schlau wenn sie sagen "Ist egal, die Wahrscheinlichkeit für den Hauptpreis ist 50/50." (Ha, dem Mathefuzzi hab ichs gezeigt, braucht eh keiner was der macht.) Dann sage ich "Nein, du bist besser dran wenn du die Tür wechselst. Die Wahrscheinlichkeit mit einem Türwechsel zu gewinnen ist 2/3, deine erste Tür hat nur eine Wahrscheinlichkeit 1/3 zu gewinnen." Natürlich beharren jetzt die meisten auf ihrem Standpunkt, es gibt ja nur noch zwei Möglichkeiten und du hast eine gewählt. Da muss die Wahrscheinlichkeit 50/50 sein. Ich diskutiere also kurz, ohne echte Argumente zu geben, lasse den anderen immer sicherer in seiner Meinung werden um dann folgendes zu sagen:

"Okay, dann stell die folgendes vor: Es gibt tausend Türen, du wählst dir eine aus. Der Showmaster öffnet 998 andere Türen, es bleiben also nur eine Tür irgendwo in der Mitte über und deine. Würdest du immer noch sagen du hättest am Anfang mit 50%iger Wahrscheinlichkeit die richtige Tür gewählt?" Es dauert ein paar Sekunden bis das gesackt ist und dann kommt die Erkenntnis. Die Gewinnwahrscheinlichkeit deiner ersten Wahl ist natürlich abhängig von der ersten Situation. Die Wahrscheinlichkeit bei der 1000-Türen Variante ist zuerst 1/1000, und dann spalten wir die Probleme sozusagen ab. Das erste Problem ist, "da ist eine Tür". Nichts anderes. Das was hinter der Tür ist gehört dir. Die Wahrscheinlichkeit dass da was ist, ist 1/1000. Das zweite Problem sind die 999 anderen Türen. Die Wahrscheinlichkeit pro Tür ist 1/1000. Der Showmaster hat bereits 998 Türen geöffnet, es bleibt noch eine über, worauf sich die 998*(1/1000) anderen Wahrscheinlichkeiten übertragen. Deine Tür hat aber immer noch 1/1000 während die noch geschlossene Tür aus dem zweiten Problem jetzt 999/1000 hat.

Wenn jemand das begriffen hat, kommen normalerweise keine Fragen mehr und ich kann weiter da sitzen und zu hören. Ich rede mir selber ein, dass man mich danach nicht als Klugscheißer sieht, sondern die Wichtigkeit von Mathematik erkannt hat. Obwohl die Wahrscheinlichkeit dafür nur 1/1000 ist.

Es gibt zwei (bekannte) Arten von Unendlichkeit. Das mag den ein oder anderen überraschen, denn umgangssprachlich versteht man "Unendlich" als "abzählbar Unendlich". Man kann sich irgendeine Menge vorstellen, z.B. A={3,6,9,12,...}. Diese Menge ist abzählbar Unendlich, denn es gibt eine so genannte Bijektion zwischen A und der Menge der natürlichen Zahlen |N. Eine Bijektion ist eine 1-zu-1 Abbildung, d.h. der eins (aus den natürlichen Zahlen) wird das erste Element aus A (3) zugeordnet. Der zwei (aus den natürlichen Zahlen) wird das zweite Element aus A (6) zugeordnet usw.

Nun mag der ein oder andere sagen "Aber in A sind doch wohl nur 1/3 aller natürlichen Zahlen enthalten und damit kleiner". Nun... nein. Das ist ja gerade das spannende an Unendlichkeit. Wenn A kleiner als |N wäre, dann müsste es ja eine Element aus |N geben, das keinen Partner in A hat. Welches würde das wohl sein? 372083742? Nein, denn es gäbe da ja das 372083742te Element aus A. Das gleiche Argument kann man für alle Elemente aus A benutzen, es gibt keine Zahl für die das Prinzip scheitert. Also, es gibt eine Bijektion zwischen A und |N, damit sind die Mengen gleich mächtig und A ist abzählbar Unendlich.

Die andere Art der Unendlichkeit heißt "überabzählbar Unendlich". Das Standardbeispiel dafür ist die Menge der reellen Zahlen |R. Sicher gehören 0,1 und 2... auch zu dieser Menge, aber auch 1.5 und 1.7. Man könnte auf die Idee kommen, einfach die Bijektion |R->|N: 0->0, 0.5->1, 1->2, 1.5->3, 2->4... zu benutzen, aber es gibt ja auch noch 0.2. Naja, geben wir der 0.2 die 5 aus |N. Aber 0.1? Was ist mit der 0.15, 0.25, 0.125, 0.114141? Kurz gesagt, egal welche zwei Zahlen aus |R wir nehmen, es gibt immer unendlich viele Zahlen dazwischen. Sogar 0.6456345345 und 0.6456345346 haben unendlich viele Zahlen dazwischen. Und jeder dieser "Zwischenzahlen" hat wiederum unendlich viele dazwischen. Damit kann es keine Bijektion mit |N geben, denn es kommen bei jeder Zuordnung von |R nach |N wieder neue (unendlich viele) Zahlen dazu. Überabzählbar unendlich eben.

Warum erzähle ich das alles? Nun, es gibt die so genannte Kontinuumshypothese, aufgestellt von David Hilbert. Diese besagt, dass es keine Menge gibt, die mächtiger ist als |N und weniger mächtig als |R. Entweder gibt es eine Bijektion mit |N oder |R. Naja, oder die Menge ist endlich. Paul Cohen bewies 1960, dass diese Hypothese in der Zermelo-Fraenkel-Mengenlehre (das ist sozusagen die Basis unserer Mathematik, darauf baut alles auf) nicht beweisbar ist. Dafür hat er die Fields-Medallie bekommen, und genau dieser Paul Cohen ist letzten Freitag gestorben. Dieser Post war also ein kleiner Tribut, wenn man so will.

Lance Fortnow, seines Zeichens ACM-Vize und bekannter Informatik-Theoretiker, hat in seinem Blog einen äußerst interessanten Beitrag, den ich mal kurz erwähnen möchte. Folgendes ist passiert: In Amerika läuft ja nach wie vor Jeopardy. Das ist eine Spielshow, wo am Schluss noch so eine Art Masterfrage gespielt wird. Jeder Spieler setzt einen beliebigen Betrag und bekommt den dann noch drauf, sollte er die Frage richtig beantworten. Der Trick ist, der Gewinner darf wieder in die Sendung kommen, also muss man sich genau überlegen wie viel man setzt.

Jetzt war in eben dieser Spielshow ein Informatiker zu Gast, der vor der Masterfrage 13400$ auf dem Konto hatte. Seine Gegner hatten jeweils 8000$. Sie mussten sowieso hoffen, dass der Informatiker die Masterfrage versaut oder so wenig Geld setzt, dass man eventuell noch vorbei ziehen könnte. Damit man aber nicht hinter dem 8000$-Gegener zurück bleibt, setzten beide alles. Beide könnten also auf 16000$ kommen und der Informatiker wusste all das natürlich auch und konnte sich denken, dass einer oder beide am Ende auf 16000$ kommen würde. Jetzt sehen die Regeln allerdings nicht vor, dass es nur einen Gewinner geben muss, also setzte der Informatiker 2600$ und kam damit auch auf 16000$, denn alle drei beantworteten die Masterfrage korrekt. Damit haben alle drei gewonnen und können in der nächsten Sendung wieder kommen. Er hätte auch 2700$ setzen können, aber er hätte nichts davon gehabt, alleiniger Sieger zu sein. Stattdessen setzte er gerade soviel, um bei richtig beantworteter Frage in die nächste Sendung zu kommen und bei falsch beantworteter Frage möglichst viel Geld mitzunehmen. Sehr intelligenter Einsatz.

Wenn man jetzt noch weiter gehen wollte, könnte man (wie ein Leser in dem Kommentaren schreibt) folgende Strategie anwenden. Alle drei spielen ganz normal, der Mensch mit dem wenigsten Geld setzt nichts, die anderen beiden setzen soviel, dass sie bei falsch beantworteter Frage den gleichen Betrag hätten. Dann wird natürlich die Frage von den beiden falsch beantwortet und alle können wieder kommen. Die Show läuft laut Wikipedia wöchentlich, damit könnte man seinen Lebensunterhalt bequem bestreiten.