0
$\begingroup$

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 !

$\endgroup$
1
$\begingroup$

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

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.