[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
[obm-l] Contando caminhos em reticulados
Olá!
Eu proponho o seguinte problema combinatório que me parece bem difícil:
Seja k > 1 e seja R um reticulado retangular m x n (linhas x colunas).
Vamos considerar caminhos de (0, 0) a (n, m) em R.
Se P e Q são caminhos de (0, 0) a (n, m) em R, podemos dizer que P <= Q
sse para todo j, 0 <= j <= m, temos max{i : (i, j) está em P} <= max{k :
(k, j) está em Q}.
Traçando um gráfico com caminhos P <= Q, vemos que os traços de P nunca
invadem a área delimitada por Q (por baixo).
De quantas maneiras podemos traçar k caminhos, P_1 <= ... <= P_k, em R?
Este é um problema que apareceu quando eu tentei resolver uma questão
proposta pelo Cláudio ou pelo Nicolau (não sei direito!) onde
perguntava-se quantas maneiras podemos preencher uma matriz A, m x n,
com elementos de {1, ..., p} tal que A(i, j) > A(i + 1, j) e A(i, j) >
A(i, j + 1) para todo (i, j). É simples mostrar uma bijeção com um
problema similar, onde trocamos '>' por '>=' e o conjunto de valores
para as entradas da matriz é menor. Quando olhamos para este segundo
problema, podemos pensar na matriz como um reticulado m x n e as
fronteiras que agrupam números iguais seriam caminhos de (0, 0) a (n,
m). Se contarmos o número de caminhos possíveis, teremos determinado
todas as matrizes satisfazendo o segundo problema e, pela bijeção
montada, teremos resolvido o problema original.
Talvez a idéia não seja o melhor caminho para chegar na resposta. De
qualquer forma, o problema que eu propus parece ser interessante por si
só. Eu lembro que o Nicolau havia comentado algo sobre o paper dele em
Matemática Quântica. Bem, eu li o primeiro capítulo (por cima) mas ainda
não tive idéias para resolver o problema. Socorro, Nicolau! ;-)
[ ]'s e boa sorte pra quem tentar o desafio.
=========================================================================
Instruções para entrar na lista, sair da lista e usar a lista em
http://www.mat.puc-rio.br/~nicolau/olimp/obm-l.html
=========================================================================