Para ir de sua casa à empresa FKH, local onde trabalha, João possui algumas opções de trajetos apresentadas no diagrama a seguir. Considere que, para fazer o trajeto, João só possa caminhar nos sentidos ^, < e >, sem passar pelo mesmo lugar mais de uma vez. A figura mostra um possível trajeto para João:
Imagem em anexo
Considerando-se as informações e a figura, o número de trajetos possíveis para João ir de casa ao trabalho é:
A resposta é 125, mas Pq?
Soluções para a tarefa
Resultado:
Motivação:
Veja bem, vou tentar dar uma explicação um pouco mais detalhada para poder mostrar como cheguei na formulação que fornece o resultado. Você pode pular para o resumo ao final se não quiser investir seu tempo nisso.
Esse é um problema de Análise Combinatória de um dos tipos mais difíceis na minha opinião. Além de ter uma característica geométrica na qual você tem que enxergar um padrão, os padrões são variáveis, isto é, você consegue chegar ao destino com quantidades variáveis de movimentos. Em problemas mais simples, você consegue saber exatamente quais movimentos são necessários e basta fazer uma permutação com elementos repetidos para encontrar a quantidade de caminhos. Neste problema isso não é possível.
Se você está com tempo de sobra, está agarrado nesse tipo questão e quer muito resolvê-la, eu sugiro sempre você começar com uma abordagem em grafo:
- Comece do seu ponte de partida como um nó
- Para cada opção que você tiver, desça uma aresta desse nó pai e chegue em nó filho
- Repita os passos 1 e 2 iterativamente
Assim, você vai conseguir esboçar a evolução do problema a medida em que você realiza os passos e uma de duas coisas vai acontecer: (i) Você vai enxergar o padrão em que esse problema se encontra e visualizar as escolhas possíveis de se fazer, encontrando uma forma fechada para a resposta; (ii) Você vai chegar a solução de forma exaustiva, nesse caso, chegaria à 125 nós no final do seu grafo.
Eu comecei assim e isso me ajudou a encontrar a fórmula fechada para a resposta.
Eu estou contando toda historinha porque a seguir vou explicar como se dá a solução fechada que encontrei, provavelmente você vai entender, mas vai saber encontrar um novo padrão em uma questão do mesmo tipo? Esse é o pulo do gato. Uma vez entendido as escolhas possíveis e quais operações a se fazer, fica fácil. O difícil está em encontrá-las.
Explicação da Solução
Imagine que você está no seu ponto de partida. Em qualquer trajetória que escolher, você usará exatamente três movimentos para cima. Independente de quantos movimentos laterais. Isso porque você não se move para baixo e muito menos passa pelo menos lugar mais de uma vez.
Dito isso, você pode escolher o que fazer entre estes movimentos superiores. Do ponto de partida, você tem cinco escolhas possíveis de movimentos laterais a se fazer antes de você ir para a rua horizontal de cima (se mover para cima):
- Não se mover lateralmente
- Mover-se lateralmente para a esquerda uma vez
- Mover-se lateralmente para a esquerda duas vezes
- Mover-se lateralmente para a direita uma vez
- Mover-se lateralmente para a direita duas vezes
Isso porque você não pode ir para a direita e para a esquerda na mesma linha (rua horizontal), dado que você não passa pelo mesmo lugar duas vezes.
Feita a sua escolha, uma dentre cinco, você obrigatoriamente terá que se mover para cima. Chegando a nova rua horizontal, você tem mais cinco opções de movimentos laterais antes de se mover para cima novamente.
Note que quais serão essas novas cinco opções dependerá diretamente de qual foi a sua escolha anterior, mas independe dela sempre serão novas cinco opções.
Ao escolher uma dentre cinco opções pela segunda vez, você estará na terceira rua horizontal. E o último caso se repetirá.
Fazendo a sua terceira escolha, novamente uma dentre cinco, você estará em algum ponto da quarta e última rua horizontal. Uma vez nesta rua, você não tem mais escolha, ou você chegou ao destino ou terá que fazer movimentos laterais já determinados para chegar ao local.
Resumo
Então é o seguinte:
- Primeira linha você tem cinco opções de movimentos laterais antes de se mover para cima para a segunda linha
- Uma vez na segunda linha, você tem mais cinco opções de movimento antes de se mover para a terceira linha
- Uma vez na terceira linha, você tem mais cinco opções de movimento antes de se mover para a quarta linha
- Uma vez na quarta linha, você não tem mais opções e deve ir para o destino
- Finalmente:
O número total de trajetos que João pode executar é de 125 movimentos.
Para resolvermos essa questão, devemos aprender o que é o Princípio Fundamental da Contagem.
O PFC determina que quando um evento é formado por mais de uma etapa, e as etapas são independentes, o número total de combinações possíveis é obtido através da multiplicação das combinações de cada etapa.
Com isso, observando o caso de João, temos que para ele ir de sua casa até a empresa, ele deve passar por 3 níveis diferentes quadras, sendo que em cada nível ele pode se mover para a direita, para a esquerda, e deve se mover para o próximo nível.
Entretanto, como não pode passar pelo mesmo local mais de uma vez, temos que em cada nível ele pode percorrer no máximo 1 + 1 (2 movimentos para a esquerda) + 1 + 1 (2 movimentos para a direita) + 1 (1 movimento para cima) = 5 movimentos.
Assim, como existem 3 níveis, temos que o número total de trajetos que João pode executar é de 5 x 5 x 5 = 125 movimentos.
Para aprender mais, acesse
https://brainly.com.br/tarefa/12945243
brainly.com.br/tarefa/17856621
