Two-Face’s one sided die

Eindeutiger Zufall

Im Film The Dark Knight trägt Harvey Dent eine Münze auf sich, die auf beiden Seiten das gleiche Symbol hat. Er wirft diese im Film mehrmals und lässt so „den Zufall“ entscheiden, was er als nächstes tun soll. Ich wollte mir ganz im Stile Harvey Dents ebenfalls eine Art Würfel bauen, der stets auf die gleiche Seite fällt. Dies ist tatsächlich möglich, und zwar in Form einer Möbiusschleife.

Eine Möbiusschleife lässt sich ganz einfach aus einem langen Streifen Papier herstellen: Man verdreht einfach das eine Ende des Streifens um 180° und fügt dann die beiden Enden zusammen. Es lässt sich einfach nachprüfen (etwa indem man mit einem Finger der Oberfläche entlangfährt), dass die entstandene Schleife nur eine Seite hat. Damit die Möbiusschleife aber tatsächlich wie ein Würfel geworfen werden kann, muss sie natürlich aus stabilem Material gebaut werden. Dazu bietet sich der 3D-Druck an.

3D-Druck: Vom Modell zum Objekt

Ich habe die Gratis-Software Blender benutzt, um ein 3D-Modell einer Möbiusschleife zu erstellen. Dabei bin ich im Wesentlichen den folgenden Ausführungen gefolgt: Blender-Forum. Ich habe zuvor noch kaum mit Blender gearbeitet und deshalb dauerte es eine Weile, bis ich tatsächliche die Schleife hingekriegt habe. Um der 2D-Schleife etwas Dicke zu verleihen, kann der Blender Modifier Solidify verwendet werden. Schliesslich habe ich noch mit Blenders Knife Project eine 1 in die Schleife gestanzt. Das entstandene 3D-Modell ist hier zu sehen:

 

 

 

IMG_3156
Prusa i3 des ETH Makerspace

Den 3D-Druck dieses Modells habe ich schliesslich im Makerspace an der ETH angefertigt. Dort gibt es mehrere Prusa i3 3D-Drucker, welche die Studierenden praktisch gratis verwenden dürfen (bloss die Materialkosten müssen selbst bezahlt werden, und die belaufen sich für ein Objekt der Grösse der Möbius-Schleife auf ca. 50 Rappen). Die Bedienung des Prusa i3 ist sehr benutzerfreundlich, es gibt eine intuitive Software, die aus dem 3D-Modell (als .stl-Datei) den Maschinencode für den Drucker generiert. Dabei berechnet die Software automatisch, wo Stützstrukturen nötig sind, um auch überhängende Stellen drucken zu können. Diese Stützstrukturen (im Beitragsbild oben noch sichtbar) können später leicht vom eigentlichen gedruckten Objekt abgebrochen werden. Der generierte Maschinencode kann via SD-Karte zum Drucker gebracht und ausgeführt werden. Der Druck dauert meist mehrere Stunden, die Dauer ist natürlich abhängig von der Grösse des Objekts und der eingestellten Qualität des Drucks (Anzahl Schichten pro Längeneinheit). Ich durfte den Druck zum Glück am Abend starten und dann am nächsten Tag fertig abholen, so hatte ich kaum zeitlichen Aufwand (vielen Dank an den Makerspace!). Mit einem Japanmesser habe ich schliesslich die Stützstrukturen von der Schleife abgelöst, fertig war der einseitige Würfel!

Bleiben die abschliessenden Fragen, ob sich der ganze Aufwand gelohnt hat und ob der Hype um den 3D-Druck tatsächlich berechtigt ist. Ich glaube das könnte leicht mit einem Würfelwurf beantwortet werden.

IMG_3179asdf

Quellen

Einführung in den 3D-Druck: ETH Makerspace

Die Karten werden neu gemischt

Nichts Neues

„Es gibt nichts Neues mehr. Alles, was man erfinden kann, ist schon erfunden.“ Dieses Zitat stammt von Charles H. Duell, leitender Angestellter des US-Patentamtes. Bemerkenswert ist aber nicht etwa die Aussage selber, sondern ihre Datierung – das Zitat stammt aus dem Jahre 1899. Die grosse Anzahl an neuen Erfindungen, die ihren Weg in unsere Gesellschaft gefunden haben, widerlegt eindeutig Duells Aussage. Aber wie sieht es heute aus? Ist es noch möglich etwas zu erschaffen, das die Welt noch nie gesehen hat?

Die Karten werden neu gemischt

Ich bezweifle nicht, dass geistreichere oder überraschendere Werke möglich sind, aber tatsächlich genügt bereits ein gewöhnliches Set bestehend aus 36 Jasskarten, um Neues zu erschaffen. Alles, was man dafür tun muss, ist das Set ordentlich zu mischen. Dadurch werden die Karten in eine zufällige Reihenfolge gebracht, 36! (36 · 35 ··· 1) verschiedene Möglichkeiten können dabei auftreten. Das Überraschende an Fakultäten ist, dass sie sehr schnell wachsen (siehe Anhang). So beträgt 36! bereits 3.72 · 1042.

Man stelle sich nun vor, dass jede Person, die je auf der Erde gelebt hat, ihr ganzes Leben mit dem Mischen von Karten verbracht habe – jede Sekunde eine neue (nie zuvor dagewesene) Reihenfolge. Laut Wikipedia beträgt die Anzahl der jemals geborenen Menschen etwa 110 Milliarden. Nehmen wir nun für alle Zeitalter eine konstante Lebenserwartung der Menschen von 80 Jahren an (das ist natürlich sehr grosszügig abgeschätzt). Was wäre dann die Wahrscheinlichkeit, dass man heute noch eine nie dagewesene Reihenfolge der Karten erreicht, wenn man die Karten zufällig mischt?

Die Wahrscheinlichkeit ergibt sich aus

99.9999999999999999999%

Bei ordentlichem Mischen der Karten kann man also mit enorm grosser Sicherheit sagen, dass die Reihenfolge der Karten noch nie zuvor existiert hat. Jedes Jassspiel schreibt so also unbemerkt Weltgeschichte.

 

Quellen

Beitragsbild: Gerrit van Honthorst: Die Falschspieler

Idee: Vsauce, Youtube (Math Magic), mit weiteren anschaulichen Beispielen zur Grösse von Fakultäten.

Anhang: Vorlesung Analysis I, ETH Zürich

 

Anhang

Für Mathematik-Interessierte: Die Fakultäten wachsen für grosse n ähnlich wie nn. Dies wird mit der Stirlingformel ausgedrückt:

Stirling-Formel

Für grosse n dominiert der Term nn im Nenner. Der Zähler bestehend aus n! wächst folglich ähnlich wie nn, da der Grenzwert des Bruchs 1 beträgt.

Das Auge und die Sonne

Eine elegante Falsch-Argumentation

Eigentlich hätte ich einen Beitrag darüber schreiben wollen, wie elegant die Naturwissenschaft sein kann. Es ist nämlich möglich, hätte ich begonnen, die Oberflächentemperatur der Sonne zu berechnen – und das nur mit der Kenntnis des sichtbaren Spektrums des menschlichen Auges. Und so wäre es weitergegangen: Für die Argumentation sind einzig die Evolutionstheorie Darwins und die Verteilung der Schwarzkörper-Strahlung Plancks nötig. Der für unser Sehorgan sichtbare Teil des elektromagnetischen Spektrums liegt ungefähr zwischen 350 und 650 nm. Für den Menschen – und wohl besonders für seine Vorfahren in der Evolutionsgeschichte – ist das Sehen von (überlebens-) wichtiger Bedeutung. Deshalb sollte man annehmen können, dass sich dieses Sinnesorgan im Laufe der Entwicklung optimiert hat und nun perfekt den Bedingungen auf der Erde angepasst ist. Da die natürliche elektromagnetische Strahlung zum allergrössten Teil von der Sonne stammt, ist es einleuchtend, dass das Auge gerade in dem Bereich am empfindlichsten sein sollte, in dem die Sonne am meisten Strahlung aussendet. Also sollte umgekehrt argumentiert das Maximum der Strahlungsleistung der Sonne gerade etwa in der Mitte des sichtbaren Spektrums liegen, also bei ungefähr 500 nm (Durchschnitt aus 350 und 650 nm). Nun kommt die Verteilung der Schwarzkörper-Strahlung zum Zug, welche Planck berechnete und damit den ersten Stein zur Quantenphysik legte. Für einen Schwarzen Körper (theoretischer Körper, der thermische Strahlung ideal absorbiert und emittiert) gilt abhängig von der Temperatur folgende Wellenlängenverteilung der thermischen Strahlung (bei welcher Wellenlänge gibt der Schwarze Körper wieviel Leistung ab):

Die Einheit ist gewöhnlich: 

(abgestrahlte Leistung normiert auf Fläche und Wellenlänge).

Sonnenspektrum

Die Sonne kann in sinnvoller Näherung als Schwarzer Körper betrachtet werden. Im folgenden Diagramm sind die gemessene Wellenlängenverteilung der Sonnenstrahlung (orange) und die theoretische Verteilung der Strahlung eines Schwarzen Körpers (gelb) eingezeichnet:

Sonne_Strahlungsintensitaet

Die beiden Kurven stimmen ziemlich gut überein. Die Maxima der Kurven liegen ungefähr bei einer Wellenlänge von 500 nm (im Diagramm oben ersichtlich). Das exakte Maximum der Schwarzkörper-Strahlung erhält man aus dem Wienschen Verschiebungsgesetz. Dieses findet man, wenn man die von Planck gefundene Verteilung der Schwarzkörper-Strahlung nach der Wellenlänge ableitet und gleich Null setzt:

Das dabei gefundene Verschiebungsgesetz lautet:

(der Wert aus der Wellenlänge, bei der die Strahlung maximal ist, multipliziert mit der Temperatur T, ist konstant).
Die Wellenlänge, bei der die Strahlung der Sonne maximal ist, scheint folglich abhängig von der Temperatur T der Sonne zu sein. Umgekehrt kann aus der maximalen Wellenlänge die Temperatur der Sonne bestimmt werden. Aus der Argumentation mit der Evolution haben wir weiter oben geschlossen, dass die maximale Strahlungsleistung der Sonne etwa in der Mitte des vom menschlichen Auge sichtbaren Spektrums liegen sollte – bei 500 nm oder 0.5 µm. Aus dem Wienschen Verschiebungsgesetz erhalten wir damit eine Temperatur T der Sonne von

Dies entspricht ziemlich genau der Oberflächentemperatur der Sonne (5’778 K). Damit konnten wir allein aus der Kenntnis des Wellenlängenbereichs des sichtbaren Spektrums des menschlichen Auges die Oberflächentemperatur der Sonne berechnen. Dabei haben wir zudem zwei grundlegende Erkenntnisse der Naturwissenschaft verwendet: die Evolution und die Verteilung der Schwarzkörper-Strahlung.  Die Schönheit der Naturwissenschaft konnte einmal mehr aufgezeigt werden, würde ich nun abschliessend schreiben und den Beitrag veröffentlichen. Unberücksichtigt würde dabei bleiben, dass die Schönheit der Naturwissenschaften genau darin liegt, dass sie sich keinen Deut um ihre Schönheit schert. Und dass das Vorangegangene schlicht falsch ist.

Die (unschöne) Wahrheit

Ich bin in Zusammenhang mit der Astronomie auf das Wiensche Verschiebungsgesetz gestossen und habe dabei die Wellenlänge ausgerechnet, bei der die Strahlung der Sonne maximal ist. Dass die resultierende Wellenlänge (etwa 500 nm, wie oben berechnet) gerade in der Mitte des sichtbaren Spektrums liegt, kann kein Zufall sein, war ich mir sicher. Zu verlockend ist die Kombination mit der Evolutionstheorie, welche die oben geführte Argumentation möglich macht und doch zweifellos ziemlich elegant ist. Eigentlich auf der Suche nach wissenschaftlichen Publikationen, die meine Evolutions-These bestätigen sollten, stiess ich schliesslich auf die Website scienceblogs.de und von dort auf die wissenschaftliche Publikation von Soffer und Lynch. Dort wurde ich auf meinen (zum Teil sogar in wissenschaftlichen Texten publizierten) Fehler aufmerksam gemacht. Ich werde hier nun kurz die Gründe aufführen, weshalb die Argumentation oben nicht richtig ist. Das Lesen der Publikation von Soffer und Lynch kann ich sehr empfehlen, sie ist bewundernswert klar verfasst.

Die Verteilung der Schwarzkörper-Strahlung ist eine Dichte-Funktion. Sie gibt an, wieviel Leistung vom Schwarzkörper ausgestrahlt wird, normiert auf eine Fläche (wenn der Körper auf eine grössere Fläche scheint, so ist natürlich auch die durch Strahlung übertragene Leistung grösser) und normiert auf ein Wellenlängen-Intervall. Es wird also die Strahlungsleistung der einzelnen Wellenlängen über ein Wellenlängen-Intervall „aufsummiert“ (bzw. integriert). Ähnlich würde man beispielsweise auch die Verteilung der Körpergrössen der Menschen in der Schweiz angeben. Es ist egal, wie gross nun das einzelne Individuum genau ist, viel interessanter sind die Anzahl Menschen, die beispielsweise zwischen 1.78 und 1.79 Meter liegen. Man normiert die Verteilung auf ein Intervall – in diesem Beispiel Zentimeter – und gibt dann die Anzahl der individuellen Werte an, die in dieses Intervall fallen.
Das menschliche Sehen wiederum ist keine Dichte-Funktion. Wir „sehen“ die Leistung der ins Auge einfallenden Strahlung bei 560, 530, bzw. 420 nm (RGB), weisen diesen Wellenlängen also einen eindeutigen Leistungs-Wert zu. Insofern hinkt der Vergleich zwischen dem menschlichen Sehen und der Verteilung der Schwarzkörper- (bzw. Sonnen-) Strahlung, da man hier „apples and oranges“ (nach Soffer und Lynch) vergleicht.

Dichte-Funktionen sind abhängig von den Intervallen, über die man normiert. Dies erscheint plausibel, da ja alle Einzelwerte über einem Intervall „aufsummiert“ werden. Werden die Intervalle geändert, so ändert sich auch die Dichte-Funktion. Normiert man die Schwarzkörper-Strahlung über Wellenlängen-Intervalle, so sieht die Kurve folgendermassen aus (wie im Diagramm oben schon gesehen):

solarspectrum1

Die kleine Kurve (mit „Luminous Efficiency“ bezeichnet) gibt die Empfindlichkeit des menschlichen Auges abhängig von der Wellenlänge an. Die Maxima der Schwarzkörper-Strahlung und der Empfindlichkeit des menschlichen Auges liegen ungefähr bei der gleichen Wellenlänge – genau wie in der obigen Argumentation vorausgesagt. Normiert man die Schwarzkörper-Strahlung allerdings auf Frequenz-Intervalle, so sieht die Sache ganz anders aus:

solarspectrum2

Die Kurve der Empfindlichkeit des Auges sieht ähnlich aus wie zuvor (sie ist in der Tat identisch zu derjenigen auf dem vorhergehenden Diagramm), allerdings hat sich die Kurve der Schwarzkörper-Strahlung verändert. Ihr Maximum liegt nun weiter links als dasjenige der Kurve des Auges – im infraroten Bereich. Der Grund dafür ist der folgende: Wellenlänge und Frequenz von Strahlung hängen über die Beziehung

zusammen. Dabei ist ν die Frequenz, λ die Wellenlänge und c die Lichtgeschwindigkeit. Durch Ableiten erhält man die Gleichung:

Der Faktor c/λ² ist gerade der Umrechnungsfaktor von Intervallen normiert auf die Wellenlänge in Bezug auf die Intervalle normiert auf die Frequenz. So sehen die gleichmässigen Intervalle auf dem linken Diagramm unten auf dem rechten verzerrt aus. Die Intervalle sind gleichmässig auf Wellenlängen normiert, werden sie aber ins auf Frequenzen normierte Diagramm gebracht, so werden sie durch den Faktor c/λ² verzogen. Die Intervalle sind bei grossen Frequenzen (kleinen Wellenlängen) viel grösser als bei kleinen Frequenzen (grossen Wellenlängen). Normiert man stattdessen auf gleichmässige Frequenz-Intervalle, so werden in Bezug auf diese Normierung bei den kleinen Frequenzen zu grosse Intervalle aufsummiert, das Maximum verschiebt sich zu kleineren Frequenzen (Infrarot-Bereich). Genau das sieht man im auf Frequenzen-Intervalle normierten Diagramm oben.

AJPSofferLynch (verschoben)AJPSofferLynch (verschoben)

 

 

 

 

 

 

Das Verzerren der Intervalle kann man folgendermassen gut plausibilisieren: Die Intervalle 100 nm bis 200 nm und 900 nm bis 1’000 nm sind offensichtlich gleich gross (Differenz von 100 nm). Rechnet man sie aber nun mit der Formel ν = c/λ um, so erhält man die folgenden Intervalle:

Das Intervall mit den kleineren Frequenzen ist nun viel kleiner als das Intervall mit den grösseren Frequenzen (wie im Diagramm oben aufgezeichnet).

Bei Dichte-Funktionen hängt das Maximum von der Intervall-Normierung ab, deshalb ist ein direkter Vergleich mit einer „normalen“ Funktion nicht sinnvoll. Das Maximum der Dichte-Funktion ist nicht allgemein gültig. So liegt das Maximum bei der Frequenz-Normierung bei grösseren Wellenlängen als bei der Wellenlängen-Normierung. Bei der „normalen“ Funktion des menschlichen Sehens dagegen wird das Maximum beim Wechsel von Wellenlängen auf Frequenzen nicht verändert.

Soffer und Lynch zeigen zudem auf, dass das menschliche Auge alles andere als ideal an das Sonnenspektrum angepasst ist. Dies einerseits wohl wegen der Wasserlebewesen-Vergangenheit des Menschen in der Evolutionsgeschichte und andererseits wegen den biochemischen Grenzen des Sehprozesses.

Abschliessend bringen Soffer und Lynch das ganze Problem auf den Punkt:

„The fact that in wavelength units the spectrum roughly agrees with the peak sensitivity of the eye is an accidental and meaningless quirk involving the units in which the spectrum is plotted.“ (S. 949)

Damit wäre die Argumentation nun endgültig abgeschlossen.

 

Quellen:

Soffer, Bernard H. und Lynch, David K.: Some paradoxes, errors, and resolutions concerning the spectral optimization of human vision. American Association of Physics Teachers, November 1999 (Link)

Nussbaumer, Harry und Schmid, Hans Martin: Astronomie, 8. Auflage. Vdf Hochschulverlag AG an der ETH Zürich, 2003.

Quellen Bilder:

Beitragsbild: nasa.gov
Spektrum Sonne: Wikipedia
Diagramme: aus Soffer und Lynch

Treaps

Das Problem

Das Ordnen und Durchsuchen von grossen Datenmengen sind Aufgaben, die in der Informatik häufig auftreten und schnell ausgeführt werden sollten. Wer will beispielsweise eine halbe Minute warten, bis Facebook beim Login den Benutzernamen in der Datenbank mit Millionen von Benutzern gefunden und mit dem eingegebenen Passwort verglichen hat? Genau dafür braucht es Algorithmen, die Daten geschickt abspeichern und so schnell wiederfinden können. Eine Lösung für diese Aufgaben sind sogenannte Treaps. Der Name setzt sich zusammen aus den Wörtern Tree und Heap und beschreibt die Idee ziemlich genau. Das Konzept der Treaps soll hier aufbauend erklärt werden:

Man versetze sich in die Lage eines (vergleichsweise kleinen) Social Networks, das eine Million Benutzer-IDs (Zahlen) abspeichern und schnell wiederfinden soll. Die offensichtlichste Lösung dafür ist wohl eine Liste. Beim Login geht das System die ganze Liste durch, bis die Benutzer-ID gefunden wurde. Im schlimmsten Fall müssen so also eine Million Zahlen verglichen werden. Wächst das Social Network weiter, so steigt auch die Zeit, die das System braucht, um die passende Benutzer-ID zu finden – und zwar linear. Bei einer Milliarde Benutzer müssen im schlimmsten Fall eine Milliarde Zahlen verglichen werden. Der Menschenverstand genügt um zu sehen, dass so das System irgendwann ziemlich langsam wird. Eine bessere Lösung muss her.

Binäre Suchbäume

Eine Lösung liefern sogenannte binäre Suchbäume (trees). Diese bestehen aus Knoten (nodes) und Verästelungen. Jeder Knoten besitzt eine Zahl (key) und maximal zwei ausgehende Äste (pointers) auf weitere Knoten. Beginnend mit einem obersten Knoten (root) entsteht so gegen unten ein „Baum“ mit immer mehr Verästelungen. Die untersten Knoten besitzen keine ausgehenden Äste mehr, sie werden auch Blätter (leaves) genannt.

Binärer Suchbaum
Grundaufbau eines binären Suchbaumes

Die Idee von binären Suchbäumen ist nun, den Baum so anzuordnen, dass bei jedem Knoten der linke ausgehende Ast auf einen Unterbaum mit kleineren Zahlen als die Zahl des Knotens und der rechte auf einen Unterbaum mit grösseren Zahlen als die Zahl des Knotens zeigt. So entsteht ein besonderer Baum.

Suchbaum
Suchbaum (Suche nach Zahl 25 dargestellt)

Will das System nun eine Zahl in diesem Baum suchen, so beginnt es beim obersten Knoten des Baumes. Mit einem Zahlenvergleich wird überprüft, ob die Zahl des Knotens grösser bzw. kleiner als die gesuchte Zahl ist. Entsprechend folgt es dem linken bzw. rechten Ast des Knotens. Dies wird solange weitergeführt, bis entweder der Knoten mit der richtigen Zahl gefunden wurde, oder der Ast, dem weiter gefolgt werden sollte, nicht mehr vorhanden ist. Im ersten Fall hat das System die Zahl gefunden, im zweiten Fall befindet sich die gesuchte Zahl nicht in der Menge. Das Hinzufügen von Zahlen in die Menge funktioniert sehr ähnlich. Befindet sich die Zahl noch nicht in der Menge, so folgt das System wiederum den entsprechenden Ästen und fügt schliesslich an der fehlenden Stelle einen neuen Knoten und den verbindenden Ast ein. Das Entfernen von Zahlen ist etwas komplizierter, kann aber vom System ebenfalls schnell ausgeführt werden. Ist der Knoten mit der zu löschenden Zahl gefunden, so kann dieser nicht einfach gelöscht werden, da so die verbindenden Ästen zu eventuellen Unterbäumen dieses Knotens fehlen würden. Folglich muss der zu löschende Knoten zuerst durch Rotationen, welche die Suchbaum-Eigenschaften des Baumes erhalten, zu einem Blatt gemacht werden (mehr dazu später). Da Blätter keine Äste zu Unterbäumen besitzen, kann der Knoten dann gelöscht werden. So weit das Konzept. Warum sollte das Abspeichern in dieser Form aber nun so viel besser als die Umsetzung mit der Liste sein?

Man stelle sich einen perfekten Baum vor: Jeder Knoten – bis auf die Blätter ganz unten – besitzt genau zwei Äste auf Unterbäume. Zählt man nun die Knoten der verschiedenen Ebenen ausgehend vom obersten Knoten, so stellt man exponentielles Wachstum fest: 1, 2, 4, 8, 16, 32, … Die Anzahl der Knoten – und somit auch die Anzahl der Zahlen, die im Baum gespeichert werden können – nimmt sehr schnell zu. Für die Operationen wie das Finden, Hinzufügen oder Löschen von Zahlen ist aber nur die Höhe des Baumes von Bedeutung. Bei 7 Zahlen braucht das System höchstens 3 Zahlenvergleiche, dann ist die Zahl gefunden. Die Anzahl der benötigten Operationen wächst folglich nur wie der Logarithmus der Anzahl Zahlen in der Menge. Bei einer Million Zahlen sind also nur log₂1’000’000 ≅ 20 Operationen nötig. Bei einer Milliarde genügen log₂1’000’000’000 ≅ 27. Das zeigt die Effektivität von Suchbäumen.

Perfekte und entartete Bäume
Ein „perfekter“ Baum (links) gegenüber einem „entarteten“ Baum (rechts)

„Entartete“ Bäume

Ein Problem gibt es aber noch: Wir haben hier von einem „perfekten“ Baum gesprochen. Was garantiert, dass der Baum wirklich „perfekt“ wird? Fügt man beispielsweise die Zahlen in geordneter Reihenfolge dem Baum zu, so entsteht ein entarteter Baum, der eigentlich wieder das Analoge zur besprochenen Liste darstellt. Das Problem des binären Suchbaumes ist also, dass der Baum bestehend aus den gleichen Zahlen auf verschiedene Weisen aufgebaut werden kann. Im schlimmsten Fall liefert er so gegenüber der Liste gar keinen Vorteil mehr. Dies sollte verhindert werden. Genau deshalb braucht es das Konzept des Heaps. Ein Heap ist ein Baum, bei dem jeder Knoten eine Priorität besitzt. Derjenige Knoten mit der höchsten Priorität befindet sich zuoberst. Alle Unterbäume müssen Knoten kleinerer Priorität aufweisen.

Heap
Heap mit Prioritäten (weiss)

Treaps

Der Treap verbindet die Konzepte des Suchbaumes und des Heaps: Jeder Knoten besitzt eine Zahl (key), eine zufällige Priorität (priority) und maximal zwei ausgehende Äste (pointers). Wiederum müssen alle Knoten des linken Unterbaumes eines Knoten eine kleinere Zahl aufweisen und diejenigen im rechten Unterbaum eine grössere. Dabei muss aber auch die Heap-Eigenschaft erfüllt werden: Alle Knoten in den Unterbäumen eines Knotens müssen eine kleinere Priorität aufweisen als der Knoten selber. Somit wird der Treap eindeutig: Zuoberst befindet sich der Knoten mit der grössten Priorität. Der linke Ast zeigt auf denjenigen Knoten, der im Unterbaum der Knoten mit kleineren Zahlen die grösste Priorität besitzt. Analog zeigt der rechte Ast auf denjenigen Knoten, der im Unterbaum der Knoten mit grösseren Zahlen die grösste Priorität besitzt. Dies wird so weitergeführt und der ganze Baum kann eindeutig aufgebaut werden (mit vollständiger Induktion beweisbar). Die zufällige Wahl der Prioritäten „garantiert“ unter den Gesetzen der Wahrscheinlichkeit einen annehmbar „perfekten“ Baum.

Treap
Treap mit Zahlen (schwarz) und Prioritäten (weiss)

Das Auffinden von Zahlen im Treap funktioniert gleich wie zuvor. Das Hinzufügen von Zahlen wird allerdings etwas komplizierter: Wie zuvor fügt man einen neuen Knoten an der benötigten Stelle an, da dieser aber nun eine zufällige Zahl als Priorität besitzt, könnte eventuell die Heap-Eigenschaft verletzt sein (wenn die Priorität grösser ist als diejenige des Knotens darüber).

Einfügen einer neuen Zahl
Einfügen einer neuen Zahl in den Treap. Die Heap-Eigenschaft wird verletzt und muss nun durch Rotationen wiederhergestellt werden.

In diesem Fall müssen Rotationen durchgeführt werden, welche die Suchbaum-Eigenschaften erhalten. Diese sind unten dargestellt:

Rotationen bei Suchbäumen
Rotationen von Unterbäumen, welche die Suchbaumeigenschaften erhalten.

Ist die Priorität des rechten Knotens zu gross, so wird eine Linksrotation durchgeführt, ist umgekehrt diejenige des linken zu gross, so wird gegen rechts rotiert. Man sieht leicht, dass dabei die Suchbaum-Eigenschaft erhalten bleibt. Das Löschen von Zahlen kann ebenfalls mit diesen Rotationen umgesetzt werden. Dabei setzt man die Priorität des zu löschenden Knoten auf -1 (kleiner als alle möglichen Prioritäten) und führt so lange Rotationen durch, bis die Heap-Eigenschaft wieder erfüllt ist. Nun ist der zu löschende Knoten zwingend ein Blatt des Treaps und kann somit entfernt werden.

Ich habe das Konzept des Treaps in der Programmiersprache C++ als Klasse umgesetzt. Der Quellcode ist am Ende dieses Beitrages zu finden. Die besprochenen Funktionen (Suchen, Hinzufügen, Löschen) und noch weitere sind als Memberfunktionen der Klasse Treap umgesetzt. Ich habe die Funktionen getestet, falls der Code aber dennoch Fehler enthalten sollte, wäre ich an Feedback interessiert.

 

Quellen

Quellcode Treap (C++): treap.cpp

Quelle Beitragsbild: Wikipedia
Quelle: Vorlesung Informatik für Mathematiker und Physiker, ETH

Die unendliche Treppe

Identische Bausteine werden aufeinander gestapelt: Ist es möglich, dies so zu tun, dass der Stapel beliebig weit nach vorne reicht, ohne dass er umfällt (siehe Bild)?

Schwerpunkte2b

Das Bauchgefühl scheint diese Frage sofort zu verneinen, es ist aber tatsächlich möglich – mathematisch betrachtet zumindest. Der Stapel wird optimiert (siehe Grafik). Konkret bedeutet das, dass der Schwerpunkt aller vorherigen Bausteine immer genau auf der Kante des nächsten Bausteines zu liegen kommen muss. So liegt beispielsweise der Schwerpunkt der ersten vier Bausteine auf der Kante des fünften Bausteins (in der Grafik mit den Pfeilen angedeutet). Bei diesem Aufbau steht der Turm gerade noch und fällt nicht um.

Harmonischebrueckerp copy

Nun folgt der mathematische Beweis, dass ein solcher Turm (mit unendlich vielen Bausteinen) in der Horizontale ins Unendliche strebt. Zuerst stellt sich die Frage, wie weit die einzelnen Bausteine gegenüber dem nachfolgenden Stein verschoben sein müssen, damit wie erwähnt der Schwerpunkt gerade über der Kante liegt. Schauen wir uns also den n-ten Stein an. Sein eigener Schwerpunkt liegt in der Mitte des Steins. Der Schwerpunkt der (n – 1) Steine über ihm liegt genau auf seiner linken Kante. Damit der Turm nicht kippt und der Schwerpunkt der n Steine genau auf der Kante des (n + 1)-ten Steins zu liegen kommt, muss

x • (n – 1) = (1 – x) • 1

gelten (Hebel mal Gewichtskraft). Die Variable x steht dabei für die Strecke, die der n-te Stein gegenüber dem nächsten verschoben ist, der Term (1 – x) folgt aus der Annahme, dass ein Baustein 2 Einheiten lang ist. Die Gleichung kann umgeformt werden zu

x • (n – 1) + x = 1
x • ((n – 1) + 1) = 1
x • n = 1
x = 1/n.

Somit ist der erste Stein gegenüber dem zweiten um 1/1 = 1 Einheit verschoben, der zweite gegenüber dem dritten um 1/2, etc. Daraus ergibt sich für die horizontale Ausdehnung des Stapels:

1 + 1/2 + 1/3 + 1/4 + 1/5 + … .

Mathematiker wissen, dass der Grenzwert dieser (harmonischen) Summe Unendlich ist. Dies kann einfach bewiesen werden:

1 + 1/2 + 1/3 + 1/4 + 1/5 + 1/6 + 1/7 + 1/8 + … >
1 + 1/2 + (1/4 + 1/4) + (1/8 + 1/8 + 1/8 + 1/8) + … =
1 + 1/2 + 1/2 + 1/2 + … .

Es ist keine grosse Kunst zu sehen, dass das ewig wiederholende Addieren von 1/2 zu 1 gegen Unendlich strebt. Somit ist es möglich, einen Stapel zu bauen, der horizontal beliebig weit reichen kann. Der Haken an der Sache ist, dass es extrem viele Bausteine braucht, um eine vernünftige Distanz zu erreichen (die gewonnene Strecke pro Stein beträgt ja 1/n, wird also immer kleiner), weshalb der Turm extrem hoch werden und eine unglaubliche Masse an Baumaterialien verschlingen würde. In der Theorie könnte man sich so aber (mit viel Geduld) eine unendliche Treppe bauen.

 

Quellen

Beitragsbild: endzeitinfo.files.wordpress.com
Bilder:  wundersamessammelsurium.info, wikipedia.org (verändert)

Gausssche Osterformel

Mond-Zyklen-1050x1680

Bereits im 1. Jahrhundert nach Christus wurde das Osterdatum auf den ersten Sonntag nach dem Frühlingsvollmond (Vollmond zwischen 21. März und 19. April) festgelegt. Das frühstmögliche Osterdatum im Jahr ist somit der 22. März (Vollmond am 21. März, Sonntag am 22. März), das späteste der 26. April (Vollmond und Sonntag am 19. April). Nun möchte man natürlich jedes Jahr das genaue Osterdatum kennen, nicht zuletzt da ja weitere Feiertage wie Auffahrt oder Pfingsten davon abhängen. Wie macht man das? Eine Möglichkeit ist natürlich, dass man das Datum jedes Jahr mit Tabellen der Mondzyklen und der Wochentage neu bestimmt. Für Mathematiker (später auch Informatiker) ist dies aber keine zufriedenstellende Lösung. Eine bessere Möglichkeit zur Bestimmung des Osterdatums entwickelte Karl Friedrich Gauss um 1800 – die Gaussche Osterformel. Diese funktioniert folgendermassen:

Gausssche Osterformel

Sei J das Jahr, dessen Osterdatum man berechnen möchte. M und N seien zwei Konstanten (gültig von 1900-2099), die 24 bzw. 5 betragen.

Dann mache man folgende Zuordnungen:

a = J mod 19 (Rest der Division von J durch 19)
b = J mod 4
c = J mod 7
d = (19a + M) mod 30
e = (2b + 4c + 6d + N) mod 7

Das Osterdatum fällt dann auf den (22 + d + e)-ten März oder (d + e – 9)-ten April.

Beispiel

J = 2014, M = 24, N = 5

a = 0 (da 2014/19 = 106 Rest 0)
b = 2 (da 2014/4 = 503 Rest 2)
c = 5
d = (0 + 24) mod 30 = 24
e = (4 + 20 + 144 + 5) mod 7 = 5

Ostern fällt 2014 auf den (24 + 5 – 9 = 20) – ten April (oh, das ist ja heute, was für ein Zufall).

Erklärung (Ansatz)

Mit der Variable d berechnet man, wie viele Tage nach dem 22. März der Frühlingsvollmond stattfindet. Der Mondzyklus hat gegenüber unserem Kalender eine Periode von ziemlich genau 19 Jahren (deshalb a = J mod 19). Pro Jahr verschiebt sich der Mondkalender um rund 19 Tage gegenüber unserem Kalender (deshalb 19*a). Ein Mondzyklus (von Vollmond bis Vollmond) dauert rund 30 Tage (deshalb d = (19a + M) mod 30).

Mit der Variable e berechnet man, wie viele Tage nach dem Frühlingsvollmond der nächste Sonntag (eben der Ostersonntag) stattfindet. (2b + 4c + N) mod 7 sind die Anzahl der Tage, die zwischen dem 22. März und dem auf dieses Datum folgende Sonntag liegen (mit den 2b werden die Schalttage einbezogen). Da man aber die Anzahl Tage zwischen dem Frühlingsvollmond und dem nächsten Sonntag wissen will, muss noch der Term 6d (-d würde zum selben Resultat führen) addiert werden.

Die Summe aus d und e ergibt die Anzahl Tage, die Ostern nach dem 22. März stattfindet. Addiert man diese mit 22, so erhält man das Osterdatum.

Ausnahmen

In seltenen Fällen kann die Gausssche Osterformel ein falsches Resultat liefern. Dies ist auf spätere Zusatzbestimmungen zur Berechnung des Osterdatums zurückzuführen. Die Osterformel wurde deshalb im 19. und 20 Jahrhundert noch verbessert.

 

Nun aber genug zur Mathematik hinter Ostern – ich wünsche allen schöne Tage!

 

Quellen

Beitragsbild: de.wallpaperpics.net
Wikipedia: Osterformel

Q.E.D.

Dürer Unterweysung der Messung

Was haben zwei beliebig lange Strecken stets gemeinsam? Ihre Länge, ist doch klar! Wer das nicht glaubt, soll sich einmal diesen Beweis anschauen:

Beweis

1. Man wähle zwei beliebig lange Strecken, die einen Punkt (hier der Punkt C) gemeinsam haben. Die anderen Endpunkte der Strecken seien die Punkte A und B. Im Folgenden soll bewiesen werden, dass die Strecke AC gleich lang wie die Strecke BC ist.

Beweis gleich lange Strecken 1

2. Man verbinde die Punkte A und B, so dass ein Dreieck ABC entsteht. Dann konstruiere man den Punkt O als Schnittpunkt der Winkelhalbierenden des Winkels ACB mit der Mittelsenkrechten von AB. Die Winkel ACO und OCB (Winkelhalbierende), sowie die Strecken AMAB und MABB (Mittelsenkrechte) sind identisch.

Beweis gleich lange Strecken 2

3. Nun konstruiere man die Projektionen des Punktes O auf die Strecken AC und BC. Die entstandenen Punkte nenne man Y und X (siehe Skizze). Die Winkel YOC und COX sind gleich gross (180°-90°-α = 90°-α). Somit sind die Dreiecke CYO und XOC kongruent, da sie eine Seite (CO) und die daran anliegenden Winkel gemeinsam haben (dritter Kongruenzsatz).

Beweis gleich lange Strecken 3

4. Da die Dreiecke CYO und XOC kongruent sind, haben sie auch die Seitenlängen CY und CX, bzw. YO und XO gemeinsam. Wir haben also bewiesen, dass CY = CX gilt. Nun bleibt nur noch YA = XB zu zeigen. Dazu führe man die Strecken AO und OB ein.

Beweis gleich lange Strecken 4

5. Die Dreiecke AMABO und BMABO sind kongruent, da sie zwei Seiten (MABO = MABO und AMAB = MABB) und den eingeschlossenen Winkel (90°) gemeinsam haben (zweiter Kongruenzsatz). Somit sind AO und OB gleich lang. Die Dreiecke AOY und BOX sind ebenfalls kongruent, da sie zwei Seiten (YO = XO, AO = OB) und den Winkel gegenüber der grössten Seite (90°) gemeinsam haben (vierter Kongruenzsatz). Somit sind auch die Strecken YA und XB gleich lang. Wir haben also gezeigt, dass CY = CX und YA = XB. Somit gilt auch CY + YA = CX + XB, was das Gleiche wie CA = CB ist. Die beliebig langen Strecken CA und CB müssen also gleich lang sein!

Beweis gleich lange Strecken 5

Wer trotz dieses extrem stichhaltigen Beweises immer noch nicht überzeugt ist, soll sich das Ganze einmal selber (möglichst genau) aufzeichnen. Nicht, dass irgendetwas faul wäre…

Quellen

Beweis: Clemens Pohle, Schweizer Mathematik-Olympiade
Beitragsbild: thumbs.dreamstime.com
Wikipedia: Kongruenzsatz

Kopfsache

New York

Ist die Mathematik nicht dann am schönsten, wenn kompliziert wirkende Dinge ganz einfach erklärt oder gar bewiesen werden können? Mit den folgenden Überlegungen kann man auf einfache Art zeigen, dass es mindestens 40 Einwohner in New York City geben muss, die genau gleich viele Haare auf dem Kopf haben.

Laut Wikipedia besitzt der Mensch je nach Haarfarbe rund 90’000 – 150’000 Kopfhaare. Da dies Durchschnittswerte sind, nehmen wir für die maximale Anzahl, die eine Person haben kann, 200’000 Kopfhaare an. Die Einwohnerzahl von New York City wurde 2012 auf über 8 Millionen geschätzt. Für diesen Beweis genügen 7’800’040 Einwohner. Nun zu den eigentlichen Überlegungen.

Der Beweis

Nach Annahme muss jeder Mensch eine Anzahl an Kopfhaaren haben, die zwischen 0 und 200’000 liegt. Somit gibt es 200’001 unterschiedliche Möglichkeiten (mit der 0). Nun kann man aus allen New Yorkern Gruppen bilden. Alle Personen mit einer vollständigen Glatze gehören zur Gruppe 0, alle Personen mit einem Kopfhaar zur Gruppe 1, … , alle Personen mit genau 200’000 Kopfhaaren zur Gruppe 200’000. Wenn alle Einwohner gleich viele Haare auf dem Kopf hätten, dann gäbe es nur genau eine Gruppe mit 7’800’040 Personen. Die Aussage, dass es mindestens 40 New Yorker gibt, die gleich viele Haare auf dem Kopf haben, wäre dann mehr als nur erfüllt. Im anderen Extremfall, wenn alle New Yorker sich gleichmässig auf die Gruppen aufteilen würden, gäbe es 200’001 Gruppen mit 39 Personen. Eine Person würde dann noch übrig bleiben (da 7’800’040 / 200’001 = 39 Rest 1). Da aber auch diese eine Anzahl an Kopfhaaren zwischen 0 und 200’000 haben muss, gehört sie zu einer der 200’001 Gruppen. Diese besteht dann folglich aus 40 Personen. Es gibt also auch in diesem (schlimmsten!) Fall eine Gruppe von 40 New Yorkern, die alle gleich viele Haare auf dem Kopf haben. Erstaunlich, nicht?

Quellen

Beitragsbild: wallibs.com
Wikipedia: New York City, Kopfhaar 
Skript „Schubfachprinzip“: imosuisse.ch

Infinite-Monkey-Theorem

Infinite-Monkey-Theorem

Das Infinite-Monkey-Theorem oder auf Deutsch „Theorem der endlos tippenden Affen“ hat nicht nur einen eigenen Eintrag auf Wikipedia, dieser wurde auch noch in die „Liste der lesenswerten Artikel“ aufgenommen.

Das Theorem besagt, dass ein Affe, der unendlich lange zufällig auf einer Schreibmaschine herumtippt, irgendwann fast sicher (die theoretische Wahrscheinlichkeit beträgt 100%) alle Werke von Shakespeares geschrieben haben wird. Jeder mögliche Text (wie wärs beispielsweise mit der Biografie deines zukünftigen Kindes?) würde im getippten Text (nebst Unmengen von zusammenhangslosen Buchstabenkombinationen) zu finden sein. In alltäglichen Zeitdimensionen kann man so jedoch keine Dichter ersetzen: Man müsste einen Affen (bei einer Tastatur mit 40 Zeichen und einer Geschwindigkeit von einem Anschlag pro Sekunde)  ca. 1200 Jahre lang tippen lassen, um mit 99.99% Wahrscheinlichkeit sagen zu können, dass er das Wort „HAMLET“ (Titel eines Werkes von Shakespeares) geschrieben hat. Der richtige Autor war da wohl schneller…

Das Infinite-Monkey-Theorem ist meiner Meinung nach ein unterhaltendes Gedankenexperiment. Ein Affe könnte in unendlicher Zeit das ganze Universum aus den einzelnen Atomen erschaffen haben…

 

Quellen

Wikipedia: Infinite-Monkey-Theorem
Beitragsbild: fc03.deviantart.net

Jackpot

Wahrscheinlichkeit Lottogewinn

Wahrscheinlichkeit Lottogewinn

Die Wahrscheinlichkeit, dass man beim Swisslotto den Jackpot knackt, beträgt 1:31’474’716 (ungefähr 0.000003%). Um zu zeigen, wie enorm klein diese Gewinnchance ist, habe ich im folgenden Beitrag 10 seltene Ereignisse zusammengestellt, deren Eintreffen wahrscheinlicher als der „Sechser im Lotto“ ist.

Seltene Ereignisse, die wahrscheinlicher als ein Lottogewinn sind

1. Zehn mal nacheinander die gleiche Zahl würfeln
Die Wahrscheinlichkeit zehn mal nacheinander die gleiche Zahl zu würfeln, beträgt 1:10’077’696 (1:69) oder ungefähr 0.00001%. Die Chance, dass beim Eintreffen dieses Ereignisses der Würfel gezinkt ist, stellt eine grössere Wahrscheinlichkeit dar.

2. Einen Vornamen richtig erraten
Auf der Seite firstname.de gibt es rund 90’000 Vornamen aus aller Welt. Ich habe nach ein Paar Vornamen gesucht und keinen gefunden, der nicht im System gespeichert wäre. Wenn man annimmt, dass es in Westeuropa ca. 90’000 verschiedene gängige Vornamen gibt, so beträgt die Wahrscheinlichkeit, dass man den Vornamen einer wildfremden Person richtig errät, etwa 1:90’000 (ungefähr 0.001%). Diese Chance kann man deutlich erhöhen, wenn man in der Schweiz auf Noah, Luca, David oder Mia, Alina, Laura (häufigste Vornamen) tippt.

3. Im nächsten Jahr ermordet werden
Laut dem Büro der Vereinten Nationen für Drogen- und Verbrechensbekämpfung UNODC gibt es jährlich in Westeuropa durchschnittlich 1 Opfer von Mord oder Totschlag auf 100’000 Einwohner. Somit beträgt die Wahrscheinlichkeit, dass es im folgenden Jahr gerade einen selber trifft, ungefähr 1:100’000 (ca. 0.001%).

4. Bei der ersten Geburt Vierlinge bekommen
Laut Wikipedia beträgt bei einer Geburt die Häufigkeit, dass gleich vier Babies zur Welt kommen, 1:600’000 (ungefähr 0.0002%). Somit ist dieses Ereignis rund 50 mal wahrscheinlicher als der Jackpot-Gewinn.

5. In einem Heft ein zufällig ausgewähltes Häuschen richtig erraten
Die Fläche eines A4-Papiers beträgt 210×297 (=62’320) mm2, diejenige eines Häuschens 4×4 (16) mm2. Somit gibt es auf einem Blatt rund 7’800 Häuschen (Vor- und Rückseite) und in einem Heft mit 100 Seiten etwa 780’000. Die Chance, ein zufälliges Häuschen in einem ganzen Heft richtig zu erraten, beträgt demnach etwa 1:780’000 (ungefähr 0.000013%).

6. Im nächsten Jahr durch einen Blitz tödlich verunfallen
Pro Jahr sterben in der Schweiz durchschnittlich 5 Personen durch einen Blitz. Somit beträgt die Wahrscheinlichkeit für den Durchschnittsschweizer, im nächsten Jahr durch solch einen Stromschlag tödlich zu verunfallen, ca. 1: 1’611’620 (ungefähr 0.00006%).

7. Eine sechsstellige Schweizer Autonummer richtig erraten
Es gibt 106 verschiedene sechsstellige Zahlen. Zusammen mit dem Wappen des Kantons sind somit 26’000’000 verschiedene sechsstellige Autoschilder möglich. Die Wahrscheinlichkeit, dass man gerade die richtige Nummer (mit dem Kanton) errät, beträgt folglich 1:26’000’000 (ungefähr 0.000004%).

8. Münze werfen, die auf der Kante landet
Laut einer Forschungsarbeit der Stanford University über Münzwürfe landet jede 6000-ste geworfene Amerikanische 5-Cent-Münze auf der Kante. Somit ist die Chance, dass eine geworfene Münze auf der Kante landet, etwa 1:6000 (ungefähr 0.02%). Dies ist also rund 250 mal wahrscheinlicher als ein Jackpot-Gewinn.

9. Vier mal nacheinander eine gezogene Jasskarte richtig erraten (ohne Trick)
Bei 36 Karten beträgt diese Wahrscheinlichkeit 1:1’679’616 (1: 364) oder etwa 0.00006%. Somit ist dieses Ereignis rund 19 mal wahrscheinlicher als der „Sechser im Lotto“.

10. Ein zufälliges Wort richtig erraten
Die Gesamtgrösse des deutschen Wortschatzes wird laut Wikipedia auf 300’000-500’000 Wörter geschätzt. Somit beträgt die Chance, ein zufällig ausgewähltes Wort richtig zu erraten ungefähr 1:400’000 (0.00025%). Ich habe am Ende dieses Beitrages ein Wort aus dem Duden (zufällig ausgewählt) hingeschrieben. Es sollte doch nicht so schwierig sein, dieses zu erraten. Immerhin ist dieses Ereignis ungefähr 80 mal wahrscheinlicher als der Jackpot-Gewinn…

 

Quellen

Wahrscheinlichkeit Jackpot Swisslotto: swisslotto.sodala.net
Website mit Vornamen: firstname.de
Häufigste Vornamen in der Schweiz: bfs.admin.ch
Wikipedia Wortschatz: de.wikipedia.org
Wikipedia Homicide Rate: en.wikipedia.org
Wikipedia Mehrlinge: de.wikipedia.org
PDF über Blitzgefahr: golfdoc.ch
Forschungsarbeit über Münzwürfe: www-stat.stanford.edu

Quelle Beitragsbild:

sngpokerstrategie.com

 

Wort aus dem Duden: präglazial (Wort aus der Geologie für voreiszeitlich)
Wahrscheinlich nicht gerade das erste, was einem in den Sinn kommt…

Illegale Farben

lucsblog Kopie

Viele DVDs und Programme werden heute mit geheimen Schlüsseln (Zahlen oder Buchstaben) kodiert, so dass sie nicht illegal vervielfältigt werden können. Wenn also diese Codes geknackt und über das Internet verbreitet werden, so kann dies zu einem grossen Problem für die Hersteller werden. Deshalb fordern einige, dass das Verbreiten von geheimen Schlüsseln für illegal erklärt wird. Somit gäbe es dann illegale Zahlen- oder Buchstabenfolgen. Aber es geht sogar noch einen Schritt weiter. Jeder Buchstabe kann in Zahlen und diese dann weiter in eine hexadezimale Zeichenkette (16er-System) umgewandelt werden. Diese werden in der Informatik gebraucht, um Farben zu definieren. So kann dann der Schlüssel als eine Kombination verschiedener Farben weitergegeben werden (was heutzutage auch so gemacht wird). Somit gibt es Farben, die nicht veröffentlicht werden sollten. Aber eine Farbe kann man ja auch nicht wirklich per Gesetz verbieten…

Beispiel: Von Buchstaben zu Farben

Da ich hier nicht illegale Schlüssel verbreiten möchte, nehme ich als Beispiel die Folge „LUCSBLOG“. Diese Buchstabenfolge kann mit der ASCII-Zeichenkodierung in binäre Zahlen (2er-System) umgewandelt werden. Die Zeichenfolge sieht dann so aus:

L = 01001100
U = 01010101
C = 01000011
S = 01010011
B = 01000010
L = 01001100
O = 01001111
G = 01000111

„LUCSBLOG“ wurde also nun zur Zahl „01001100 01010101 01000011 01010011 01000010  01001100 01001111 01000111“. Im Dezimalsystem lautet diese Zahl „5500376544776572743“ und im Hexadezimalsystem „4C554353424C4F47″. Eine Farbe besteht in der Informatik aus einer 6-stelligen Hexadezimalzahl. Es ergeben sich somit die Farben „4C5543“ und „53424C„, die restlichen Ziffern („4F47“) bleiben übrig. In einem Mal- oder Bildbearbeitungsprogramm kann man nun diese Farben in ein Bild malen. Den Rest schreibt man einfach unten hin. Die Farben im Beitragsbild entsprechen der Buchstabenfolge „LUCSBLOG“.

Schon hat man aus einer Text- oder Zahlenfolge eine Farbfolge gemacht. Diese sollte jedoch, wenn die ursprüngliche Folge ein geheimer Schlüssel war, nicht unbedingt verbreitet werden…

 

Nützliche Links:
Text zu Binär – Umrechner
Binär – Umrechner
Farben anzeigen

Quellen:
Illegal Numbers – Numberphile

Einmal um die Welt

Rügen Eisenbahnschiene

Man stelle sich die folgende Situation vor: Es wird eine riesige Eisenbahnstrecke rund um die Erde gebaut. Diese muss folglich die Länge des Erdumfangs (ca. 40’075’000 m) haben. So weit der Plan. Nun hat man sich aber beim Bau dieser Strecke um 10 m verrechnet, wodurch sie zu lang geworden ist und die beiden Enden, welche den Kreis schliessen sollten, nicht genau zusammenpassen. Man beschliesst die Enden trotzdem mit Gewalt zusammenzubringen und dann anschliessend die Eisenbahnstrecke weltweit auf kleine Stützen zu stellen, damit der Fehler ausgeglichen werden kann. Da werden wohl Stützen, die wenige Zentimeter hoch sind, genügen, oder?

Nicht ganz. Die Höhe der Stützen entspricht dem Radius des grossen Kreises (Erdumfang + 10m) minus den Radius des kleinen Kreises (Erdumfang).

Der Radius des grossen Kreises ist gleich 40’075’000 m + 10 m / 2π, also 6’378’135.94 m. Derjenige des kleinen Kreises ist gleich 40’075’000 m / 2π, also 6’378’134.34 m.

Wenn man nun die beiden Strecken subtrahiert, so kommt man zum Resultat 1.6 m. Die gebaute Eisenbahnstrecke muss also auf der ganzen Welt auf 1.6 m hohe Stützen gestellt werden, damit die Ungenauigkeit von 10 m (≈0.000025%) kompensiert werden kann. Erstaunlich, nicht?

19. Januar 2038

iStock_000009996218Medium-Kopie

Im Jahr 2038 wird das Ende unserer Zeit sein, wenn wir nicht vorher handeln. Das Ganze ist aber nicht schon wieder eine neue Weltuntergangs-Theorie, sondern hat mit Informatik und Mathematik zu tun…

Viele heutige Computersysteme berechnen die aktuelle Uhrzeit, indem sie die verstrichenen Sekunden seit dem 1. Januar 1970 00:00:00 (Zeitzone ±0)  abzählen. Diese werden als vorzeichenbehaftete 32-Bit-Zahl gespeichert. Eine 32-Bit-Zahl besteht aus 32 Stellen, die entweder eine 1 oder eine 0 enthalten können. Es können also 232 (= 4’294’967’296) verschiedene Zahlen dargestellt werden. Da es eine vorzeichenbehaftete Zahl ist (+ und -), können somit die Zahlen von -2’147’483’648 bis +2’147’483’647 (beim + als letzte Ziffer eine 7, da die 0 ja auch dazugehört) gespeichert werden. Umgerechnet bedeutet das die Zeitspanne vom 13. Dezember 1901 20:45:52 Uhr bis zum 19. Januar 2038 um 3:14:07 Uhr. Computersysteme, welche die aktuelle Zeit als vorzeichenbehaftete 32-Bit-Zahl speichern, werden also vom 19. Januar 2038 zurück zum 13. Dezember 1901 springen. Dies kann beispielsweise bei Banken verheerende Folgen haben. Deshalb sollten sie vorher auf 64-Bit umsteigen, womit dann Daten bis ins Jahr 292’277’026’596 dargestellt werden können (sollte vorerst reichen). Mit unserer „32-Bit-Zeit“ werden wir nur noch höchstens ca. 25 Jahre leben können, dann wird alles zu Ende gehen…

Übrigens: Diesen Beitrag habe ich so eingestellt, dass er am 5. Juli 2013 um 03:53:20 Uhr (Zeitzone ±0) veröffentlicht wird. Warum wohl?

 

Quellen: Unixzeit (Wikipedia) und „End of Time (Unix)“, Numperphile (Youtube)

Quelle Beitragsbild: erlebnisreise-mexiko.de

Das Ziegenproblem

türen

Das folgende Problem: Du hast es bei einer Show bis in die letzte Runde geschafft und stehst nun vor drei identisch aussehenden Türen. Hinter einer befindet sich ein Auto, hinter den zwei anderen jeweils eine Ziege (die man nicht unbedingt gewinnen möchte). Nun musst du eine der drei Türen auswählen und was sich dahinter befindet, gehört dir.
Nach deiner Wahl öffnet der Moderator aber nicht sofort die gewählte Tür, sondern macht zuerst eine der beiden anderen auf, hinter der sich eine Ziege befindet. „Möchten Sie noch etwas an Ihrer Wahl ändern?“, wirst du nun vom Moderator gefragt. Was tust du? Setzt du weiterhin auf die gleiche Tür oder änderst du deine Wahl?

Es klingt erstaunlich, aber wer seine Wahl ändert, gewinnt mit doppelter Wahrscheinlichkeit das Auto. Wenn du auf deiner gewählten Tür beharrst, so hast du eine Chance von 1/3 (ein Auto und zwei Ziegen), dass du das Auto gewinnst. Daran ändert das Öffnen einer „Ziegen-Türe“ nichts. Wenn man aber wechselt, so gewinnt man in 2/3 aller Fälle. Das kann man sich so vorstellen: Wenn man beim ersten Versuch gerade die Tür mit dem Auto gewählt hat und dann wechselt, so ist das Auto dahin. Falls man aber beim ersten Versuch auf eine der Ziegen getippt hat (da es zwei hat beträgt die Wahrscheinlichkeit dafür 2/3), dann gewinnt man das Auto, da ja der Moderator die Tür mit der anderen Ziege aufmacht und man dann zwingend zur Tür mit dem Auto wechselt. So seltsam es also auch klingen mag: Wer in diesem Fall seine Wahl ändert, verdoppelt seine Gewinnchancen.

Quelle Bild: www.analytix.de

9+7=10

binary

Wir alle rechnen mit dem Dezimalsystem. Wir zählen bis neun und beginnen dann bei zehn mit einer zweiten Stelle, der 1 vor der 0. Genau das Gleiche bei 100 (102), bei 1000 (103) und bei jeder folgenden Zehnerpotenz. Dies macht ja durchaus auch Sinn, da wir genau zehn Finger haben. Man muss aber überhaupt nicht so rechnen.

Computer beispielsweise rechnen mit dem Binärsystem. Sie kennen nur die Ziffern 0 und 1 (Strom oder kein Strom) und fangen bei jeder Zweierpotenz mit einer neuen Stelle an. Unser 1-10 sieht dann so aus:

1, 10, 11, 100, 101, 110, 111, 1000, 1001, 1010

Ein anderes halbwegs gebräuchliches System ist das Hexadezimalsystem. Da beginnt man bei den Sechzehnerpotenzen mit einer neuen Stelle. Die 10 in diesem System wäre also genau das Gleiche wie bei uns die 16. Für die Zahlen zehn bis fünfzehn müssen im Hexadezimalsystem neue Zeichen erfunden werden (da sie ja bis fünfzehn einstellig bleiben). Dafür hat man einfach die Buchstaben A-F genommen, damit man nicht noch neue Zeichen lernen muss. Unser 1-16 sieht dann so aus:

1, 2, 3, 4, 5, 6, 7, 8, 9, A, B, C, D, E, F, 10

Wenn man also nun die Zahlen 9 und 7 addiert, ist das Resultat zwar eigentlich immer noch das Gleiche, man schreibt es aber nicht als 16, sondern als 10. Die Rechnung würde also durchaus Sinn ergeben, wenn wir anstatt zehn sechzehn Finger hätten und deshalb mit diesem System rechnen würden. Da aber das Dezimalsystem als Standard angesehen wird, ist es nicht so ratsam, diese Rechnung bei der nächsten Prüfung hinzuschreiben. Obwohl sie eigentlich nicht falsch wäre.

Übrigens: Wer hat den Witz auf dem Beitragsbild verstanden?

Quelle Bild: equinoxstudios.files.wordpress.com

 

 

1729 – A rather dull number?

Law-of-Large-Numbers

Geschichte

Die Zahl 1729 ist als Hardy-Ramanujan-Zahl bekannt geworden. Ihre Berühmtheit begann als der Britische Mathematiker G. H. Hardy seinen kranken Indischen Kollegen Srinivasa Ramanujan in einem Spital besuchen ging. Dazu nahm sich Hardy ein Taxi, das, wie er bemerkte, die Nummer 1729 trug. Im Spital angekommen erzählte er dies Ramanujan, um mit ihm ins Gespräch zu kommen und meinte, dass diese Zahl „a rather dull number“ (eine ziemlich dumme/langweilige Zahl) sei. „No“, antwortete Ramanujan, „it is a very interesting number. It is the smallest number expressible as the sum of two positive cubes in two different ways.“ (Die kleinste Zahl, die man als Summe zweier positiver Kubikzahlen auf zwei unterschiedliche Arten bilden kann).

Beweis

Diese beiden Arten sind die folgenden:

1= 1         123 = 1728         1+1728 = 1729

93 = 729    103  = 1000        729+1000 = 1729

Fazit

Natürlich hat dies Ramanujan nicht gerade während des Gesprächs herausgefunden, sondern als Mathematiker einfach auswendig gekonnt. Ich finde es ist aber trotzdem eine lustige Geschichte und sicher auch bemerkenswert, wenn man bedenkt, dass der gute Mann auch noch krank war.

 

Quelle: Wikipedia

Quelle Bild: ahalffast.com