Exercício Resolvido - Análise combinatória: Quantos caminhos de comprimento mínimo de A até B

A figura abaixo representa um mapa de uma cidade, na qual há 7 avenidas na direção norte-sul e 6 avenidas na direção leste-oeste.

a) Quantos são os trajetos de comprimento mínimo ligando o ponto A ao ponto B?

b) Quantos desses trajetos passam por C?

Solução:

Comentário breve sobre a questão: Exercícios desse tipo são resolvidos da mesma forma que anagramas pois saindo de A para chegar em B temos vários caminhos de comprimento mínimo, porém todos eles andam somente para cima e para a direita. Não faz sentido em algum momento, andar para baixo ou para a esquerda, pois dessa forma não vamos percorrer o caminho mais curto para chegar em B.

Se fosse o contrário, de B para A, andaríamos apenas para baixo e para a esquerda.

Assim, em cada ponto do mapa, temos duas opções, ir para cima (C) ou para a direita (D).

Ao exercício:
a) Devemos fazer um caminho qualquer. Para facilitar, vou fazer o caminho pela borda, partindo do ponto A vou andar: DDDDDDCCCCC.
Pronto, agora calculamos o anagrama destas letra e descobrimos quantos caminhos mínimos temos:
= 11! / (6! * 5!) = (11*10*9*8*7) / 5*4*3*2*1 = 11*3*2*7 = 462 caminhos

b)Para fazer este exercício, o raciocínio é o mesmo, porém calculamos quantos caminhos temos de A até C, depois de C até B e multiplicamos:
de A até C:
DDDDCCCC -> 8! / (4! * 4!) = 8*7*6*5 / 4*3*2*1 = 7*2*5 = 70
de C até B:
DDC -> 3! / (2! * 1!) = 3

70*3 = 210 caminhos