28a Olimpíada Brasileira de Informática

Condomínio colorido

Um condomínio composto por exatamente seis casas, R, S, W, X, Y e Z, decidiu pintar todas as casas, com a condição de que casas vizinhas não podem ter a mesma cor. As únicas casas vizinhas são as seguintes:

  • R, S, X e Y são vizinhas de W.
  • X é vizinha de Y.
  • R e S são vizinhas de Z.

Questão 1. Qual dos seguintes pares são casas que devem ter cores diferentes uma da outra?

Questão 2. Se X tem a mesma cor de Z, então qual das seguintes afirmações é necessariamente verdadeira?

Questão 3. Qual dos seguintes pares de casas podem ter a mesma cor?

Questão 4. Qual das seguintes casas pode ter a mesma cor que W?

Questão 5. Se o menor número de cores possível é usado, e uma das casas é a única que é pintada de uma determinada cor, essa casa pode ser:

IJ I1 I2
Tarefas Iniciação Nível 2
Promoção
logo sbc
Patrocínio
Apoio
Coordenação