Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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\}$

share|improve this question
    
Did you try proving it or finding counterexamples yourself? –  Yuval Filmus Apr 9 '11 at 15:42

1 Answer 1

up vote 6 down vote accepted

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.

share|improve this answer
    
So... in a week or so? –  Asaf Karagila Jan 11 at 0:20

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.