[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
[obm-l] Re: [obm-l] RE: [obm-l] RE: [obm-l] RE: [obm-l] Partição
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" <jopereira@vesper.com.br>
To: <obm-l@mat.puc-rio.br>
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: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>
> =========================================================================
=========================================================================
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>
=========================================================================