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