[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
[obm-l] RE: [obm-l] RE: [obm-l] RE: [obm-l] Partição
Complementando a resposta...
-n, -n+1, -n+2... n-2, n-1, n
-n, -n+1, -n+2... n-2, n-1, n
-n, -n+1, -n+2... n-2, n-1, n
Podemos formar os n+i primeiros trios da seguinte forma:
(-n+i,i,n-2*i), com i de 0 a n. Repare que a soma é zero.
Os últimos n termos são:
(i+n, -n+i -1, n-2*i+1), com i de 1 a n. Mais uma vez, a soma é zero.
Se considerarmos o Item 1, até 2001, temos:
1 2 3 ... 332 333 334 ... 665 666 667
668 669 670 ... 999 1000 1001 ... 1332 1333 1334
1335 1336 1337 ... 1666 1667 1668 ... 1999 2000 2001
Os trios seriam:
( 1,1000,2001)
( 2,1001,1999)
( 3,1002,1997)
...
(333,1334,1335)
e
(334, 668,2000)
(335, 667,1998)
...
(667, 999,1336)
SDS
JG
-----Original Message-----
From: João Gilberto Ponciano Pereira [mailto:jopereira@vesper.com.br]
Sent: Thursday, February 20, 2003 3:43 PM
To: 'obm-l@mat.puc-rio.br'
Subject: [obm-l] RE: [obm-l] RE: [obm-l] Partição
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>
=========================================================================
=========================================================================
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>
=========================================================================