Streichhölzer brechen oder Alice im Land der mathematischen Fehler

Ich habe ein Lieblingsrätselforum. Vor kurzem bin ich dort auf folgende Aufgabe gestoßen:

Einmal saß Vasya in seiner Küche und brach nichts für nichts zu tun. Pleite, pausiere und überlege - wie hoch ist die Wahrscheinlichkeit, dass mindestens ein Match genau in der Mitte pleite ist? Das Angebot an Streichhölzern für Vasya ist unbegrenzt.


Ich habe schnell bewiesen, dass die Wahrscheinlichkeit für dieses Ereignis Null ist. Ich bin stolz auf mich und habe eine Entscheidung und eine Antwort gepostet. Ich erwarte ein Pluszeichen im Karma. Es stellte sich jedoch heraus, dass die Antwort des Autors völlig anders war: 1 - 1 / e . Mit Blick auf die Zukunft werde ich sagen, dass diese Antwort falsch ist.

Falsche Copyright-Lösungen sind in Online-Rätseln weit verbreitet. Und ich würde diesen Beitrag niemals schreiben, wenn der Autor des Problems und seine falsche Lösung nicht der britische Logiker und Algebraist Charles L. Dodgson wäre, der besser unter dem Pseudonym Lewis Carroll bekannt ist.

Trivia


Alle Mathematiker wissen, dass der Autor von Alice im Wunderland ein Mathematiker war. Es ist allgemein bekannt, dass Königin Victoria, die beide Alice gelesen hatte, die anderen Bücher der Autorin lesen wollte und sehr überrascht war, als sie ihre Abhandlungen über analytische Geometrie und lineare Algebra brachte. Neben diesen grundlegenden Bereichen interessierte sich Carroll für mathematische Rätsel und andere interessante Dinge. 1888 veröffentlichte er das Buch "Mathematical Curiosities" und fünf Jahre später die Fortsetzung "Midnight Tasks", aus der die Aufgabe der Streichhölzer hervorging (natürlich erschien im Original kein Vasya). Fünf Jahre später starb Charles Dodgson.

Carrolls Entscheidung


Die im Forum veröffentlichte Lösung war sehr umständlich. Ich musste eher raten, was genau der Autor sagen wollte. Dann wandte ich mich der Quelle zu - dem Buch "Midnight Tasks". Ich musste mich ein zweites Mal wundern: Mein Forumsgegner hat kein einziges Wort falsch interpretiert. Als ich vom Russischen ins Russische übersetzte, bekam ich Folgendes:

Nimm n Übereinstimmungen, jede von ihnen wird durch n Punkte in n + 1 gleiche Teile geteilt. Angenommen, n ist ungerade und Übereinstimmungen können nur an markierten Punkten und mit jeweils gleicher Wahrscheinlichkeit unterbrochen werden. Dann ist die Wahrscheinlichkeit, dass eine Übereinstimmung nicht in der Mitte abgebrochen wird, 1 - 1 / n , und die Wahrscheinlichkeit, dass eine der n Übereinstimmungen nicht in der Mitte abgebrochen wird, ist (1 - 1 / n) n . Wenn wir n gegen unendlich tendieren, erhalten wir 1 / e. Dementsprechend beträgt die Wahrscheinlichkeit, dass mindestens eine Übereinstimmung genau in der Mitte abgebrochen wird, 1 - 1 / e .


Warum funktioniert das nicht?


In seiner Entscheidung verwaltete der Autor die einzige Variable n. Tatsächlich haben wir zwei Variablen: die Anzahl der Übereinstimmungen und die Anzahl der Punkte auf jeder von ihnen. Bezeichne sie mit p bzw. q. Dann ist die Wahrscheinlichkeit , dass keine Übereinstimmungen p nicht in der Mitte der q Punkte ist , an dem F (p, q) = gleich aufgebrochen werden (1 - 1 / q) p . Wenn wir p und q ins Unendliche stürzen, stürzt F auf die gewünschte Wahrscheinlichkeit ... oder stürzt nicht?

Das Problem ist, dass die Funktion zweier Variablen F nicht hatGrenze im Unendlichen. In diesem Fall können wir jedoch eine bestimmte Grenze erreichen, indem wir uns entlang einer bestimmten Flugbahn ins Unendliche bewegen (in diesem Fall findet Carroll eine Grenze entlang der durch die Gleichung p = q beschriebenen Flugbahn). Der Wert dieser Grenze hängt jedoch vollständig von der Flugbahn ab. Wenn wir zum Beispiel n Punkte markieren, aber nicht n Übereinstimmungen, sondern 2n nehmen, erhalten wir die Wahrscheinlichkeit (1 - 1 / n) 2n , die im Grenzfall 1 / e 2 ergibt .

Auf die gleiche Weise können wir 1 / e 3 und 1 / e 42 und sogar 1 / e 256 erhalten . Offensichtlich ist die gewählte Lösungsmethode für diese Aufgabe nicht geeignet.

Tiefer in die Wildnis
Es gibt zwei fundamentale Gründe, warum dieser Grenzwertübergang Carroll bei der Lösung des Problems (zumindest bei der korrekten Lösung) nicht geholfen hat und helfen konnte. Die erste davon lautet wie folgt: Wenn wir eine endliche Anzahl von Punkten auf einem Segment markiert haben, erhalten wir im Grenzfall eine unendliche, aber abzählbare Menge von ihnen. Gleichzeitig hat die Menge der Punkte des Segments ein Potenzkontinuum, das eine Unendlichkeit höherer Ordnung ist. Diese Unterscheidung wurde von George Cantor in den 70er Jahren des 19. Jahrhunderts getroffen. Zum Zeitpunkt des Schreibens von Midnight Problems war die Cantor-Mengen-Theorie jedoch noch nicht die Grundlage der mathematischen Analyse, zu der sie später wurde, und Carroll war laut Biographen "weit vom neuesten Stand der mathematischen Wissenschaft seiner Zeit entfernt". Auf die eine oder andere Weise stellen sie sich selbst an der Grenze des Ortes eines möglichen Bruchs als nur eine kleine Teilmenge der Übereinstimmungspunkte heraus.

Der zweite Grund ist, dass es sich im anfänglichen und im einschränkenden Fall tatsächlich um unterschiedliche Wahrscheinlichkeitsräume und unterschiedliche Definitionen von Wahrscheinlichkeit handelt. Wenn wir einen Punkt aus n auswählen, geschieht dies innerhalb des diskreten Wahrscheinlichkeitsraums, während die Auswahl eines Punkts auf einem Segment bereits eine geometrische Wahrscheinlichkeit darstellt. Auch wenn ein solcher Übergang korrekt ist, bedarf er einer zusätzlichen Begründung.


Was ist die richtige Antwort?



Natürlich Null. Die geometrische Wahrscheinlichkeit, zu einem einzelnen Punkt zu gelangen, ist null, nicht hineinzukommen ist eins. Die Wahrscheinlichkeit, in einer unendlichen Anzahl von Versuchen nicht einmal darauf zu kommen, ist gleich Eins im Grad der Unendlichkeit, was wiederum gleich ... Einheit ist? Nicht wirklich. Dies ist die gleiche Unsicherheit wie Null geteilt durch Null. Hier sind subtilere Methoden erforderlich.

Beeindruckend, nicht zu sehen
Lassen Sie uns zeigen, dass für ein beliebig kleines d die Wahrscheinlichkeit P, mindestens eine Übereinstimmung in zwei Hälften zu brechen, kleiner als d ist.

Finden Sie c so, dass 1 - d = e c . Um genau zu sein, c = ln (1 - d) . Die Streichhölzer sollen eine Einheitslänge haben und nummeriert sein. Füllen Sie in der Mitte des ersten Matches ein Segment der Länge 1 - e c / 2 , in der Mitte der zweiten Länge von 1 - e c / 4 , in der Mitte der n-ten Länge von 1 - e c / 2 n . Beachten Sie, dass c <0 ist , daher sind alle angegebenen Längen positiv.

Die Wahrscheinlichkeit, dass an einem Punkt, der zu dem schattierten Segment gehört, keine Übereinstimmung gebrochen wird, ist gleich e c / 2 · e c / 4E * ... * C / 2 n * ... e = (c / 2 + C / 4 + ... + C / 2 n + ...) = e c = 1 - d . Daher ist die Wahrscheinlichkeit, dass mindestens ein Fehler in das schattierte Segment fällt, d. Da, wenn eine der Übereinstimmungen in der Mitte unterbrochen wird, der Fehler auf das schattierte Segment fällt, können wir schließen, dass P <d ist .

Die Zahl d wurde willkürlich gewählt. Daher ist P kleiner als irgendeine positive Zahl, d.h. P = 0, t.p.d.


Tatsächlich


Der mysteriöse Fehler eines professionellen Mathematikers faszinierte mich und ich beschloss, das Originalbuch zu finden. Nachdem ich etwa zwanzig Minuten lang Google gequält hatte, gelang es mir immer noch, das zu erreichen, was ich wollte. Was habe ich gesehen

Seitenscan
Bild


Erstens war die Darstellung viel logischer als in der russischen Übersetzung, was mir anfangs sehr seltsam erschien. Vergleichen Sie zum Beispiel:

Die Wahrscheinlichkeit eines Ausfalls beträgt (n - 1) / n

und
Die Wahrscheinlichkeit, eine Übereinstimmung an einem Punkt zu brechen, beträgt (n - 1) / n


Zweitens fehlte einfach ein Teil des Beweises aus der Übersetzung im Original! Insbesondere wurde dort nicht einmal der Wert 1 - 1 / e angegeben . Außerdem gab es einen interessanten Hinweis:
NB Was hier folgt, wurde NICHT durchdacht.
Wichtiger Hinweis: Der nächste Teil wurde nicht sorgfältig durchdacht.


All dies deutet darauf hin, dass Carrolls „falsche Entscheidung“ eher ein Entwurf als eine vollständige Begründung war. Aus irgendeinem Grund, den wir nicht kannten, konnte er dieser Aufgabe einfach nicht genügend Aufmerksamkeit widmen. Aus Berechnungen geht auch hervor, dass die mathematische Analyse nicht das Spezialgebiet des Autors ist.

Nachdem ich die Frage geklärt hatte, die mich auf diese Weise beschäftigte, setzte ich mich hin und schrieb meinen ersten Beitrag über Habr.

Post-Skript
Ich dachte über die Kommentare bezüglich der Existenz dieser Wahrscheinlichkeit nach. In der Tat ist dies ein ernstes Problem, das ich nicht sofort bemerkt habe.

Wenn Sie versuchen, einen probabilistischen Raum „ins Gesicht“ zu bauen, in dem es sinnvoll ist, über eine solche Wahrscheinlichkeit zu sprechen, dann entsteht tatsächlich ein Problem mit dem Maß. Es scheint, dass es nicht so einfach ist, ein geeignetes Maß für die Sigma-Addition in einem Würfel mit abzählbaren Dimensionen festzulegen, wie ich es gerne hätte.

Andererseits ist es möglich, die Wahrscheinlichkeit eines Ereignisses während der endlosen Unterbrechung von Übereinstimmungen als Grenze für die Unterbrechung von Übereinstimmungen zu bestimmen, wenn die Tendenz besteht, dass Sie wissen, wo Sie sich befinden. Dann wird alles ganz offensichtlich und meine Entscheidung unter dem Spoiler ist nicht mehr erforderlich.

Jetzt auch beliebt: