Caro Domingos Jr.: Tentei trabalhar com a sua idéia dos subconjuntos de {1,2,...,n} contendo n, mas não consegui estabelecer uma relação de recorrência usável entre T(n) e T(n+1).
Dado um subconjunto X de {1,2,..,n} com k elementos e com soma S (portanto, média = S/k), minha idéia foi passar de X para X U {n+1}, com soma S + n + 1 ( e média (S+n+1)/(k+1) ) e ver quais destes novos subconjuntos têm média inteira. O problema é que X U {n+1} pode ter média inteira sem que X o tenha. Resultado: eu caí numa série de equações de congruência mod k e mod k+1 e a álgebra ficou medonha.... No entanto, um ataque direto (sobre o valor de P(n)) funcionou e, de quebra, ainda produziu uma fórmula fechada para P(n), a partir da qual ficou fácil provar que P(n) - n é sempre par. P(n) = no. de subconjuntos de {1,2,..,n} com média inteira. Seja X um subconjunto de {1,2,...,n} com k elementos. Se X tem média inteira, então a soma S dos elementos de X é divisível por k. Valor mínimo de S = 1 + 2 + ... + k = k(k+1)/2 Valor máximo de S = (n-k+1) + (n-k+2) + ... + n = k(n-k) + k(k+1)/2 Assim, temos que: k(k+1)/2 <= S <= k(n-k) + k(k+1)/2, ou seja, (k+1)/2 <= S/k <= n - k + (k+1)/2 Consideremos dois casos - k par e k ímpar: CASO 1: k par ==> k = 2p com p inteiro positivo: (2p+1)/2 = p + 1/2 <= S/k <= n - 2p + (2p+1)/2 = n - p + 1/2 S/k é inteiro ==> S/k pertence a {p+1, p+2, ..., n-p}, ou seja, S/k pode assumir n - 2p = n - k valores distintos. CASO 2: k ímpar ==> k = 2p - 1 com p inteiro positivo: ((2p-1)+1)/2 = p <= S/k <= n - (2p-1) + ((2p-1)+1)/2 = n - p + 1 S/k é inteiro ==> S/k pertence a {p, p+1, ..., n-p+1} S/k pode assumir n - 2p + 2 = n - k + 1 valores distintos. Assim: P(n) = SOMATÓRIO ( no. de subconjuntos com k elementos e média inteira ) 1 <= k <= n P(n) = SOMATÓRIO (n - k) + SOMATÓRIO (n - k + 1) 1 <= k <= n 1 <= k <= n k par k ímpar P(n) = SOMATÓRIO (n - k) + SOMATÓRIO ( 1 ) 1 <= k <= n 1 <= k <= n k ímpar P(n) = n^2 - n(n+1)/2 + [ (n+1)/2 ] ****************************** * P(n) = n(n-1)/2 + [ (n+1)/2 ] * ****************************** onde [x] = maior inteiro menor ou igual a x. Agora, voltamos ao problema original. De posse da fórmula para P(n), obtemos: P(n) - n = n(n-3)/2 + [ (n+1)/2 ] n é par ==> n = 2m com m inteiro positivo ==> P(n) - n = m(2m-3) + m = 2m^2 - 3m + m = 2m(m-1) => Par n é ímpar ==> n = 2m-1 com m inteiro positivo ==> P(n) - n = (2m-1)(m-2) + m = 2m^2 - 3m + 2 + m = 2(m^2 - m + 1) => Par Um abraço, Claudio Buffara. ----- Original Message ----- From: "Domingos Jr." <[EMAIL PROTECTED]> To: <[EMAIL PROTECTED]> Sent: Thursday, December 26, 2002 9:18 PM Subject: Re: [obm-l] Re: > 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]> ========================================================================= ========================================================================= 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]> =========================================================================