Re: [obm-l] PROBLEMA DIFICIL

[gugu@xxxxxxx]

   Caros colegas,
   O enunciado do problema (e o resto da prova da segunda fase do nível U deste
ano estão em http://www.obm.org.br/provas/obm2005/2Fase_Nivelu2005.pdf ou em
http://www.obm.org.br/provas/obm2005/2Fase_Nivelu2005.doc , por exemplo.
   Uma solução é como segue (vou colocar algumas linhas com pontinhos antes...):
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
     Usaremos o fato de que, se a soma de vários números reais em [-1,1] é 0,
então podemos reordená-los de modo que as somas parciais sempre estejam em
[-1,1] (basta que a cada momento colocamos um número dos que faltam que tenha
sinal contrário ao valor atual da soma).
     Podemos supor, reordenando os vetores e girando o plano, se for preciso,
que a soma de vetores da lista que tem o maior módulo possível é
v_1+v_2+...+v_k, a qual é igual a (0,a), com a>0; não é difícil ver que as
ordenadas dos v_i para i<=k devem ser positivas, pois se algum desses v_i tiver
ordenada negativa simplesmente retiramos esse v_i da lista e aumentamos o módulo
da soma (como a soma total é 0, v_(k+1)+...+v_n=(0,-a), e as ordenadas dos v_i
são negativas). Podemos ainda, reordenando v_1,v_2,...,v_k usando o fato
inicial, supor que, para s<=k, a abscissa de v_1+v_2+...+v_s sempre pertença a
[-1,1]. Do mesmo modo, podemos supor que, para k+1<=t<=n, a abscissa de
v_(k+1)+v_(k+2)+...+v_t também pertence a [-1,1]. Agora usamos de novo o fato
inicial para ordenadas para intercalar os v_i com 1<=i<=k com os v_j com
k+1<=j<=n (preservando a ordem dos v_i e dos v_j) de maneira que a ordenada das
somas parciais sempre esteja em [-1,1]. Qualquer uma dessas somas parciais será
a soma de uma parcela do tipo v_1+v_2+...+v_s, com s<=k com outra do tipo
v_(k+1)+v_(k+2)+...+v_t, com k+1<=t<=n, e logo tem abscissa em [-2,2]. Assim,
qualquer soma parcial tem módulo limitado por (2^2+1^2)^(1/2)=5^(1/2).
    Abraços,
              Gugu


Citando Valter Rosa <valter.rosa@uol.com.br>:

> Como eu acho a definição deste problema ?
> Dá pra colocar aqui na lista ?
>
>   ----- Original Message -----
>   From: Joÿffffe3o Silva
>   To: obm-l@mat.puc-rio.br
>   Sent: Wednesday, December 28, 2005 8:48 PM
>   Subject: [obm-l] PROBLEMA DIFICIL
>
>
>   Alguem sabe como se faz o problema 3 da OBM, nivel universitario, fase 2,
> deste ano (2005) ?
>
>
> ------------------------------------------------------------------------------
>   Yahoo! doce lar. Faça do Yahoo! sua homepage.
>
>
> ------------------------------------------------------------------------------
>
>
>   No virus found in this incoming message.
>   Checked by AVG Free Edition.
>   Version: 7.1.371 / Virus Database: 267.14.8/215 - Release Date: 27/12/2005
>




----------------------------------------------------------------
This message was sent using IMP, the Internet Messaging Program.

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