Em uma reunião há n 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 a conhece b, então b conhece a ). 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 n pessoas em que “conhecer” é uma relação simétrica. Podemos modelar essa situação por um grafo simples com n 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 i definimos
d_i = \text{número de pessoas que \(i\) conhece}.ú
Como cada pessoa pode conhecer de 0 até todas as outras, temos
d_i \in \{0,1,2,\dots,n-1\}.
Logo, há n 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 n-1 (que conhece todo mundo). Se existisse um vértice de grau n-1, 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-1 não aparece na lista de graus. Isso reduz o número de valores possíveis de grau de n para, no máximo, n-1.

Passo 4

Temos n pessoas (ou seja, n graus d_1,d_2,\dots,d_n) mas apenas n-1 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.

Exercícios relacionados