Flashcard FC303345
Pelo princípio da casa dos pombos, como calcular o número mínimo de retiradas para garantir, no pior caso, ao menos um elemento de um grupo com k ocorrências em um total de N itens
Princípio da Casa dos Pombos
FGV · 2018
Pelo princípio da casa dos pombos, como calcular o número mínimo de retiradas para garantir, no pior caso, ao menos um elemento de um grupo com k ocorrências em um total de N itens?
Mostrar resposta e comentário
Resposta
Retire \( (N-k)+1 \) itens — todos os não desejados mais um.Pelo princípio da casa dos pombos, no pior caso removem-se todos os itens que não pertencem ao grupo alvo, que somam \(N-k\).
Assim, a retirada seguinte será necessariamente do grupo alvo, totalizando \( (N-k)+1 \).
Exemplo:
Suponha 8 bolas: 5 vermelhas, 2 azuis e 1 verde. Para garantir ao menos uma vermelha, primeiro retire todos os não-vermelhos: \(2+1=3\).
Depois retire mais uma: \(3+1=4\).
Cálculo: \( (N-k)+1=(8-5)+1=4\).
Veja como foi cobrado:
https://flashcardsconcursos.com.br/portal/flashcard/300435
Conteúdo do catálogo FC Concursos · Atualizado em