Mostre que em uma reunião de 5 pessoas há sempre 2 com o mesmo número de conhecidos. E se forem 6 pessoas, o resultado ainda vale?

Passo 1

O que o enunciado pede:
  • Mostrar que, numa reunião de 5 pessoas, sempre existem duas pessoas que têm o mesmo número de conhecidos entre as presentes.
  • Responder se o mesmo fato continua válido quando há 6 pessoas.
Informações relevantes dadas (ou implícitas e que vamos usar):
  • Há um conjunto finito de pessoas (primeiro com 5, depois com 6).
  • A relação “ser conhecido” é mútua: se A conhece B, então B conhece A (portanto cada pessoa tem um número inteiro de conhecidos entre 0 e n-1, onde n é o total de pessoas).
  • O número de conhecidos de cada pessoa é um número inteiro entre 0 e n-1.
    Nada mais será assumido.

Passo 2

Ferramenta central — Princípio da casa dos pombos (pigeonhole principle):
  • Enunciado simples: se colocamos m objetos em k caixas e m>k, então alguma caixa contém pelo menos dois objetos.
  • Exemplo rápido e intuitivo: se tiver 5 meias e só 4 gavetas, alguma gaveta terá pelo menos duas meias.
    Vou usar esse princípio para comparar “pessoas” com “caixas” e “valores possíveis do número de conhecidos” com “gavetas”.

Passo 3

Entendendo quais valores o número de conhecidos pode assumir:
  • Se há n pessoas, cada pessoa pode conhecer entre 0 e n-1 das outras — ou seja, os possíveis graus (número de conhecidos) são os inteiros
0,1,2,\dots,n-1.
  • Isso dá n valores possíveis ao todo. Porém há uma restrição importante: não é possível que, ao mesmo tempo, exista alguém com 0 conhecidos e alguém com n-1 conhecidos. Por quê? Porque se existe alguém com n-1 conhecidos, essa pessoa conhece todas as outras, então nenhuma outra pessoa pode ter 0 conhecidos.

Passo 4

Aplicando à reunião de 5 pessoas:
  • Aqui n=5. Os valores possíveis “teóricos” para o número de conhecidos são
0,1,2,3,4,
ou seja, 5 valores.
  • Pela observação do passo anterior, não é possível ter simultaneamente os extremos 0 e 4. Portanto, na prática, só podem ocorrer no máximo 4 valores distintos de número de conhecidos entre as 5 pessoas.
  • Agora aplicamos o princípio da casa dos pombos: temos 5 pessoas (objetos) e no máximo 4 valores distintos de número de conhecidos (caixas). Como 5>4, alguma “caixa” contém pelo menos duas pessoas — isto é, existem pelo menos duas pessoas com o mesmo número de conhecidos.
  • Conclusão: para 5 pessoas, sempre existem duas com o mesmo número de conhecidos.

Passo 5

Discussão detalhada do porquê a hipótese alternativa falha (contradição direta):
  • Se tentássemos ter todos os 5 números diferentes entre 0 e 4, eles seriam exatamente 0,1,2,3,4.
  • Mas ter alguém com 0 e alguém com 4 ao mesmo tempo é impossível, como explicado: a pessoa com 4 conhece todas as outras, então não existe quem não conheça ninguém. Logo essa configuração é contraditória.
  • Assim não é possível que todos os 5 graus sejam distintos; logo ao menos dois graus coincidem.

Passo 6

E se forem 6 pessoas?
  • Agora n=6. Os valores possíveis “teóricos” são
0,1,2,3,4,5,
ou seja, 6 valores.
  • Novamente não podem ocorrer simultaneamente 0 e 5. Portanto, na prática, só podem ocorrer no máximo 5 valores distintos de número de conhecidos entre as 6 pessoas.
  • Aplicando o princípio da casa dos pombos: temos 6 pessoas e no máximo 5 valores distintos, logo 6>5 implica que alguma classe de valor contém pelo menos duas pessoas — existem, portanto, pelo menos duas pessoas com o mesmo número de conhecidos.
  • Conclusão: para 6 pessoas o resultado também vale.

Passo 7

Generalização rápida (opcional, para fixar a ideia):
  • Para qualquer reunião com n pessoas, os valores possíveis de número de conhecidos são 0,1,\dots,n-1 ( n valores), mas 0 e n-1 não podem ocorrer simultaneamente, então existem no máximo n-1 valores distintos realizáveis. Com n pessoas e só n-1 caixas possíveis, pelo princípio da casa dos pombos duas pessoas terão o mesmo número de conhecidos. Portanto o fato vale para qualquer n\ge 2.

Resposta

Para 5 pessoas: sim — sempre existem duas pessoas com o mesmo número de conhecidos.
Para 6 pessoas: sim — o resultado continua válido.

Exercícios relacionados