Split integer numbers from 1 to 31 into sets such that a maximum value in each set is the sum of the others. This is a problem from mathematical contest for kids.
Split integer numbers $1, 2,\ldots, 31$ into sets such that a maximum value in each set is the sum of the others, or show that it's impossible.
My analysis so far has been that if we suppose that it's possible, and we end up with the collection of sets $G$, then if we denote the maximum element of each set $g \in G$ as $m(g)$, 
$$\sum_{x \in g} x = \sum_{x \in g \setminus {m(g)}} x + m(g) = 2 \cdot m(g)$$
$$\sum_{i=1}^{31}i = \sum_{g \in G} \sum_{x \in g} x = \sum_{g \in G} 2 \cdot m(g) = 2 \cdot \sum_{g \in G} m(g) $$
However 
$$\sum_{i=1}^{31}i = \frac{1 + 31}{2} \cdot 31 = 16 \cdot 31$$
So 
$$2 \cdot \sum_{g \in G} m(g) = 16 \cdot 31$$ and
$$ \sum_{g \in G} m(g) = 8 \cdot 31$$
Thus I need to find a set of maximum elements sum of which is 31, and then for each of the maximum elements, augment their sets by some other numbers so that their sum is equal to the respective maximum elements.
I wasn't able to analyse it further, and when I tried to work out the solution by hand, somehow I always was unable to find a required partition. 
There seem to be many ideas to prune the search (like 31 will be a maximum element, then it's either that we take $31 = 30 + 1$ and then $29$ will be a maximum element, or we'll have $31$ and $30$ as maximum elements). However I still don't see how this could be done without the use of a computer. Implementing a search procedure in a programming language should also be an interesting problem, and I think it could be done, but if it won't find a solution, I think such a brute force rejection won't be considered as a satisfactory solution in a sense that there should be some less computationally hard argument.
 A: The sum of all the numbers is $ \frac{31\times32}{2} = 496$.
The sum of the maximum values in all the subsets is $\frac{496}{2} = 248$. 
Since each subset has at least 3 elements, we have $|G| \leq \frac{31}{3}$.
If $|G| \leq 9$, then the sum of the subsets is at most $ 31+30+29+ \ldots + 23 = 243 < 248 $, hence a contracdiction.
Hence, $|G| = 10$. We have 9 sets of 3 elements and 1 set of 4 elements. 
We play around with the numbers to discover that the following sets work:
$ \{ 31, 28, 3 \} $
$ \{ 30  , 29  , 1  \}$
$ \{ 27  , 20  , 7  \}$
$ \{ 26  , 18  , 8  \}$
$ \{ 25  , 16  , 9  \}$
$ \{ 24  , 14  , 10  \}$
$ \{ 23  , 11  , 12  \}$
$ \{ 22  , 17  , 5  \}$
$ \{ 21  , 15  , 4, 2  \}$
$ \{ 19  , 13  , 6  \}$ 
Note: Because this is a competition problem, and there doesn't seem to be another argument that leads to a contradiction, we believe that a solution exists. 
The idea I was pursuing was to maximize the minimum of the maximum of the subsets, and try to derive a contradiction. 
We can show that the max is 20, which leads to $ 31, 29, 27, 26, 25, 24, 23, 22, 21, 20 $, but that requires $31=30+1, 29=28+1$.
With a max of 19, that yields the above construction. 
