See matemaatika aitab planeerida oma järgmise pidu

fotoViktorBurkivski12JUL2014F / Eesti Iluduskuninganna 2014 (Juuli 2019).

Anonim

Oletame, et plaanite oma järgmisel võistlusel ja valite külalisloendisse. Kellele peaksite kutseid saatma? Mis sõprade ja võõraste kombinatsioon on õige kombinatsioon?

Tuleb välja, et matemaatikud on töötanud selle probleemi versioonis peaaegu sajandiks. Sõltuvalt sellest, mida soovite, võib vastus olla keeruline.

Meie raamat "Graafiteooria vaimuv maailm" uurib selliseid mõistatusi ja näitab, kuidas neid graafikute abil saab lahendada. Selline küsimus võib tunduda väike, kuid see on ilus näide sellest, kuidas graafikuid saab kasutada matemaatiliste probleemide lahendamiseks sellistes valdkondades nagu teadused, kommunikatsioon ja ühiskond.

Mänguasjad on sündinud

Kuigi on hästi teada, et Harvard on üks kõrgemaid akadeemilisi ülikoole riigis, võite olla üllatunud, et õppisin, et oli aeg, mil Harvardil oli üks rahvusest parimaid jalgpallimeeskondi. Kuid 1931. aastal juhtis seda All-American quarterback Barry Wood, nii oli see nii.

Sellel hooajal oli Harvardi armee. Poolmajanduses, ootamatult, tõi Army Harvardi 13-0. Harvardi president andis armee käsukäsi komandendile selgelt hämmeldunud, et kui armee võiks olla parem kui Harvardi jalgpallis, siis Harvard oli paremas teaduslikus konkurentsis.

Kuigi Harvard tuli 14-13-aastasele relvajõudude võitlusele, nõustus komandant väljakutsega konkureerida Harvardi vastu midagi teaduslikumalt. Lepiti kokku, et kaks võistlevad - matemaatikas. See viis armee ja Harvardi matemaatika meeskondade valimiseni; showdown toimus West Pointis 1933. aastal. Harvardi üllatusena võitis Armee.

Harvardi armee võistlus viis lõpuks 1938. aastani üliõpilastele iga-aastase matemaatika konkursi, mida nimetatakse Putnami eksamiks, mille nimi on Harvardi presidendi sugulane William Lowell Putnam. See eksam oli mõeldud stimuleerima Ameerika Ühendriikides ja Kanadas tervislikku võistlust matemaatika valdkonnas. Aastate jooksul ja kuni selle päeva lõpuni on eksam sisaldanud palju huvitavaid ja sageli keerulisi probleeme - sealhulgas seda, mida me eespool kirjeldame.

Punased ja sinised jooned

1953. aasta eksam sisaldas järgmist probleemi (ümber sõnastatud): lennumasinas on kuus punkti. Iga punkt on iga teise punktiga ühendatud kas sinise või punase joonega. Näidake, et on kolm neist punktidest, mille vahele jäävad ainult sama värvi jooned.

Matemaatika puhul, kui mõne punkti paari vahel on joonistatud punktide kogum, nimetatakse seda struktuuri graafiks. Nende graafikute uurimist nimetatakse graafi teooriaks. Graafi teoorias aga nimetatakse punkte tippudeks ja jooned nimetatakse servadeks.

Graafikuid saab kasutada erinevate olukordade esindamiseks. Näiteks selles Putnami probleemis võib punkt kujutada inimest, punane joon võib tähendada, et inimesed on sõbrad ja sinine joon tähendab, et nad on võõrad.

Näiteks nimetame punktid A, B, C, D, E, F ja valime ühe neist, ütleme A. Viisest joonest, mis on võetud A-st viie teise punkti juurde, peab olema kolm sama värvi joont.

Ütle, et read A-st B, C, D on kõik punased. Kui kahe B, C ja D vahel olev joon on punane, siis on nende vahel ainult kolm punast joont. Kui ükski teine ​​B, C ja D joon ei ole punane, siis on need kõik sinist värvi.

Mis siis, kui oli ainult viis punkti? Võib olla kolm punkti, kus kõik nendevahelised jooned on ühesugused. Näiteks võivad read A-B, B-C, C-D, D-E, E-A olla punased ja teised sinised.

See, millest me nägime, on väike arv inimesi, keda võib kutsuda poolele (kus kõik kaks inimest on sõbrad või võõrad), nii et kolm vastastikust sõpra või kolm vastastikust võõrast isikut on kuus.

Mis siis, kui me sooviksime, et neli inimest oleksid vastastikused sõbrad või vastastikused võõrad? Milline on kõige väiksem arv inimesi, kellele me peate poole pealt kutsuma, et olla sellest kindel? Sellele küsimusele on vastatud. See on 18

Mis siis, kui me sooviksime, et viis inimest oleksid vastastikused sõbrad või vastastikused võõrad? Selles olukorras on vähim arv inimesi, kellele on peod võistlusele kutsutud, olema teadmata. Keegi ei tea. Kuigi seda probleemi on lihtne kirjeldada ja võib-olla tundub üsna lihtne, on see tuntud raske.

Ramsey numbrid

Mida me oleme arutanud on tüüpi arv graafi teooria nimega Ramsey number. Need numbrid on antud Briti filosoofi, majandusteadlase ja matemaatiku Frank Plumpton Ramsey nime järgi.

Ramsey suri 26-aastaselt, kuid omandas väga varases eas väga uudse matemaatika teoreemi, mis tõi kaasa meie küsimuse siin. Ütleme, et meil on veel üks tasand, mis on täis punkte, mis on ühendatud punaste ja siniste joontega. Valisime kaks positiivset täisarvu nimega r ja s. Soovime täpselt r punkte, kus kõik nendevahelised jooned on punased või punktid, kus kõik jooned nende vahel on sinist värvi. Mis on väikseim punkt, mida me saame seda teha? Seda nimetatakse Ramsey numbriks.

Näiteks ütleme, et tahame, et meie lennukil oleks vähemalt kolm punkti, mis on ühendatud kõikide punaste joontega ja kolme punktiga, mis on ühendatud kõigi siniste joontega. Ramsey number - kõige vähem punkte, mida me peame seda tegema, on kuus.

Kui matemaatikud probleemi näevad, küsivad nad sageli endalt: kas see viitab teisele küsimusele? See on juhtunud Ramsey numbritega - ja partei probleemidega.

Näiteks siin on üks: pidu kavandavad viis tüdrukut. Nad otsustasid kutsuda poisse poisse, olgu nad poisid või mitte. Kui palju poisse nad peavad kutsuma, et olla kindel, et nende seas on alati kolm poissi, nii et kolm neist viiest tüdrukust on kõik kolm poega sõpru või ei tunne kõiki kolme poega? Tõenäoliselt pole vastusesse kerge välja arvata. See on 41!

Väga vähe Ramsey numbreid on teada. Kuid see ei takista matemaatikud üritades neid probleeme lahendada. Sageli ei suuda üks probleem lahendada veelgi huvitavamat probleemi. Selline on matemaatiku elu.

menu
menu