> 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 é <[EMAIL PROTECTED]> =========================================================================