Mathematiker würfeln und bekommen Stein-Schere-Papier

Wie Bill Gates die Geschichte erzählt, forderte Warren Buffett ihn einmal zu einem Würfelspiel heraus. Jeder würde einen von vier Würfeln auswählen, die Buffett gehören, und dann würden sie würfeln, wobei die höhere Zahl gewinnt. Dies waren keine Standardwürfel – sie hatten eine andere Auswahl an Zahlen als die üblichen 1 bis 6. Buffett bot an, Gates zuerst wählen zu lassen, damit er den stärksten Würfel auswählen konnte. Aber nachdem Gates die Würfel untersucht hatte, gab er einen Gegenvorschlag zurück: Buffett sollte zuerst wählen.

Gates hatte erkannt, dass Buffetts Würfel eine merkwürdige Eigenschaft aufwiesen: Keiner von ihnen war der Stärkste. Hätte Gates zuerst gewählt, dann hätte Buffett einen anderen Würfel finden können, der ihn schlagen könnte (d. h. einen mit einer Gewinnchance von mehr als 50 %).

Buffetts vier Würfel (nennen wir sie A, B, C und D) bildete ein Muster, das an Stein-Schere-Papier erinnerte, in dem A Beats B, B Beats C, C Beats D und D Beats A. Mathematiker sagen, dass ein solcher Würfelsatz „intransitiv“ ist.

„Es ist überhaupt nicht intuitiv, dass [intransitive Würfel] überhaupt existieren sollten“, sagte er Brian Conrey, dem Direktor des American Institute of Mathematics (AIM) in San Jose, der 2013 eine einflussreiche Abhandlung zu diesem Thema verfasste.

Mathematiker haben das erfunden erste Beispiele von intransitiven Würfeln vor mehr als 50 Jahren und schließlich erwies sich Dass es möglich ist, intransitive Zyklen beliebiger Länge zu erstellen, wenn Sie Würfel mit immer mehr Seiten betrachten. Was Mathematiker bis vor kurzem nicht wussten, war, wie verbreitet intransitive Würfel sind. Müssen Sie sich solche Beispiele sorgfältig ausdenken oder können Sie Würfel zufällig auswählen und eine gute Chance haben, eine intransitive Menge zu finden?

Drei Würfel betrachten, wenn Sie das wissen A Beats B und B Beats C, das scheint ein Beweis dafür zu sein A ist der stärkste; Situationen wo C Beats A sollte selten sein. Und in der Tat, wenn sich die Würfelzahlen zu unterschiedlichen Summen addieren dürfen, dann glauben Mathematiker, dass diese Intuition zutrifft.

Aber ein Papier online gestellt Ende letzten Jahres zeigt sich, dass diese Intuition in einer anderen natürlichen Umgebung spektakulär versagt. Angenommen, Sie verlangen, dass Ihre Würfel nur die Zahlen verwenden, die auf einem normalen Würfel erscheinen, und dieselbe Summe wie ein normaler Würfel haben. Dann zeigte das Papier, wenn A Beats B und B Beats C, A und C grundsätzlich gleiche Chancen haben, sich gegeneinander durchzusetzen.

"Wissend, dass A Beats B und B Beats C gibt Ihnen nur keine Auskunft darüber, ob A Beats C," sagte Timothy Gowers von der University of Cambridge, ein Fields-Medaillengewinner und einer der Mitwirkenden an dem neuen Ergebnis, das durch eine offene Online-Zusammenarbeit, bekannt als Polymath-Projekt, bewiesen wurde.

Inzwischen noch einer jüngsten Papier analysiert Sätze von vier oder mehr Würfeln. Dieser Befund ist wohl noch paradoxer: Wenn Sie zum Beispiel vier Würfel zufällig auswählen und das finden A Beats B, B Beats C und C Beats D, dann ist es leicht mehr wahrscheinlich für D schlagen A als umgekehrt.

Weder stark noch schwach

Die jüngsten Ergebnisse begannen vor etwa einem Jahrzehnt, nachdem Conrey an einem Treffen für Mathematiklehrer teilgenommen hatte, bei dem es um intransitive Würfel ging. „Ich hatte keine Ahnung, dass solche Dinge existieren könnten“, sagte er. „Ich war irgendwie fasziniert von ihnen.“

Er beschloss (später kam sein Kollege hinzu Kent Morrison bei AIM), um das Thema mit drei Highschool-Schülern zu erkunden, die er betreute – James Gabbard, Katie Grant und Andrew Liu. Wie oft, fragte sich die Gruppe, werden zufällig ausgewählte Würfel einen intransitiven Zyklus bilden?

Intransitive Würfelsätze gelten als selten, wenn sich die Seitenzahlen der Würfel zu unterschiedlichen Summen addieren, da der Würfel mit der höchsten Summe wahrscheinlich die anderen schlägt. Also beschloss das Team, sich auf Würfel zu konzentrieren, die zwei Eigenschaften haben: Erstens verwenden die Würfel die gleichen Zahlen wie auf einem Standardwürfel – 1 bis n, im Falle einer n-seitige sterben. Und zweitens ergeben die Seitenzahlen die gleiche Summe wie bei einem Standardwürfel. Aber im Gegensatz zu Standardwürfeln kann jeder Würfel einige der Zahlen wiederholen und andere weglassen.

Bei sechsseitigen Würfeln gibt es nur 32 verschiedene Würfel, die diese beiden Eigenschaften haben. Mit Hilfe eines Computers konnte das Team also alle Tripel identifizieren, in denen A Beats B und B Beats C. Das stellten die Forscher zu ihrem Erstaunen fest A Beats C in 1,756 Dreiergruppen und C Beats A in 1,731 Tripeln – nahezu identische Zahlen. Basierend auf diesen Berechnungen und Simulationen von Würfeln mit mehr als sechs Seiten, vermutete das Team dass, wenn die Anzahl der Würfelseiten gegen unendlich geht, die Wahrscheinlichkeit, dass A Beats C nähert sich 50%.

Die Vermutung mit ihrer Mischung aus Zugänglichkeit und Nuancen erschien Conrey als gutes Futter für ein Polymath-Projekt, in dem viele Mathematiker online zusammenkommen, um Ideen auszutauschen. Mitte 2017 schlug er Gowers, dem Begründer des Polymath-Ansatzes, die Idee vor. „Mir hat die Frage wegen ihres Überraschungswerts sehr gut gefallen“, sagte Gowers. Er schrieb ein Blog-Post über die Vermutung, die eine Flut von Kommentaren hervorrief, und im Laufe von sechs weiteren Beiträgen gelang es den Kommentatoren, sie zu beweisen.

In ihrer Zeitung, online veröffentlicht Ende November 2022 besteht ein wesentlicher Teil des Beweises darin, zu zeigen, dass es größtenteils keinen Sinn macht, darüber zu sprechen, ob ein einzelner Würfel stark oder schwach ist. Buffetts Würfel, von denen keiner der stärksten der Packung ist, sind nicht so ungewöhnlich: Wenn Sie einen Würfel zufällig auswählen, hat das Polymath-Projekt gezeigt, ist es wahrscheinlich, dass er etwa die Hälfte der anderen Würfel schlägt und gegen die andere Hälfte verliert. „Fast jeder Würfel ist ziemlich durchschnittlich“, sagte Gowers.

Das Projekt weicht in einer Hinsicht vom ursprünglichen Modell des AIM-Teams ab: Um einige technische Einzelheiten zu vereinfachen, erklärte das Projekt, dass die Reihenfolge der Zahlen auf einem Würfel wichtig ist – so würden beispielsweise 122556 und 152562 als zwei verschiedene Würfel betrachtet. Aber das Ergebnis von Polymath, kombiniert mit den experimentellen Beweisen des AIM-Teams, erzeuge eine starke Vermutung, dass die Vermutung auch im ursprünglichen Modell zutrifft, sagte Gowers.

„Ich war absolut erfreut, dass sie diesen Beweis erbracht haben“, sagte Conrey.

Bei Ansammlungen von vier oder mehr Würfeln hatte das AIM-Team ein ähnliches Verhalten wie bei drei Würfeln vorhergesagt: Zum Beispiel, wenn A Beats B, B Beats C und C Beats D dann sollte es eine ungefähr 50-50-Wahrscheinlichkeit geben D Beats A, nähert sich genau 50-50, wenn die Anzahl der Seiten auf den Würfeln gegen unendlich geht.

Um die Vermutung zu testen, simulierten die Forscher Kopf-an-Kopf-Turniere für Sätze von vier Würfeln mit 50, 100, 150 und 200 Seiten. Die Simulationen folgten ihren Vorhersagen nicht ganz so genau wie im Fall von drei Würfeln, waren aber immer noch nah genug, um ihren Glauben an die Vermutung zu stärken. Aber obwohl die Forscher es nicht bemerkten, trugen diese kleinen Diskrepanzen eine andere Botschaft: Für Sätze von vier oder mehr Würfeln ist ihre Vermutung falsch.

„Wir wollten wirklich, dass [die Vermutung] wahr ist, denn das wäre cool“, sagte Conrey.

Bei vier Würfeln Elisabetta Cornacchia der Eidgenössischen Technischen Hochschule Lausanne und Jan Hązła des African Institute for Mathematical Sciences in Kigali, Ruanda, zeigte in a Krepppapier Ende 2020 online gepostet, dass if A Beats B, B Beats C und C Beats D und dann D hat eine Chance von etwas mehr als 50% zu schlagen A – wahrscheinlich irgendwo um die 52 %, sagte Hązła. (Wie bei der Polymath-Arbeit verwendeten Cornacchia und Hązła ein etwas anderes Modell als in der AIM-Arbeit.)

Die Erkenntnis von Cornacchia und Hązła ergibt sich aus der Tatsache, dass ein einzelner Würfel zwar in der Regel weder stark noch schwach ist, ein Würfelpaar jedoch manchmal gemeinsame Stärkebereiche haben kann. Wenn Sie zwei Würfel zufällig auswählen, haben Cornacchia und Hązła gezeigt, besteht eine gute Wahrscheinlichkeit, dass die Würfel korrelieren: Sie neigen dazu, gegen dieselben Würfel zu schlagen oder zu verlieren. „Wenn ich Sie bitte, zwei Würfel zu erstellen, die nahe beieinander liegen, stellt sich heraus, dass dies möglich ist“, sagte Hązła. Diese kleinen Korrelationstaschen stoßen die Turnierergebnisse von der Symmetrie weg, sobald mindestens vier Würfel im Bild sind.

Die jüngsten Papiere sind nicht das Ende der Geschichte. Die Arbeit von Cornacchia und Hązła enthüllt nur ansatzweise genau, wie Korrelationen zwischen Würfeln die Symmetrie von Turnieren aus dem Gleichgewicht bringen. In der Zwischenzeit wissen wir jedoch, dass es viele Sätze intransitiver Würfel gibt – vielleicht sogar einen, der subtil genug ist, um Bill Gates dazu zu bringen, zuerst zu wählen.