Re:[obm-l] Tres problemas olimpicos

["Paulo Santa Rita" <paulosantarita@xxxxxxxxxxx>]

Ola Fernando e demais
colegas desta lista ... OBM-L,

Voce agora vai resolver. Se mesmo assim voce nao conseguir e se ninguem 
quiser publicar uma solucao, eu publico.

Eu nao disse que voce deve ou pode fazer por Analise Combinatoria simples, 
dessas que se estuda no segundo grau. Disse que voce deveria estudar os 
casos classicos onde so se usa D ( para a direita ) e S ( para cima ) e, a 
seguir, estudar as insercoes. Isso vai lhe levar a seguinte ideia :

1) Os movimentos possiveis podem ser representados em uma Matriz. Se o 
problema e ir de (0,0) ate (A,B) uma matriz de A linhas e B colunas e uma 
boa ideia. Seja C ( MATRIZ 1) esta Matriz. Ela tem a forma :

C00 = 1 e Cij=0 se i#0 e/ou j#0

ou seja, e a matriz com 1 no elemento c11 e zero nas demais posicoes.
Para facilitar as coisas, imagine que as linhas sao numeradas  a partir de 
zero, de baixo pra cima e que as colunas sao numeradas de zero a partir da 
esquerda.

2) Apos a primeira iteracao teremos somente duas novas matrizes. Da seguinte 
forma :

MATRIZ 11 :

C00=1, C01=2 e demais elementos iguais a zero

MATRIZ 12

C00=1, C10=2 e demais elmentos iguais a zero

3) Apos a segunda iteracao teremos quatro matrizes :

MATRIZ 111
C00=1, C01=2,C02=3 demais elementos nulos
MATRIZ 112
C00=1, C01=2,C11=3 demais elementos nulos
MATRIZ 121
C00=1, C10=2,C20=3 demais elementos nulos
MATRIZ 122
C00=1, C10=2,C11=3 demais elementos nulos

Bom ficou clarissimo que estou construindo todos os caminhos validos. Cada 
matriz anterior dara origem a ZERO, UMA, DUAS ou TRES novas matrizes e TODOS 
os caminhos validos e possiveis estarao representados atraves das matrizes 
que construimos.

Assim, definimos uma sequencia M1, M2,... de CONJUNTOS DE MATRIZES em que 
cada Mi contem TODOS os caminhos possiveis de comprimento i. E claramente 
facil especificar Mi em funcao de i

Agora o ponto fundamental, onde entra a criatividade :

1) Apos cada iteracao, ou seja, apos cada geracao de geracao da Mi nos 
precisamos contabilizar quais caminhos nos interessam acompanhar, ou seja, 
os elementos de Mi que atendem as limitacoes do problema, qual seja estar 
dentro do retangulo definido pelos pontos dados

2) Voce vai retirar de cada Mi:

2.1 ) as Matrizes que representam caminhos que ultrapassaram os limites do 
retangulo
2.2 ) as matrizes com caminhos impossiveis de prosseguir, pois as posicoes 
vizinhas estao todas ocupadas
2.3) as matrizes que representam caminhos que ja atingiram legalmente o 
ponto final

Portanto, APOS CADA ITERACAO, voce prcisa descontar os numeros definidos em 
2.1 e 2.2. O total de caminhos sera a soma dos valores idos com 2.3

Poxa, agora ficou claro certo. na verdade, isso e A IDEIA, o fundamental. O 
resto e burocracia e malabarismo algebrico : E impossivel voce nao resolver 
agora. De qualquer forma, eu vou esperar um pouco e publicar uma solucao 
formal e completa.

OBS1 : O caso 2.2. acima e, em verdade, o mais interessante . Nele estao 
incluidas  orbitas periodicas. Num espaço de escala, eles representam 
solucoes estaveis de equacoes a diferencas finitas. Aqui vamos apenas 
ignora-las

OBS2 : Generalizes esta tecnica para tres dimensoes, isto e, indo de, 
digamos, (0,0,0) ate (40,50,90)

Um Abracao
Paulo Santa Rita
5,1030,250506










>From: "fernandobarcel" <fernandobarcel@bol.com.br>
>Reply-To: obm-l@mat.puc-rio.br
>To: "obm-l" <obm-l@mat.puc-rio.br>
>Subject: Re:[obm-l] Tres problemas olimpicos
>Date: Thu, 25 May 2006 05:33:10 -0300
>
>Oi Paulo,
>obrigadíssimo pela sua boa vontade, mas quanto mais eu penso, mais tenho 
>certeza que esse problema não tem solução analítica.
>
>Não consegui ver nenhuma forma simples para inserir alterações de percurso. 
>Além da condição de contorno de não poder sair do quadriculado, a única 
>regra é que para cada um dos caminhos válidos, qualquer trecho (ou 
>subsequência) da sequência total de letras não pode ter simultaneamente 
>#S=#I e #D=#E.
>
>Mas não sei como encaixar isso em casos simples de análise combinatória.
>
>Agradecerei muito se você ou algum outro colega da lista mostrar alguma 
>solução para o problema.
>
>Fernando.

_________________________________________________________________
COPA 2006: (¯`·._.·[ Ooooooola ]·._.·´¯) e + frases para seu MSN  Clique 
aqui! http://copa.br.msn.com/extra/frases/

=========================================================================
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
=========================================================================