XXVI Olimpíada Brasileira de Informática

Dona Minhoca

Dona Minhoca construiu quatro túneis -- Q, R, S e T -- embaixo da terra, ligando os quadro cômodos -- A, B, C e D -- da sua residência. Cada tunel tem exatamente o mesmo comprimento e conecta exatamente dois cômodos diferentes, da seguinte forma:

  • Q conecta A e C
  • R conecta B e C
  • S conecta A e B
  • T conecta B e D

Questão 1. Qual das seguintes alternativas é uma ordem correta de cômodos num passeio em que Dona Minhoca visita todos os cômodos de sua residência, partindo do cômodo A, usando apenas os túneis e nunca usando um túnel mais de uma vez?
A, B, C, D
A, C, B, D
A, C, D, B
A, D, B, C
A, D, C, B

Questão 2. Se Dona Minhoca está no cômodo D e deseja ir para o cômodo C por uma sequência de túneis que não é mais longa do que o necessário, quantos túneis ela deve percorrer?
1
2
3
4
5

Questão 3. Se Dona Minhoca quer passear pelos cômodos da sua residência usando apenas túneis, qualquer das alternativas seguintes é uma sequência possível de túneis que ela pode usar EXCETO
R, Q, S, R, Q
S, T, T, R, Q
T, R, R, T, T
Q, S, R, T, S
T, S, Q, R, T

Questão 4. Se num passeio pelos cômodos Dona Minhoca percorre o comprimento inteiro de cada túnel exatamente uma vez, qual seguintes alternativas é uma lista completa e correta dos cômodos que ela visita duas vezes?
B
A, B
B, C
B, D
B, C, D

Tarefas Iniciação Nível 1
Promoção
logo sbc
Patrocínio
Apoio
Coordenação