Yhteyksien kartoittaminen seuraavassa shindigissä. unclibraries_commons 

Oletetaan, että suunnittelet seuraavaa puolueesi ja hämmentävät vierasluetteloa. Kenelle pitäisi lähettää kutsuja? Mikä ystävien ja vieraiden yhdistelmä on oikea yhdistelmä?

Osoittautuu, että matemaatikot ovat työskennelleet tämän ongelman versiossa lähes vuosisadan ajan. Riippuen siitä, mitä haluat, vastaus voi olla monimutkainen.

Meidän kirja, ”Graafioteorian kiehtova maailma, ”Tutkii tällaisia ​​pulmia ja näyttää, kuinka ne voidaan ratkaista kaavioiden avulla. Tällainen kysymys saattaa tuntua pieneltä, mutta se on kaunis osoitus siitä, miten kaavioita voidaan käyttää matemaattisten ongelmien ratkaisemiseen niin monilla eri aloilla kuin tieteet, viestintä ja yhteiskunta.

Palapeli syntyy

Vaikka on hyvin tiedossa, että Harvard on yksi maan tärkeimmistä akateemisista yliopistoista, saatat olla yllättynyt siitä, että Harvardilla oli aika, jolloin Harvardilla oli yksi maan parhaista jalkapallojoukkueista. Mutta 1931issa, jota johtaa All-amerikkalainen pelinrakentaja Barry Wood, näin tapahtui.

Tuona kaudella Harvard pelasi armeijaa. Puoliajalla, yllättäen, armeija johti Harvard 13 – 0. Harvardin presidentti kertoi selkeästi, että armeijan komentajoukkoja oli, että kun armeija voi olla parempi kuin Harvard jalkapallossa, Harvard oli ylivoimainen tieteellisessä kilpailussa.

Vaikka Harvard palasi voittamaan armeijan 14-13in, komentaja hyväksyi haasteen kilpailla Harvardia vastaan ​​jotakin enemmän tieteellistä. Sovittiin, että nämä kaksi kilpailevat matematiikassa. Tämä johti armeijan ja Harvardin valitsemiseen matematiikkajoukkoja; Showdown tapahtui West Pointissa 1933issa. Harvardin yllätykseksi armeija voitti.

Harvardin armeijan kilpailu johti vuotuiseen matematiikkakilpailuun 1938-opiskelijoille, jota kutsuttiin Putnam-tenttinimetty William Lowell Putnam, Harvardin presidentin sukulainen. Tämä tentti on suunniteltu edistämään terveellistä kilpailua matematiikassa Yhdysvalloissa ja Kanadassa. Vuosien varrella ja jatkuen tähän päivään asti tämä tentti on sisältänyt monia mielenkiintoisia ja usein haastavia ongelmia, kuten edellä kuvatun.

Punainen ja sininen viiva

1953-tentti sisälsi seuraavan ongelman (uudelleen muotoiltu hieman): Tasossa on kuusi pistettä. Jokainen piste on yhdistetty jokaiseen toiseen pisteeseen linjalla, joka on joko sininen tai punainen. Osoita, että näistä kolmesta kohdasta on vedetty vain samanvärisiä rivejä.

Jos matematiikassa on joukko pisteitä joidenkin pisteiden parien välissä, sitä kutsutaan kuvaajaksi. Näiden kaavioiden tutkimusta kutsutaan kaavion teoriaksi. Graafiteoriassa pisteitä kutsutaan kuitenkin pisteiksi ja viivoja kutsutaan reunoiksi.

Kuvioita voidaan käyttää edustamaan monenlaisia ​​tilanteita. Esimerkiksi tässä Putnam-ongelmassa kohta voi edustaa henkilöä, punainen viiva voi tarkoittaa sitä, että ihmiset ovat ystäviä ja sininen viiva tarkoittaa, että he ovat vieraita.

Osoita, että saman värin linjat yhdistävät kolme pistettä. Gary Chartrand

Kutsumme esimerkiksi pisteitä A, B, C, D, E, F ja valitsemalla yksi niistä, sano A. A. Viiden viivan, jotka on piirretty A: sta viiteen muuhun kohtaan, on oltava kolme samaa väriä.

Sano, että linjat A: sta B: hen, C, D ovat kaikki punaisia. Jos jokin B: n, C: n, D: n välillä oleva rivi on punainen, on kolme pistettä, joiden välissä on vain punaisia ​​viivoja. Jos yhtään linjaa kahden B: n, C: n, D: n välillä ei ole punainen, ne ovat kaikki sinisiä.

Mitä jos olisi vain viisi pistettä? Ei voi olla kolmea pistettä, joissa kaikki niiden väliset viivat ovat värillisiä. Esimerkiksi rivit A – B, B – C, C – D, E – E, A voivat olla punaisia, toiset sininen.

Silloin, mitä näimme, pienin joukko ihmisiä, jotka voidaan kutsua juhliin (jossa jokainen on joko ystäviä tai vieraita) siten, että on kolme yhteistä ystävää tai kolme keskinäistä vieraita, on kuusi.

Entä jos haluaisimme neljä ihmistä olla keskinäisiä ystäviä tai keskinäisiä vieraita? Mikä on pienin määrä ihmisiä, jotka meidän on kutsuttava puolueeseen, jotta olisimme varmoja tästä? Tähän kysymykseen on vastattu. Se on 18.

Entä jos haluaisimme viisi ihmistä olla keskinäisiä ystäviä tai keskinäisiä vieraita? Tässä tilanteessa pienin määrä ihmisiä, jotka kutsutaan puolueeseen tämän takaamiseksi, on - tuntematon. Kukaan ei tiedä. Vaikka tätä ongelmaa on helppo kuvata ja ehkä kuulostaa melko yksinkertaiselta, se on tunnetusti vaikeaa.

Ramsey-numerot

Olemme keskustelleet siitä, kuinka monta numeroa graafiteoriassa kutsutaan Ramsey-numeroksi. Nämä numerot on nimetty brittiläiselle filosofille, taloustieteilijälle ja matemaatikolle Frank Plumpton Ramsey.

Ramsey kuoli 26in iässä, mutta sai hyvin varhaisessa iässä hyvin utelias lause matematiikassa, joka herätti kysymyksen täällä. Sano, että meillä on toinen kone, jossa on pisteitä, jotka on yhdistetty punaisella ja sinisellä viivalla. Valitsemme kaksi positiivista kokonaislukua, nimeltään r ja s. Haluamme olla täsmälleen r-pisteitä, joissa kaikki niiden väliset viivat ovat punaisia ​​tai pisteitä, joissa kaikki niiden väliset viivat ovat sinisiä. Mikä on pienin määrä pisteitä, joita voimme tehdä tämän kanssa? Tätä kutsutaan Ramsey-numeroksi.

Esimerkiksi sanomme, että haluamme, että koneessamme on vähintään kolme pistettä, jotka on yhdistetty kaikkiin punaisiin viivoihin ja kolmeen pisteen, jotka on yhdistetty kaikkiin sinisiin viivoihin. Ramsey-numero - pienin määrä pisteitä, jotka meidän on tehtävä tämän toteuttamiseksi - on kuusi.

Kun matemaatikot tarkastelevat ongelmaa, he usein kysyvät itseltään: ehdottaako tämä toista kysymystä? Näin on tapahtunut Ramsey-numeroilla - ja puolueongelmilla.

Esimerkiksi tässä on yksi: Viisi tyttöä suunnittelee juhlia. He ovat päättäneet kutsua joitakin pojia puolueeseen, olivatpa he tietävät pojat vai eivät. Kuinka monta poikaa heidän täytyy kutsua olemaan varma siitä, että heidän joukossaan on aina kolme poikaa niin, että kolme viidestä tytöstä on joko ystäviä kaikkien kolmen pojan kanssa tai että he eivät tunne kaikkia kolmea poikaa? Se ei luultavasti ole helppo arvioida vastauksessa. Se on 41!

Hyvin harvat Ramsey-numerot ovat tunnettuja. Tämä ei kuitenkaan estä matemaatikkoja yrittämästä ratkaista tällaisia ​​ongelmia. Usein ongelman ratkaisematta jättäminen voi johtaa vielä mielenkiintoisempaan ongelmaan. Tällainen on matemaatikon elämä.

Tietoja kirjoittajista

Gary Chartrand, matematiikan emeritusprofessori, Western Michigan University; Arthur Benjamin, matematiikan professori, Harvey Mudd College, ja Ping Zhang, matematiikan professori, Western Michigan University

Tämä artikkeli julkaistiin alunperin Conversation. Lue alkuperäinen artikkeli.

Liittyvät kirjat:

at InnerSelf Market ja Amazon