 |
|
|
|||
 |
|||||
|
|
|
|
|||
|
|
|||||
Rogério César dos Santos
Enunciando o problema Neste artigo vamos encontrar o ponto do plano pelo qual passam mais caminhos em uma malha quadricular de percursos. Considere o sistema de caminhos quadriculado na figura abaixo, no qual um móvel, partindo do ponto A = (0, 0), precisa chegar em B = (3, 3), e só pode se deslocar sobre aqueles segmentos verticais e horizontais que ligam dois pontos de coordenadas inteiras. Além disso, o móvel só pode se mover para a direita ou para cima.
Contando os caminhos Cada caminho para ir de (0, 0) a (m, n) é composto por m deslocamentos horizontais unitários H e n deslocamentos verticais unitários V. O que distingue esses caminhos é a ordem em que os deslocamentos se sucedem. Escolher um caminho é equivalente a ordenar m letras H e n letras V. A contagem de caminhos pode, portanto, ser feita usando a expressão O número de caminhos de (0, 0) até (N, N) que passam por (m, n) é igual ao número de caminhos para ir de (0, 0) a (m, n) multiplicado pelo número de caminhos para ir de (m, n) a (N, N), que por sua vez é igual ao número de caminhos de (0, 0) até (N – m, N – n). Note que, nessa última contagem, (m, n) funciona como a origem
Portanto, o número de caminhos de (0, 0) até (N, N) passando por (m, n) é c(m, n) = No nosso exemplo 3 por 3, o número de caminhos que passam, por exemplo, pelo ponto (1, 2) é c(1, 2) = Podemos representar os valores de c(m, n) para todos os valores de m e n (0
Primeira proposição: da simetria da matriz B A primeira proposição que vamos demonstrar, que é sugerida pelo exemplo anterior, é:
Demonstração A expressão
Segunda proposição: da diagonal da matriz A segunda proposição, que se pode inferir a partir dos resultados da diagonal secundária da matriz do nosso exemplo, a saber 20, 12, 12, 20, é: para 0 Ou seja, o número de caminhos diminui quando pegamos pontos mais afastados da origem, pelo menos até a metade da diagonal. No nosso caso, de 20 para 12. Além disso, para N/2 < x
Demonstração Por P = (x, x), onde 0
caminhos, indo de (0, 0) até (N, N). Já por Q = (x + 1, x + 1) passam
caminhos. Vamos supor por contradição que
Então
desenvolvendo e simplificando os fatoriais
onde essa última implicação seria válida para N par ou ímpar, pois x é inteiro. Logo, uma contradição. Agora, para N/2 < x Observe ainda que, de acordo com os cálculos acima, c(x + 1, x + 1) = c(x, x) se e somente se x = Neste caso, c Observe, portanto, que essa segunda proposição está dizendo que, na diagonal, os pontos que possuem mais caminhos passando por eles são os pontos (1, 1) e, por simetria, (N –1, N – 1), onde excluímos, claro, os pontos (0, 0) e (N, N), que são de passagem obrigatória.
Terceira proposição: dos pontos abaixo e acima da diagonal Vamos enfim provar nossa terceira e última proposição. Ela vai nos dizer que c(x, x)
Demonstração Faremos por indução sobre i. Para i = 0, é fácil ver que a igualdade se verifica. Para N = 1, também é fácil ver que c(0, 0)= c(1, 1) = 2 e c(1, 0) = c(0, 1) = 1. Suponhamos então, por hipótese de indução, que, para i > 0, temos c(x, x) > c(x, x – i). Temos c(x, x) > c(x, x - 1)
Completando o processo de indução, vamos provar que c(x, x) > c(x, x – (i + 1)): c(x, x, – (i + 1)) =
Basta agora provar a desigualdade : 2Nx – 2Ni – 2x2 + 2xi + ix – i2 + x – i E a última desigualdade é verdadeira, pois x
Agora, juntando as conclusões das duas últimas proposições, concluímos que em qualquer quadriculado de caminhos N por N, os pontos pelos quais passam mais caminhos são os pontos (1, 1) e (N – 1, N – 1), sem contar é claro os pontos (0, 0) e (N, N):
|
|
Pelo fato de o ponto de chegada ser (3, 3), chamaremos esse reticulado de 3 por 3, apesar de haver 4 × 4 = 16 pontos de coordenadas inteiras. A pergunta que vamos levantar no nosso estudo é: sem contar os pontos (0, 0) e (3, 3), dentre todos os demais pontos de coordenadas inteiras desse reticulado de caminhos, por qual ou por quais deles passa o maior número de caminhos que partem de (0, 0) e chegam em (3, 3)?
do número de permutações com repetição de m + n objetos, sendo m de um tipo e n de outro. Essa expressão é igual, também, a 
(isso pode ser concluído diretamente, observando que um caminho fica determinado ao se escolherem as m posições dos deslocamentos horizontais na sequência de m + n deslocamentos).
= 3.3 = 9
m 
é simétrica em relação a n e m, de forma que fica evidente que c(m, n) = c(n, m). Agora, de (0, 0) até (N – n, N – m) há 
caminhos. E de (N – n, N – m) até (N, N) há 
caminhos. Logo, c(N – n, N – m) = 
= c(n, m) caminhos, e, de acordo com o primeiro passo dessa demonstração, também é igual a c(N – m, N – n), o que conclui a demonstração.
ou seja, N deve ser ímpar. 
, os dois pontos centrais da diagonal secundária, como foi o caso do nosso exemplo anterior, no qual c(1, 1) = c(2, 2) = 12.
c(x, x – i) para todo x = 1, ..., N, com i = 0, ..., x. Pela simetria, novamente, o leitor poderá se convencer facilmente de que, por consequência, c(x, x) 
=
< 1:
Enfim, o ponto procurado