6
$\begingroup$

I have a set containing numbers $1$ to $49: \{1,2,3, \cdots, 49\}$.

Now, I want to divide the set into $7$ subsets such that each subset should contain $7$ elements and sum of the elements of each subset should be $175$.

Is it possible to prove that such subsets exist?

  • 1
    I retagged this to combinatorics, which is the appropriate tag I believe.2010-09-06

2 Answers 2

12

Lookup Magic Squares.

which has the following:

22  47  16  41  10  35  4
5    23  48  17  42  11  29
30  6   24  49  18  36  12
13  31  7   25  43  19  37
38  14  32  1   26  44  20
21  39  8   33  2   27  45
46  15  40  9   34  3   28
7

Magic squares are fine, but here any single 7x7 Latin square works. An $n\times n$ Latin square is a square with the property that all the integers $1\ldots n$ appear exactly once on each row and column. There are several ways of constructing these. When $n=7$ we have for example the following $$ \begin{array}{ccccccc} 1&2&3&4&5&6&7\\ 7&1&2&3&4&5&6\\ 6&7&1&2&3&4&5\\ 5&6&7&1&2&3&4\\ 4&5&6&7&1&2&3\\ 3&4&5&6&7&1&2\\ 2&3&4&5&6&7&1\\ \end{array} $$

Given an $n\times n$ Latin square we can construct a solution to this problem (or its generalization of partitioning the integers $\{1,2,\ldots,n^2\}$ into $n$ equal sum groups of $n$ each) as follows.

Add $n(i-1)$ to all the entries on row $\#i$. After that the sum of the entries on any column equals $\sum_{i=1}^ni+ n\left(\sum_{i=1}^{n}(i-1)\right)$, which is manifestly independent of the column. Furthermore, the integer $n(i-1)+j$, $1\le i,j\le n$, can only appear on row $\#i$, and does occur there exactly once (wherevere the entry $j$ of that row of the Latin square resides). The above 7x7 Latin square gives rise to the groups $$\{1,7+7=14,6+14=20,5+21=26,4+28=32,3+35=38,2+42=44\}$$ from the first column, $\{2,8,21,27,33,39,45\}$ from the second, $\{3,9,15,28,34,40,46\}$ from the third column, and so forth.

It is also possible to construct magic squares from Latin squares, but then you need richer structure. You need two so called mutually ortogonal Latin squares (=MOLS).