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.

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?

share|improve this question
1  
I retagged this to combinatorics, which is the appropriate tag I believe. –  Asaf Karagila Sep 6 '10 at 15:40
add comment

2 Answers

up vote 12 down vote accepted

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
share|improve this answer
add comment

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).

share|improve this answer
add comment

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.