Concurso: OBMEP | Ano: 2025 | Assunto: Combinatória / Teoria dos Grafos
Enunciado:
Dizemos que uma família é amistosa se ela possui 10 membros e cada um deles conhece exatamente 5 outros membros.
Qual é o menor valor de \( k \) tal que em todo grupo de \( k \) pessoas dessa família é sempre possível encontrar duas que se conheçam?
Alternativas:
- (A) 3
- (B) 5
- (C) 4
- >(D) 6
- (E) 7
Ver Solução
1. Interpretando o problema:
Podemos representar os membros como vértices de um grafo, onde cada pessoa é ligada a 5 outras → o grafo é regular de grau 5 com 10 vértices.
2. O que se pede:
Qual o menor número \( k \) de pessoas escolhidas da família que garante que ao menos duas se conheçam?
3. Estratégia:
Queremos garantir que **sempre** haja pelo menos uma aresta (conhecimento) entre as \( k \) pessoas escolhidas.
Ou seja, **evitar um subconjunto de \( k \) vértices totalmente desconexos** (sem nenhuma conexão entre si).
4. Usando o conceito de conjunto independente:
Qual o maior conjunto de vértices em que nenhum conhece o outro? Isso é o chamado número de independência do grafo.
No grafo de 10 vértices, cada um conectado a 5 outros, o número máximo de pessoas que podem ser escolhidas sem que nenhuma conheça a outra é 5.
5. Conclusão:
Se escolhermos **6 pessoas**, pelo menos duas se conhecem obrigatoriamente.
Portanto, o menor valor de \( k \) que garante isso é: \[ \boxed{6} \]
Gabarito: (D) 6
🧠 Mapas Mentais de Matemática
