Questão 19 (Nível 3) da OBMEP 2025

Resolução comentada

Pense na família como um grafo com 10 vértices em que cada pessoa tem exatamente 5 conhecidos (grafo 5-regular). Queremos o menor k tal que todo grupo de k pessoas tenha duas que se conhecem, ou seja, o maior conjunto de pessoas que não se conhecem (conjunto independente) tem tamanho menor que k.

1. Limite superior: seja S um conjunto de m pessoas que não se conhecem. Cada uma tem 5 conhecidos, todos fora de S. Então há 5m conhecimentos saindo de S para os 10-m pessoas de fora.
2. Cada pessoa de fora tem no máximo 5 conhecidos, logo 5m \le 5(10-m), ou seja, m \le 5.
3. Esse máximo é possível: m=5 ocorre quando cada pessoa de fora conhece todos os 5 de S. Exemplo: duas turmas de 5 pessoas, em que todos de uma turma conhecem todos da outra e ninguém conhece alguém da própria turma (grafo bipartido completo K_{5,5}). Cada pessoa conhece exatamente 5, e cada turma é um grupo de 5 pessoas sem conhecidos entre si.
4. Portanto, com k=5 não é garantido: a turma inteira serve de contraexemplo.
5. Com k=6: como todo grupo sem conhecidos tem no máximo 5 pessoas, qualquer grupo de 6 tem duas que se conhecem.

Logo o menor valor que garante é k=6.

Alternativa D.

Pegadinha: A alternativa B engana quem acha que 5 basta por cada pessoa ter 5 conhecidos; o contraexemplo K_{5,5} mostra que 5 pessoas podem não se conhecer.

Por que as outras alternativas estão erradas

• ACom 3 pessoas é fácil escolher três sem conhecidos, por exemplo dentro de uma turma do exemplo K_{5,5}.
• BCom 5 pessoas ainda há contraexemplo: uma das turmas de K_{5,5} não tem conhecidos entre si.
• CCom 4 pessoas também é possível escolher um grupo sem conhecidos.
• E7 garante, mas não é o menor, pois 6 já basta.

Assuntos: Lógica e raciocínio lógico, Princípio fundamental da contagem.

Reportar erro na resolução

O que está errado?

Conta ou raciocínio errado Chega em outra resposta Explicação confusa Outro problema

Detalhes (opcional) Não preencha

Enviar Sem cadastro: não guardamos quem enviou.