Re: [obm-l] Problema

["Cláudio \(Prática\)" <claudio@xxxxxxxxxxxxxxxxxxxxxxx>]

É isso aí. Parabéns.

Esse é o tipo de problema em que persistência é recompensada.

Um abraço,
Claudio.

----- Original Message -----
From: "Domingos Jr." <dopikas@uol.com.br>
To: <obm-l@mat.puc-rio.br>
Sent: Friday, March 28, 2003 1:49 PM
Subject: Re: [obm-l] Problema


> Acho que consegui:
>
> Vamos começar montando partições de forma a usar o menor número de
elementos
> necessários e sempre com a exigência de que nenhum elemento pode ser
> expresso como soma de outros dois (possivelmente o mesmo).
>
> Considere sempre que os elementos estão ordenados já que toda hora estarei
> trabalhando com a diferença de elementos.
>
> Pelo PCP, existe uma partição com pelo menos 330 elementos, seja ela P1 e
> {x1, x2, ..., x330} contido em P1
>     o conjunto D1 = {x2 - x1, x3 - x1, ..., x330 - x1} tem elementos todos
> distintos e com certeza nenhum elemento de D1 pode ser colocado em P1.
> |D1| = 329, pelo PCP, temos que uma das partições P2, ..., P5 tem pelo
menos
> 66 elementos.
>     seja I = {i1, ..., i66} contido em {2, ..., 330} índices tais que:
>     { x[i1] - x1, ..., x[i66] - x1 } contido em P2
>     o conjunto D2 = { (x[i2]-x1)-(x[i1]-x1), ..., (x[i66]-x1)-(x[i1]-x1) }
=
>         { x[i2] - x[i1], ..., x[i66] - x[i1] } tem todos os elementos
> distintos e com certeza nenhum deles pertence a P1 ou P2 (vc entende por
> que?), |D2|=65 e, repetiremos o argumento...
>     seja J = {j1, ..., j17} contido em I tal que:
>     { x[j1] - x[i1], ..., x[j17] - x[i1] } contido em P3
>         D3 = { x[j2] - x[j1], ..., x[j17] - x[j1] }, com nenhum elemento
em
> P1, P2 ou P3
>     seja K = {k1, ..., k6} contido em J tal que:
>     { x[k1] - x[j1], ..., x[k6] - x[j1] } contido em P4
>         D4 = { x[k2] - x[k1], ..., x[k6] - x[k1] }, com nenhum elemento em
> P1, P2, P3 ou P4
>     seja L = {l1, l2, l3} contido em K tal que:
>     { x[l1] - x[k1], ..., x[l3] - x[k1] } contido em P5
>         D5 = { x[l2] - x[l1], x[l3] - x[l1] }, com nenhum elemento em P1,
> P2, P3, P4 ou P5
>     D5 contido em P6
>         mas então, se queremos que em P6 não haja nenhum elemento que seja
a
> soma de outros dois, então x[l3] - x[l2] não pertence a P6, mas também não
> pode pertencer a nenhuma outra partição, basta ver os índices l3 e l2 como
> índices em K, J, I e {2, 330} que vemos que esse inteiro é uma diferença
> entre dois elementos de cada uma das partições!
>
> Se não tem nenhum erro, acho que matei o problema! (Ufa, eu tinha proposto
> um deadline para hj, se não conseguisse ia desistir...).
>
> [ ]'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
> O administrador desta lista é <nicolau@mat.puc-rio.br>
> =========================================================================

=========================================================================
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
O administrador desta lista é <nicolau@mat.puc-rio.br>
=========================================================================