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

["Domingos Jr." <dopikas@xxxxxxxxxx>]

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.

Infelizmente não achei a mensagem original...

Fiz algum progresso nesse problema, vejam:

primeiramente dá pra perceber que p|k(k+1)/2, logo p|k ou p|k+1.

Vou provar que se k = 2pq é sempre possível particionar o conjunto.
k(k+1)/2 = pq(2pq+1)
portanto cada parte terá soma q(2pq+1). Defina
P_1 = {1, k, 2, k-1, 3, k-2, ..., q, k-q+1}
P_2 = {q+1, k-q, ..., 2q, k-2q+1}
...
P_p = {(p-1)q+1, k-(p-1)q, ..., pq, k-pq+1}

Com um pouco de reflexão vemos que os conjuntos acima de fato formam uma
partição de {1, 2, ..., k} e a soma dos elementos de cada partição é q(k+1)
= q(2pq+1), como desejado.

se k+1 = 2pq, podemos fazer algo similar:
k(k+1)/2 = pq(2pq-1)
portanto cada parte terá soma q(2pq-1) = qk. Defina
P_1 = {1, k-1, 2, k-2, ..., q, k-q}
P_2 = {q+1, k-q-1, ..., 2q, k-2q}
...
P_p = {(p-1)q+1, k-(p-1q)-1, ..., pq-1, k-pq+1} U {k}

que também serve de partição de {1, 2, ..., k} com a propriedade desejada,
ou seja, cada parte soma qk.

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?

[ ]'s

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