O interessante � que a conclus�o da observa��o � razoavelmente simples:
Seja S um subconjunto de [N], ent�o se S = {x1, x2, ..., x[k]} com x1 < x2 <
... < x[k] ent�o se existe i tq x[i+1]-x[i] > 3 ent�o o complemento de S,
[N] - S apresenta tr�s elementos consecutivos, x[i]+1, x[i]+2, x[i]+3. isso
mostra que 1 <= x[i+1]-x[i] <= 2 e portanto podemos ter
S = {x1, x1 + 1, x1 + 3, x1 + 4, x1 + 6, ...} [alterne a diferen�a entre 1 e
2]
ou
S = {x1, x1 + 2, x1 + 3, x1 + 5, x1 + 6, ...} [alterne a diferen�a entre 2 e
1]
mas ent�o x1, x1+3 e x1+6 formam uma PA de tamanho 3...
[ ]'s
----- Original Message -----
From: <[EMAIL PROTECTED]>
To: <[EMAIL PROTECTED]>
Sent: Monday, September 29, 2003 3:31 PM
Subject: [obm-l] Re: [obm-l] conjunto contendo PA
Se eu nao estou enganado este e o problema que foi resolvido na Eureka!12
do Olimpiadas ao redor do mundo.Ou alguem muito parecido com ele.
-- Mensagem original --
>Ol�!
>
>Gostaria provar um resultado do tipo:
>para N suficientemente grande ([N]:= {1, 2, 3, ..., N}) se S contido em
[N]
>� tal que n�o possui uma PA de tamanho 3 ent�o |S| <= N/2.
>
>Se isso vale, obtenha um valor de N m�nimo que satisfa�a essa condi��o.
>
>(obs: isso provaria que tomando N = 2K + 1, ent�o |S| <= k e por tanto,
n�o
>� poss�vel particionar [2K + 1] em dois de forma a evitar PA's de tamanho
>3
>nas duas parti��es).
>
>[ ]'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
=========================================================================
