Re: [obm-l] Questão da Eureka 01

[Carlos Yuzo Shine <cyshine@xxxxxxxxx>]

Oi gente,

Imagine os n^2 + 1 números em fila. Agora, escreva
sobre cada número a quantidade de termos da maior
subseqüência crescente que começa com esse número. Se
uma dessas quantidades for maior ou igual a n+1, o
problema acabou (você encontrou uma subseqüência
crescente com n+1 termos!).

Se não ocorrer isso, todas as quantidades são no
máximo n. Como há n^2+1 números e n possíveis valores
para as quantidades, pelo Princípio da Casa dos
Pombos, há n+1 quantidades iguais, digamos, a k. Sejam
a_1, a_2, ..., a_{n+1} os números associados a essas
quantidades, na ordem em que aparecem na seqüência.
Temos que a_i > a_{i+1}. Se a_i < a_{i+1}, considere
uma subseqüência crescente de k termos iniciada por
a_{i+1}; coloque a_i "na frente" dessa seqüência e
você obtém uma subseqüência crescente de k+1 termos.
Absurdo, pois a maior subseqüência crescente iniciada
por a_i tem k termos.

Assim, a subseqüência a_1, a_2, ..., a_{n+1} é
decrescente e acabou.

Para você visualizar melhor, sugiro fazer um caso
particular. Tome n=2 e, por exemplo, a seqüência
  4,1,3,2,5

A maior subseqüência iniciada com o 4 é 4,5. Fazendo o
mesmo com os outros números obtemos
  2 3 2 2 1
  4,1,3,2,5

Note que há três 2's e que a subseqüência
correspondente 4,3,2 é decrescente.

[]'s
Shine

--- Faelccmm@aol.com wrote:

> Olá pessoal,
> 
> O questão abaixo encontra-se na Eureka 01 e foi
> resolvido na Eureka 03. O 
> problema é que eu enviei para vários fóruns e
> listas, inclusive esta lista OBM-l, 
> e ninguém entendeu a resolução presente na Eureka 03
> (pg. 57). 
> Se conseguirem entender a resolução, gostaria que
> "traduzissem" para mim OU, 
> se preferirem, dar uma outra solução.
> 
> 
> 1) Mostre que toda sequência com n^2 + 1 elemento
> possui uma subsequência 
> crescente com n + 1 elementos ou uma subsequência
> decrescente com n + 1 
> elementos.
> 
> 
> []s, 
> Rafael 
> "Deus não joga dados com o universo" (Albert
> Einstein)
> 
> 
> 


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