Em uma reunião, há 6 pessoas. Mostre que, necessariamente, há 3 que se conhecem mutuamente ou 3 que não se conhecem mutuamente. Observação: naturalmente, se
conhece
, então
conhece
. Dica:desenhe um hexágono e use linhas cheias para ligar pessoas que se conhecem e linhas tracejadas para ligar pessoas que não se conhecem. Use o Princípio das Gavetas para garantir que saindo de um vértice há três linhas do mesmo tipo.
Passo 1
Resumindo o enunciado: temos uma reunião com 6 pessoas e a relação “conhece” é simétrica (se
conhece
, então
conhece
). Queremos provar que sempre existe um trio de pessoas que se conhecem mutuamente ou um trio que não se conhece mutuamente. Para isso, vamos representar as 6 pessoas como vértices de um grafo completo de 6 vértices e usar linhas cheias para marcar conexões de conhecimento e linhas tracejadas para marcações de desconhecimento.
Passo 2
Escolhemos um vértice arbitrário
. Ele tem 5 arestas incidindo sobre os outros 5 vértices, cada aresta sendo ou cheia ou tracejada. Pelo Princípio das Gavetas, ao dividir 5 arestas em 2 tipos, ao menos
dessas arestas são do mesmo tipo (todas cheias ou todas tracejadas).
Passo 3
Sejam
,
e
os três vértices que se ligam a
pelas arestas do tipo mais frequente (três arestas iguais).
Passo 4
Caso 1: essas três arestas sejam cheias. Então
conhece
,
e
. Se alguma aresta entre
,
e
também for cheia, digamos entre
e
, então
formam um triângulo de conhecimento. Se nenhuma das arestas entre
,
e
for cheia (todas tracejadas), então
é um triângulo de desconhecimento.
Caso 2: essas três arestas sejam tracejadas. Então
não conhece
,
e
. Se alguma aresta entre
,
e
também for tracejada, digamos entre
e
, então
formam um triângulo de desconhecimento. Se nenhuma das arestas entre
,
e
for tracejada (todas cheias), então
é um triângulo de conhecimento.
Em ambos os casos, encontramos um trio de três pessoas que se conhecem mutuamente ou que não se conhecem mutuamente.
Resposta
Está demonstrado que em qualquer reunião de 6 pessoas existe sempre um trio que se conhece mutuamente ou um trio que não se conhece mutuamente.