Flashcard FC368426
Se N objetos são distribuídos entre k compartimentos, qual o número mínimo que necessariamente estará em algum compartimento?
Princípio da Casa dos Pombos
Instituto Consulplan · 2024
Se N objetos são distribuídos entre k compartimentos, qual o número mínimo que necessariamente estará em algum compartimento?
Mostrar resposta e comentário
Resposta
Ao menos \( \lceil N/k \rceil\) itens.Explicação:
Suponha, por contradição, que nenhum compartimento tenha ≥ \( \lceil N/k\rceil\); então cada um teria no máximo \( \lceil N/k\rceil-1\).
Assim o total seria ≤ \(k\cdot(\lceil N/k\rceil-1)
Exemplo:
Distribuem-se 23 cartas em 6 caixas.
Fazendo \(23\div6\) obtém-se quociente 3 e resto 5, ou seja \(23=6\cdot3+5\).
Se cada caixa tivesse 3 cartas sobrariam 5 cartas que aumentam 5 caixas para 4 cartas.
Logo, necessariamente, existe ao menos uma caixa com 4 cartas, conforme \( \lceil 23/6\rceil=4\).
Veja como foi cobrado:
https://flashcardsconcursos.com.br/portal/flashcard/365038
Conteúdo do catálogo FC Concursos · Atualizado em