Combinatória

De quantas maneiras podemos ir de A até B sobre a seguinte grade sem passar duas vezes pelo mesmo local e
sem mover-se para a esquerda? A figura abaixo mostra um caminho possível.


Gab.: 7 776

Em cada coluna que passamos, decidiremos quantas casas subiremos ou desceremos (pode ser zero) e depois andamos uma casa para a direita:

 1) Se estamos na linha 1 (topo), podemos descer 1, 2, 3, 4 ou 5 casas ou ficar parados (6 opções)
 2) Se estamos na linha 2, podemos descer 1, 2, 3 ou 4 casas, subir 1 casa ou ficar parados (6 opções)
 3) Se estamos na linha 3, podemos descer 1, 2 ou 3 casas, subir 1 ou 2 casas ou ficar parados (6 opções)
 4) Se estamos na linha 4, podemos descer 1 ou 2 casas, subir 1, 2 ou 3 casas ou ficar parados (6 opções)
 5) Se estamos na linha 5, podemos descer 1 casa, subir 1, 2, 3 ou 4 casas ou ficar parados (6 opções)
 6) Se estamos na linha 6, podemos subir 1, 2, 3, 4 ou 5 casas ou ficar parados (6 opções)

Note que tomaremos essa decisão 5 vezes (uma por coluna). Ao chegarmos à última coluna, já estará definido o número de casas que subiremos para chegar ao local, então não deveremos decidir.

Portanto, temos 6^5 = 7776 caminhos.

Olá, agradeço pela resposta.

Ao ler seu texto, tive algumas perguntas (algumas quase que retóricas, mas postarei para cessar qualquer resquício de dúvida).


1) O que te levas a afirmar que "depois andamos uma casa para a direita" é o fato de que, independente do caminho escolhido, sempre será preciso andar 5 casas para à direita, correto?

2) Não entendi por que você considerou o topo como ponto de partida. Pela figura mostrada na questão, apesar de não mostrar explicitamente a posição de A e B, acredito que o ponto A está na base da linha 1. Não acho que isso mude muita coisa, no entanto, não vi benefício ou afim;

3) Ademais, quando vi essa questão pela primeira vez, tentei por permutação, no entanto, não obtive êxito. Nesse caso não seria possível porque existem alguns caminhos maiores e outros menores, certo?

Mais uma vez, obrigada.

1) Correto. Como não é possível andar para a esquerda, em todos os caminhos andaremos 5 casas para a direita.

 2) Não considerei o topo o ponto de partida. Apenas quis mostrar que, independentemente de que linha estamos, sempre teremos 6 opções. Começamos da última linha, e temos 6 opções antes de quantas casas subir antes de andar para a direita. Na próxima coluna, independentemente de quantas casas subimos antes, teremos outras 6 opções (o número de opções em cada coluna independe da linha em que estamos, ou seja, da decisão tomada na coluna anterior).

 3) Correto, os caminhos têm tamanhos diferentes. Além disso, torna-se difícil resolver o problema por permutação pois não podemos passar duas vezes pelo mesmo local. Logo, em uma mesma coluna, ou subimos um número de casas, ou descemos, mas não os dois.

Espero que tenha ficado mais claro.

Ficou sim. Obrigada pela disponibilidade e pelos detalhes nas explicações!  

Outra solução:

São 5 linhas e 5 colunas

a) Para pontos na linha vertical externa direita existe apenas 1 possibilidade: para cima

b) Para pontos na linha vertical externa esquerda existem 2 possibilidades: para cima e para a direita

c) Para pontos na linha horizontal superior existem 2 possibilidades: para a direita e para baixo.

d) Para pontos na linha horizontal inferior existem 2 possibilidades: para a direita e para cima.

e) Para pontos nas linhas internas existem 3 possibilidades: cima, baixo, direita.

Solução: n = 2⁵.3⁵ ---> n = 7776 ou n = 2 776

Ada Augusta:

Pela legislação brasileira não é permitido usar ponto (.) como separador decimal [o correto é virgula (,)], nem para separar grupos de três algarismos (a única exceção é para quantias de dinheiro: R$2.776,00)

Ou se escrevem todos os algarismos juntos ou de deixa um espaço.

Assim existe um erro no seu gabarito 2.776 ---> o correto é 2776 ou 2 776

Obrigada pela solução alternativa, Elcio.


Sobre a sua observação final, editei a resposta. Não sabia que o ponto era considerado errado no Brasil. Valeu pela informação!

O ponto para separar grupos de três algarismos é proibido pelo SI, logo vale para todos os países que adotam o SI, inclusive o Brasil.