Mapping tilkoblinger på neste shindig. unclibraries_commons
La oss si at du planlegger neste fest og plager deg over gjestelisten. Til hvem skal du sende invitasjoner? Hvilken kombinasjon av venner og fremmede er den rette blandingen?
Det viser seg at matematikere har jobbet med en versjon av dette problemet i nesten et århundre. Avhengig av hva du vil, kan svaret være komplisert.
Vår bok, "Den fascinerende verden av grafteori, "Utforsker gåter som disse og viser hvordan de kan løses gjennom grafer. Et spørsmål som dette kan virke lite, men det er en vakker demonstrasjon av hvordan grafer kan brukes til å løse matematiske problemer på så ulike felt som vitenskap, kommunikasjon og samfunn.
Et puslespill er født
Selv om det er kjent at Harvard er en av de beste akademiske universitetene i landet, kan du bli overrasket over at det var en tid da Harvard hadde en av landets beste fotballag. Men i 1931, ledet av All-American quarterback Barry Wood, slik var tilfellet.
Den sesongen spilte Harvard hæren. I halvtid ledet Army uventet Harvard 13-0. Helt opprørt, fortalte Harvards president hærens kommandant for kadetter at mens hæren kan være bedre enn Harvard i fotball, var Harvard overlegen i en mer vitenskapelig konkurranse.
Selv om Harvard kom tilbake for å beseire Army 14-13, tok kommandanten utfordringen til å konkurrere mot Harvard i noe mer vitenskapelig. Det ble enighet om at de to skulle konkurrere - i matematikk. Dette førte til at Army og Harvard valgte matematikklag; showdownen skjedde i West Point i 1933. Til Harvards overraskelse vant hæren.
Harvard-Army-konkurransen førte til slutt til en årlig matematikkonkurranse for undergraduates i 1938, kalt Putnam eksamen, oppkalt etter William Lowell Putnam, en slektning til Harvards president. Denne eksamenen ble utformet for å stimulere en sunn rivalisering i matematikk i USA og Canada. Gjennom årene og frem til denne dagen har denne eksamen inneholdt mange interessante og ofte utfordrende problemer - inkludert den som vi beskriver ovenfor.
Røde og blå linjer
1953-eksamenen inneholdt følgende problem (omformulert litt): Det er seks poeng i flyet. Hvert punkt er koblet til hvert annet punkt med en linje som er enten blå eller rød. Vis at det er tre av disse punktene mellom hvilke kun linjer av samme farge er tegnet.
I matte, hvis det er en samling poeng med linjer trukket mellom noen par punkter, kalles denne strukturen en graf. Studien av disse grafer kalles grafteori. I grafteori blir poengene imidlertid kalt vertices og linjene kalles kanter.
Grafer kan brukes til å representere et bredt spekter av situasjoner. For eksempel, i dette Putnam-problemet kan et punkt representere en person, en rød linje kan bety at folk er venner og en blå linje betyr at de er fremmede.
Vis at det er tre punkter forbundet med linjer av samme farge. Gary Chartrand
For eksempel, la oss ringe til punktene A, B, C, D, E, F og velge en av dem, si A. Av de fem linjene trukket fra A til de andre fem punktene må det være tre linjer av samme farge.
Si linjene fra A til B, C, D er alle røde. Hvis en linje mellom noen av B, C, D er rød, så er det tre punkter med bare røde linjer mellom dem. Hvis ingen linje mellom noen av B, C, D er rød, så er de alle blå.
Hva om det bare var fem poeng? Det kan ikke være tre poeng hvor alle linjer mellom dem er fargede det samme. For eksempel kan linjene A-B, B-C, C-D, D-E, E-A være rød, med de andre blå.
Fra det vi så, kan det minste antall personer som kan inviteres til en fest (hvor hver to mennesker er venner eller fremmede) slik at det er tre felles venner eller tre felles fremmede er seks.
Hva om vi vil at fire personer skal være felles venner eller felles fremmede? Hva er det minste antallet mennesker vi må invitere til en fest for å være sikker på dette? Dette spørsmålet er besvart. Det er 18.
Hva om vi ønsker fem personer å være felles venner eller felles fremmede? I denne situasjonen er det minste antall personer å invitere til en fest å bli garantert av dette - ukjent. Ingen vet. Selv om dette problemet er lett å beskrive og kanskje høres ganske enkelt, er det notorisk vanskelig.
Ramsey tall
Det vi har diskutert er en type nummer i grafteori kalt et Ramsey-nummer. Disse tallene er oppkalt etter den britiske filosofen, økonomen og matematikeren Frank Plumpton Ramsey.
Ramsey døde i en alder av 26, men oppnådde i svært tidlig alder en veldig nysgjerrig teori i matematikk, noe som ga opphav til vårt spørsmål her. Si at vi har et annet fly fullt av punkter forbundet med røde og blå linjer. Vi velger to positive heltall, kalt r og s. Vi vil ha nøyaktig r poeng der alle linjer mellom dem er røde eller s poeng der alle linjene mellom dem er blå. Hva er det minste antall poeng vi kan gjøre dette med? Det kalles et Ramsey nummer.
For eksempel, si at vi vil at flyet vårt skal ha minst tre punkter forbundet med alle røde linjer og tre punkter forbundet med alle blå linjer. Ramsey-nummeret - det minste antall poeng vi trenger for å få dette til å skje - er seks.
Når matematikere ser på et problem, spør de ofte: Er dette et annet spørsmål? Dette er hva som har skjedd med Ramsey-tall - og festproblemer.
For eksempel, her er en: Fem jenter planlegger en fest. De har besluttet å invitere noen gutter til festen, enten de kjenner guttene eller ikke. Hvor mange gutter trenger de å invitere til å være sikker på at det alltid vil være tre gutter blant dem slik at tre av de fem jentene er venner med alle tre guttene eller ikke er kjent med alle tre guttene? Det er sannsynligvis ikke lett å lage et godt gjetning på svaret. Det er 41!
Svært få Ramsey-tall er kjent. Dette hindrer imidlertid ikke matematikere fra å prøve å løse slike problemer. Ofte kan det ikke oppstå et enda mer interessant problem å ikke løse et problem. Slik er livet til en matematiker.
Om forfatterne
Gary Chartrand, professor emeritus of mathematics, Western Michigan University; Arthur Benjamin, professor i matematikk, Harvey Mudd College, og Ping Zhang, professor i matematikk, Western Michigan University
Denne artikkelen ble opprinnelig publisert på Den Conversation. Les opprinnelige artikkelen.
Relaterte bøker:
at InnerSelf Market og Amazon
