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

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

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