# Partition of equal size and equal sum

Let $p,q$ be odd primes. Is it always possible to partition $\{1,\ldots,pq\}$ into $p$ disjoint subsets $A_1,\cdots,A_q$ such that for all $i,j$ we have $|A_i|=|A_j|$ and $\sum_{x\in A_i}x=\sum_{y\in A_j}y$?

For example we can do that for $p=3$ and $q=5$.

Partition into 3 subsets: $\{1,4,10,12,13\},\{2,5,8,11,14\},\{3,6,7,9,15\}$

Partition into 5 subsets: $\{1,8,15\},\{2,9,13\},\{3,10,11\},\{4,6,14\},\{5,7,12\}$

-
Did you try proving it or finding counterexamples yourself? –  Yuval Filmus Apr 9 '11 at 15:42

First let me note the typo; $A_q$ should be $A_p$.

Now it turns out that much more is true; for any positive integers $m$ and $n$, with a few easy-to-understand exceptions, you can put the numbers $\{\,1,\dots,mn\,\}$ into an $m\times n$ array so that all the row sums are equal and all the column sums are equal.

E.g., for $m=3$, $n=5$, there's $$\pmatrix{1&13&10&4&12\cr8&2&11&14&5\cr15&9&3&6&7\cr}$$

So the rows give you a partition into $m$ subsets of equal size and equal sum, and at the same time the columns give you a partition into $n$ subsets of equal size and equal sum.

The only restrictions on $m$ and $n$ are they must both exceed 1; they must both be even or both be odd; they can't both be 2. In particular, primality is irrelevant.

I can't give a proof here, but it's done in Thomas R. Hagedorn, Magic rectangles revisited, Discrete Mathematics 207 (1999), 65-72.

-