Mostre que em um grupo de 10 pessoas (em que duas pessoas são amigas ou inimigas) há três amigos mútuos ou quatro inimigos mútuos, e que há três inimigos mútuos ou quatro amigos mútuos.

Passo 1

Resumindo, temos um grupo de 10 pessoas em que cada par é ou amigo (vamos colorir essa aresta de vermelho) ou inimigo (aresta azul). Precisamos mostrar duas afirmações simétricas:
1. Há 3 amigos mútuos (triângulo vermelho) ou 4 inimigos mútuos ( K_4 azul).
2. Há 3 inimigos mútuos (triângulo azul) ou 4 amigos mútuos ( K_4 vermelho).
O conteúdo que vamos usar é o princípio da casa dos pombos aplicado aos graus de um vértice em K_{10}.

Passo 2

Escolhe uma pessoa A. Ela se conecta às outras 9 pessoas com arestas que são vermelhas ou azuis. Pelo princípio da casa dos pombos, entre essas 9 arestas, pelo menos 5 têm a mesma cor. Suponha que pelo menos 5 delas sejam vermelhas, ou seja, A tem pelo menos 5 “amigos” diretos. Denotemos esses amigos por B_1,B_2,B_3,B_4,B_5.

Passo 3

Examina as arestas entre os B_i. Se existirem i\neq j tais que a aresta (B_i,B_j) seja vermelha, então \{A,B_i,B_j\} forma um triângulo vermelho. Isso dá três amigos mútuos.

Passo 4

Se, em vez disso, nenhuma das arestas entre os B_1,\dots,B_5 for vermelha, isso significa que todas são azuis. Logo esses 5 vértices formam um subgrafo completo azul K_5. Num K_5 azul sempre há um K_4 azul, dando quatro inimigos mútuos.

Passo 5

O mesmo raciocínio vale se, em vez de 5 arestas vermelhas, A tiver pelo menos 5 arestas azuis (inimigos). Basta trocar ``vermelho \leftrightarrow azul'' no argumento acima e concluímos que haverá um triângulo azul (três inimigos mútuos) ou um K_4 vermelho (quatro amigos mútuos).

Resposta

Mostramos que, em qualquer coloração de K_{10} com duas cores (vermelho = amizade, azul = inimizade), sempre aparece um triângulo vermelho ou um K_4 azul, e também sempre aparece um triângulo azul ou um K_4 vermelho. Portanto, em qualquer grupo de 10 pessoas há três amigos mútuos ou quatro inimigos mútuos, e há três inimigos mútuos ou quatro amigos mútuos.

Exercícios relacionados