Teorema de l'amistat

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

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

É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 $K_{n}\,$. 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 $K_{3}\,$ o del cicle de longitud 3: $C_{3}\,$, comunament anomenat triangle.

Ara agafeu un $K_{6}\,$. 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 $K_{6}\,$ 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

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

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 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

Un acolorit de dos colors de K₅ sense un K₃ monocrom.

La conclusió del teorema de l'amistat no es té en grups de menys de sis persones. Per demostrar això, s'acoloreix K₅ de vermell i blau de manera que no contingui cap triangle els costats del qual siguin tots del mateix color. Dibuixem K₅ 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:

$R(3,3:2)=6.\,$

Referències

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

Vegeu també

• Coloració de grafs

Enllaços externs

• Bogomolny, Alexander. «Party Acquaintances». Interactive Mathematics Miscellany and Puzles (en anglès).