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

["Igor Castro" <cnavalhpg@xxxxxxxxxxxx>]

Bem legal a segunda solucao pro problema6(shine)!!!

----- Original Message ----- 
From: "Carlos Yuzo Shine" <cyshine@yahoo.com>
To: <obm-l@mat.puc-rio.br>
Sent: Tuesday, May 02, 2006 12:59 PM
Subject: [obm-l] OBM Nível U, problemas 5 e 6 da segunda fase 2005.


> 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
> =========================================================================
>
>
> -- 
> No virus found in this incoming message.
> Checked by AVG Free Edition.
> Version: 7.1.385 / Virus Database: 268.5.1/327 - Release Date: 28/4/2006
>
> 


		
_______________________________________________________ 
Abra sua conta no Yahoo! Mail: 1GB de espaço, alertas de e-mail no celular e anti-spam realmente eficaz. 
http://br.info.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
=========================================================================