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

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

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.


A idéia é a seguinte: eu gostaria de um número pequeno r tal que para 
todo conjunto S de tamanho |S| = r tenhamos tenhamos x_1 < x_2 < x_3 e 
y_1 > y_2 > y_3 em S com x_3 - x_1 >= 2(x_2 - x_1) e y_1 - y_3 >= 2(y_1 
- y_2), ou seja, quero encontrar tanto uma seq. monótona crescente com a 
propriedade acima quanto uma decrescente.

Suponha que f(n) é o menor valor para o qual qualquer conjunto S de 
tamanho |S| >= f(n) possua uma seq. de tamanho n da maneira colocada no 
enunciado.
Então se se tivermos um conjunto T com |T| >= f(n)*(r-1) elementos, T 
deve possuir uma seq. de tamanho n + 1 da maneira colocada no enunciado.
Para ver isso, ordene T, pegue o menor elemento e jogue num conjunto X, 
elimine os próximos r-2 elementos de T e novamente pegue um elemento de 
T e jogue em S, repita o processo até não haver mais elementos em T. 
Note que |X| >= f(n) pois a cada passo estamos retirando (r-1) elementos 
de T e um deles vai para X.

Por hipótese, X possui uma seq. de tamanho n com a propriedade desejada. 
Seja x_1, x_2, ..., x_n tal seq. e, sem perda de generalidade*, assuma 
que ela é crescente.

Temos r-2 elementos entre x_1 e x_2 em T (os que foram descartados), 
sejam y_1 < y_2 < ... < y_{r-2} tais elementos. Note que, o conjunto 
{x_1, y_1, ..., y_{r-2}, x_2} tem r elementos e, portanto possui uma 
seq. crescente de tamanho 3, digamos z_1 < z_2 < z_3, com a propriedade 
desejada.

Agora veja que a seqüência z_1 < z_2 < z_3 < x_3 < x_4 <  ... < x_n 
satisfaz a propriedade desejada, pois
x_3 - z_3 >= x_3 - x_2 >= 2(x_2 - x_1)
z_3 - z_1 <= x_2 - x_1, logo
x_3 - z_3 >= 2(z_3 - z_1).

* se a seq. fosse decrescente, ou seja, x_1 > x_2 > ... > x_n, 
tomaríamos z_1 > z_2 > z_3

Então, o que vocês acham?
A idéia me lembra a demonstração do teorema de Van der Waerden.
http://en.wikipedia.org/wiki/Van_der_Waerden%27s_theorem

[ ]'s
=========================================================================
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
=========================================================================