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