Flashcard FC368407
Em um conjunto com n elementos, qual o número mínimo de elementos "marcados" necessário para garantir que qualquer subgrupo de tamanho k contenha pelo menos um marcado?
Princípio da Casa dos Pombos
Instituto Consulplan · 2025
Em um conjunto com n elementos, qual o número mínimo de elementos "marcados" necessário para garantir que qualquer subgrupo de tamanho k contenha pelo menos um marcado?
Mostrar resposta e comentário
Resposta
n-(k-1)Explicação:
Se existirem ≥ k elementos não marcados, é possível escolher um subgrupo de tamanho k sem marcados. Portanto o número máximo de não marcados é k-1, e assim o mínimo de marcados é \(n-(k-1)\).
Exemplo:
Considere \(n=30\) e \(k=8\). Então o mínimo de marcados é
\(30-(8-1)=30-7=23\).
Se houvesse apenas 22 marcados, haveria 8 não marcados e poderíamos formar um grupo de 8 sem marcados; com 23 marcados isso não é possível.
Veja como foi cobrado:
https://flashcardsconcursos.com.br/portal/flashcard/365019
Conteúdo do catálogo FC Concursos · Atualizado em