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

[João Gilberto Ponciano Pereira <jopereira@xxxxxxxxxxxxx>]

Ops!! Sorry! Parece que entendi o problema de forma errada... Estava fazendo
3 conjuntos de M elementos, e não M conjuntos de 3 elementos, como pedia o
problema.... Neste caso, temos o seguinte:

A soma total dos elementos do conjunto é 3M *(3M+1)/2. Como os conjuntos de
3 elementos deve ter soma igual, esta soma deverá ser de 3M*(3M+1)/2/M =>
Soma = (9M + 1)/2. Já é possível concluir que M é obrigatoriamente ímpar.

Agora, podemos considerar a seqüência com a seguinte nomenclatura:

a(1,-n), a(1,-n+1), ... a(1,0), ... a(1,n)
a(2,-n), a(2,-n+1), ... a(2,0), ... a(2,n)
a(3,-n), a(3,-n+1), ... a(3,0), ... a(3,n)
Com n de -(m-1)/2 a (m-1)/2

Onde a(i,j) = j+(M-1)/2 + M*(i-1) + 1

Se considerarmos que, em cada subconjunto válido, teremos um elemento de
cada linha, temos

a(i1,1) + a(i2,2) + a(i3,3) = (9M+1)/2 = j1 + j2 + j3 + 3*(M-1)/2 + M*((1-1)
+ (2-1) + (3-1)) + 3

Resumindo, temos que j1 + j2 + j3 = 0. Exemplo:

 1  2  3  4  5
 6  7  8  9 10
11 12 13 14 15

fica:
-2 -1 0 1 2
-2 -1 0 1 2
-2 -1 0 1 2

Os conjuntos podem ser:(-2, 1, 1) (-1,-1, 2) ( 0, 2,-2) ( 1, 0,-1) ( 2,-2,
0)
Traduzindo:            ( 1, 9,14) ( 2, 7,15) ( 3,10,11) ( 4, 8,12) ( 5,
6,13)

Ou seja, temos que provar que, sejam S1, S2, S3 conjuntos idênticos =
(-n...,0,1,2,...n)
Devemos formar 2n+1 trios (um elemento de cada conjunto), tais que a soma do
trio seja zero.

Acho que vale para qualquer n, mas preciso pensar mais um pouco...

-----Original Message-----
From: João Gilberto Ponciano Pereira [mailto:jopereira@vesper.com.br]
Sent: Thursday, February 20, 2003 1:23 PM
To: 'obm-l@mat.puc-rio.br'
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)
 
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.

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