Exercício Resolvido - Caminhos: Análise combinatória: Vestibular UERJ 2011

Cálculo do número de caminhos mínimos entre dois pontos

Uma rede é formada de triângulos equiláteros congruentes, conforme a representação abaixo.

Uma formiga se desloca do ponto A para o ponto B sobre os lados dos triângulos, percorrendo
X caminhos distintos, cujos comprimentos totais são todos iguais a d.

Sabendo que d corresponde ao menor valor possível para os comprimentos desses caminhos, X
equivale a:
(A) 20
(B) 15
(C) 12
(D) 10

Solução:

Para saber quantos caminhos de menor comprimento são possíveis, devemos percorrer, inicialmente, um dos menores caminhos. Seja ele o caminho partindo de A, andando 4 linhas na horizontal e 2 na diagonal até chegar em B:

Neste caso, podemos dizer que a formiga percorreu o caminho HHHHDD, já que foi quatro vezes para a esquerda na horizontal, e duas vezes para cima na direção diagonal.
Assim, para saber quantos caminho de comprimento igual a esse basta calcular o número de formas de combinar as quatro letras H e as duas D para formar "palavras" diferentes, ou seja, devemos calcular o número de anagramas possíveis de serem formados com HHHHDD.
Supondo que todas as seis letras sejam diferentes, podemos dizer que é possível "embaralhá-las" de K formas distintas, onde:

K = 6*5*4*3*2*1 = 6! = 720

Porém, temos quatro letras H e duas D. Com isso num mesmo anagrama ao trocarmos dois H's de lugar, o anagrama segue o mesmo. Por exemplo, seja a palavra HDHDHH. Ao trocar o último H com o primeiro H, a palavra continua sendo exatamente a mesma e como são quatro letras H's que temos, existem 4*3*2*1 = 4! combinações de H's possíveis para cada palavra. O mesmo com a letra D, que possui duas iguais, neste caso teremos 2*1 = 2! combinações. Assim, o número de caminhos diferentes será:

Neste caso são 15 caminhos de comprimento mínimo possíveis. Resposta (B)