Cada pareja se conoce o no se conoce. ¿A partir de cuántas personas resulta inevitable un trío del mismo tipo?
El trío inevitable
Enunciado
En una reunión, para cada pareja de personas ocurre exactamente una de estas dos cosas: se conocen mutuamente o son desconocidas entre sí.
¿Cuál es el menor número de personas que garantiza que, sean cuales sean esas relaciones, habrá tres que se conozcan mutuamente o tres que sean mutuamente desconocidas?
Ver solución
Solución
Respuesta: el menor número es 6.
Primero veremos por qué seis personas bastan.
Elige una persona cualquiera, \(X\). Respecto de las otras cinco, cada relación es de uno de dos tipos: conocer o no conocer.
Por el principio del palomar, al menos tres de esas cinco relaciones son del mismo tipo. Llamemos \(A\), \(B\) y \(C\) a tres personas con esa misma relación respecto de \(X\).
Si \(X\) conoce a las tres, solo hay dos posibilidades:
- alguna pareja entre \(A\), \(B\) y \(C\) se conoce; esa pareja junto con \(X\) forma un trío de conocidos;
- ninguna pareja se conoce; entonces \(A\), \(B\) y \(C\) son mutuamente desconocidas.
Si \(X\) no conoce a ninguna de las tres, el razonamiento es simétrico: o alguna pareja forma con \(X\) un trío de desconocidos, o las tres se conocen mutuamente.
Por tanto, entre seis personas uno de los dos tipos de trío es inevitable.
Ahora debemos comprobar que cinco no bastan.
Coloca cinco personas en los vértices de un pentágono y haz que cada una conozca únicamente a sus dos vecinas. Las relaciones de conocimiento forman un ciclo de cinco vértices, que no contiene ningún triángulo.
Las relaciones entre desconocidos son las cinco diagonales del pentágono. Estas también forman un ciclo de cinco vértices y tampoco contienen ningún triángulo.
Así, con cinco personas pueden evitarse ambos tipos de trío, mientras que con seis ya no:
Idea esencial: seis obligan mediante el principio del palomar; cinco todavía escapan mediante el pentágono.