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
pessoas em que cada par é ou amigo (vamos colorir essa aresta de vermelho) ou inimigo (aresta azul). Precisamos mostrar duas afirmações simétricas:
. Há
amigos mútuos (triângulo vermelho) ou
inimigos mútuos (
azul).
. Há
inimigos mútuos (triângulo azul) ou
amigos mútuos (
vermelho).
O conteúdo que vamos usar é o princípio da casa dos pombos aplicado aos graus de um vértice em .
O conteúdo que vamos usar é o princípio da casa dos pombos aplicado aos graus de um vértice em
Passo 2
Escolhe uma pessoa
. Ela se conecta às outras
pessoas com arestas que são vermelhas ou azuis. Pelo princípio da casa dos pombos, entre essas
arestas, pelo menos
têm a mesma cor. Suponha que pelo menos
delas sejam vermelhas, ou seja,
tem pelo menos
“amigos” diretos. Denotemos esses amigos por
.
Passo 3
Examina as arestas entre os
. Se existirem
tais que a aresta
seja vermelha, então
forma um triângulo vermelho. Isso dá três amigos mútuos.
Passo 4
Se, em vez disso, nenhuma das arestas entre os
for vermelha, isso significa que todas são azuis. Logo esses
vértices formam um subgrafo completo azul
. Num
azul sempre há um
azul, dando quatro inimigos mútuos.
Passo 5
O mesmo raciocínio vale se, em vez de
arestas vermelhas,
tiver pelo menos
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
vermelho (quatro amigos mútuos).
Resposta
Mostramos que, em qualquer coloração de
com duas cores (vermelho
amizade, azul
inimizade), sempre aparece um triângulo vermelho ou um
azul, e também sempre aparece um triângulo azul ou um
vermelho. Portanto, em qualquer grupo de
pessoas há três amigos mútuos ou quatro inimigos mútuos, e há três inimigos mútuos ou quatro amigos mútuos.