Calculo do Número de Caminhos

[petras]

1- No diagrama abaixo calcule de quantas formas é possível mover o boneco da posição A até a posição B, andando sempre um quarteirão por vez, apenas para o norte ou para o leste. (R: 784)

Anexos

Sem título.png (25.41 KiB) Visualizado 1179 vezes

[3,14159265]

Fala, cara! Beleza? Vou tentar explicar aqui, espero que você entenda:

Se não tivesse aquele retângulo, do ponto A para o ponto B seriam 6 quarteirões para o L e 6 quarteirões para o N, ou seja: LLLLLLNNNNNN. De quantas formas eu posso arranjar essas letras? De 12!/(6!*6!) = 924 formas.

Tá, mas eu tenho aquele retângulo ali, e agora? Bom, agora você precisa subtrair desses 924 caminhos todos em que eu passaria pelo meio do retângulo, pois esse caminho está bloqueado.

Concorda que pra chegar ali no meio do retângulo eu tenho que andar 3 quarteirões pro leste e 4 para o norte? Só se eu passar por aquele ponto que o retângulo vai fazer alguma diferença na minha vida. Ele não influencia se os meus 7 primeiros quarteirões não forem permutações de LLLNNNN. E de quantas formas eu posso chegar lá? Seriam 7!/(4!*3!) = 35 formas. Certo, mas não acabou aí. Depois que eu cheguei lá, qual é o caminho que eu NÃO POSSO FAZER? Eu não posso andar pro NORTE! Então como ficaria?

LLLNNNNNNLLL

Já calculei que eu tenho 35 formas de chegar lá e o N na oitava posição é fixo porque eu quero passar por onde eu não poderia. Agora eu tenho que saber de quantas formas eu posso seguir o meu caminho depois de ter passado pelo meio do retângulo. De quantas formas eu posso permutar as letras em azul? De 4!/(3!*1!) = 6 formas. Então, no final das contas, naqueles 924 caminhos iniciais, 35*6 = 140 não podem ser feitos, pois eles passariam pelo meio do retângulo. Já temos nossa resposta: 924-140 = 784.

[petras]

Grato 3,14.