# Pigeon Hole Principle (Same sum)

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\;.$$

• @Eric: You’re welcome! – Brian M. Scott Nov 19 '15 at 22:36