Re: [obm-l] Problema

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

Também tenho quebrado a cabeça com ele...

Uma primeira idéia foi considerar que existe uma divisão em 6 partições onde
nenhum elemento é soma de outros dois pertencendo a mesma partição e, para
cada partição, definir um conjunto de elementos que NÃO podem entrar na
partição, pois se entrasse haveria um elemento (não necessariamente o que
estaria para entrar) que desrespeitará a propriedade desejada.

A partir daí, queria provar que a intersecção desses 6 conjuntos não seria
nunca vazia, o que indicaria que existe um inteiro que não pode ser inserido
em nenhuma partição pois quebraria a nossa regra.

Para provar que a intersecção não é vazia eu imaginei que fosse possível
somar as cardinalidades de cada conjunto e verificar que o número é
suficientemente grande para exigir que um elemento esteja em todos os 6
conjuntos.

Infelizmente, não tenho conseguido mostrar elementos (claro, distintos
dentro de um mesmo conjunto) em quantidade suficiente para realizar uma
prova como a que propus acima.

Vou continuar pensando no problema e, quem sabe, algo se ilumina!
Alguma outra idéia?

[ ]'s

> Caros colegas da lista:
>
> Aqui vai um que esta dando trabalho:
>
> O conjunto {1,2,...,1978} eh particionado em 6 subconjuntos. Prove que um
> destes subconjuntos contem um elemento que eh igual a soma de dois
elementos
> (nao necessariamente distintos) deste mesmo subconjunto.
>
> Agradeco qualquer ajuda.
>
> Um abraco,
> Claudio.

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