Flashcard FC303349
Como calcular o número mínimo de retiradas necessárias para **garantir** pelo menos k itens de um tipo usando o princípio da casa dos pombos?
Princípio da Casa dos Pombos
FGV · 2018
Como calcular o número mínimo de retiradas necessárias para **garantir** pelo menos k itens de um tipo usando o princípio da casa dos pombos?
Mostrar resposta e comentário
Resposta
(Resposta): Retirar todas as não-desejadas e mais k.Explicação:
Se o total de itens for \(T\) e a quantidade do tipo desejado for \(M\), no pior caso podem ser retirados primeiro todos os itens que não são do tipo desejado, isto é \(T-M\). Depois disso, só restam itens do tipo desejado, então são necessárias mais \(k\) retiradas para garantir k desse tipo. Assim:
\( \text{mínimo} = (T - M) + k \), desde que \(k \le M\).
Exemplo:
Considere uma caixa com 3 vermelhos, 8 brancos e 6 pretos. Queremos garantir 4 brancos.
Here, \(T=3+8+6=17\), \(M=8\), \(k=4\).
\( \text{mínimo} = (17-8)+4 = 9+4 = 13.\)
Ou seja, no pior caso as primeiras 9 retiradas são todas não-brancas; após isso, mais 4 retiradas garantem 4 brancos.
Veja como foi cobrado:
https://flashcardsconcursos.com.br/portal/flashcard/300439
Conteúdo do catálogo FC Concursos · Atualizado em