[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
[obm-l] RE: [obm-l] Re: RE:_[obm-l]_Partição
Ok... Eu errei nas contas... Eu admito! Podem jogar as pedras! (rs)
Claudio, agora ficou fácil a proposta de generalizar o problema. Vou te
deixar pensando algum tempo e depois mando a resposta.
"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: Friday, February 21, 2003 2:24 PM
To: obm-l@mat.puc-rio.br
Subject: [obm-l] Re: RE:_[obm-l]_Partição
Oi, Rafael (e JG):
Bem observado, mas o engano é facilmente remediável. O que importa é que a
idéia do JG foi muito boa (e o que é melhor - produziu uma solução diferente
da que eu achei), mas ele errou nas contas e fez a quebra do conjunto do
meio (668 até 1334) no ponto errado. Ao invés de 1000, ele deveria ter
começado com 1001, de forma que o primeiro trio deveria ser (1,1001,2001), o
segundo (2,1002,1999), etc.
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 corrigidos passam a ser:
( 1,1001,2001)
( 2,1002,1999)
( 3,1003,1997)
...
(334,1334,1335)
e
(335, 668,2000)
(336,669,1998)
...
(667, 1000,1336)
Um abraço,
Claudio.
----- Original Message -----
From: "Rafael" <matduvidas@yahoo.com.br>
To: <obm-l@mat.puc-rio.br>
Sent: Friday, February 21, 2003 10:57 AM
Subject: RE:_[obm-l]_Partição
> Mas nas conas do JG a soma dos conjuntos dá 2002!!!
>
> Veja isso de novo:
> > > ( 1,1000,2001) não seria: (1, 1000, 2001)
> > > ( 2,1001,1999) (2, 1001, 1999)
> > > ( 3,1002,1997) (3, 1002, 1997)
> > > ...
> > > (333,1334,1335) (333, 1332, 1337)
> > > (334, 1333, 1335)???
> > > e
> > > (334, 668,2000)
> > > (335, 667,1998)
> > > ...
> > > (667, 999,1336)
>
> Alguma coisa está errada não?
>
> Abraços,
>
> Rafael.
>
>
>
> --- Cláudio_(Prática)
> <claudio@praticacorretora.com.br> escreveu: > 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
>
>
> > > 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.
>
> _______________________________________________________________________
> Busca Yahoo!
> O serviço de busca mais completo da Internet. O que você pensar o Yahoo!
encontra.
> http://br.busca.yahoo.com/
> =========================================================================
> 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>
=========================================================================