Aquest teorema diu:
«En qualsevol grup de 6 o més persones sempre hi ha o bé un grup de 3 persones que es coneixen mútuament o bé un grup de 3 persones que no es coneixen».
Aquí, les torres representen les 6 persones. El blau pot representar, per exemple, que les persones es coneixen i vermell que no es coneixen.
Un primer repte
Gira les barres per canviar-les de color.
Comprova que sempre hi ha un triangle monocolor.
Un segon repte
Si en lloc de tenir totes les connexions entre els 6 vèrtexs (el que s’anomena gràfic complet) hi ha una connexió inexistent, llavors sí que existeixen configuracions sense triangles monocolors.
Posa, per exemple, una de les barres exteriors de l’hexàgon de costat. D’aquesta forma es representa que no és ni blava ni vermella.
Ara el repte és aconseguir que la resta de barres no continguin cap triangle d’un sol color.
Hi ha més d’una solució, aquestes i les corresponents intercanviant els colors en són una mostra.
- Ubicació: Sala Martin Gardner
- Edat mínima: a partir de 10 anys.
- Temps requerit: 5 minuts.
- Nombre de participants: Una o més persones
- Paraules clau: Combinatòria, Teoria de Ramsey, Grafs
- Taxonomia: Combinatòria
Frank Ramsey i la Teoria de Ramsey
Frank Ramsey (1903 – 1930) va ser un matemàtic anglès. A partir de les seves investigacions s’ha creat la branca de la combinatòria coneguda com a Teoria de Ramsey.
La teoria de Ramsey, busca regularitats en mig del desordre i en quines condicions apareixen.
Considerem per exemple els grafs complets \mathbf{K} consistents en una sèrie de punts o vèrtexs units entre de totes les maneres possibles per mitjà d’arestes. Amb 3 punts \mathbf{K}_{3} és un triangle, amb 4 \mathbf{K}_{4} un quadrilàter i les seves dues diagonals.
Si acolorim les arestes amb dos colors. Quina mida ha de tenir el graf \mathbf{K} per estar segurs que apareix un triangle d’un sol color? En aquest cas estem buscant el nombre de Ramsey \mathbf{R}(3,3)
La resposta sabem que és 6: ens cal el graf \mathbf{K}_{6} amb 6 vèrtexs i les seves 15 arestes com el que tenim.
La demostració és simple:
- En primer lloc, es veu que amb 3, 4 o 5 vèrtexs hi ha configuracions del graf que no tenen triangles monocolors.
- A continuació cal assegurar que en el cas \mathbf{K}_{6} sempre hi ha un triangle monocolor.
- Ens fixem en un dels seus vèrtexs, de les 5 arestes que surten d’ell n’hi haurà 3 o més del mateix color.
- Per tal que no es formin triangles monocolors les arestes que uneixen els extrems d’aquestes 3 arestes han de ser de l’altre color.
- Però llavors es forma un triangle monocolor amb els extrems d’aquestes 3 arestes.
- Així doncs, un \mathbf{K}_{6} de dos colors sempre contindrà un \mathbf{K}_{3} d’un color.
Aquest és el nombre de Ramsey més petit, el següent és \mathbf{R}(4,3)=9. Encara es desconeixen molts nombres de Ramsey i en altres sols s’han demostrat el seu límit superior o inferior. Podeu veure els darrers resultats obtinguts a Wolfram Alpha Mathword.