Legal! É uma solução diferente da minha e você foi mais "técnico" do que eu para achá-la.
O que eu fiz foi dividir o conjunto {1,2,...,2001} em três subconjuntos: A1 = {1,2,...,667} A2 = {668,669,...,1334} A3 = {1335,1336,...,2001} E começar a formar as partições (lidas verticalmente) com cada subconjuntinho de 3 elementos recebendo um elemento de A1, um de A2 e um de A3: A1: 0001 0002 0003 ... 0333 0334 0335 0336 ... 0666 0667 A2: 1334 1332 1330 ... 0670 0668 1333 1331 ... 0671 0669 ou seja, eu coloquei os elementos de A1 em ordem crescente de 1 em 1 e os de A2 em ordem decrescente de 2 em 2 (mod 2). Finalmente, eu coloquei os elementos de A3 de modo que cada soma fosse igual a 3003 meio torcendo pra dar tudo certo, com base nos casos especiais (M=3, 5 e 7) que eu fiz na mão e deram certo. No entanto, uma vez concluída a partição, é fácil ver que tudo daria certo, pois a soma dos dois primeiros elementos colocados em cada subconjuntinho eram todas distintas: 1335 1334 1333 ... 1003 1002 1668 1667 ... 1337 1336 Além disso: 3003 - 1668 = 1335 ==> todos os complementos estavam em A3. Um abraço, Claudio. ----- Original Message ----- From: "João Gilberto Ponciano Pereira" <[EMAIL PROTECTED]> To: <[EMAIL PROTECTED]> Sent: Thursday, February 20, 2003 5:26 PM Subject: [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:[EMAIL PROTECTED]] > Sent: Thursday, February 20, 2003 3:43 PM > To: '[EMAIL PROTECTED]' > 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:[EMAIL PROTECTED]] > Sent: Thursday, February 20, 2003 1:23 PM > To: '[EMAIL PROTECTED]' > 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:[EMAIL PROTECTED]] > Sent: Thursday, February 20, 2003 12:34 PM > To: [EMAIL PROTECTED] > 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 é <[EMAIL PROTECTED]> > ========================================================================= > ========================================================================= > 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 é <[EMAIL PROTECTED]> > ========================================================================= > ========================================================================= > 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 é <[EMAIL PROTECTED]> > ========================================================================= ========================================================================= 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 é <[EMAIL PROTECTED]> =========================================================================