GIANT STEPS E OBM
Solução:
Usaremos o diagrama a seguir, ilustrando a situação. Cada pessoa é representada por um vértice do hexágono. Quando duas pessoas se conhecem, ligamos os vértices correspondentes por um segmento em vermelho; se elas não se conhecem, usamos um segmento em verde. O que devemos mostrar é que, nesta figura, necessariamente existe um triângulo formado por linhas vermelhas ou um triângulo formado por linhas verdes.
Consideremos os segmentos que incidem em um dos vértices P1. Como eles são 5, há pelo menos 3 deles que são vermelhos ou pelo menos 3 que são verdes. Admitamos que haja 3 vermelhos (o argumento no caso de serem verdes é análogo).
Denotemos por P2, P3 e P4 os vértices ligados a P1 por segmentos vermelhos. Se algum dos segmentos P2P3, P2P4 ou P3P4 é vermelho, este segmento, juntamente com os que ligam seus extremos a P1, formam um triângulo de lados em vermelho.
Por outro lado, se nenhum deles é vermelho, eles formam um triângulo de lados verdes, o que completa a demonstração.
Com isso, mostramos que existem pelo menos 3 pessoas que se conhecem mutuamente ou 3 pessoas que não se conhecem mutuamente.