Flashcard FC368450
Qual o número máximo de dias que se pode escolher sem ter dias consecutivos em um ciclo de m dias disponíveis (considerando domingo↔segunda como consecutivos)?
Exercícios Envolvendo Datas e Calendários
Instituto Consulplan · 2024
Qual o número máximo de dias que se pode escolher sem ter dias consecutivos em um ciclo de m dias disponíveis (considerando domingo↔segunda como consecutivos)?
Mostrar resposta e comentário
Resposta
O máximo é ⌊m/2⌋.Num ciclo os dias formam uma sequência circular; escolher dias sem consecutividade equivale a selecionar vértices sem arestas adjacentes. O tamanho máximo desse conjunto independente num ciclo com m vértices é \(\lfloor m/2\rfloor\).
Se m é par, máximo = \(m/2\). Se m é ímpar, máximo = \((m-1)/2\).
Exemplo:
Se m = 5 disponíveis então \(\lfloor5/2\rfloor = 2\). Não é possível escolher 3 dias sem que dois fiquem consecutivos num ciclo de 5.
Se m = 6 então \(\lfloor6/2\rfloor = 3\); uma escolha válida é dias 1, 3 e 5.
Veja como foi cobrado:
https://flashcardsconcursos.com.br/portal/flashcard/365062
Conteúdo do catálogo FC Concursos · Atualizado em