Re: [obm-l] Particionando {1,2,..., k}

["Fabio Dias Moreira" <fabio@xxxxxxxxxxxxxxxxxxx>]

Domingos Jr. said:
> Olá, tinha um problema na lista que perguntava o que se pode dizer sobre
> k, um inteiro para o qual, dado um primo p, podemos particionar
> {1, 2, 3, ..., k} em p partes cuja soma de elementos em cada parte é a
> mesma.
> [...]
> Agora a questão que fica é, se p|k e k/p é ímpar ou p|k+1 e (k+1)/p é
> ímpar, é possível particionar o conjunto em p partes de mesma soma?
> [...]

Se você souber fazer o problema para {1, 2, ..., 3p}, você sabe fazer para
{1, 2, ..., qp}, q ímpar: particione o conjunto {3p+1, 3p+2, ..., qp} em p
conjuntos de mesma soma (isso é possível pois a sua partição de {1, 2,
..., (q-3)p} tem o mesmo número de elementos em cada parte do conjunto,
logo somar 3p a todos os elementos das partições mantém as p somas
iguais). Junte cada uma desses pedaços com um elemento da partição de {1,
2, ..., 3p}, e acabou.

Logo, para o caso k ímpar, p|k, basta resolver, na realidade, o problema
de particionar {1, 2, ..., 3p} em conjuntos de 3 elementos com a mesma
soma. Não me falhando a memória, o Paulo Santa Rita resolveu esse problema
aqui na lista há algum tempo atrás.

[]s,

-- 
Fábio "ctg \pi" Dias Moreira


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