How would you prove this theory of computation problem?

Question

I have trouble proving the following statement, I'm supposed to do it for our theory of computation course but since I've been trying for days I'm looking for a hint :

What is the smallest value of $n\ge 1$ such that the following is true? (Write down the value if there is one and provide a proof of correctness of your argument or present a counterexample.) Let $S$ be a subset of $\{1,\ldots,n^2\}$ of cardinality exactly $n$. Then there are two disjoint and nonempty subsets of it whose elements sum up to the same value. That is to say there are $S_1$ and $S_2$ such that (1) $\emptyset\ne S_1,S_2\subset S$, (2) $S_1\cap S_2 = \emptyset$ and (3) $\sum_{i\in S_1} i = \sum_{j\in S_2} j$.

(original scan)

Clarifications : We want it to work for all possible subset S

So far, I tried with the Pigeonhole principle and with the fact that for (n+1) numbers we have (2n+1) more numbers in the set {1,2,...,(n+1)^2 } because I thought it would lead me somewhere with a proof by Induction but couldn't manage to do so.

I know there might be some missunderstanding with the statement so feel free to ask for clarifications and I'll edit in order to help you helping me :)

Thank you !

Answer 1

There are $2^n-1$ non-empty subsets of $S$. The maximum sum of one of them is $n^3-\frac 12n(n-1)$. At $n=10$ there are more subsets than possible sums, so two of them must have the same sum. That leaves (using MJD's comment) the range $7,8,9,10$ to resolve.

Answer 2

Hint: if there are two distinct subsets with the same sum, by removing the intersection you get two disjoint subsets with the same sum.

How many subsets of $S$ are there? How many possible sums? If there are more subsets than possible sums, Pigeonhole says there are two subsets with the same sum. This will get you a bound on $n$, though more work may be required to get the lowest possible $n$.

Answer 3

The answer is $8$. Here is the proof it is true for $8$ or $9$ and a sequence for $7$ is given. Although the Conway Guy sequence also works for length $7$. This link is also very interesting, and it proves the conway-guy sequence works for all lengths (which had only been established up to $79$ previously)