Questão 6. Seja n um inteiro positivo. Uma formiga está inicialmente no ponto (0,0) do plano cartesiano, e deseja chegar no ponto ( n, n ). A cada passo, a formiga pode sair do ponto ( x, y ) para um dentre os três seguintes pontos: (x+1, y+1),(x+1, y-1) ou (x-1, y+1). Sabendo que a formiga nunca passa por um mesmo ponto mais de uma vez e que ela nunca sai do primeiro quadrante Q=\{(x, y) \mid x \geq 0, y \geq 0\}, de quantas formas ela pode realizar seu objetivo?

Passo 1

O enunciado pede: contar de quantas formas a formiga, partindo de (0,0), chega a (n,n) usando apenas os passos
(1,1),\quad (1,-1),\quad (-1,1),
sem sair do primeiro quadrante Q=\{(x,y)\mid x\ge0,\\ y\ge0\} e sem passar por um mesmo ponto mais de uma vez.
Informações importantes dadas pelo enunciado:
  • O destino é (n,n).
  • Cada passo é uma das três vetores acima.
  • A formiga nunca sai do primeiro quadrante.
  • A formiga não repete pontos (nenhum vértice do caminho é percorrido duas vezes).
  • n é um inteiro positivo (fixo).
Vou transformar essa informação em quantidades que podemos contar.

Passo 2

Contagem das ocorrências de cada tipo de passo.
Denotemos por
U=\text{número de passos }(1,1),ú
D=\text{número de passos }(1,-1),ú
L=\text{número de passos }(-1,1).ú
A variação total de x ao final é
\Delta x = U + D - L.
Como a formiga sai de x=0 e chega em x=n, temos
U + D - L = n. \tag{1}
A variação total de y ao final é
\Delta y = U - D + L.
Como sai de y=0 e chega em y=n, temos
U - D + L = n. \tag{2}
Somando (1) e (2) obtemos
2U = 2n \quad\Rightarrow\quad U = n.
Subtraindo (2) de (1) dá
2D - 2L = 0 \quad\Rightarrow\quad D = L.
Portanto, toda trajetória que chega a (n,n) deve conter exatamente U=n passos do tipo (1,1) e um número igual D=L=k (algum k\ge0) de passos (1,-1) e (-1,1).
Assim o comprimento total do caminho é n + 2k. Essa informação já reduz muito o problema: sabemos quantos de cada tipo ocorrem, resta contar as ordens possíveis e as restrições de quadrante e de não-repetição.

Passo 3

Mudança de variáveis para simplificar as restrições.
É conveniente trabalhar com as grandezas
p = x+y,\qquad q = x-y.
Observe como os passos atuam nessas variáveis:
  • Para (1,1): (p,q)\mapsto(p+2,q).
  • Para (1,-1): (p,q)\mapsto(p,q+2).
  • Para (-1,1): (p,q)\mapsto(p,q-2).
O ponto inicial (0,0) corresponde a (p,q)=(0,0). O destino (n,n) corresponde a (p,q)=(2n,0).
Duas observações úteis:
  1. Apenas os passos U=(1,1) aumentam p (em +2). Para alcançar p=2n a partir de p=0 é necessário exatamente n passos U (coerente com U=n acima).
  2. Os passos D e L não modificam p; eles apenas alteram q por +2 ou -2. O valor q deve estar sempre tal que |q|\le p porque
x=\frac{p+q}{2}\ge0,\qquad y=\frac{p-q}{2}\ge0
equivalem a |q|\le p.
Portanto o movimento organiza-se por “níveis” de p: o passo U leva a um novo nível (p aumenta em 2), enquanto entre dois passos U podemos fazer uma sequência de passos D e L que faz oscilar q mantendo p fixo. Começamos em p=0, obrigatoriamente o primeiro passo tem de ser U (se fizesse D ou L violaria |q|\le p em p=0). Do mesmo modo, o último passo também tem de ser um U, porque só um U aumenta p até 2n — e, se já tivéssemos alcançado p=2n antes do final, não haveria como voltar a (2n,0) sem mais Us.

Passo 4

Representação por sequência de níveis: definição das variáveis-chave.
Chame de r_i o valor de \dfrac{q}{2} = \dfrac{x-y}{2} imediatamente após o i-ésimo passo U. Mais precisamente:
  • Antes de qualquer U temos p=0,q=0.
  • Após o primeiro U (quando p=2) chamamos esse valor de r_1.
  • Após o segundo U (quando p=4) chamamos r_2.
  • Após o n-ésimo U (quando p=2n) chamamos r_n.
Pelo que foi dito, r_0=0 (antes de qualquer U) e r_n=0 (pois no alvo q=0). Os passos entre o i-ésimo U e o (i+1)-ésimo U (ou seja, no nível p=2i) mudam \dfrac{q}{2} em incrementos +1 (cada D) ou -1 (cada L). Como não permitimos revisitar pontos, dentro de um mesmo nível (mesmo p) a sequência de passos deve mover \dfrac{q}{2} sempre numa direção (pois se misturarmos sinais inevitavelmente voltamos a um valor de q já visitado naquele nível). Assim, entre U_i e U_{i+1} o valor \dfrac{q}{2} sofre um deslocamento inteiro \Delta_i que é ou não-negativo (somente +1 repetido) ou não-positivo (somente -1 repetido). Em símbolos:
r_{i+1}=r_i + \Delta_i,\qquad \Delta_i\in\mathbb{Z},\quad |\Delta_i|\le i,
porque no nível p=2i o máximo que \dfrac{q}{2} pode variar sem sair da condição |q|\le p é i unidades (cada unidade corresponde a duas unidades de q). Além disso, como r_0=0 e r_n=0, os \Delta_i satisfazem
\sum_{i=1}^{n-1}\Delta_i = 0.
Resumo dos limites:
  • Para cada i=1,2,\dots,n-1: r_i é inteiro e |r_i|\le i.
  • A cada passo entre os U's o incremento \Delta_i = r_{i+1}-r_i satisfaz |\Delta_i|\le i e é todo do mesmo sinal (isto garante que não há revisita no mesmo nível).
Portanto existe uma bijeção entre caminhos válidos da formiga e sequências inteiras (r_1,r_2,\dots,r_{n-1}) tais que
r_0=0,\quad r_n=0,\quad r_{i+1}-r_i\in\{-i,\,-i+1,\dots,0,\dots,i-1,i\}
e tais que, para cada i, a mudança entre r_i e r_{i+1} é alcançável por uma sequência monotônica de passos D ou L (o que é exatamente a restrição |\Delta_i|\le i). Essa descrição reduz o problema de contar caminhos a contar tais sequências inteiras.

Passo 5

Contagem sequencial e fatoração do número de possibilidades.
A forma mais simples de contar essas sequências é construir r_1,r_2,\dots,r_{n-1} um a um, e ver quantas opções há para cada r_{i} quando os anteriores já estão fixados.
  • O valor r_1 (após o primeiro U) é necessariamente 0 (não há como fazer D ou L em p=0 antes do primeiro U, e o primeiro U não muda q). Logo, r_1 é fixo — fator 1.
  • Dado r_1=0, quantas opções existem para r_2? As condições são
    r_2\in\mathbb{Z},\qquad |r_2-r_1|\le 1,\qquad |r_2|\le 2.
    Com r_1=0 isso dá r_2\in\{-1,0,1\}: portanto há 3 opções.
  • Agora considere r_3. Para qualquer valor admissível de r_2 (cada um em \{-1,0,1\}) as condições para r_3 são
    r_3\in\mathbb{Z},\qquad |r_3-r_2|\le 2,\qquad |r_3|\le 3.
    A interseção desses intervalos tem sempre exatamente 5 valores inteiros, independente do r_2 escolhido. Logo, tendo escolhido r_2, há 5 opções para r_3.
  • Em geral, para cada i com 2\le i\le n-1, ao escolher r_i as condições para r_{i+1} são
    r_{i+1}\in\mathbb{Z},\qquad |r_{i+1}-r_i|\le i,\qquad |r_{i+1}|\le i+1.
    A interseção desses dois intervalos tem exatamente 2i+1 valores inteiros possíveis (uma conta direta dos extremos mostra que os valores admissíveis vão de -i-1 até i+1 com as restrições impostas pela proximidade a r_i, e o número efetivo de inteiros possíveis é sempre 2i+1). Portanto, independentemente do valor de r_i que já tenha sido fixado (desde que ele seja admissível), existem exatamente 2i+1 escolhas possíveis para r_{i+1}.
Assim o número total de sequências (r_1,\dots,r_{n-1}) é o produto dos números de escolhas em cada etapa:
\underbrace{1}_{r_1}\times \underbrace{3}_{r_2}\times \underbrace{5}_{r_3}\times\cdots\times \underbrace{(2n-3)}_{r_{n-1}}.
Portanto o total de caminhos válidos é
\prod_{k=1}^{n-1}(2k-1).
(Para ver de forma ainda mais direta: ao construir r_2,r_3,\dots,r_{n-1} sequencialmente, na etapa i (construção de r_i com i\ge2) há exatamente 2i-1 alternativas inteiras; multiplicando sobre todas as etapas obtém-se o produto acima.)

Passo 6

Escrita em fórmulas equivalentes e conclusão.
A expressão
\prod_{k=1}^{n-1}(2k-1)
é o produto dos n-1 primeiros números ímpares. Pode ser escrita de várias formas equivalentes úteis:
\prod_{k=1}^{n-1}(2k-1)=(2n-3)!! \quad\text{(fatorial duplo)}
ou em termos de fatoriais clássicos:
\prod_{k=1}^{n-1}(2k-1)=\frac{(2n-2)!}{2^{\,n-1}(n-1)!}.
Portanto o número procurado de caminhos da formiga é qualquer dessas expressões; todas são equivalentes.

Resposta

\prod_{k=1}^{n-1}(2k-1)=\frac{(2n-2)!}{2^{\,n-1}(n-1)!}=(2n-3)!!.

Exercícios relacionados