Mapping verbindings by jou volgende shindig. unclibraries_commons
Kom ons sê jy beplan jou volgende partytjie en bekommer oor die gaslys. Aan wie moet jy uitnodigings stuur? Watter kombinasie van vriende en vreemdelinge is die regte mengsel?
Dit blyk dat wiskundiges al amper 'n eeu op 'n weergawe van hierdie probleem gewerk het. Afhangende van wat jy wil, kan die antwoord ingewikkeld wees.
Ons boek, "Die fascinerende wêreld van grafteorie, "Verken legkaarte soos hierdie en toon hoe hulle deur grafieke opgelos kan word. 'N Vraag soos hierdie mag dalk klein lyk, maar dit is 'n pragtige demonstrasie van hoe grafieke gebruik kan word om wiskundige probleme op so uiteenlopende gebiede as die wetenskappe, kommunikasie en samelewing op te los.
'N Legkaart word gebore
Hoewel dit bekend is dat Harvard een van die top akademiese universiteite in die land is, kan jy verbaas wees om te leer dat daar 'n tyd was toe Harvard een van die land se beste sokker spanne gehad het. Maar in 1931, gelei deur All-American quarterback Barry Wood, so was die geval.
Daardie seisoen het Harvard Army gespeel. Tydens 'n halfuur het Army onverwags Harvard 13-0 gelei. Duidelik ontsteld, het Harvard se president aan Army se kommandant van kadette gesê dat terwyl Army dalk beter as Harvard in sokker is, Harvard beter was in 'n meer wetenskaplike kompetisie.
Alhoewel Harvard teruggekom het om die weermag 14-13 te verslaan, het die kommandant die uitdaging aanvaar om Harvard in iets meer wetenskaplik te kompeteer. Daar is ooreengekom dat die twee in wiskunde sal meeding. Dit het daartoe gelei dat Army en Harvard wiskunde spanne kies; die optrede het in Wespunt in 1933 plaasgevind. Tot Harvard se verrassing het die leër gewen.
Die Harvard-Army-kompetisie het uiteindelik gelei tot 'n jaarlikse wiskunde-kompetisie vir voorgraadse studente in 1938, die Putnam eksamen, vernoem na William Lowell Putnam, 'n familielid van Harvard se president. Hierdie eksamen is ontwerp om 'n gesonde wedywering in wiskunde in die Verenigde State en Kanada te stimuleer. Oor die jare en tot op die dag het hierdie eksamen baie interessante en dikwels uitdagende probleme bevat - insluitende die een wat ons hierbo beskryf.
Rooi en blou lyne
Die 1953-eksamen het die volgende probleem bevat ('n bietjie geformuleer): Daar is ses punte in die vliegtuig. Elke punt word aan elke ander punt verbind deur 'n lyn wat blou of rooi is. Toon aan dat daar drie van hierdie punte is waarvan slegs lyne van dieselfde kleur geteken word.
In wiskunde, as daar 'n versameling punte is met lyne wat tussen sommige pare punte geteken word, word die struktuur 'n grafiek genoem. Die bestudering van hierdie grafieke word grafieteorie genoem. In grafiekteorie word die punte egter hoekpunte genoem en die lyne word rande genoem.
Grafieke kan gebruik word om 'n wye verskeidenheid situasies voor te stel. Byvoorbeeld, in hierdie Putnam-probleem kan 'n punt 'n persoon verteenwoordig, 'n rooi lyn kan beteken dat die mense vriende is en 'n blou lyn beteken dat hulle vreemdelinge is.
Toon aan dat daar drie punte verbind is met lyne van dieselfde kleur. Gary Chartrand
Byvoorbeeld, laat ons die punte A, B, C, D, E, F noem en een van hulle kies. A. Van die vyf lyne wat van A na die ander vyf punte getrek word, moet daar drie lyne van dieselfde kleur wees.
Sê die lyne van A na B, C, D is almal rooi. As 'n lyn tussen enige twee van B, C, D rooi is, dan is daar drie punte met slegs rooi lyne tussen hulle. As geen lyn tussen enige twee van B, C, D rooi is nie, dan is hulle almal blou.
Wat as daar net vyf punte was? Daar mag nie drie punte wees waar al die lyne tussen hulle dieselfde kleur is nie. Byvoorbeeld, die lyne A-B, B-C, C-D, D-E, E-A mag rooi wees, met die ander blou.
Van wat ons gesien het, is die kleinste aantal mense wat uitgenooi kan word na 'n partytjie (waar elke twee mense vriende of vreemdelinge is), sodat daar drie gesamentlike vriende of drie onderlinge vreemdelinge is, ses.
Wat as ons wil hê dat vier mense gemeenskaplike vriende of wedersydse vreemdelinge moet wees? Wat is die kleinste aantal mense wat ons moet uitnooi vir 'n partytjie om hiervan seker te wees? Hierdie vraag is beantwoord. Dit is 18.
Wat as ons wil hê dat vyf mense gemeenskaplike vriende of wedersydse vreemdelinge moet wees? In hierdie situasie is die kleinste aantal mense wat uitgenooi word om 'n partytjie te waarborg, onbekend. Niemand weet. Alhoewel hierdie probleem maklik omskryf kan word en dalk heel eenvoudig klink, is dit berug moeilik.
Ramsey-nommers
Wat ons bespreek het, is 'n tipe getal in grafiekteorie, 'n Ramsey-nommer. Hierdie nommers is vernoem na die Britse filosoof, ekonoom en wiskundige Frank Plumpton Ramsey.
Ramsey het op die ouderdom van 26 gesterf, maar op sy vroeë ouderdom 'n baie nuuskierige stelling in wiskunde verkry, wat aanleiding gegee het tot ons vraag hier. Sê ons het 'n ander vliegtuig vol punte wat deur rooi en blou lyne verbind word. Ons kies twee positiewe heelgetalle, genaamd r en s. Ons wil presies r punte hê waar al die lyne tussen hulle rooi of s punte is, waar al die lyne tussen hulle blou is. Wat is die kleinste aantal punte waarmee ons dit kan doen? Dit heet 'n Ramsey-nommer.
Byvoorbeeld, sê ons wil hê ons vliegtuig moet ten minste drie punte verbind deur alle rooi lyne en drie punte wat met alle blou lyne verbind word. Die Ramsey-nommer - die kleinste aantal punte wat ons nodig het om dit te laat gebeur - is ses.
Wanneer wiskundiges na 'n probleem kyk, vra hulle hulself dikwels: stel dit 'n ander vraag voor? Dit is wat met Ramsey-nommers gebeur het - en partyprobleme.
Byvoorbeeld, hier is een: Vyf meisies beplan 'n partytjie. Hulle het besluit om 'n paar seuns uit te nooi na die partytjie, of hulle die seuns ken of nie. Hoeveel seuns moet hulle nooi om seker te maak dat daar altyd drie seuns onder hulle sal wees sodat drie van die vyf meisies met al drie seuns vriende is of nie al drie seuns ken nie? Dit is waarskynlik nie maklik om 'n goeie raaiskoot op die antwoord te maak nie. Dit is 41!
Baie min Ramsey-nommers is bekend. Dit stop egter nie wiskundiges om sulke probleme op te los nie. Dikwels kan een probleem nie opgelos word om 'n selfs meer interessante probleem op te los nie. So is die lewe van 'n wiskundige.
Oor die skrywers
Gary Chartrand, Professor Emeritus van Wiskunde, Western Michigan University; Arthur Benjamin, professor in wiskunde, Harvey Mudd College, en Ping Zhang, professor in wiskunde, Western Michigan University
Hierdie artikel is oorspronklik gepubliseer op Die gesprek. Lees die oorspronklike artikel.
Verwante Boeke:
at InnerSelf Market en Amazon
