Die Aufgabe von vor 165 Jahren verfolgt Mathematiker

Im Jahr 1850 formulierte Rev. Thomas Kirkman, ein britischer Mathematiker und Rektor der Gemeinde in Lancashire, in einem Unterhaltungsmagazin für Mathematikliebhaber ein unschuldig aussehendes Puzzle:

„Fünfzehn junge Schulmädchen gehen sieben Tage lang in drei Reihen spazieren: Sie müssen jeden Tag arrangieren "Damit sich dasselbe Schulmädchenpaar nie zweimal in derselben Reihe trifft."

Die Aufgabe sieht einfach aus, aber wenn Sie versuchen, sie zu lösen, stellen Sie sofort fest, dass dies nicht der Fall ist. Sie können versuchen, es mit Bleistift und Papier zu lösen oder in der HTML-Version zu spielen .

Aufgrund seiner falschen Einfachheit wurde die Aufgabe schnell berühmt. Liebhaber der Mathematik schickten ihre Entscheidungen, und Wissenschaftler veröffentlichten wissenschaftliche Artikel mit dem Versuch, eine allgemeine Lösung für das Problem zu formulieren.

Infolgedessen hat dieses Rätsel dazu beigetragen, einen neuen Bereich der Mathematik zu formen: kombinatorische Schemata , denen nun dicke Lehrbücher gewidmet sind.. Was als einfache Aufgabe begann, Menschen in Gruppen (oder Schemata, wie sie später genannt wurden) zu verteilen, ist jetzt eine Methode, die in der Versuchsplanung, bei Fehlerkorrekturcodes in der Informatik, in der Kryptographie, in der Landwirtschaft, im Sport und sogar bei Spielbetrug verwendet wird (Es gab eine Geschichte, in der ein kriminelles Kartell in sieben Jahren Millionen von Dollar verdient hat, indem es Tickets mit allen möglichen Kombinationen von 5 von 46 in einer 6 von 46 Lotterie gekauft hat, wenn die Kosten für die Tickets niedriger waren als die zusätzlichen Boni für den Gewinn von 5 von 46 plus die Wahrscheinlichkeit, den Jackpot zu gewinnen).

Zum Beispiel verwendet der klassische Hamming-Code zum Lösen von Fehlern die Lösung des Problems mit Schulmädchen (Erstellen von Gruppen von drei Schulmädchen, bei denen kein Paar wiederholt wird), jedoch nur für das Schema von sieben Mädchen (Bit).


Fano Flugzeug für (7, 3, 2)

Am überraschendsten ist, dass Mathematiker seit 165 Jahren nicht in der Lage sind, das Problem allgemein zu lösen. Sie können immer noch keine Antwort geben, was die Rätsellösung unter den Anfangsbedingungen ist: Es gibt n Schulmädchen, Sie müssen Gruppen der Größe k erstellen , sodass sich Gruppen von t Mädchen nie zweimal in derselben Gruppe getroffen haben. Eine solche Formulierung wird als Schema (n, k, t) bezeichnet .

Zum Beispiel gibt es für eine Gruppe von 19 Mädchen mehr als 11 Milliarden mögliche Drillinge, bei denen sich jedes Paar nur einmal trifft. Diese Nummer ist die Antwort. Aber die Anzahl der Optionen wächst exponentiell mit einer Zunahme der Anzahl von Schulmädchen.

Es ist klar, dass das Problem unter bestimmten Bedingungen gelöst wird und unter einigen anderen nicht. Wenn zum Beispiel Drillinge aller möglichen Paare aus sechs Schulmädchen bestehen, ist das Problem offensichtlich nicht gelöst (es gibt fünf mögliche Paare mit Schulmädchen Anya, gleichzeitig hat jedes Triplett zwei Paare mit Anya und fünf sind nicht in zwei geteilt). Das heißt, nach dem Teilbarkeitsprinzip werden viele Optionen (n, k, t) sofort eliminiert .

Gleichzeitig gibt es (n, k, t) , die dem Teilbarkeitsprinzip vollständig entsprechen, aber noch keine Lösung haben: zum Beispiel (47, 3, 2) .

In den letzten Jahren ist die Lösung für viele Kombinationen bekannt geworden (n, k, t)die algebraisch oder mit brutaler Gewalt auf Computern überprüft wurden. Aber wie kann man das allgemein lösen, was mit Ausnahmen wie (47, 3, 2) ? Wie kann man verstehen, ob ein Problem eine Lösung hat oder nicht?

Diese Aufgabe gilt seit langem als eines der bekanntesten Probleme der Kombinatorik, sagt der Mathematiker Gil Kalai von der Hebrew University in Jerusalem in einem Interview mit Wired. Er erinnert sich, dass er vor anderthalb Jahren mit Kollegen darüber gestritten hat, und sie kamen zu dem Schluss, dass "wir die Antwort nie erfahren werden, weil die Aufgabe eindeutig zu kompliziert ist".

Nur zwei Wochen später bewies der junge Mathematikprofessor Peter Keevash aus Oxford, dass Kalai falsch lag. In einem wissenschaftlichen ArtikelAb Januar 2014 argumentiert er, dass es fast immer eine Lösung für ein Problem gibt, wenn die Teilbarkeitsbedingung erfüllt ist. In einem neuen Artikel vom April 2015 zeigte er, wie die ungefähre Anzahl von Lösungen für bestimmte Parameter berechnet werden kann.

Niemand erwartete, dass die Wahrscheinlichkeitstheorie auf die Lösung des Problems angewendet werden würde, aber die Methode funktionierte perfekt.

Als sie zu den Lotterien zurückkehrten, erkannten die Betrüger, dass es möglich ist, die Anzahl der gekauften Tickets zu reduzieren, indem sie alle Kombinationen von 5 von 46 kaufen (wenn sie 6 von 46 Zahlen angeben). Dann erhalten sie absolut alle zusätzlichen Preise und möglicherweise auch einen Jackpot. Obwohl das Schema (46, 6, 5) noch nicht berechnet wurde, gibt es Schemata, die nah genug für die praktische Anwendung sind. Einer von ihnen wurde wahrscheinlich von einem kriminellen Kartell benutzt.

Die Anzahl neu berechneter Schaltungen wächst stetig. Viele von ihnen finden praktische Anwendung, wie (15, 3, 2) aus dem klassischen Problem und (46, 6, 5) . Es erscheinen 1000-seitige Anleitungen mit Diagrammen. Mathematiker wissen jedoch immer noch nicht, wie sie feststellen können, ob für bestimmte Bedingungen eine Lösung existiert. Dank Kivash haben wir erfahren, dass die Wahrscheinlichkeit dafür recht hoch ist. Zumindest ist jetzt klar, dass es bei all den Unbekannten besser ist, nach einer Lösung zu suchen, als sie aufzugeben. Darüber hinaus gibt es Werkzeuge zur Erzeugung von Probe für alle Parameter - Schaltungen.

Dank der Arbeit von Kivash hoffte man jedoch, dass eine Methode entwickelt werden könnte, um genaue Ergebnisse zu erzielenSchemata für beliebige Parameter. In diesem Fall ist dies ein außerordentlicher Durchbruch in der Mathematik.

Die Arbeit von Kivash ist jedoch rein theoretisch. Experten sagen, dass die Erstellung praktischer Algorithmen auf der Grundlage seiner Methode die harte Arbeit mehrerer weiterer Generationen von Mathematikern erfordern wird.

Source: https://habr.com/ru/post/de380785/