[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
[obm-l] Subconjuntos de {1,2,..,n} com M�dia Inteira
Caro Domingos Jr.:
Infelizmente a "solu��o" que eu propuz anteriormente � incorreta, pela
simples raz�o de que pode haver mais de um subconjunto de {1,2,..,n} com a
mesma m�dia inteira (por exemplo, {1,3,5} e {2,3,4}). Assim, a f�rmula que
eu deduzi para P(n) subestima o n�mero de tais subconjuntos para n > 4,
apesar de dar o valor correto para n = 1, 2, 3 e 4.
No entanto, me ocorreu uma outra id�ia que acho que funciona:
Seja In = {1, 2, ..., n}
Para todo sunbconjunto X de In, defina M(X) = m�dia aritm�tica dos elementos
de X.
Seja @n = { X contidos em In tais que M(X) � inteiro).
( @n � um conjunto cujos elementos s�o subconjuntos de In)
Assim, P(n) = n�meros de elementos de @n.
ID�IA: Se P(n) � par, ent�o @n pode ser particionado em pares (n�o
ordenados) distintos de subconjuntos de In com m�dia inteira. Se P(n) �
�mpar, tal parti��o n�o poder� existir.
Seja X = { A(1) , A(2) , ... , A(k) } um subconjunto n�o-vazio de In.
Seja X* = { n+1-A(1) , n+1-A(2) , ... , n+1-A(k) }
FATO 1:
X pertence a @n <==> X* pertence a @n
DEM:
Inicialmente, observe que In cont�m X <==> In cont�m X*.
Al�m disso, temos que M(X*) = n + 1 - M(X)
Assim, M(X) � inteiro <==> M( X*) � inteiro
Portanto: X pertence a @n <==> X* pertence a @n.
------
Assim, se P(n) � par, a id�ia � decompor @n em pares da forma { X , X* } com
X <> X*.
Por outro lado, se P(n) � �mpar, a id�ia � mostrar que existe um n�mero
�mpar de X pertencentes a @n tais que X = X*.
FATO 2:
Se n � par (n = 2m) , ent�o para todo X em @n, teremos X <> X*
DEM:
Suponhamos que exista X em @n tal que X = X*. Ent�o:
X = X* ==> M(X) = M(X*) ==>
M(X) = n + 1 - M(X) (FATO 1) ==>
2M(X) = n +1 = 2m +1 ==>
Par = �mpar ==> Contradi��o ==> X <> X*
Conclus�o: n � par ==> para todo X em @n, X <> X*.
------
FATO 3:
Se n � �mpar (n = 2m-1), ent�o existe um n�mero �mpar de elementos X em @n
tais que X = X*.
DEM:
Para n = 1, o resultado � claro ( X = X* = {1}� o �nico elemento de @1).
Assim, suponhamos que n >= 3 (e portanto, m>=2).
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).
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
Tamb�m neste caso, todo X que � igual a X* tem m�dia inteira.
Al�m disso, cada X com esta propriedade conter� o elemento m = (n+1)/2.
Da mesma forma que antes, temos que:
A(1) < A(2) < ... < A(r-1) < A(r) = m.
Se X for unit�rio, ent�o necessariamente X = {m}, o qual tem m�dia inteira.
Assim, o n�mero de elementos unit�rios X de @n tais que X = X* � igual a 1.
Por outro lado, para k >= 3, o n�mero de elementos X de @n com k=2r-1
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).
Conclus�o: o n�mero total de elementos de X de @n � igual a:
1 + C(m-1,1) + C(m-1,2) + ... + C(m-1,m-1) = 2^(m-1).
Assim, o n�mero total de elementos X de @n tais que X = X* � igual a:
(2^(m-1) - 1) + 2^(m-1) = 2^m - 1, um n�mero �mpar.
------
Qualquer que seja n, @n pode ser particionado em subconjuntos de dois tipos:
Tipo 1: Pares da forma {X , X*} onde X <> X*
Tipo 2: Conjuntos unit�rios da forma { X }, tais que X = X*.
O FATO 2 implica que se n � par, ent�o @n n�o cont�m subconjuntos do Tipo 2.
Assim, @n � particionado em pares da forma { X, X* } com X<>X*, ou seja, @n
tem um n�mero par de elementos.
Assim, n � par ==> P(n) � par ==> P(n) - n � par.
O FATO 3 implica que se n � �mpar, ent�o @n tem um n�mero �mpar de
subconjuntos do Tipo 2. Assim, se a parti��o contiver r subconjuntos do Tipo
1 e 2s-1 subconjuntos do Tipo 2, ent�o o n�mero de elemntos de @n ser� igual
a 2r + 2s - 1, um n�mero �mpar.
Assim, n � �mpar ==> P(n) � �mpar ==> P(n) - n � par.
Espero que n�o haja nenhum furo desta vez.
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:
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.
----- Original Message -----
From: "Cl�udio (Pr�tica)" <claudio@praticacorretora.com.br>
To: <obm-l@mat.puc-rio.br>
Sent: Saturday, December 28, 2002 2:19 PM
Subject: Re: [obm-l] Re:
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." <dopikas@uol.com.br>
To: <obm-l@mat.puc-rio.br>
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 � <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>
=========================================================================
=========================================================================
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>
=========================================================================