Eu pensei no seguinte: vamos esquecer que a gente vai somar, para cada
subconjunto, o menor com o maior. Vamos somar todos os maiores com todos os
menores.
Note que 1 é o menor elemento de 2^1999 conjuntos (todos os conjuntos {1} U S,
sendo S subconjunto de {2,3,...,2000}. O 2 é o menor elemento de 2^1998
conjuntos ({2} U T, T contido em {3,...,2000}). Assim, continuando a ideia, a
soma dos menores é m = 1*2^1999 + 2*2^1998 + ... + 1999*2^1 + 2000*2^0
(contamos aqui {2000})
A dos maiores é essencialmente o mesmo raciocínio: obtemos a soma M =
2000*2^1999 + 1999*2^1998 + ... + 2*2^1 + 1*2^0 (contamos aqui {1}).
A soma de todos os a_X's é, então, m + M = 1*2^1999 + 2*2^1998 + ... + 1999*2^1
+ 2000*2^0 + 2000*2^1999 + 1999*2^1998 + ... + 2*2^1 + 1*2^0. Colocando em
evidência por potência de 2, obtemos sempre 2001*2^k. Assim, a soma de todos os
a_X's é 2001(2^1999 + 2^1998 + ... + 2^1 + 2^0) = 2001(2^2000 - 1) (nesse
último passo usamos a soma da PG de 2000 termos com razão 2 e primeiro termo
1). Mas há 2^2001 - 1 subconjuntos não vazios, então a média pedida é 2001.
[]'s
Shine
________________________________
From: João Maldonado <joao_maldona...@hotmail.com>
To: obm-l@mat.puc-rio.br
Sent: Saturday, December 10, 2011 2:07 PM
Subject: [obm-l] RE: [obm-l] Re: [obm-l] Moldávia-2000
Foi exatamente o que eu fiz.
Vou tentar expor minha solução aqui
Notação -> (a, b) são todos os subconjuntos com menor elemento a e com maior
elemento b
(1, 2000) -> Temos C(1998, 0) + C(1998, 1) + C(1998, 2)... + C(1998, 1998)
possibilidades. Logo Soma = 2001.2^1998
(1, 1999) -> 2000.2^1997
.
.
.
(1, 2) -> 3.2^0
(2, 2000) -> 2002.2^1997
.
.
.
(2, 3) -> 5.2^0
.
.
.
(1999, 2000) -> 3999.2^0
Falta agora calcular essa soma.
Seja a soma S(a) a soma de todos os subconjuntos que começam por a, temos
S(a) = (a, 2000) + (a, 1999) +... + (a, a+2) + (a, a+1) = (2000+a).2^(1999-a)
+ (1999+a).2^(1998-a) +... + (2a+1).2^0 = 2a.( 2^(1999-a) + 2^(1998-a)
+...+2^0)) + (2000-a). 2^(1999-a) + (1999-a).2^(1998-a) +... + 1.2^0
Sendo (2000-a). 2^(1999-a) + (1999-a).2^(1998-a) +... + 1.2^0 = K(a)
Sabemos que (x+1).2^x +...+1.2^0 = (x+2).(2^x + 2^(x-1) +... + 2^ 0) - (1.2^x
+ 2.2^(x-1) + 3.2^(x-2) +... +(x+1)2^0) = (x+2).(2^(x+1)-1) - ((2^x + 2^(x-1)
+...+(2^0)) + (2^ (x-1)+ 2^(x-2) +...+(2^0)) + (2^ (x-2)+
2^(x-3) +...+(2^0)) + (2^ (x-3)+ 2^(x-4) +...+(2^0)) +... + (2^2
+ 2^1 + 2^0) + (2^1 + 2^0) + 2^0)) =
(x+2).(2^(x+1)-1) - ((2^(x+1)-1) + (2^x-1) +... +(2^1-1)) = (2^(x+2)-2 - (x+1)
= (x+2).(2^(x+1)-1) - (2^(x+2) - x - 3) = x.2^(x+1) + 1
Substituindo x por 2000-a, temos
K(a) = (2000-a)2^(2001-a) + 1
S(a) = 2a(2^(2000-a)-1) + (2000-a).2^(2001-a) + 1 = 4000. 2^(2000-a) - 2a + 1
A soma total vale S(a) com a variando de 1 até 1999 + (1+2+3...+2000) =
4000.(2^2000-2) - 2( 1999.2000)/2 + 1999 + 2000.2001/2 = 4000(2^2000-1)
-1999001
Dividindo por 2^(2000-1) Temos que a média é aproximadamente 4000, o que é
impossível já que nem existe um termo maior que 3999
O interessante é que ontem obtive uma média de quase 2000, o que é
plausível, devo ter errado em alguma coisa
Pessoalmente, este método é bastante complicado e demorado para uma olimpíada
de matemática.
Não há um método mais fácil?
Se não, no que eu errei?
[']s
João
________________________________
From: luca...@dcc.ufba.br
Date: Sat, 10 Dec 2011 09:08:21 -0200
Subject: [obm-l] Re: [obm-l] Moldávia-2000
To: obm-l@mat.puc-rio.br
2011/12/10 João Maldonado <joao_maldona...@hotmail.com>
>
>
>106) Moldávia-2000 Para cada subconjunto não vazio X do conjunto M = {1, 2,
>..., 2000}, seja a_x a soma do menor com o maior elemento de X. Determine a
>média aritmética de todos tais números a_x assim obtidos.
>
>
>Parece que consegui uma solução de um jeito extremamente complicado de se
>generalizar (tentei fazer as contas mas devo ter errado em algo). Alguém tem
>uma outra solução para esse problema?
>
>
>
>
>Obs. O problema está na página 42 da Eureka! 11
Uma idéia: fixe um par de números de M, multiplique sua soma pela quantidade de
subconjuntos que os tem como primeiro e último números e então faça o mesmo
para todos os outros pares e some seus resultados. Isso dá uma expressão
fechada para conjuntos M que estejam em progressão aritmética.
--
[]'s
Lucas
=========================================================================
Instruções para entrar na lista, sair da lista e usar a lista em
http://www.mat.puc-rio.br/~obmlistas/obm-l.html
=========================================================================
