Flashcard FC628406
Se há n itens, dos quais c são do tipo desejado, quantas retiradas no pior caso garantem pelo menos r desse tipo?
Princípio da Casa dos Pombos
NC UFPR (FUNPAR) · 2019
Se há n itens, dos quais c são do tipo desejado, quantas retiradas no pior caso garantem pelo menos r desse tipo?
Mostrar resposta e comentário
Resposta
No pior caso, retirar (n - c) + r itens.Explicação:
Para garantir r itens de um tipo, considere o pior caso, em que se retiram primeiro todos os itens que não são desse tipo, são n - c, depois ainda é necessário retirar mais r para obter r do tipo, totalizando (n - c) + r.
Se houver dois requisitos para tipos diferentes, calcule cada quantidade necessária e escolha o maior, por exemplo \( \max\{(n-c_A)+r,\,(n-c_B)+s\} \).
Exemplo:
Há 12 meias, 5 azuis e 3 vermelhas, queremos garantir 2 azuis e 2 vermelhas.
Para azuis: \( (12-5)+2 = 9.\)
Para vermelhas: \( (12-3)+2 = 11.\)
Logo, são necessárias 11 retiradas no pior caso para garantir ambos.
Veja como foi cobrado:
https://flashcardsconcursos.com.br/portal/flashcard/626425
Conteúdo do catálogo FC Concursos · Atualizado em