Kortlægning af forbindelser ved din næste shindig. unclibraries_commons 

Lad os sige, at du planlægger din næste fest og plager over gæstelisten. Hvem skal du sende invitationer til? Hvilken kombination af venner og fremmede er den rigtige blanding?

Det viser sig, at matematikere har arbejdet på en version af dette problem i næsten et århundrede. Afhængigt af hvad du vil, kan svaret være kompliceret.

Vores bog, “Den fascinerende verden af ​​grafteori, ”Udforsker gåder som disse og viser, hvordan de kan løses gennem grafer. Et spørgsmål som dette kan virke lille, men det er en smuk demonstration af, hvordan grafer kan bruges til at løse matematiske problemer inden for så forskellige områder som videnskab, kommunikation og samfund.

Et puslespil er født

Selvom det er velkendt, at Harvard er et af de bedste akademiske universiteter i landet, kan du blive overrasket over at høre, at der var en tid, da Harvard havde et af landets bedste fodboldhold. Men i 1931 ledet af Hele amerikansk quarterback Barry Wood, sådan var tilfældet.

Den sæson spillede Harvard hær. Ved pausen førte hæren uventet Harvard 13–0. Klart forstyrret fortalte Harvards præsident Armys kommandant for kadetter, at selvom hæren måske er bedre end Harvard i fodbold, var Harvard overlegen i en mere videnskabelig konkurrence.

Selvom Harvard kom tilbage for at besejre hæren 14-13, accepterede kommandanten udfordringen om at konkurrere mod Harvard i noget mere videnskabeligt. Det blev aftalt, at de to skulle konkurrere - i matematik. Dette førte til, at hær og Harvard valgte matematikhold; opgørelsen fandt sted i West Point i 1933. Til Harvards overraskelse vandt hæren.

Harvard – Army konkurrencen førte til sidst til en årlig matematik konkurrence for studerende i 1938, kaldet Putnam eksamen, opkaldt efter William Lowell Putnam, en slægtning til Harvards præsident. Denne eksamen var designet til at stimulere en sund rivalisering inden for matematik i USA og Canada. Gennem årene og fortsætter den dag i dag har denne eksamen indeholdt mange interessante og ofte udfordrende problemer - inklusive den, vi beskriver ovenfor.

Røde og blå linjer

1953-eksamen indeholdt følgende problem (omformuleret en smule): Der er seks punkter i flyet. Hvert punkt er forbundet til hvert andet punkt med en linje, der enten er blå eller rød. Vis, at der er tre af disse punkter, mellem hvilke der kun tegnes linjer i samme farve.

I matematik, hvis der er en samling af punkter med linjer trukket mellem nogle par punkter, kaldes denne struktur en graf. Undersøgelsen af ​​disse grafer kaldes grafteori. I grafteori kaldes punkterne imidlertid hjørner, og linjerne kaldes kanter.

Grafer kan bruges til at repræsentere en lang række situationer. For eksempel kan et punkt i dette Putnam-problem repræsentere en person, en rød linje kan betyde, at folk er venner, og en blå linje betyder, at de er fremmede.

Vis, at der er tre punkter forbundet med linjer i samme farve. Gary Chartrand

Lad os f.eks. Kalde punkterne A, B, C, D, E, F og vælge en af ​​dem, siger A. Af de fem linjer trukket fra A til de andre fem punkter skal der være tre linjer i samme farve.

Sig, at linjerne fra A til B, C, D alle er røde. Hvis en linje mellem to af B, C, D er rød, er der tre punkter med kun røde linjer mellem dem. Hvis der ikke er nogen linje mellem to af B, C, D er rød, så er de alle blå.

Hvad hvis der kun var fem point? Der er muligvis ikke tre punkter, hvor alle linjer mellem dem er farvet ens. For eksempel kan linjerne A – B, B – C, C – D, D – E, E – A være røde, mens de andre er blå.

Fra det vi så, så er det mindste antal mennesker, der kan inviteres til en fest (hvor hvert andet folk enten er venner eller fremmede), således at der er tre fælles venner eller tre gensidige fremmede, er seks.

Hvad hvis vi gerne vil have, at fire mennesker er fælles venner eller fremmede? Hvad er det mindste antal mennesker, vi skal invitere til en fest for at være sikre på dette? Dette spørgsmål er blevet besvaret. Det er 18.

Hvad hvis vi gerne vil have, at fem mennesker er fælles venner eller gensidige fremmede? I denne situation er det mindste antal mennesker, der inviterer til en fest, der garanteres dette, ukendt. Ingen ved. Selvom dette problem er let at beskrive og måske lyder ret simpelt, er det notorisk vanskeligt.

Ramsey-numre

Det, vi har diskuteret, er en type tal i grafteori kaldet et Ramsey-nummer. Disse tal er opkaldt efter den britiske filosof, økonom og matematiker Frank Plumpton Ramsey.

Ramsey døde i en alder af 26, men opnåede i sin meget tidlige alder en meget nysgerrig sætning i matematik, hvilket gav anledning til vores spørgsmål her. Sig, at vi har et andet plan fuld af punkter forbundet med røde og blå linjer. Vi vælger to positive heltal, navngivet r og s. Vi ønsker at have nøjagtigt r punkter, hvor alle linjer mellem dem er røde eller s punkter, hvor alle linjer mellem dem er blå. Hvad er det mindste antal point, vi kan gøre dette med? Det kaldes et Ramsey-nummer.

Sig for eksempel, at vi ønsker, at vores fly skal have mindst tre punkter forbundet med alle røde linjer og tre punkter forbundet med alle blå linjer. Ramsey-antallet - det mindste antal point, vi har brug for for at få dette til at ske - er seks.

Når matematikere ser på et problem, spørger de sig ofte: Foreslår dette et andet spørgsmål? Dette er, hvad der er sket med Ramsey-numre - og partiproblemer.

For eksempel er her en: Fem piger planlægger en fest. De har besluttet at invitere nogle drenge til festen, uanset om de kender drengene eller ej. Hvor mange drenge har de brug for at invitere for at være sikre på, at der altid vil være tre drenge blandt dem, således at tre af de fem piger enten er venner med alle tre drenge eller ikke er bekendt med alle tre drenge? Det er sandsynligvis ikke let at gætte et godt gæt på svaret. Det er 41!

Meget få Ramsey-numre kendes. Dette forhindrer dog ikke matematikere i at forsøge at løse sådanne problemer. Ofte kan manglende løsning af et problem føre til et endnu mere interessant problem. Sådan er en matematikers liv.

Om forfatterne

Gary Chartrand, emeritus professor i matematik, Western Michigan University; Arthur Benjamin, professor i matematik, Harvey Mudd Collegeog Ping Zhang, professor i matematik, Western Michigan University

Denne artikel blev oprindeligt offentliggjort den The Conversation. Læs oprindelige artikel.

Relaterede Bøger:

at InnerSelf Market og Amazon