Re: [obm-l] Re:

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

> Seja P(n) o numero de subconjuntos de 1,2,...,n com m�dia inteira.
> Prove que P(n)-n � sempre par.


um esbo�o, gostaria de receber coment�rios:

seja T(i) o n�mero de subconjuntos de {1, 2, ... i}, contendo i e com m�dia
inteira.

seja A(i) a seguinte proposi��o:
A(i) : P(i) - i � par e T(i+1) � �mpar

P(1) = 1
P(1) - 1 = 0, que � par
T(2) = 1, que � �mpar, logo A(1) vale.

suponha que A(i) � v�lido para todo 1 <= i < k
n�o � muito dif�cil perceber que P(i+1) = P(i) + T(i+1), pois todo
subconjunto de {1, 2, ... i} � subconjunto de {1, 2, ... i, i + 1} e a m�dia
permanece inalterada.
Os subconjuntos do segundo que n�o s�o subconjuntos do primeiro devem
necessariamente conter "i+1" e por tanto s�o contados por T(i+1).

P(i+1) - (i+1) = P(i) - i + T(i+1) - 1
P(i) - i � par (hip. da indu��o)
o que implica P(i+1) - (i+1) par se provarmos que T(i+1) � �mpar.

Existe uma rela��o entre T(i) e T(i+1), podemos v�-la da seguinte maneira:
um subconjunto de {1, 2, ... i} contendo i pode nos ajudar a formar um
subconjunto de {1, 2, ... , i, i + 1} contendo i + 1.

A id�ia � simples, subtraindo 1 de um dos elementos e somando-o a i. O
cuidado que deve-se tomar � que para n�o subtrair de um elemento de forma a
repetir um elemento, por exemplo { 1, 3, 5 } -> { 1, 3 - 1, 5 + 1 }, mas {1,
2, 3} n�o pode ser levado em outro conjunto de 3 elementos contendo 4!

Acho q a demonstra��o pode sair mostrando um mapeamento que saia dos
subconjuntos de T(i) e leve-os aos subconjuntos de T(i+1) esse mapa pode ser
parcial, considerando apenas uma esp�cie simples de trabalhar e deixando
apenas alguns casos patol�gicos de fora...

Assumindo a conjectura acima (n�o deve ser dif�cil provar, mas estou sem
muito tempo...) pelo princ�pio da indu��o, vale para todo n >= 1, P(n) - n �
par.

[ ]'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>
=========================================================================