[obm-l] Re: [obm-l] RE: [obm-l] Partição

["Cláudio \(Prática\)" <claudio@xxxxxxxxxxxxxxxxxxxxxxx>]

Caro João Gilberto:

Obrigado pelos comentários. Os meus seguem abaixo:

----- Original Message -----
From: "João Gilberto Ponciano Pereira" <jopereira@vesper.com.br>
To: <obm-l@mat.puc-rio.br>
Sent: Thursday, February 20, 2003 1:23 PM
Subject: [obm-l] RE: [obm-l] Partição


> "2) Determine todos os inteiros positivos M tais que o conjunto {1 2, ...,
> 3M} admite uma partição em M subconjuntos de 3 elementos tal que a soma
dos
> elementos de cada subconjunto é constante."
>
> A Questão é... Como distribuir os elementos?
> Vamos imaginar uma seqüência de 6 consecutivos....
>
> n-2, n-1, n, n+1, n+2, n+3. Neste caso, podemos fazer 3 pares de forma que
a
> soma seja 2n-1:
> (n-2) e (n+3)
> (n-1) e (n+2)
> (n) e (n+1).
>
> Logo, se M for par, basta ir distribuindo os números de 6 em 6 (1 a 6, 7 a
> 12... 3M-6 a 3M), pelo método acima.
>
> E se M for ímpar? Neste caso, podemos dividir os 9 primeiros termos (1 a
9)
> em 3 grupos de soma igual:
> 1,5,9 = 15
> 2,6,7 = 15
> 3,4,8 = 15
> Para o restante, podemos seguir de 6 em 6. (1 a 9, 10 a 15, 16 a 21...1996
a
> 2001)
>
Tudo bem, mas o que o problema pede é uma partição em subconjuntos
(disjuntos) de 3 e não de 2 elementos. Além disso (e aí eu posso ter me
expressado mal) a soma dos três elementos de QUALQUER SUBCONJUNTO deve ser
constante, isto é, igual à soma dos três elementos de QUALQUER OUTRO
SUBCONJUNTO.

Como 1 + 2 + ... + 3M = 3M*(3M+1)/2, cada um dos M subconjuntos deve ter
soma igual a:
(1 + 2 + ... + 3M)/M = 3*(3M + 1)/2.

Aí, de cara, você já deduz que 3M +1 deve ser par ==> M deve ser ímpar.

Agora, o problema é achar para quais ímpares o problema é possível.

Você mesmo já deu uma solução para M = 3 (3M = 9). Uma segunda solução
seria:
{1,6,8}
{2,4,9}
{3,5,7}.

Com um pouco de esforço você acha uma partição para M = 5 (3M = 15):
Soma de cada subconjunto = 3*(3*5+1)/2 = 24
Uma partição possível:
{1,10,13}
{2,8,14}
{3,6,15}
{4,9,11}
{5,7,12}

Para M = 7 (3M = 21 e soma de cada subconjunto = 33)
{1,14,18}
{2,12,19}
{3,10,20}
{4,8,21}
{5,13,15}
{6,11,16}
{7,9,17}

A idéia, agora, é extrapolar a lei de formação das partições e ver se ele
funciona para cada M ímpar.
Meu chute é que sim, mas ainda não tenho uma prova.


> Proposta: Podemos pensar até num exercício um pouco mais elaborado, do
tipo:
>
> 3) Determine todos os inteiros positivos M tais que o conjunto {1 2, ...,
> kM} admite uma partição em M subconjuntos de k elementos tal que a soma
dos
> elementos de cada subconjunto é constante.
>
Soma dos elementos do conjunto inteiro = kM*(kM+1)/2

Soma de cada subconjunto = k*(kM + 1)/2 ==>
k é par ==> M pode ser qualquer inteiro positivo (a princípio)
ou
k é ímpar e (kM+1) é par ==> kM é ímpar ==> M é ímpar

Aqui, esperamos que a demonstração para o caso k = 3 (se e quando
encontrada) deve ser adaptável ao caso geral.

Um abraço,
Claudio.

> -----Original Message-----
> From: Cláudio (Prática) [mailto:claudio@praticacorretora.com.br]
> Sent: Thursday, February 20, 2003 12:34 PM
> To: obm-l@mat.puc-rio.br
> Subject: [obm-l] Partição
>
>
> Caros colegas da lista:
>
> Estou embananado com este aqui:
>
> 1) Prove que existe uma partição de {1, 2, ..., 2001} em 667 subconjuntos
de
> 3 elementos tal que a soma dos elementos de cada subconjunto é igual a
3003.
>
> 2) Determine todos os inteiros positivos M tais que o conjunto {1 2, ...,
> 3M} admite uma partição em M subconjuntos de 3 elementos tal que a soma
dos
> elementos de cada subconjunto é constante.
>
> Um abraço,
> Claudio.
>
> =========================================================================
> 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>
=========================================================================