Se a una festa ognuno condivide un amico con gli altri, uno è amico di tutti: il teorema dell’amicizia

Siamo ad una festa e ci accorgiamo che ciascun invitato ha esattamente un amico in comune con ogni altro partecipante, allora ci chiediamo se c’è qualcuno che conosce tutti gli invitati. La risposta è sì, ce lo dice il Teorema dell’Amicizia – da non confondere con il Paradosso dell'Amicizia – un teorema riguardante la teoria dei grafi che è stato dimostrato per la prima volta nel 1966 dai tre matematici ungheresi Paul Erdős, Alfréd Rényi e Vera T. Sós. Vediamo come funziona il teorema nel caso di una festa e cosa questo ha a che vedere con i mulini a vento.

La situazione è questa, ci troviamo ad una festa dove si verifica una situazione particolare:

ciascun invitato ha esattamente un amico in comune con ogni altro invitato, non uno di più, non uno di meno.

Il teorema dell’Amicizia, allora ci dice che

tra tutti gli invitati ve ne è esattamente uno che è amico di tutti gli invitati.

Vediamo, con un esempio, perché questo accade. Supponiamo che i primi ad arrivare alla festa siano stati Marta, Edo e Marco, e che siano tutti e 3 amici tra di loro per cui, presi due a due, hanno esattamente un amico in comune: Marta ed Edo hanno Marco come amico in comune, Marco ed Edo hanno Marta come amica in comune, Marta e Marco hanno Edo come amico in comune. Usando il linguaggio della teoria dei grafi possiamo descrivere questa situazione con uno schema (vedi immagine sotto) in cui l’amicizia tra due persone è rappresentata da una linea che le unisce.

Uno schema di questo tipo si chiama grafo, le posizioni occupate dai tre amici si chiamano vertici (o nodi) e le linee che li uniscono – le loro relazioni – si chiamano archi (o spigoli).

Ma torniamo alla festa, tra i partecipanti c’è anche Vale, che è amica di Marco, ma non può essere amica anche di Marta perché, se lo fosse Vale ed Edo avrebbero due amici in comune (vedi figura sotto), ovvero Marco e Marta, mentre alla nostra festa due partecipanti possono avere al massimo un amico in comune. Per lo stesso motivo Vale non può essere amica di Edo.

A questo punto, però, c’è un altro problema: Vale e Marco non hanno amici in comune, per cui deve esserci almeno un altro partecipante alla festa, il quale deve essere amico sia di Vale che di Marco. Per fortuna alla nostra festa partecipa anche Luca, un amico comune di Vale e Marco, il quale non è amico né di Edo né di Marta. Luca, infatti, non può essere amico di Edo perché altrimenti avrebbe ben due amici in comune con Marco, ovvero Edo e Vale, e per lo stesso motivo non può essere amico di Marta.

Se alla nostra festa non ci fossero altri partecipanti, quindi, la situazione non potrebbe che essere quella dell’immagine sotto in cui un partecipante, Marco è amico di tutti, e lo schema (o grafo) che rappresenta la situazione è costituito da 2 triangoli con un vertice in comune.

Se immaginiamo ora di aggiungere altri due partecipanti seguendo le stesse regole, come abbiamo fatto per Carla e Luca, non possiamo fare altro che aggiungere al grafo un nuovo triangolo che condivida con gli altri triangoli il vertice costituito da Marco, l’unico invitato amico di tutti (vedi figura sotto).

Il grafo che abbiamo ottenuto è costituito da tre triangoli che condividono un vertice disposto al centro e continuando ad aggiungere partecipanti alla festa dovremmo aggiungere nuovi triangoli, tutti con lo stesso vertice in comune, e Marco continuerebbe a risultare l'unico amico di tutti. La forma del grafo, come possiamo vedere, ricorda un po’ le pale di un mulino a vento: secondo il Teorema dell’Amicizia, infatti, qualunque festa verifichi le stesse regole della nostra festa potrà essere rappresentata con un grafo a forma di mulino a vento.

non perderti questo articolo

Perché è impossibile pettinare una palla pelosa: la spiegazione del teorema