I'm trying to solve this problem using the pigeon hole principle.
Suppose you have 2n possible integers $ \big\{x_{1},x_{2},x_{3},...x_{2n}\big\} $ where each integer can be represented using n bits. Prove that there exist two sets $ S_{1} , S_{2} \subseteq [2n] $ such that : $$ \sum_{i \in s_{1}} x_{i} = \sum_{i \in s_{2}} x_{i} $$
So, we know that for any 2n-set, the number of possible subsets is 4^n right? And given the fact that every positive integer can be represented as n bits, we can figure out the number of possible sums. Then if number of sets > number of sums, the pigeon hole principle can be applied. But I'm not sure about how to figure out the number of possible sums.
# Possible_Sums = BiggestP_Sum - SmallestP_Sum (not sure about that)
Biggest number with n bits : $ 2^n $
BiggestP_Sum = $\frac{2^n(2^n+1)}{2} - \frac{2n(2n+1)}{2} $ (sum of the 2n biggest numbers)
SmallestP_Sum = $\frac{2n(2n+1)}{2}$
So, Possible_Sums = $ \frac{2^n(2^n+1)}{2} - 2n(2n+1) $
Is this correct ?
Thanks !
You have the right idea, but a lot of the details are wrong. The largest number representable with $n$ bits is $2^n-1$, not $2^n$. However, the smallest is $0$, so there are $2^n$ different numbers representable with $n$ bits. The smallest $2n$ are $0$ through $2n-1$; their sum is
$$\frac{2n(2n-1)}2=n(2n-1)\;.$$
The largest $2n$ are $2^n-1$ through $2^n-2n$; their sum is
$$\frac{2n\big((2^n-1)+(2^n-2n)\big)}2=n(2^{n+1}-2n-1)\;.$$
The number of different sums is therefore at most
$$n(2^{n+1}-2n-1)-n(2n-1)+1=n2^{n+1}-4n^2+1\;.$$
(The $+1$ is necessary: if $a$ and $b$ are integers, and $a\le b$, the number of integers in the interval $[a,b]$ is $b-a+1$, not $b-a$.)
There are, as you said, $2^{2n}$ subsets of the set of $2n$ integers. To complete the argument, you need to show that
$$2^{2n}>n2^{n+1}-4n^2+1\;.$$