Teorema de l'amistat

De Viquipèdia
Salta a la navegació Salta a la cerca
Els 78 grafs possibles d'amics-estranys amb 6 vèrtexs. A cada graf, les arestes de color blau/vermell mostren la relació mútua d'amics/estranys.

El teorema d'amics i estranys o teorema de l'amistat és un teorema en el camp matemàtic anomenat teoria de Ramsey.

Formulació del teorema[modifica]

Suposeu que en una festa hi ha sis persones. Considereu dues d'aquestes persones. Pot ser que es reuneixin per primera vegada, en aquest cas són mútuament estranyes, o pot ser que s'hagin conegut abans, en aquest cas se'ls anomenarà mútuament conegudes. Ara, el teorema de l'amistat diu:

En qualsevol grup de sis persones, n'existeixen tres que són mútuament conegudes o mútuament desconegudes.

Conversió a grafs[modifica]

És convenient expressar aquest problema usant el llenguatge de teoria de grafs.

Suposeu que un graf té sis vèrtexs i cada parell de vèrtexs està unit per una aresta. Aquest graf es diu graf complet. Un graf complet de n vèrtexs es denota per . En el cas d'un graf de tres vèrtexs, i en el qual cada vèrtex és adjacent als altres, es tracta d'un graf complet o del cicle de longitud 3: , comunament anomenat triangle.

Ara agafeu un . Aquest graf complet té quinze arestes en total. Siguin les sis persones de la festa representades per sis vèrtexs. Siguin les arestes acolorides amb els colors vermell o blau, depenent de si les persones representades pels vèrtexs incidents a l'aresta són mútuament conegudes o desconegudes, respectivament. El teorema de l'amistat afirma ara:

No importa com s'hagin acolorit les arestes de amb els colors vermell o blau, no es pot evitar que existeixi un trianble vermell, és a dir, un triangle que tingui els seus tres costats de color vermell, la qual cosa representa tres persones mútuament estranyes o un triangle blau, que representa tres persones mútuament conegudes.

Prova[modifica]

Elegiu un dels vèrtexs P. Hi ha cinc arestes incidents a P, cadascuna acolorida amb el color vermell o blau. Segons el principi del colomar, almenys tres arestes han de ser del mateix color, perquè si n'hi ha menys de tres d'un sol color, per exemple vermella, llavors n'hi ha almenys tres que són de color blau.

Siguin A, B, C, els altres vèrtexs extrems d'aquestes tres arestes, totes del mateix color, per exemple blau. Si alguna de les arestes AB, BC, CA és blava, llavors aquesta aresta juntament amb les dues arestes incidents a P formen els costats d'un triangle blau. Si cap de les arestes AB, BC, CA és blava, llavors les tres arestes són de color vermell i es té un triangle vermell de vèrtexs ABC.

Treball de Ramsey[modifica]

La total simplicitat d'aquest argument, que produeix amb tanta força una interessant conclusió, és el que fa atractiu aquest teorema. En 1930, en un treball titulat «On a Problem in Formal Logic» (Sobre un problema en lògica formal), Frank P. Ramsey va demostrar un teorema molt general, conegut en l'actualitat com a teorema de Ramsey en el qual el teorema de l'amistat és un cas particular. El teorema de Ramsey és la base sobre la qual se sosté l'àrea de la combinatòria coneguda com a teoria de Ramsey.

Àmbit del teorema de l'amistat[modifica]

Un acolorit de dos colors de K5 sense un K3 monocrom.

La conclusió del teorema de l'amistat no es té en grups de menys de sis persones. Per demostrar això, s'acoloreix K5 de vermell i blau de manera que no contingui cap triangle els costats del qual siguin tots del mateix color. Dibuixem K5 com un pentàgon que envolta una estrella i acolorim de vermell els costats del pentàgon i de blau els de l'estrella. Per tant, sis és el mínim nombre pel qual es pot donar per bona la conclusió del teorema de l'amistat. En la teoria de Ramsey, això es denota per:

Referències[modifica]

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

Vegeu també[modifica]

Enllaços externs[modifica]