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 A conhece B, então B conhece A. 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 A conhece B, então B conhece A). 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 P. 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
\bigl\lceil \tfrac{5}{2}\bigr\rceil = 3
dessas arestas são do mesmo tipo (todas cheias ou todas tracejadas).

Passo 3

Sejam A, B e C os três vértices que se ligam a P pelas arestas do tipo mais frequente (três arestas iguais).

Passo 4

Caso 1: essas três arestas sejam cheias. Então P conhece A, B e C. Se alguma aresta entre A, B e C também for cheia, digamos entre A e B, então \{P,A,B\} formam um triângulo de conhecimento. Se nenhuma das arestas entre A, B e C for cheia (todas tracejadas), então \{A,B,C\} é um triângulo de desconhecimento.
Caso 2: essas três arestas sejam tracejadas. Então P não conhece A, B e C. Se alguma aresta entre A, B e C também for tracejada, digamos entre A e B, então \{P,A,B\} formam um triângulo de desconhecimento. Se nenhuma das arestas entre A, B e C for tracejada (todas cheias), então \{A,B,C\} é 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.

Exercícios relacionados