Flashcard FC368415
Se em todo grupo de s elementos há pelo menos t com uma certa propriedade, qual o menor número possível de elementos com essa propriedade em um conjunto de N elementos?
Princípio da Casa dos Pombos
Instituto Consulplan · 2024
Se em todo grupo de s elementos há pelo menos t com uma certa propriedade, qual o menor número possível de elementos com essa propriedade em um conjunto de N elementos?
Mostrar resposta e comentário
Resposta
\( \min = N - (s - t)\)Explicação:
Sejam U os elementos sem a propriedade.
Se \(U \ge s - t + 1\), podemos escolher \(s - t + 1\) desses e mais \(t-1\) quaisquer, formando um grupo de \(s\) com no máximo \(t-1\) com a propriedade — contradição.
Logo \(U \le s - t\) e o número mínimo com a propriedade é \(N - (s - t)\).
Exemplo:
Em um prédio com \(N=50\) pessoas, se em qualquer grupo de \(s=8\) há pelo menos \(t=3\) falantes de inglês, então mínimo de falantes = \(50-(8-3)=50-5=45\).
Veja como foi cobrado:
https://flashcardsconcursos.com.br/portal/flashcard/365027
Conteúdo do catálogo FC Concursos · Atualizado em