Dieses Mathe-Puzzle hilft Ihnen, Ihre nächste Party zu planen
Mapping-Verbindungen bei Ihrem nächsten Shindig.
unclibraries_commons 

Nehmen wir an, Sie planen Ihre nächste Party und quälen sich über die Gästeliste. An wen schicken Sie Einladungen? Welche Kombination aus Freunden und Fremden ist die richtige Mischung?

Es stellt sich heraus, dass Mathematiker seit fast einem Jahrhundert an einer Version dieses Problems arbeiten. Je nachdem, was Sie wollen, kann die Antwort kompliziert sein.

Unser Buch, "Die faszinierende Welt der Graphentheorie"Erforscht Rätsel wie diese und zeigt, wie sie durch Graphen gelöst werden können. Eine Frage wie diese mag klein erscheinen, aber es ist eine schöne Demonstration, wie Graphen zur Lösung mathematischer Probleme in so unterschiedlichen Bereichen wie Wissenschaft, Kommunikation und Gesellschaft verwendet werden können.

Ein Puzzle ist geboren

Es ist zwar bekannt, dass Harvard eine der besten Universitäten des Landes ist, aber Sie werden überrascht sein zu erfahren, dass Harvard einst eine der besten Fußballmannschaften der Nation war. Aber in 1931, geführt von All-American Quarterback Barry WoodDas war der Fall.

In dieser Saison spielte Harvard Army. Zur Halbzeit, unerwartet, führte die Armee Harvard 13-0. Der Harvard-Präsident war sichtlich verärgert und sagte dem Kommandanten der Armee, dass die Armee zwar besser als Harvard im Fußball sei, Harvard aber in einem wissenschaftlichen Wettbewerb überlegen sei.


Innerself-Abonnieren-Grafik


Obwohl Harvard zurückkam, um Armee 14-13 zu besiegen, akzeptierte der Kommandant die Herausforderung, gegen Harvard in etwas Gelehrterem zu konkurrieren. Es wurde vereinbart, dass die beiden konkurrieren würden - in Mathematik. Dies führte dazu, dass Army und Harvard Mathematikteams auswählten; Der Showdown fand in West Point in 1933 statt. Zu Harvards Überraschung gewann Army.

Der Harvard-Army-Wettbewerb führte schließlich zu einem jährlichen Mathematikwettbewerb für Studierende in 1938, genannt the Putnam-Prüfung, benannt nach William Lowell Putnam, einem Verwandten des Harvard-Präsidenten. Diese Prüfung wurde entwickelt, um eine gesunde Rivalität in Mathematik in den Vereinigten Staaten und Kanada zu stimulieren. Im Laufe der Jahre und bis heute hat diese Prüfung viele interessante und oft herausfordernde Probleme enthalten - einschließlich der oben beschriebenen.

Rote und blaue Linien

Die 1953-Prüfung enthielt das folgende Problem (ein wenig umformuliert): Es gibt sechs Punkte im Flugzeug. Jeder Punkt ist mit jedem anderen Punkt durch eine Linie verbunden, die entweder blau oder rot ist. Zeigen Sie, dass es drei dieser Punkte gibt, zwischen denen nur Linien der gleichen Farbe gezeichnet werden.

Wenn es in Mathematik eine Sammlung von Punkten mit Linien gibt, die zwischen einigen Paaren von Punkten gezeichnet sind, wird diese Struktur als Graph bezeichnet. Das Studium dieser Graphen wird Graphentheorie genannt. In der Graphentheorie heißen die Punkte jedoch Eckpunkte und die Linien heißen Kanten.

Diagramme können verwendet werden, um eine Vielzahl von Situationen darzustellen. Zum Beispiel kann in diesem Putnam-Problem ein Punkt eine Person darstellen, eine rote Linie kann bedeuten, dass die Leute Freunde sind und eine blaue Linie bedeutet, dass sie Fremde sind.

Mathetest
Zeigen Sie, dass drei Punkte durch Linien derselben Farbe verbunden sind. Gary Chartrand

Nehmen wir zum Beispiel die Punkte A, B, C, D, E, F und wählen Sie eine davon, sagen wir A. Von den fünf Linien, die von A zu den anderen fünf Punkten gezogen werden, müssen drei Linien derselben Farbe sein.

Angenommen, die Zeilen von A nach B, C, D sind alle rot. Wenn eine Linie zwischen zwei beliebigen Punkten von B, C, D rot ist, gibt es drei Punkte, zwischen denen nur rote Linien liegen. Wenn keine Linie zwischen zwei beliebigen Punkten von B, C, D rot ist, sind sie alle blau.

Was wäre, wenn es nur fünf Punkte gäbe? Es gibt möglicherweise nicht drei Punkte, an denen alle Linien zwischen ihnen gleich gefärbt sind. Zum Beispiel können die Linien A-B, B-C, C-D, D-E, E-A rot sein, während die anderen blau sind.

Von dem, was wir gesehen haben, ist die kleinste Anzahl von Leuten, die zu einer Party eingeladen werden können (wo jede zwei Leute Freunde oder Fremde sind), so dass es drei gemeinsame Freunde oder drei gegenseitige Fremde gibt, sechs.

Was wäre, wenn wir möchten, dass vier Menschen gemeinsame Freunde oder Fremde sind? Was ist die kleinste Anzahl an Personen, die wir zu einer Party einladen müssen, um sich dessen sicher zu sein? Diese Frage wurde beantwortet. Es ist 18.

Was wäre, wenn wir möchten, dass fünf Menschen gemeinsame Freunde oder Fremde sind? In dieser Situation ist die kleinste Anzahl von Personen, die zu einer Party eingeladen werden, um dies zu garantieren, unbekannt. Niemand weiß. Während dieses Problem einfach zu beschreiben ist und vielleicht einfach klingt, ist es bekanntlich schwierig.

Ramsey-Nummern

Was wir besprochen haben, ist eine Art von Zahl in der Graphentheorie, eine Ramsey-Zahl. Diese Zahlen sind nach dem britischen Philosophen, Ökonom und Mathematiker benannt Frank Plumpton Ramsey.

Ramsey starb im Alter von 26, erlangte jedoch schon in jungen Jahren ein sehr seltsames Theorem in Mathematik, das unsere Frage hier aufwarf. Angenommen, wir haben eine andere Ebene voller Punkte, die durch rote und blaue Linien verbunden sind. Wir wählen zwei positive Ganzzahlen aus, die r und s heißen. Wir wollen genau R Punkte haben, wo alle Linien zwischen ihnen rot oder s Punkte sind, wo alle Linien zwischen ihnen blau sind. Was ist die kleinste Anzahl von Punkten, mit denen wir das machen können? Das nennt man Ramsey-Nummer.

Nehmen wir zum Beispiel an, dass unser Flugzeug mindestens drei Punkte haben soll, die durch alle roten Linien und drei Punkte verbunden sind, die durch alle blauen Linien verbunden sind. Die Ramsey-Zahl - die kleinste Anzahl von Punkten, die wir dafür benötigen - ist sechs.

Wenn Mathematiker ein Problem betrachten, fragen sie sich oft: Schlägt das eine andere Frage vor? So ist es mit Ramsey-Zahlen und Parteiproblemen geschehen.

Zum Beispiel, hier ist eins: Fünf Mädchen planen eine Party. Sie haben beschlossen, einige Jungs zur Party einzuladen, ob sie die Jungs kennen oder nicht. Wie viele Jungen müssen sie einladen, um sicher zu gehen, dass es immer drei Jungen unter ihnen geben wird, so dass drei der fünf Mädchen entweder mit allen drei Jungen befreundet sind oder nicht alle drei Jungen kennen? Es ist wahrscheinlich nicht einfach, die Antwort gut zu schätzen. Es ist 41!

Das GesprächSehr wenige Ramsey-Zahlen sind bekannt. Das hält die Mathematiker jedoch nicht davon ab, solche Probleme zu lösen. Oft kann die Lösung eines Problems zu einem noch interessanteren Problem führen. So ist das Leben eines Mathematikers.

Über den Autor

Gary Chartrand, emeritierter Professor für Mathematik, Western Michigan University; Arthur Benjamin, Professor für Mathematik, Harvey Mudd College-und Ping Zhang, Professor für Mathematik, Western Michigan University

Dieser Artikel wurde ursprünglich veröffentlicht am Das Gespräch.. Lies das Original Artikel.

Bücher zum Thema:

at InnerSelf Market und Amazon