Re: [obm-l] Problema

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

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