Considere 4 cidades distintas C1, C2, C3 e C4. Entre quaisquer duas dessas cidades, há um único caminho que as conecta, exceto entre as cidades C2 e C4, entre as quais não há caminho. Assim, ao todo, são 5 caminhos: um que conecta C1 e C2, um que conecta C1 e C3, um que conecta C1 e C4, um que conecta C2 e C3 e um que conecta C3 e C4. Utilizando-se apenas esses caminhos, é possível fazer um passeio que começa e termina em uma dessas 4 cidades. Nada impede que um passeio passe mais de uma vez por uma mesma cidade. O tamanho do passeio é dado pelo número de caminhos percorridos desde a cidade de origem até a cidade de destino. A quantidade de passeios distintos de tamanho 3 que começam na cidade C1 e terminam na cidade C4 é
- A)3.
Errada, porque há mais de 3 passeios possíveis de tamanho 3 entre C1 e C4.
- B)4.
Errada, porque a contagem correta ainda passa de 4 quando você lista todos os trajetos possíveis.
- C)5.
Certa, pois existem 5 sequências distintas de 3 caminhos ligando C1 a C4.
- D)6.
Errada, porque ela superestima a quantidade; o total não chega a 6.
- E)7.
Errada, porque também superestima a quantidade; a contagem correta é 5, não 7.
Gabarito: C
Aqui a ideia é contagem de passeios, ou seja, sequências de cidades ligadas por caminhos, permitindo repetir cidade. Como o tamanho do passeio é 3, você precisa contar as sequências com 3 deslocamentos que saem de C1 e chegam em C4. As ligações possíveis são: C1 com C2, C3 e C4; C2 com C1 e C3; C3 com C1, C2 e C4; e C4 com C1 e C3. Então basta montar os trajetos de 3 passos que comecem em C1 e terminem em C4. Vamos listar: C1-C2-C1-C4, C1-C2-C3-C4, C1-C3-C1-C4, C1-C4-C1-C4 e C1-C4-C3-C4. São 5 passeios distintos. Repare que o problema não pede caminho simples nem sem repetição, então repetir cidade é permitido e entra na conta. Logo, a resposta correta é a alternativa C. Em questões de contagem da FGV, vale ficar atento a essa diferença: passeio pode repetir vértices, e isso aumenta bastante o número de possibilidades.