Re: [obm-l] idéia - problema da IMC

["Domingos Jr." <dopikas@xxxxxxxxxx>]

Domingos Jr. wrote:

> Olá!
>
> Tive uma idéia pra um dos problemas da IMC (um que eu achei bem 
> difícil...).
> Enunciado (copiado de uma msg da lista):
>
> 5) Let X be a set of  binomial(2k-4, k-2) + 1  real numbers,
> k>=2. Prove that there exists a monotone sequence x_1, x_2, ..., x_k in
> X such that |x_{i+1} - x_1| >= 2|x_i - x_1|
> for all i = 2,...,k-1.
>
Vou tentar re-escrever isso aqui de forma decente... vou provar que se 
um conjunto de reais S
tem tamanho |S| >= n! então há uma seq. de n elementos satisfazendo as 
condições do enunciado.

Lema 1: se X é um conjunto de k reais, então uma das duas vale:
(i) Existe uma seq. monótona de tamanho k (ou seja, o conjunto X 
ordenado) satisfazendo as CE
(ii) Existe uma seq. crescente com 3 elementos e que satisfaz as 
condições do enunciado (CE)

Dem.: Sejam x_1 < x_2 < ... < x_k os elementos de X.
Se não há uma seq. crescente de 3 elementos nas CE, então
a seq. monótona decrescente x_k > x_{k-1} > ... > x_1 é tal que, para 
todo 1 <= j < k
x_k - x_j >= 2(x_k - x_{j+1}), caso contrário teríamos para algum j,
x_k - x_j < 2(x_k - x_{j+1}) e, portanto, x_j < x_{j+1} < x_k é uma seq. 
de tamanho 3
nas CE, pois x_k - x_j = x_k - x_{j+1} + x_{j+1} - x_j < 2(x_k - 
x_{j+1}), logo
x_{j+1} - x_j < x_k - x_{j+1}, donde tiramos que
x_k - x_j > 2(x_{j+1} - x_j).
Caso não haja uma seq. decrescente de 3 elementos nas CE um raciocínio 
análogo mostra
que a seq. x_1 < ... < x_k está nas CE.

Lema 2: se y_1 < y_2 < ... < y_k é uma seq. nas CE e z_1 < ... < z_r são 
reais entre
y_1 e y_2 (inclusive) nas CE, então z_1 < ... < z_r < y_3 < ... < y_k é 
uma seq. nas CE.

Dem.: precisamos mostrar que para todo j >= 3
y_{j+1} - z_1 >= 2(y_j - z_1)
note que z_1 = y_1 + s, com s >= 0, temos então
y_{j+1} - z_1 = y_{j+1} - y_1 - s
y_j - z_1 = y_j - y_1 - s
Por hipótese, temos y_{j+1} - y_1 >= 2(y_j - y_1), logo
y_{j+1} - z_1 = y_{j+1} - y_1 - s >= 2(y_j - y_1) - s >= 2(y_j - y_1 - 
s) = 2(y_j - z_1).
Evidentemente o lema se estende para o caso de seq. decrescentes nas CE.

Definição: f(n) := menor inteiro tal que qualquer conjunto S com |S| = 
f(n) reais possui
uma seq. monótona nas CE com pelo menos n termos.

Teorema: f(n) < n! para n >= 2
Dem.: os casos n = 2, 3 são triviais, suponha n > 3
Seja T um conjunto com |T| = (n-1) (f(n)-1) elementos.
Se y_1 < y_2 < ... < y_{(n-1)(f(n)-1)} são os elementos de T, defina
X = {x_{1 + (n-1).r}, r = 0..f(n)-1}, temos que |X| = f(n), então, pela
hip. de indução X possue uma seq. x_1, x_2, ..., x_n nas CE.
se a seq. for crescente, então considere os elementos x_1 e x_2 e
todos os elementos entre eles em T (há pelo menos n-1 desses
por construção); estamos considerando pelo menos n+1 elementos e,
de acordo com o lema 1 ou
(i) há uma seq. de tamanho n+1 nas CE (e aí não precisamos fazer mais 
nada) ou
(ii) temos pelo menos uma seq. crescente e uma seq. decrescente de 
tamanho 3 nas CE.
tome z_1 < z_2 < z_3 satisfazendo as CE e aplique o lema 2, a seq.
z_1 < z_2 < z_3 < y_3 < ... < y_n tem tamanho n+1 e satisfaz as CE.

Isso demonstra que f(n+1) <= (n-1)(f(n)-1), disso segue f(n) < n! para 
todo n >= 2.

[ ]'s

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