Mostre que em um conjunto de n pessoas há duas pessoas que conhecem exatamente o mesmo número de pessoas do conjunto.

Passo 1

Resumindo o problema: temos um grupo de n pessoas em que “conhecer” é uma relação mútua (se A conhece B então B conhece A). Para cada pessoa definimos seu grau d como o número de pessoas que ela conhece. Queremos mostrar que, nesse grupo, existem pelo menos duas pessoas com o mesmo valor de d. O conteúdo usado será o Princípio da Casa dos Pombos (pigeonhole principle) aplicado aos graus possíveis de cada vértice em um grafo simples.

Passo 2

Observamos que, em um grafo simples com n vértices, cada vértice (pessoa) pode ter grau mínimo 0 (não conhece ninguém) e grau máximo n-1 (conhece todas as outras). Logo, para as n pessoas, os graus estão entre
0,1,2,\dots,n-1.

Passo 3

Para ter todos os graus distintos, as n pessoas teriam de ocupar exatamente os n valores \{0,1,2,\dots,n-1\}. Mas vamos mostrar que isso é impossível: não podem coexistir alguém com grau 0 e alguém com grau n-1.

Passo 4

Suponha que exista uma pessoa P com grau n-1. Então P conhece todas as outras n-1 pessoas, de modo que não há ninguém com grau 0. Analogamente, se alguém tivesse grau 0, não poderia existir alguém com grau n-1. Concluímos que, na prática, apenas n-1 valores distintos de grau podem ocorrer simultaneamente.

Passo 5

Como há n pessoas (pombos) e apenas n-1 valores possíveis de grau (câmaras), pelo Princípio da Casa dos Pombos necessariamente duas pessoas compartilham o mesmo grau.

Resposta

Mostramos que não há como atribuir distintos todos os n valores de grau a n pessoas, sobrando um valor de grau para ser repetido. Portanto, existem sempre duas pessoas com o mesmo número de conhecidos.

Exercícios relacionados