Questo puzzle matematico ti aiuterà a pianificare la tua prossima festa
Mappatura delle connessioni al tuo prossimo shindig.
unclibraries_commons 

Diciamo che stai pianificando la tua prossima festa e stai tormentando la lista degli invitati. A chi dovresti inviare gli inviti? Quale combinazione di amici e sconosciuti è il giusto mix?

Risulta che i matematici hanno lavorato a una versione di questo problema per quasi un secolo. A seconda di cosa vuoi, la risposta può essere complicata.

Il nostro libro, "Il mondo affascinante della teoria dei grafi, "Esplora enigmi come questi e mostra come possono essere risolti attraverso i grafici. Una domanda come questa potrebbe sembrare piccola, ma è una bella dimostrazione di come i grafici possono essere usati per risolvere problemi matematici in campi così diversi come le scienze, la comunicazione e la società.

Un puzzle è nato

Mentre è risaputo che Harvard è una delle migliori università accademiche del paese, potresti essere sorpreso di apprendere che c'è stato un periodo in cui Harvard aveva una delle migliori squadre di calcio della nazione. Ma in 1931, guidato da Quarterback all-americano di Barry Wood, tale era il caso.

Quella stagione Harvard ha giocato nell'esercito. All'intervallo, inaspettatamente, l'esercito ha guidato Harvard 13-0. Chiaramente sconvolto, il presidente di Harvard disse al comandante dell'esercito di cadetti che, mentre l'esercito poteva essere migliore di Harvard nel calcio, Harvard era superiore in una competizione più accademica.


innerself iscriviti alla grafica


Sebbene Harvard sia tornato per sconfiggere l'Esercito 14-13, il comandante ha accettato la sfida di competere contro Harvard in qualcosa di più erudito. Fu deciso che i due avrebbero gareggiato - in matematica. Ciò portò l'esercito e Harvard a selezionare squadre di matematica; lo showdown è avvenuto a West Point in 1933. Con sorpresa di Harvard, l'esercito vinse.

La competizione Harvard-Army alla fine ha portato a un concorso annuale di matematica per laureandi in 1938, chiamato il Esame Putnam, chiamato per William Lowell Putnam, un parente del presidente di Harvard. Questo esame è stato progettato per stimolare una sana rivalità in matematica negli Stati Uniti e in Canada. Nel corso degli anni e continuando fino ad oggi, questo esame ha contenuto molti problemi interessanti e spesso impegnativi, tra cui quello descritto sopra.

Linee rosse e blu

L'esame 1953 conteneva il seguente problema (riformulato un po '): ci sono sei punti nel piano. Ogni punto è collegato a ogni altro punto da una linea blu o rossa. Mostra che ci sono tre di questi punti tra cui vengono disegnate solo le linee dello stesso colore.

In matematica, se esiste una raccolta di punti con linee tracciate tra alcune coppie di punti, quella struttura viene chiamata grafico. Lo studio di questi grafici è chiamato teoria dei grafi. Nella teoria dei grafi, tuttavia, i punti sono chiamati vertici e le linee sono chiamate archi.

I grafici possono essere utilizzati per rappresentare un'ampia varietà di situazioni. Ad esempio, in questo problema Putnam, un punto può rappresentare una persona, una linea rossa può significare che le persone sono amici e una linea blu significa che sono estranei.

test di matematica
Mostra che ci sono tre punti collegati da linee dello stesso colore. Gary Chartrand

Per esempio, chiamiamo i punti A, B, C, D, E, F e ne selezioniamo uno, diciamo A. Delle cinque linee tracciate da A agli altri cinque punti, ci devono essere tre linee dello stesso colore.

Dire che le linee da A a B, C, D sono tutte rosse. Se una linea tra due qualsiasi di B, C, D è rossa, allora ci sono tre punti con solo linee rosse tra loro. Se nessuna linea tra due qualsiasi di B, C, D è rossa, allora sono tutte blu.

E se ci fossero solo cinque punti? Non ci possono essere tre punti in cui tutte le linee tra di loro sono colorate allo stesso modo. Ad esempio, le linee A-B, B-C, C-D, D-E, E-A potrebbero essere rosse, con le altre blu.

Da quello che abbiamo visto, quindi, il minor numero di persone che possono essere invitati a una festa (in cui ogni due persone sono amici o estranei) in modo tale che ci siano tre amici in comune o tre estranei è sei.

E se desiderassimo che quattro persone fossero amici in comune o estranei? Qual è il più piccolo numero di persone che dobbiamo invitare a una festa per essere certi di questo? Questa domanda ha avuto risposta. È 18.

E se desiderassimo che cinque persone fossero amici in comune o estranei? In questa situazione, il numero minimo di persone da invitare a una parte per garantirne la presenza è sconosciuto. Nessuno sa. Mentre questo problema è facile da descrivere e forse sembra piuttosto semplice, è notoriamente difficile.

Numeri Ramsey

Quello di cui abbiamo discusso è un tipo di numero nella teoria dei grafi chiamato numero di Ramsey. Questi numeri prendono il nome dal filosofo, economista e matematico britannico Frank Plumpton Ramsey.

Ramsey morì all'età di 26, ma ottenne alla sua tenera età un teorema molto curioso in matematica, che diede origine alla nostra domanda qui. Supponiamo di avere un altro piano pieno di punti collegati da linee rosse e blu. Selezioniamo due numeri interi positivi, chiamati r e s. Vogliamo avere esattamente punti r in cui tutte le linee tra loro sono rosse o punti in cui tutte le linee tra loro sono blu. Qual è il più piccolo numero di punti con cui possiamo fare questo? Questo è chiamato un numero Ramsey.

Ad esempio, diciamo che vogliamo che il nostro aereo abbia almeno tre punti collegati da tutte le linee rosse e tre punti collegati da tutte le linee blu. Il numero di Ramsey - il minor numero di punti di cui abbiamo bisogno per farlo accadere - è sei.

Quando i matematici considerano un problema, spesso si chiedono: questo suggerisce un'altra domanda? Questo è quello che è successo con i numeri di Ramsey - e i problemi di partito.

Per esempio, eccone uno: cinque ragazze stanno organizzando una festa. Hanno deciso di invitare alcuni ragazzi alla festa, che conoscano o no i ragazzi. Quanti ragazzi hanno bisogno di invitare per essere certi che ci saranno sempre tre ragazzi tra loro in modo che tre delle cinque ragazze siano o amici con tutti e tre i ragazzi o non conoscano tutti e tre i ragazzi? Probabilmente non è facile fare una buona ipotesi alla risposta. È 41!

The ConversationSono noti pochissimi numeri Ramsey. Tuttavia, questo non impedisce ai matematici di cercare di risolvere tali problemi. Spesso, non riuscire a risolvere un problema può portare a un problema ancora più interessante. Questa è la vita di un matematico.

Riguardo agli Autori

Gary Chartrand, professore emerito di matematica, Western Michigan University; Arthur Benjamin, professore di matematica, Mudd Collegee Ping Zhang, professore di matematica, Western Michigan University

Questo articolo è stato pubblicato in origine The Conversation. Leggi il articolo originale.

Libri correlati:

at InnerSelf Market e Amazon