[obm-l] OBM Nível U, problemas 5 e 6 da segunda fase 2005.

[Carlos Yuzo Shine <cyshine@xxxxxxxxx>]

Oi gente,

Na época da prova o Gugu e eu discutimos os problemas
5 e 6 da prova. Aí vão as soluções. A solução da 5 é
do Gugu. A 6 tem uma solução do Gugu e outra minha,
baseada em idéias que li no Proofs From The Book e que
também apareceram na OPM de alguns anos atrás.

Espero que estejam legíveis.

[]'s
Shine

> ----- Forwarded message from gugu@impa.br -----
>     Date: Mon, 24 Oct 2005 19:22:26 -0200
>     From: gugu@impa.br
> Reply-To: gugu@impa.br
>  Subject: Re: OBMU
>       To: Yuri Lima <yglima@yahoo.com>
> 
>    Oi Yuri,
>    Vamos lá:
> 5) Escreva x^(-x)=e^(-x.ln(x))=soma(n=0 a
infinito)((-x.ln(x))^n/n!). É só provar agora que
Integral(0 a 1)((x.ln(x))^n dx)=(-1)^n.n!/(n+1)^(n+1),
o que eu deixo para você fazer (qualquer problema me
avise).
> 6) Tem que provar que, se P_r(x)=Binomial(x+r,r),
então um polinômio do tipo f(x)=Soma(j=1 a
m)c_j.P_r_j(x), onde r_1<r_2<...<r_m não pode ter m
raízes naturais distintas, se não for identicamente
nulo.
> Para isso, provaremos por indução que para um tal
polinômio f(x), se c_m>0, não existem i_1<i_2<...<i_m
naturais com (-1)^(m-k).f(i_k)<=0 para todo k<=m. Para
m=1 isso é óbvio, pois f(x)>0 sempre. Para r<=s,
P_s(x)=P_r(x).P_(s-r)(x+r)/Binomial(s,r), e logo,
dividindo tudo por P_r_1(x), podemos supor r_1=0. A
partir daí, a indução se faz aplicando o operador M
(de menos) a f(x), dado por Mf(x)=f(x+1)-f(x).
> Temos, para r=0, MP_r(x)=0 e, para r>=1,
MP_r(x)=P_(r-1)(x+1). Detalhes com você.

> > Oi Gugu,
> >
> > Antes, algumas definições.
> >
> > Considere o reticulado Z^2. Defina caminho entre
dois pontos P e Q de Z^2 como uma seqüência de pontos
do reticulado, cada um igual ao anterior mais (0,-1)
ou (1,0), com o primeiro termo igual a P e o último
igual a Q. Defina sistema de caminhos sem interseção
ligando dois subconjuntos X a Y de Z^2, cada um com n
elementos, como um conjunto de n caminhos disjuntos,
cada um ligando um ponto de X e um ponto de Y.
> >
> > Afirmação. Se A = (a_{rs}) é a matriz do problema
6 da OBM (lembrando que sua entrada a_{rs} é {i_r +
j_s\choose i_r}), então det(A) é igual ao número de
sistemas de caminhos sem interseção ligando X =
{(0,i_1),(0,i_2),...,(0,i_n)} a Y =
{(j_1,0),(j_2,0),...,(j_n,0)}.
> >
> > Note que a partir desse resultado o problema 6
agora se torna imediato, já que não é difícil achar um
sistema de caminhos sem interseção ligando X a Y (faça
uma figura e veja!).
> >
> > Demonstração da afirmação: Pela definição de
determinante, det(A) é a soma de n! termos, cada um
igual a sgn(p)a_{1p(1)}...a_{np(n)}, sendo p uma
permutação de (1,2,...,n). Considerando que a_{rs} =
{i_r + j_s\choose i_r}, esse termo sem o sinal é igual
ao número de maneiras de n caminhos ligarem os pares
de pontos (0,i_k) a (j_{p(k)},0), intersectando ou
não. Em particular, todos os nossos sistemas de
caminhos sem interseção estão sendo contados quando p
é a identidade (não é difícil provar que se p não é a
identidade então dois caminhos se intersectam; é só
fazer uma figura e usar continuidade). Então os
sistemas de caminhos sem interseção aparecem com o
sinal positivo no determinante.
> >
> > Os sistemas de caminhos com alguma interseção se
anulam no determinante: considere a interseção que
está mais à esquerda (ou seja, com abscissa mínima);
caso haja mais de uma, tome a que está mais para baixo
(com ordenada mínima). Suponha que a interseção seja
entre os caminhos ligando os pares (0,i_l), (j_m,0) e
(0,i_p), (j_q,0). Esse sistema de caminhos está sendo
contado numa parcela do determinante com dois fatores
iguais a a_{lm} e a_{pq}. Acontece que podemos obter
uma sistema de caminhos com as mesmas arestas com os
mesmos caminhos, exceto que trocamos os caminhos
ligando os pares (0,i_l), (j_m,0) e (0,i_p), (j_q,0)
pelos que ligam os pares (0,i_l), (j_q,0) e (0,i_p),
(j_m,0). Mas esse sistema de caminhos está sendo
contado numa outra parcela do determinante, com todos
os fatores iguais, exceto os termos a_{lm} e a_{pq}
que são substituídos por a_{lq} e a_{pm}. Mas o sinal
da permutação está trocado nessa parcela, já que
fizemos uma inversão, então esse sistema de caminhos
aparece cortado. Note que a escolha dessa inversão não
tem ponto fixo e é bijetiva, logo *todos* os caminhos
com interseção se anulam no determinante, e o
resultado segue, já que tal inversão não se aplica a
sistemas de caminhos sem interseção.
> >
> > Que tal?
> >
> > []'s
> > Shine
> >
> >
> >
> >
> > __________________________________
> > Yahoo! Mail - PC Magazine Editors' Choice 2005
> > http://mail.yahoo.com
> >
> 
> 
> 
> 
>
----------------------------------------------------------------
> This message was sent using IMP, the Internet
> Messaging Program.
> 
> 


__________________________________________________
Do You Yahoo!?
Tired of spam?  Yahoo! Mail has the best spam protection around 
http://mail.yahoo.com 
=========================================================================
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
=========================================================================