Flos Mathe-Blog

(Quadrat-)Wurzeln aus ganzen Zahlen

Veröffentlicht am 20. Dezember 2011 in Allgemeines, Mathematik, Primzahlen and Zahlentheorie. 0 Comments Tags: Anmerkung, anschaulich, Beweis, interessant, interessante Fakten, Lösung, Mathematik, überraschend.

Den Standard-Beweis, dass $\sqrt{2}$ , die Quadratwurzel aus 2, keine Bruchzahl ist, kennt vermutlich fast jeder noch aus der eigenen Schulzeit. In dem vor zwei Jahren veröffentlichten Artikel “Roots of integers” in John D. Cook’s Blog (“The Endeavour“) entdeckte ich heute einen viel schöneren, weil allgemeineren Beweis dieser Tatsache, den ich nicht vorenthalten möchte.

Betrachtet man eine beliebige ganze Zahl $z$ und zieht deren $n$ -te Wurzel (falls $z \ge 0$ oder $n$ ungerade, ansonsten ist die $n$ -te Wurzel von $z$ nicht definiert), so gibt es nur zwei Möglichkeiten: Entweder die Wurzel ist ganzzahlig, oder sie ist eine irrationale Zahl. Ein irgendwie verblüffendes und doch einleuchtendes Resultat. Denkt man eine Weile über diese Aussage nach, so wird schnell intuitiv klar, dass sie richtig ist. Auch der Beweis ist nicht schwierig:

Sei $\frac{a}{b}$ eine vollständig gekürzte rationale Zahl. “Vollständig gekürzt” heißt, dass $a$ und $b$ keine gemeinsamen Teiler mehr haben. (Das ist keine echte Einschränkung, denn andernfalls lässt der Bruch sich um den größten gemeinsamen Teiler von $a$ und $b$ kürzen.) Weiter sei $n$ eine beliebige natürliche Zahl (und insbesondere nicht gleich 0).

Ist nun $\left(\frac{a}{b}\right)^n = \frac{a^n}{b^n}$ eine ganze Zahl, dann muss $b^n$ ein Teiler von $a^n$ sein. Aus dem Satz der eindeutigen Primfaktorzerlegung folgt, dass auch $b$ ein Teiler von $a$ sein muss. Da $a$ und $b$ als teilerfremd vorausgesetzt waren, gilt also $b = 1$ (ein negatives Vorzeichen können wir ggf. im Zähler $a$ des Bruches unterbringen, denn $\frac{a}{-b} = \frac{-a}{b}$ ).

Also ist auch $\frac{a}{b}$ eine ganze Zahl!

Wir können jetzt sofort per Widerspruchsbeweis die Behauptung folgern: Wäre die $n$ -te Wurzel der ganzen Zahl $z$ ein echter Bruch, das heißt $\sqrt[n]{z} = \frac{a}{b}$ für geeignete teilerfremde Zahlen $a \in \mathbb{Z}$ und $b \in \mathbb{N}$ mit $b > 1$ , dann wäre $\left(\frac{a}{b}\right)^n = z$ keine ganze Zahl (denn das geht nur für $b=1$ ).

Es können als Wurzeln von ganzen Zahlen also nur ganze oder irrationale Zahlen auftreten. Da $2$ offenbar keine Quadratzahl ist (denn zwischen $1^2 = 1$ und $2^2 = 4$ gibt es keine weiteren Quadratzahlen), muss $\sqrt{2}$ folglich irrational sein. Dasselbe gilt für alle $n$ -ten Wurzeln (für $n > 1$ ) aus ganzen Zahlen, die nicht Quadratzahlen sind.

Insbesondere sind zum Beispiel die Wurzeln aus Primzahlen immer irrational!

Der Beweis durch Widerspruch

Veröffentlicht am 16. Dezember 2011 in Beweismethoden, Mathematik, Paradoxa and Primzahlen. 0 Comments Tags: anschaulich, Beweis, fehlerhafter Beweis, Mathematik, paradox, Primzahlen.

Was ist der Beweis durch Widerspruch?

Um eine Aussage zu verifizieren kann man sich in der Mathematik vieler allgemeiner Beweis-Methoden bedienen. Eine davon ist etwa das sehr intuitive Schubfachprinzip. Auch der Beweis durch Widerspruch ist eine recht anschauliche Beweis-Methode, die in vielen Fällen Verwendung findet.

Oft ist dabei der Beweis durch Widerspruch, oder auch “indirekter Beweis”, sogar leichter zu führen als der “direkte”.

Und wie funktioniert das?

Nehmen wir einmal an, wir wollen die Aussage $A$ beweisen (zum Beispiel: “Es gibt unendlich viele Primzahlen” oder “Ein Schachbrett, auf dem zwei gegenüberliegende Ecken verdeckt sind, lässt sich nicht lückenlos mit 2×1-Dominosteinen überdecken”). Der direkte Beweis, das heißt die “direkte” Folgerung der Aussage aus anderen, schon bekannten Aussagen, will uns dabei aber nicht gelingen oder ist zu aufwändig. Dann können wir einen Umweg gehen, und die Gültigkeit der Aussage A indirekt beweisen. Die Artikelüberschrift verrät, dass ein Widerspruch dabei die zentrale Rolle spielt.

Wir betrachten dazu die Negation der Aussage $A$ , das heißt $\neg A$ . Nun versuchen wir, mit Hilfe von bereits bekannten Tatsachen und gültigen Umformungen und Schlussfolgerungen, aus $\neg A$ einen Widerspruch herzuleiten. Gelingt uns dies, dann wissen wir: Wäre die Aussage $A$ nicht wahr, dann könnten wir – mit gültigen Schlüssen – widersprüchliche Aussagen beweisen.

Gehen wir davon aus, dass die Mathematik widerspruchsfrei ist (So gutgläubig [1] muss man sein, auch wenn das nachgewiesenermaßen nicht beweisbar ist.), so muss dann die Aussage $A$ wahr sein!

Ein erstes Beispiel

Als Anwendung zeigen wir nun, dass sich ein Schachbrett nicht lückenlos mit Dominosteinen überdecken lässt, die 2×1 Felder groß sind, wenn zwei gegenüberliegende Ecken des Brettes nicht belegt werden dürfen (z.B. weil sie verdeckt oder ausgeschnitten sind).

Ein Schachbrett, auf dem die Felder a1 und h8 ausgeschnitten sind.

Zwei gegenüberliegende Ecken fehlen dem Schachbrett

Wir nehmen dazu an, das Schachbrett ließe sich mit solchen 2×1-Dominos lückenlos überdecken. Betrachten wir das Brett nicht nur als ein 8×8 Felder großes Raster, sondern beachten auch die abwechselnd schwarz und weiß (bzw. rot und blau, Schach ist bunt!) gefärbten Felder, so stellen wir fest: Jeder Dominostein bedeckt genau ein Feld jeder Farbe, das heißt in unserem Fall genau ein rotes und ein blaues Feld. Zählen wir die roten und blauen Felder, dann bemerken wir dabei auch schnell, dass es 32 blaue, aber nur 30 rote Felder gibt. (Zählen müssen wir gar nicht, und auch die konkreten Anzahlen sind unwichtig: Auf dem normalen Schachbrett, bevor wir die Eckfelder ausgeschnitten haben, gibt es gleich viele Felder jeder Farbe, die beiden entfernten Eckfelder waren beide rot. Also gibt es jetzt zwei rote Felder weniger als blaue, mehr müssen wir nicht wissen.)

Und das ist auch schon unser Widerspruch! Mit jedem Dominostein verdecken wir ein rotes und ein blaues Feld, niemals jedoch zwei blaue. Die angenommene lückenlose Überdeckung kann es nicht geben, da sonst (mindestens) ein Dominostein mehr blaue als rote Felder überdecken müsste.

Ein zweites Beispiel

In diesem zweiten Beispiel wird noch klarer, was der Widerspruch eigentlich bedeutet. (Im ersten Beispiel hätte man mit Hilfe der Farben der Felder auch noch “direkter” vorgehen können.) Wir wollen zeigen, dass es unendlich viele Primzahlen gibt.

Unsere Annahme ist jetzt also, es gäbe nur endlich viele Primzahlen. Dann muss es auch eine größte Primzahl geben, denn könnten wir zu jeder Primzahl eine noch größere finden, dann gäbe es eben mehr als endlich viele Primzahlen. Wir nennen diese (hypothetisch existierende) größte Primzahl $P$ und betrachten dann das Produkt

$1 \cdot 2 \cdot 3 \cdot 4 \cdot \ldots \cdot P = P!$

aller Zahlen von 1 bis einschließlich $P$ (siehe: Fakultät). Addieren wir zu dieser (riesig großen) Zahl $P!$ nun noch $1$ dazu, so erhalten wir eine Zahl $P! + 1$ , die durch keine der Zahlen $1, 2, 3, 4, \ldots, P$ teilbar ist. Denn beim Teilen durch eine dieser Zahlen lässt $P! + 1$ offenbar immer den Rest $1$ .

Wir wissen aber, dass jede Zahl sich als Produkt von Primzahlen schreiben lässt. Da $P$ die größte Primzahl ist, müsste also eine der Zahlen $1, 2, 3, \ldots, P$ ein Teiler von $P! + 1$ sein.

Wir konnten aus der Annahme, es gäbe nur endlich viele Primzahlen, also sowohl herleiten, dass $P! + 1$ durch eine der ersten $P$ natürlichen Zahlen teilbar ist, als auch, dass dies nicht der Fall ist. Ein Widerspruch!

Die anfängliche Annahme kann also nicht richtig sein, es muss demnach unendlich viele Primzahlen geben.

Mit einem Zitat von G. H. Hardy (Schachspieler und Mathematiker) zum Beweis durch Widerspruch schließt sich der Kreis in Bezug auf das erste Beispiel: “[Er] ist eine der schärfsten mathematischen Waffen. Dies ist ein weit kühnerer Zug als jedes Gambit im Schach; ein Schachspieler opfert dabei einen Bauern oder eine Figur, ein Mathematiker riskiert das ganze Spiel.”

Fußnoten

[1] “Gott existiert, weil die Mathematik widerspruchsfrei ist, und der Teufel existiert, weil wir das nicht beweisen koennen.” – André Weil

Erweiterung des Lemmas von Bézout

Veröffentlicht am 9. September 2009 in Beweismethoden and Mathematik. 1 Comment Tags: Beweis, Bézout, interessant, Lemma, Lemma von Bézout, Mathematik, Neuigkeiten, überraschend, verblüffend.

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

Veröffentlicht am 28. Mai 2009 in Anekdoten, Beweismethoden, Mathematik, Probleme and Rätsel. 1 Comment Tags: anschaulich, Beweis, interessant, interessante Fakten, Mathematik.

Von 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.

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.
Lege die große Scheibe von A nach B.
Das geht auch, schließlich liegen die anderen beiden Scheiben auf C.
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:

Verschiebe die drei oberen Scheiben von A nach C.
Hm. Das ist lösbar, haben wir ja schon gesehen.
Wir benötigen sieben Verschiebungen.
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.
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:

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.
Wir legen die größte, gewissermaßen die “neue”, Scheibe auf Platz B.
Das kostet eine einzige Verschiebung.
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

Veröffentlicht am 25. Mai 2009 in Angewandtes, Kombinatorik, Mathematik, Paradoxa, Probleme and Wahrscheinlichkeit. 2 Comments Tags: interessant, interessante Fakten, Mathematik, paradox, verblüffend, Wahrscheinlichkeit.

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.

Fußnoten:

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

Rätsel: Kopfrechnen

Veröffentlicht am 22. April 2009 in Mathematik, Probleme and Rätsel. 5 Comments Tags: interessant, Mathematik, Rätsel.

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

Veröffentlicht am 8. November 2008 in Angewandtes, Graphentheorie, Mathematik, Probleme and Rätsel. 2 Comments Tags: anschaulich, Euler, Graphentheorie, Mathematik, Problem, Rätsel.

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

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

Veröffentlicht am 3. Oktober 2008 in Mathematik, Primzahlen, Probleme and Rätsel. 2 Comments Tags: interessante Fakten, Mathematik, Neuigkeiten, Primzahlen, Rätsel.

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

Veröffentlicht am 3. Oktober 2008 in Angewandtes, Mathematik, Probleme and Rätsel. 0 Comments Tags: Mathematik, paradox, Problem, Rätsel.

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?

Veröffentlicht am 21. August 2008 in Angewandtes, Kombinatorik and Mathematik. 12 Comments Tags: Mathematik, Problem, Wahrscheinlichkeit.

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$ , geschrieben als $n!$ als $n \cdot (n-1) \cdot (n-2) \cdot \ldots \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.)

Flos Mathe-Blog

(Quadrat-)Wurzeln aus ganzen Zahlen