Flashcard FC303354
Se em qualquer subconjunto de k elementos há pelo menos r bons, qual o máximo de elementos estragados que pode haver no total?
Princípio da Casa dos Pombos
FGV · 2016
Se em qualquer subconjunto de k elementos há pelo menos r bons, qual o máximo de elementos estragados que pode haver no total?
Mostrar resposta e comentário
Resposta
Máximo de estragados: \(k-r\)Explicação:
Se houvesse pelo menos \(k-r+1\) estragados, poderia-se escolher esses \(k-r+1\) estragados e completar até \(k\) itens, obtendo um subconjunto de tamanho \(k\) com no máximo \(r-1\) bons, contradizendo a hipótese. Portanto o número total de estragados é ≤ \(k-r\).
Exemplo:
Suponha 20 lâmpadas, e que em qualquer conjunto de \(k=5\) lâmpadas haja pelo menos \(r=2\) funcionando. Então
\(b_{\max}=k-r=5-2=3\)
e o mínimo de funcionando é \(g_{\min}=20-b_{\max}=20-3=17\).
Veja como foi cobrado:
https://flashcardsconcursos.com.br/portal/flashcard/300444
Conteúdo do catálogo FC Concursos · Atualizado em