Em uma reunião há
pessoas presentes. Mostre que existem duas pessoas que conhecem exatamente o mesmo número de outros participantes (admita que “conhecer” seja uma relação simétrica, ou seja, se
conhece
, então
conhece
). Dica:note não ser possível que, simultaneamente, haja uma pessoa que conheça todas as outras e outra que não conheça ninguém.
Passo 1
O enunciado descreve uma reunião com
pessoas em que “conhecer” é uma relação simétrica. Podemos modelar essa situação por um grafo simples com
vértices, em que cada vértice representa uma pessoa e cada aresta uma amizade mútua. Queremos mostrar que existem dois vértices com o mesmo grau (ou seja, duas pessoas que conhecem exatamente o mesmo número de outras). O conteúdo principal aqui é o Princípio da Casa dos Pombos aplicado aos graus dos vértices.
Passo 2
Para cada pessoa
definimos
Como cada pessoa pode conhecer de 0 até todas as outras, temos
Logo, há
valores possíveis para os graus.
Passo 3
Note que não é possível existir simultaneamente alguém com grau 0 (que não conhece ninguém) e alguém com grau
(que conhece todo mundo). Se existisse um vértice de grau
, ele estaria conectado a todos os outros, inclusive ao vértice de grau 0, o que é contraditório. Logo, ou o valor 0 ou o valor
não aparece na lista de graus. Isso reduz o número de valores possíveis de grau de
para, no máximo,
.
Passo 4
Temos
pessoas (ou seja,
graus
) mas apenas
valores diferentes podem ocorrer. Pelo Princípio da Casa dos Pombos, dois desses graus devem coincidir. Em outras palavras, existem duas pessoas com o mesmo número de conhecidos.
Resposta
Existem, portanto, duas pessoas que conhecem exatamente o mesmo número de outros participantes.