1

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.

Andrey Surovtsev
  • 559
  • 1
    $\sum_{g \in G} m(g) = 8 \cdot 31$ implies $|G|>8$. On the other hand, each $g\in G$ must contain at least 3 elements. Thus, $|G|\leqslant \frac{31}{3}$, hence $G\leqslant 10$. – Olivier Roche Nov 08 '19 at 09:24
  • 1
    @OlivierRoche, thank you! $|G| = 9$ can't be true because $sum_{i=23}^{31} = 243 < 248 = 8 \cdot 31$. Thus the only possibility is that $|G| = 10$. Still couldn't get any further, but I'll ponder upon it, maybe I'll have to satisfy with the brute-force style solution, just taking into account that $sum_{i=22}^{31} = 265$, and $265 - 248 = 17$, so we have to decrease the maximum sum by 17, which probably leaves not so much variants to consider. – Andrey Surovtsev Nov 08 '19 at 16:46
  • @OlivierRoche following these ideas I managed to find a solution! I don't feel so much of a satisfaction because it didn't feel that the process of finding the solution was well directed. Instead it felt like I was performing some sort of manual search procedure which ended up well, but I could have as well miss the right trajectory, or didn't play with the sets long enough to get the solution. In this case I would probably write a brute force implementation and with your constraints on $G$, it would be if not straightforward then manageable at least. – Andrey Surovtsev Nov 08 '19 at 21:02
  • @OlivierRoche Thus such a solution probably wouldn't be something that was intended by designers of the problem. However I suppose I'm too picky and actually a bit of analyzing and a bit of playing with numbers that I managed to do based on your hint was exactly what they expect on a math contest. I wonder why didn't you post your input as an answer, I would have marked it then – Andrey Surovtsev Nov 08 '19 at 21:04

1 Answers1

1

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.

Calvin Lin
  • 68,864
  • Thank you! Using Olivier's hint I also have come up with an answer, but my search process was a bit less ordered, I think I cannot even reproduce it.. that's why I was a bit unsatisfied. My sets are: {31, 15, 16} {30, 17, 13} {29, 19, 10} {28, 22, 6} {27, 26, 1} {25, 18, 7} {24, 21, 3} {23, 14, 9} {20, 12, 8} {11, 5, 4, 2}

    Your idea of maximizing their minimum allows to organize that process a bit!

     – Andrey Surovtsev Nov 10 '19 at 15:51
  • 1
    Yea, it was hard to motivate the search. At times I was thinking that it wasn't possible, and at other times I was thinking that they chose a large enough number to make this possible. – Calvin Lin Nov 10 '19 at 15:56