Flashcard FC303356
Como determinar o menor número de pessoas em uma mesa circular para que qualquer cadeira vazia tenha ao menos um vizinho ocupado?
Princípio da Casa dos Pombos
FGV · 2016
Como determinar o menor número de pessoas em uma mesa circular para que qualquer cadeira vazia tenha ao menos um vizinho ocupado?
Mostrar resposta e comentário
Resposta
N mínimo = \(\lceil C/3\rceil\), obtido permitindo no máximo blocos de 2 cadeiras vazias entre ocupados.Explicação:
Se houvesse um bloco de 3 cadeiras vazias, a próxima pessoa poderia sentar-se na cadeira do meio sem ter vizinhos, logo o maior bloco vazio permitido é de 2 cadeiras.
Portanto o padrão que minimiza ocupados é repetir 1 ocupada + 2 vazias, período 3, e para C cadeiras o mínimo de pessoas é \(N=\lceil C/3\rceil\).
Exemplo: Para uma mesa com 15 cadeiras: \(N=\lceil 15/3\rceil=\lceil 5\rceil=5\). Assim 5 pessoas, dispostas no padrão 1-0-0-1-0-0..., garantem que qualquer cadeira vazia tenha um vizinho ocupado.
Veja como foi cobrado:
https://flashcardsconcursos.com.br/portal/flashcard/300446
Conteúdo do catálogo FC Concursos · Atualizado em