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