Re: [obm-l] Re: [obm-l] conjunto contendo PA

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

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: <peterdirichlet2002@zipmail.com.br>
To: <obm-l@mat.puc-rio.br>
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
=========================================================================