Um robô se move em um plano cartesiano. Ele precisa ir da origem ( 0,0 ) até o ponto
dando apenas passos unitários para a direita ou para cima. Quantos caminhos diferentes ele pode fazer?
Passo 1
O enunciado dá as seguintes informações e pede uma única coisa:
- O robô parte do ponto
. - O destino é o ponto
. - O robô só pode dar passos unitários para a direita (vou chamar de
) ou para cima (vou chamar de ). - Pergunta: Quantos caminhos diferentes o robô pode fazer obedecendo essas regras?
Passo 2
Entendendo o que cada caminho é, de forma bem concreta.
- Para ir de
até usando somente passos unitários para a direita, o robô precisa dar exatamente passos do tipo . - Para ir de
até usando somente passos unitários para cima, o robô precisa dar exatamente passos do tipo . - Ou seja, qualquer caminho válido é uma sequência de exatamente
letras e letras , totalizando passos.
Exemplo pequeno para visualizar: para ir até
há duas sequências possíveis de passos de comprimento
:
e
. Isso mostra a ideia: caminhos correspondem a arranjos das letras
e
.
Passo 3
Transformando o problema em contagem de arranjos (combinações).
- Temos
posições para preencher com passos. - Precisamos escolher em quais
dessas posições vão ficar os passos (ou equivalentemente escolher as posições dos ). - O número de maneiras de escolher
posições entre é um coeficiente binomial, escrito . - Portanto o número de caminhos é
(igual a ).
Passo 4
Apresentando a fórmula e explicando cada símbolo.
- A fórmula do coeficiente binomial é
- Aqui
(lê-se “n fatorial”) é o produto . - As variáveis significam:
-
= número total de posições (aqui ); -
= número de posições que escolhemos para um dos tipos de passo (aqui para os , ou para os ).
-
- Substituindo no nosso caso:
Passo 5
Calcular
de modo prático, sem calcular fatorial completo.
- Podemos escrever o numerador de forma parcial:
- Mas é mais simples cancelar antes de multiplicar. Observe que
porque os fatores
do
cancelam parte do
.
- Agora simplificamos frações com cancelamento:
-
no numerador dividido por no denominador dá . -
no numerador dividido por no denominador dá . - Ainda resta o
no denominador que podemos cancelar com esse obtido (ou ver diretamente).
-
- Fazendo as contas resultantes:
Passo 6
Interpretação final e checagem rápida.
- Também podia-se calcular
e obter o mesmo resultado . - Teste mental pequeno: para
(um passo e dois ) teríamos caminhos, que bate com a listagem . A lógica é a mesma aqui, só com números maiores.
Passo 7
Mensagem rápida de incentivo (você tá indo bem!).
- Problemas de caminhos em grade são sempre transformar o percurso em permutações da sequência de passos e contar quantas sequências distintas existem.
- Com prática, isso vira automático na prova: some os deslocamentos nas direções independentes e use o coeficiente binomial.