Flashcard FC303304
Como fixar um assento e usar restrições de vizinhança para determinar os vizinhos em um arranjo circular?
Orientação no Plano, no Espaço e no Tempo
FGV · 2015
Como fixar um assento e usar restrições de vizinhança para determinar os vizinhos em um arranjo circular?
Mostrar resposta e comentário
Resposta
Fixe uma posição para eliminar a rotação e aplique as restrições de vizinhança para eliminar opções até sobrar a disposição possível.Explicação:
1. Fixar um assento: escolha arbitrariamente uma posição para um elemento (isso elimina simetrias por rotação).
2. Posicionar vizinhos obrigatórios: coloque imediatamente quem deve estar à esquerda/direita desse elemento.
3. Usar restrições de não-vizinho: exclua as cadeiras proibidas para cada elemento e veja se restam posições válidas; repita até obter uma ou nenhuma solução.
exemplo:
Sejam cinco pessoas P, Q, R, S, T com:
- R é vizinho à esquerda de Q
- P não é vizinho de T
- S não é vizinho de Q
Procedimento:
- Fixe Q em uma cadeira.
- Coloque R imediatamente à esquerda de Q.
- Restam 3 cadeiras; como S não pode ser vizinho de Q, S não pode ocupar as cadeiras ao lado de Q, restando duas opções.
- Teste uma opção: se S ocupar uma cadeira que deixa P e T em cadeiras adjacentes, isso viola "P não é vizinho de T". Exclua essa opção.
- Sobrará uma disposição válida única. Ex.: ordem circular (no sentido horário) Q, R, P, S, T, logo os vizinhos de P são R e S.
Veja como foi cobrado:
https://flashcardsconcursos.com.br/portal/flashcard/300394
Conteúdo do catálogo FC Concursos · Atualizado em