Flashcard FC452446
Se há k categorias distintas, quantos itens são necessários no mínimo para garantir que pelo menos dois pertençam à mesma categoria?
Princípio da Casa dos Pombos
Instituto Verbena · 2024
Se há k categorias distintas, quantos itens são necessários no mínimo para garantir que pelo menos dois pertençam à mesma categoria?
Mostrar resposta e comentário
Resposta
k+1Explicação:
Na pior situação retiramos um item de cada categoria, totalizando k itens sem repetição, então a próxima retirada não pode criar uma nova categoria, obrigando uma repetição.
Formalmente, com k "caixas" e itens distribuídos, ao inserir \(k+1\) itens, alguma caixa conterá pelo menos 2 itens, logo é necessário \(k+1\).
Exemplo:
Em uma gaveta há meias de 4 cores diferentes, para garantir duas meias da mesma cor, use \(k=4\).
Calcula-se \(k+1 = 4+1 = 5\).
Assim, ao retirar 5 meias, necessariamente haverá pelo menos duas da mesma cor.
Veja como foi cobrado:
https://flashcardsconcursos.com.br/portal/flashcard/451178
Conteúdo do catálogo FC Concursos · Atualizado em