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
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á
pessoas.
Informações relevantes dadas (ou implícitas e que vamos usar):
- Há um conjunto finito de pessoas (primeiro com
, depois com ). - 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
e , onde é o total de pessoas). - O número de conhecidos de cada pessoa é um número inteiro entre
e .
Nada mais será assumido.
Passo 2
Ferramenta central — Princípio da casa dos pombos (pigeonhole principle):
- Enunciado simples: se colocamos
objetos em caixas e , então alguma caixa contém pelo menos dois objetos. - Exemplo rápido e intuitivo: se tiver
meias e só 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á
pessoas, cada pessoa pode conhecer entre e das outras — ou seja, os possíveis graus (número de conhecidos) são os inteiros
- Isso dá
valores possíveis ao todo. Porém há uma restrição importante: não é possível que, ao mesmo tempo, exista alguém com conhecidos e alguém com conhecidos. Por quê? Porque se existe alguém com conhecidos, essa pessoa conhece todas as outras, então nenhuma outra pessoa pode ter conhecidos.
Passo 4
Aplicando à reunião de
pessoas:
- Aqui
. Os valores possíveis “teóricos” para o número de conhecidos são
ou seja,
valores.
- Pela observação do passo anterior, não é possível ter simultaneamente os extremos
e . Portanto, na prática, só podem ocorrer no máximo valores distintos de número de conhecidos entre as pessoas. - Agora aplicamos o princípio da casa dos pombos: temos
pessoas (objetos) e no máximo valores distintos de número de conhecidos (caixas). Como , alguma “caixa” contém pelo menos duas pessoas — isto é, existem pelo menos duas pessoas com o mesmo número de conhecidos. - Conclusão: para
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
números diferentes entre e , eles seriam exatamente . - Mas ter alguém com
e alguém com ao mesmo tempo é impossível, como explicado: a pessoa com 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
graus sejam distintos; logo ao menos dois graus coincidem.
Passo 6
E se forem
pessoas?
- Agora
. Os valores possíveis “teóricos” são
ou seja,
valores.
- Novamente não podem ocorrer simultaneamente
e . Portanto, na prática, só podem ocorrer no máximo valores distintos de número de conhecidos entre as pessoas. - Aplicando o princípio da casa dos pombos: temos
pessoas e no máximo valores distintos, logo 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
pessoas o resultado também vale.
Passo 7
Generalização rápida (opcional, para fixar a ideia):
- Para qualquer reunião com
pessoas, os valores possíveis de número de conhecidos são ( valores), mas e não podem ocorrer simultaneamente, então existem no máximo valores distintos realizáveis. Com pessoas e só 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 .
Resposta
Para
pessoas: sim — sempre existem duas pessoas com o mesmo número de conhecidos.
Para pessoas: sim — o resultado continua válido.
Para