Teorema degli amici e degli sconosciuti

Il Teorema degli amici e degli sconosciuti (in inglese: Theorem on friends and strangers) è un teorema di matematica nel dominio della teoria di Ramsey.

Le 76 possibili combinazioni amici-sconosciuti in un grafo di 6 nodi. In qualsiasi grafo, esiste sempre una tripletta di nodi rossi o blu reciprocamente amici o sconosciuti.

Nel 1930, il matematico statunitense Frank P. Ramsey pubblicò l'articolo intitolato On a Problem in Formal Logic, che dimostrava il teorema omonimo, dando origine alla Teoria di Ramsey nell'area della matematica combinatoria.
Il Teorema degli amici e degli sconosciuti è un caso particolare del Teorema di Ramsey, valido per insiemi di almeno 6 elementi e dimostrabile mediante il formalismo dei grafi come corollario del principio dei cassetti.

Enunciato

Si consideri una festa alla quale sono presenti sei persone. Si considerino tutte le possibili coppie dei sei presenti presi a due a due. Diciamo che sono reciprocamente sconosciuti se si incontrano per la prima volta; diciamo invece che sono reciprocamente amici se già si erano incontrati almeno un'altra volta prima della festa.

Il Teorema degli amici e degli sconosciuti afferma che in ogni festa di sei persone almeno tre di esse sono (a coppie) reciprocamente sconosciute oppure almeno tre di esse sono (a coppie) reciprocamente amiche.

Riconduzione alla teoria dei grafi

La dimostrazione del teorema è formata da tre passaggi logici, più agevolmente descrivibili se si formalizza il problema mediante la teoria dei grafi.

Si consideri un grafo di 6 vertici, nel quale ogni coppia di vertici (non coincidenti) sia congiunta da un bordo. Tale grafo si dice completo poiché non possono esserci più spigoli.
Un grafo completo rispetto a $n$ vertici è indicato con la notazione $K_{n}$ .

Si consideri ora un grafo $K_{6}$ (completo di 6 vertici), che avrà 15 bordi in totale. Si supponga che i 6 vertici rappresentino le 6 persone presenti alla festa. Si colorino i bordi di rosso o blu a seconda che le due persone siano sconosciute una all'altra ovvero si conoscano reciprocamente. Il teorema, nella terminologia della teoria dei grafi, asserisce che:

per tutte le possibili combinazioni di colore rosse o blu sui 15 bordi di

K_{6}

, non sarà mai possibile evitare di tracciare un triangolo di colore rosso (avente tre lati e tre vertici relativi a coppie che sono reciprocamente sconosciute), ovvero un triangolo di colore blu (avente tre lati e tre vertici relativi a coppie di persone che si conoscono reciprocamente l'una con l'altra). In altre parole, qualsiasi sia la colorazione, esisterà sempre almeno un triangolo monocromatico, i cui tre bordi sono dello stesso colore rosso o blu.

Dimostrazione

Si consideri un vertice a piacere P. Esisteranno cinque bordi aventi la loro origine in P. Ognuno di essi sarà di colore rosso oppure di colore blu. Il principio dei cassetti afferma che almeno tre di essi devono essere dello stesso colore. Ciò implica che se meno di tre di essi sono di un colore (ad esempio il rosso), allora almeno tre bordi fra quelli rimanenti devono essere dell'altro colore (ad es. blu).

Siano A, B e C gli estremi di questi tre triangoli, aventi lo stesso colore, ad esempio blu. Se uno dei segmenti (bordi) AB, BC o CA è di colore blu (ad es. AB), allora sono di colore blu anche i bordi che uniscono il vertice P agli estremi del segmento dato (ad es. PA E PB), formando un triangolo di colore blu (di vertici PAB).
Se invece nessuno dei tre bordi AB, BC o CA è blu, allora per esclusione tutti e tre i bordi sono rossi e abbiamo un triangolo rosso di vertici ABC.

Dominio di esistenza

Una colorazione a coppie di 2 elementi di un grafo completo of K₅, nel quale non esistono triangoli monocromatici K₃

La conclusione del teorema non è più vera se sostituiamo l'insieme ipotetico di sei persone con un insieme di numerosità inferiore a sei. Per dimostrarlo, coloriamo un grafo completo a 5 vertici (quanto le 5 persone prese in considerazione), indicato con $K_{5}$ . Rappresentiamo $K_{5}$ come un pentagono circoscritto alla stella a 5 punte (un pentagramma). Coloriamo i bordi del pentagono con il colore rosso e i bordi della stella con il colore blu. La figura così ottenuta rappresenta tutti i possibili bordi di collegamento fra i 5 vertici, considerati a copie di 2: come si vede nella figura, nel pentagono non esiste un singolo triangolo i cui tre lati siano tutti dello stesso colore rosso o blu.

Pertanto, 6 è il numero più piccolo per il quale possiamo ritenere vera e dimostrabile la conclusione del teorema. Nell'ambito della teoria di Ramsey, questa proprietà dimostrata per via geometrica viene espressa in modo analitico nel modo seguente:

R(3,3: 2) = 6

Bibliografia

V. Krishnamurthy. Culture, Excitement and Relevance of Mathematics, Wiley Eastern, 1990, ISBN 81-224-0272-0.

Voci correlate

Collegamenti esterni

(EN) Alexander Bogomolny, Party Acquaintances at cut-the-knot, su cut-the-knot.org.

Portale Matematica: accedi alle voci di Wikipedia che trattano di matematica