Domingos Jr. wrote:
Vou tentar re-escrever isso aqui de forma decente... vou provar que se um conjunto de reais SOl�!
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.
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 =========================================================================
