Kuidas Matemaatika Mõistatused Aitavad Teil Täiuslikku Pidu Planeerida

Õige segu inimestest, kes juba tunnevad üksteist, poisse ja tüdrukuid - Ramsey numbrid võivad vastata.

Järgmine essee trükitakse uusimaid uuringuid kajastava veebiväljaande The Conversation loal.

.

Oletame, et plaanite oma järgmist pidu ja kannatate külaliste nimekirja üle. Kellele peaksite kutsed saatma? Milline sõprade ja võõraste kombinatsioon on õige segu ?.

Tuleb välja, et matemaatikud on selle probleemi versiooni kallal töötanud juba ligi sajandi. Sõltuvalt sellest, mida soovite, võib vastus olla keeruline.

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

Sündis pusle

Ehkki on hästi teada, et Harvard on üks riigi tipptasemel akadeemilisi ülikoole, võite olla üllatunud, kui teate, et Harvardil oli aeg, kus oli üks riigi parimatest jalgpallimeeskondadest. Kuid 1931. aastal juhtus seda kogu Ameerika ameeriklasest tagamängija Barry Woodiga.

Sel hooajal mängis Harvard armeed. Poolajaks juhtis armee Harvardi ootamatult 13–0. Selgelt ärritunud, ütles Harvardi president armee kadettide komandandile, et kuigi armee võib jalgpallis olla parem kui Harvard, oli Harvard teadlaslikumas konkurentsis parem.

Ehkki Harvard tuli tagasi armee 14-13 alistama, võttis komandant vastu väljakutse konkureerida Harvardi vastu milleski teaduslikumas. Lepiti kokku, et need kaks võistlevad - matemaatikas. See viis armee ja Harvardi matemaatikameeskondade valimiseni; showdown toimus West Poonis 1933. Harvardi üllatuseks võitis armee.

Harvardi-armee võistlus viis 1938. aastal üliõpilaste matemaatikavõistluseni, mida nimetati Putnami eksamiks ja mille nimi oli Harvardi presidendi sugulane William Lowell Putnam. Selle eksami eesmärk oli stimuleerida matemaatikas tervislikku võistlust Ameerika Ühendriikides ja Kanadas. Aastate jooksul ja tänapäevani jätkates on see eksam sisaldanud palju huvitavaid ja sageli väljakutseid pakkuvaid probleeme - sealhulgas ka seda, mida kirjeldame eespool.

Punased ja sinised jooned

1953. aasta eksam sisaldas järgmist (veidi ümber sõnastatud) probleemi: lennukis on kuus punkti. Iga punkt on ühendatud iga teise punktiga joonega, mis on kas sinine või punane. Näidake, et neid punkte on kolm, mille vahele tõmmatakse ainult sama värvi jooned.

Matemaatikas, kui mõne punktipaari vahele on tõmmatud joonte kogum, nimetatakse seda struktuuri graafiks. Nende graafikute uurimist nimetatakse graafiteooriaks. Graafiteoorias nimetatakse punkte aga tippudeks ja jooni servadeks.

Graafikuid saab kasutada väga erinevate olukordade esitamiseks. Näiteks selles Putnami probleemis võib punkt tähistada inimest, punane joon võib tähendada, et inimesed on sõbrad ja sinine - võõrad.

Nimetagem näiteks punkte A, B, C, D, E, F ja valige üks neist, ütleme A. Viiest joonest, mis on A-st viie ülejäänud punktini tõmmatud, peab olema kolm sama värvi joont.

Oletame, et jooned A-st B-ni, C, D on kõik punased. Kui B, C, D suvalise kahe vahel on joon punane, siis on kolm punkti, mille vahel on ainult punased jooned. Kui ükski joon B, C, D vahel ei ole punane, siis on nad kõik sinised.

Mis oleks, kui oleks ainult viis punkti? Ei pruugi olla kolme punkti, kus kõik nende vahel olevad jooned on sama värvi. Näiteks jooned A – B, B – C, C – D, D – E, E – A võivad olla punased, teised sinised.

Sellest, mida nägime, on siis kõige väiksem arv inimesi, keda saab kutsuda peole (kus iga kaks inimest on kas sõbrad või võõrad) nii, et on kolm ühist sõpra või kolm vastastikku võõrast.

Mis oleks, kui me tahaksime, et neli inimest oleksid ühised sõbrad või võõrad? Kui palju inimesi peame peole kutsuma, et selles kindel olla? Sellele küsimusele on vastatud. Kell on 18.

Mis oleks, kui sooviksime, et viis inimest oleksid ühised sõbrad või võõrad? Selles olukorras on väikseim arv inimesi, keda on võimalik peole kutsuda, teadmata. Keegi ei tea. Kuigi seda probleemi on lihtne kirjeldada ja võib-olla kõlab see üsna lihtsalt, on see teadupärast keeruline.

Ramsey numbrid

Selle üle, mida oleme arutanud, on graafiteoorias teatud tüüpi number, mida nimetatakse Ramsey numbriks. Need numbrid on nimetatud Briti filosoofile, majandusteadlasele ja matemaatikule Frank Plumpton Ramseyle.

Ramsey suri 26-aastaselt, kuid saavutas juba väga varajases eas matemaatikas väga uudishimuliku teoreemi, mis tekitas meie siin küsimuse. Oletame, et meil on veel üks tasapind täis punkte, mis on ühendatud punaste ja siniste joontega. Valime kaks positiivset täisarvu, nimega r ja s. Me tahame saada täpselt r punkte, kus kõik nende vahel olevad jooned on punased või s punkte, kus kõik nende vahel olevad jooned on sinised. Mis on väikseim punktide arv, millega seda teha saame? Seda nimetatakse Ramsey numbriks.

Oletame näiteks, et tahame, et meie lennukil oleks vähemalt kolm punkti, mis on ühendatud kõigi punaste joontega, ja kolm punkti, mis on ühendatud kõigi siniste joontega. Ramsey number - kõige väiksem punktide arv, mida me selle elluviimiseks vajame - on kuus.

Kui matemaatikud probleemi vaatavad, küsivad nad endalt: kas see viitab veel ühele küsimusele? Nii on juhtunud Ramsey numbritega - ja parteiprobleemidega.

Näiteks siin on üks: viis tüdrukut plaanivad pidu. Nad on otsustanud kutsuda peole mõned poisid, olenemata sellest, kas nad poisse tunnevad või mitte. Kui palju poisse on vaja kutsuda, et olla kindel, et nende seas on alati kolm poissi, nii et kolm viiest tüdrukust on kõigi kolme poisiga sõbrad või pole kõigi kolme poisiga tuttavad? Tõenäoliselt pole vastuse osas hea aimata. Praegu on 41 !.

Ramsey numbreid on teada väga vähe. See aga ei takista matemaatikuid selliseid probleeme lahendamast. Sageli võib ühe probleemi lahendamata jätmine põhjustada veelgi huvitavama probleemi. Selline on matemaatiku elu.