[obm-l] Re: [obm-l] Re: [obm-l] Subconjuntos de {1,2,..,n} com Média Inteira

["larryp" <larryp@xxxxxxxxxx>]

Caro Domingos Jr.:

Obrigado pela observação. Apesar de ser fácil mostrar que se X tem aquela
forma específica, então X = X*, este fato tinha que estar explicitado na
demostração.

Sobre o cálculo de P(n) propriamente dito, eu chequei o site:
http://www.research.att.com/~njas/sequences/
e a sequência dos P(n), que começa com 1, 2, 5, 8, 15, 26, 45, ... estava
lá. Infelizmente, o site só indica uma fórmula assintótica para P(n) ~
2^(n+1)/n.

Interessante observar que, distribuindo os 2^n - 1 subconjuntos não vazios
de In por n grupos de acordo com a classe de congruência mod n a que
pertence a soma de seus elementos, a fórmula assintótica acima diz que a
classe 0 tem proporcionalmente mais elementos do que o que seria de se
esperar (2^n / n).

Outra sequência que lá está é a do meu outro problema - o da reordenação dos
naturais tal que cada segmento inicial tem média inteira. Esta começa com 1,
3, 2, 6, 4, 11, 5, 14, ...

Vou seguir seu conselho e postar uma nova mensagem com este problema pra ver
se alguém tem alguma contribuição a fazer.

Um abraço,
Claudio Buffara.

----- Original Message -----
From: "Domingos Jr." <dopikas@uol.com.br>
To: <obm-l@mat.puc-rio.br>
Sent: Thursday, January 02, 2003 9:02 PM
Subject: [obm-l] Re: [obm-l] Subconjuntos de {1,2,..,n} com Média Inteira


> Olá, estive viajando e por tanto só estou lendo suas mensagens em 2003!
>
> (...)
> até aqui parece tudo bem...
>
> > Seja X um elemento de @n com k elementos ( 1 <= k <= n ).
> >
> > No que se segue, vamos escrever X da seguinte forma:
> > X = { A(1) , A(2) , ... , A(k) }
> > e supor sempre que A(1) < A(2) < ... < A(k).
> >
> > Assim, X* = ( n+1-A(k) , n+1-A(k-1) , ... , n+1-A(1) }
> > e n+1-A(k) < n+1-A(k-1) < ... < n+1-A(1)
> >
> > Consideremos, separadamente, os casos: k par e k ímpar
> >
> > CASO 1: k é par => k = 2r.
> > X = X*  ==>
> > A(2r) = n+1-A(1) ,
> > A(2r-1) = n+1-A(2) ,
> >  ...
> > A(r+1) = n+1-A(r)  ==>
> > X = X* = { A(1) , ... , A(r) , n+1-A(r) , ... , n+1-A(1) }
> >
> > Assim, M(X) = M(X*) = r(n+1)/k = (n+1)/2 = m.
> >
> > Ou seja, todo X que é igual a X* tem média inteira.
> >
> > Repare que A(1) < A(2) < ... < A(r) < n+1-A(r), ou seja:
> > A(1) < A(2) < ... < A(r) < (n+1)/2 = m.
> >
> > Desta forma, o número de elementos X de @n com k=2r elementos tais que X
=
> > X* é igual ao número de subconjuntos de r elementos do conjunto {1, 2,
> ...,
> > m-1}, ou seja, C(m-1,r).
>
> a demonstração aqui precisa ser nas duas direções, troque => por <=>!
> a mesma coisa para a próxima...
>
> > Por conseguinte, o número total de elementos de X de @n é obtido pela
soma
> > destes valores desde k = 1 até k = m-1, ou seja, este número é igual a:
> > C(m-1,1) + C(m-1,2) + ... + C(m-1,m-1)  =  2^(m-1) - 1.
> >
> > CASO 2: k é ímpar => k = 2r-1.
> > X = X*  ==>
> > A(2r-1) = n+1-A(1) ,
> > A(2r-2) = n+1-A(2) ,
> >  ...
> > A( r+1) = n+1-A(r-1) ,
> > A(r) = n+1-A(r)  ==>
> > A(r) = (n+1)/2 = m  e
> > X = X* = { A(1) , .. , A(r-1) , A(r) = m , n+1-A(r-1) , ... ,
 n+1-A(1) }
> >
> > M(X) = M(X*) = [m + (r-1)(n+1)] / k = [m + (r-1)2m]/(2r-1) =
> > = m(2r-1)/(2r-1) = m
> >
>
> (...)
>
> > Espero que não haja nenhum furo desta vez.
>
> Assim esperamos!
>
> > Ainda permanece o problema de se determinar uma expressão para P(n) em
> > função de n, ou pelo menos, em função de P(m) com m < n. Além disso,
este
> > problema pode ter alguma relação com o seguinte:
>
> determinar P(n) deve ser bem complicado, eu acho que pode ser utilizada a
> idéia da minha mensagem anterior, decompor P(n+1) = P(n) + T(n).
>
> > Seja a sequência X: N --> N  (N = conjunto dos inteiros positivos),
> definida
> > por:
> > X(1) = 1, e, para n >=1, X(n+1) = menor inteiro positivo tal que:
> > (i) X(n+1) não pertence a { X(1) , X(2) , ... , X(n) }, e
> > (ii) o conjunto { X(1), ..., X(n), X(n+1) } tem média inteira.
> > Prove que X é uma bijeção.
> >
> > Um abraço,
> > Claudio Buffara.
>
> Que tal colocar essa problema como uma nova postagem? Assim mais pessoas
> acompanhariam...
>
> Gostei, parece que funciona, mas é mais complicada e extensa do que eu
> imaginava (e desejava!). Uma pena, no entanto, que a minha idéia não tenha
> podido ser melhor explorada (se é que dela pode-se sair em algum
resultado),
> parecia uma alternativa bem elegante...
>
> [ ]'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>
> =========================================================================


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