Show Equal Sums in Subset of {1,2,...2048} w/ Size 15

[Doom of Doom]

Let $$M$$ = {1, 2, ..., 2048}, and $$X \subset M$$ such that $$\left| X \right| = 15$$.

Show that there are two distinct subsets of $$X$$ whose sum of elements is the same.

ie.
$$A,B \subset X$$ and $$A \cap B = \oslash$$

$$\sum_{\substack{a\in A}}a$$ = $$\sum_{\substack{b\in B}}b$$Does this have something to do with the fact that 2^11=2048?

 

[CRGreathouse]

Does this have something to do with the fact that 2^11=2048?

Since 11 < 15, you can't make X a superincreasing sequence. If it was superincreasing you couldn't make a set with the required property.

 

[Doom of Doom]

Ah, I see.

Actually, I now see that this works for |X|>12, because I can choose 12 numbers in M such that
X={1,2,4,8,16,32,64,128,256,512,1024,2048}.
So, this property does not hold for |X|=12.

How do I prove that this property holds for |X|>12, though?

 

[Kummer]

This problem is similar. But in that problem you have enough to solve.

 

[al-mahed]

the sum off sucessives 2^1 + 2^2 + ... + 2^n is not equal to 2^(n+1)

1 + 2^1 + 2^2 + ... + 2^n = [2^(n+1) - 1]/(2-1)

 

[BoTemp]

I'm assuming that $$\left| X \right| = 15$$ means number of elements in X, right? I would suggest that whoever posed the problem was a bit too happy with the ellipses, and should've written
M= {1,2,3,4,5,...2048}.

I can't think of a more elegant proof than constructing a test case, though.
Take a 15 terms separated by two (2,4,6,...32), construct the sequence (1,3,5,...31) and change one of the terms so the sums work out. You could probably expand that into a better procedure, but 1 test case is all it takes.

 

[LukeD]

BoTemp: I think this is saying that it works for any X when |X| = 15, so showing that it works for 1 such X doesn't prove anything.

So... let me get this straight though, A and B are disjoint subsets of X. They don't necessarily partition X, right?

Seems a little similar to linear dependence, but we don't exactly have a ring here...

I'm guessing that this is why it's 15. But what is special about 15? Is there something special about 14 or 13? As someone said, 2^11 = 2048. That makes me suspect that it might work with some number higher than 13 from some Linear Algebra intuition. Since we have only integers, we will want to work over a finite field. I'm tempted to try to work in (F3)^11

 

[al-mahed]

Given 15 distinct elements of M (subset X), shows that there are allways at least two distinct subsets of X whose sum of elements is the same.

Is that correct?

 

[al-mahed]

Given 15 distinct elements of M (subset X), shows that there are allways at least two distinct subsets of X whose sum of elements is the same.

Is that correct?

I mean: is this the correct interpretation?

 

[LukeD]

Yes, I believe that that is the correct interpretation.

I'm currently taking a take home exam, so I can't think of this problem at the moment, but I can offer this:

If you can find the right way to represent each element of M and each sum as an element of F3^n where n is less than or equal to 13, then you'll have it proved.

The reason why is because if you have n+2 (or more) vectors in an n dimensional vector space, the n+2 vectors are affinely dependent. This means that, if your vectors are $$x_1, x_2, \dotsc, x_{n+2}$$, then there are $$\lambda_1, \dotsc, \lambda_{n+2}$$ not all 0 such that $$\lambda_1x_1 + \dotsb + \lambda_{n+2}x_{n+2}$$ and (here's the important part and where this differs from linear dependence) $$\sum_{i=1}^{n+2}\lambda_i = 0$$

Then you can put all of vectors with negative coefficients on the other side of the equation and you'll have 2 distinct subsets with the same sum.

 

[ramsey2879]

Let $$M$$ = {1, 2, ..., 2048}, and $$X \subset M$$ such that $$\left| X \right| = 15$$.

Show that there are two distinct subsets of $$X$$ whose sum of elements is the same.

ie.
$$A,B \subset X$$ and $$A \cap B = \oslash$$

$$\sum_{\substack{a\in A}}a$$ = $$\sum_{\substack{b\in B}}b$$


Does this have something to do with the fact that 2^11=2048?

No you can use fractorials to solve this. How many possible subsets of $$X$$ are there? How many sums are there that are less than say (15*2048) - 120? I think that there are more possible subsets then there are possible sums! Note that if there are subsets that have the same sum but are not distinct, then you can remove the common elements to form distinct subsets having the same sum.
Edit: Well let's see. The sum of the number of subsets of $$1,2,3,4, ...or |X|$$ elements is 2^X less 2. (Example subsets of 1,2,or 3 elements of a set of 4 elements is 1+4+6+4+1 - 2 = 2^4-2). That is over 2048 more subsets than the maximum possible sum so there must be more than that many subsets with the same sum. Take such subsets and exclude the common elements and you have your distinct subsets with the same sum.

 

[LukeD]

Well of course there is more than one way of doing this. I just said to use $$\mathbb{F}_3^k$$ because then we don't need to worry about counting sums or anything at all. If you can represent the elements properly, it just becomes a really simple linear algebra problem.

 

[Rainbow Child]

... How do I prove that this property holds for |X|>12, though?

As ramsey said the solution comes from the fact that the power set $$\mathcal{P}$$ has more elements than the maximum sum of any subset. Let's now put the problem in a more general setting.

Let $$M$$= {1, 2, ..., N}, and $$X \subset M$$ such that $$\left| X \right| = n<N$$. Which is the relation that $$(N,\,n)$$ must obey in order to have the desired property?

• The subset of $$X$$ with the maximum sum of it's elements is the one with the last $n$ elements, yielding to
  $$s_{max}=\sum_{j=N-n+1}^{N}j\Rightarrow s_{max}=\frac{2\,N-n+1}{2}\,n$$
• The number $\alpha$ of the possible subsets of $$X$$, is the number of the elements of the power set $$\mathcal{P}(X)$$, i.e. $$\alpha=2^n-2$$ where the term -2, comes out because we exclude $${\emptyset,\,X}$$

Thus in order to have the desired property we must have more subsets than the maximum sum, i.e.

$$\alpha>s_{max}\Rightarrow 2^n-2>\frac{2\,N-n+1}{2}\,n \quad (*)$$

And now we can play ball!

If you choose $$N=2048$$ then the first natural number that makes $$(*)$$ true is $$n=15$$.
Of course someone could choose some $n$ and read from $$(*)$$ the proper values of $$N$$