Questão de Raciocínio Lógico · FGV PC-SC 2024 (nº 13)

Um passeio em um grafo é uma sequência de cidades (vértices) conectadas por caminhos (arestas). O tamanho do passeio é o número de caminhos percorridos. Quando o problema diz que "nada impede que um passeio passe mais de uma vez por uma mesma cidade", significa que podemos revisitar cidades e caminhos.

Para encontrar a quantidade de passeios de tamanho 3 que começam em $C_1$ e terminam em $C_4$, precisamos listar todas as sequências de 4 cidades ($C_1 \to X \to Y \to C_4$) onde cada par consecutivo de cidades é conectado por um caminho.

As conexões entre as cidades são:

• $C_1 \leftrightarrow C_2$
• $C_1 \leftrightarrow C_3$
• $C_1 \leftrightarrow C_4$
• $C_2 \leftrightarrow C_3$
• $C_3 \leftrightarrow C_4$
• Não há conexão entre $C_2$ e $C_4$.

Vamos listar os passeios passo a passo, começando em $C_1$ e terminando em $C_4$ após 3 caminhos:

1. Primeiro passo: $C_1 \to C_2$

   • Segundo passo: $C_2 \to C_1$
     • Terceiro passo: $C_1 \to C_4$
     • Passeio: $C_1 \to C_2 \to C_1 \to C_4$
   • Segundo passo: $C_2 \to C_3$
     • Terceiro passo: $C_3 \to C_4$
     • Passeio: C_1 \to C_2 \to C_3 \to C_4\

2. Primeiro passo: $C_1 \to C_3$

   • Segundo passo: $C_3 \to C_1$
     • Terceiro passo: $C_1 \to C_4$
     • Passeio: $C_1 \to C_3 \to C_1 \to C_4$
   • Segundo passo: $C_3 \to C_2$
     • Terceiro passo: De $C_2$, as únicas opções são $C_1$ ou $C_3$. Nenhuma delas é $C_4$, e não há caminho direto $C_2 \leftrightarrow C_4$. Portanto, este ramo não leva a $C_4$.
   • Segundo passo: $C_3 \to C_4$
     • Terceiro passo: De $C_4$, as únicas opções são $C_1$ ou $C_3$. Nenhuma delas é $C_4$. Como o passeio deve ter tamanho 3 e terminar em $C_4$, se já chegamos em $C_4$ no segundo passo, o terceiro passo nos levaria para fora de $C_4$. Portanto, este ramo não leva a um passeio de tamanho 3 que termina em $C_4$.

3. Primeiro passo: $C_1 \to C_4$

   • Segundo passo: $C_4 \to C_1$
     • Terceiro passo: $C_1 \to C_4$
     • Passeio: $C_1 \to C_4 \to C_1 \to C_4$
   • Segundo passo: $C_4 \to C_3$
     • Terceiro passo: $C_3 \to C_4$
     • Passeio: $C_1 \to C_4 \to C_3 \to C_4$

Contando os passeios distintos encontrados:

1. C_1 \to C_2 \to C_1 \to C_4\
2. C_1 \to C_2 \to C_3 \to C_4\
3. C_1 \to C_3 \to C_1 \to C_4\
4. C_1 \to C_4 \to C_1 \to C_4\
5. $C_1 \to C_4 \to C_3 \to C_4$

Ao todo, são 5 passeios distintos.

Comentário das alternativas:

• (A) Incorreta: Esta alternativa seria o resultado se alguns passeios fossem desconsiderados, talvez por uma interpretação errônea de que cidades não podem ser revisitadas, ou por um erro de contagem.
• (B) Incorreta: Semelhante à alternativa A, indica uma contagem incompleta dos passeios possíveis.
• (C) Correta: A contagem sistemática de todos os passeios de tamanho 3, considerando as conexões do grafo e a permissão de revisitar cidades, resulta em 5 passeios distintos.
• (D) Incorreta: Esta alternativa pode ser um distrator para quem comete um pequeno erro de cálculo ou inclui um passeio inválido (como $C_1 \to C_3 \to C_2 \to C_4$, que não é possível devido à ausência de conexão entre $C_2$ e $C_4$).
• (E) Incorreta: Semelhante à alternativa D, indica um erro de contagem ou a inclusão de passeios inválidos.