Flashcard FC303339
Se N objetos são distribuídos entre k recipientes, como provar que ao menos um recipiente contém mais que ⌊N/k⌋ objetos?
Princípio da Casa dos Pombos
FGV · 2019
Se N objetos são distribuídos entre k recipientes, como provar que ao menos um recipiente contém mais que ⌊N/k⌋ objetos?
Mostrar resposta e comentário
Resposta
Porque escrevendo \(N = kq + r\) com \(0\le r0\) então \(r\) recipientes têm \(q+1\) itens, logo existe recipiente com mais que \(\lfloor N/k\rfloor=q\).Pelo algoritmo da divisão, existem inteiros \(q\) e \(r\) tais que \(N = kq + r\) e \(0\le rSe \(r=0\), todos os recipientes têm exatamente \(q=\lfloor N/k\rfloor\) itens. Se \(r>0\), as \(r\) unidades restantes obrigam \(r\) recipientes a terem \(q+1\) itens.
Portanto, quando \(r>0\) existe necessariamente pelo menos um recipiente com mais que \(\lfloor N/k\rfloor\).
Exemplo:
Distribuem-se 14 objetos em 4 recipientes: \(14\div4=3\) resto \(2\).
Como \(4\times3=12\), sobram 2 objetos que aumentam 2 recipientes para \(3+1=4\).
Assim, existe recipiente com mais que \(\lfloor14/4\rfloor=3\).
Veja como foi cobrado:
https://flashcardsconcursos.com.br/portal/flashcard/300429
Conteúdo do catálogo FC Concursos · Atualizado em