Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Difficlut problem

  1. Oct 27, 2007 #1
    Let [tex]M[/tex] = {1, 2, ..., 2048}, and [tex]X \subset M[/tex] such that [tex]\left| X \right| = 15 [/tex].

    Show that there are two distinct subsets of [tex]X[/tex] whose sum of elements is the same.

    [tex]A,B \subset X[/tex] and [tex]A \cap B = \oslash[/tex]

    [tex]\sum_{\substack{a\in A}}a[/tex] = [tex]\sum_{\substack{b\in B}}b[/tex]

    Does this have something to do with the fact that 2^11=2048?
    Last edited: Oct 27, 2007
  2. jcsd
  3. Oct 27, 2007 #2


    User Avatar
    Science Advisor
    Homework Helper

    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.
  4. Oct 27, 2007 #3
    Ah, I see.

    Actually, I now see that this works for |X|>12, because I can choose 12 numbers in M such that
    So, this property does not hold for |X|=12.

    How do I prove that this property holds for |X|>12, though?
  5. Oct 27, 2007 #4
    This problem is similar. But in that problem you have enough to solve.
  6. Dec 10, 2007 #5
    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)
  7. Dec 10, 2007 #6
    I'm assuming that [tex]\left| X \right| = 15 [/tex] 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.
  8. Dec 10, 2007 #7
    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
  9. Dec 11, 2007 #8
    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?
  10. Dec 13, 2007 #9
    I mean: is this the correct interpretation?
  11. Dec 13, 2007 #10
    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 [tex]x_1, x_2, \dotsc, x_{n+2}[/tex], then there are [tex]\lambda_1, \dotsc, \lambda_{n+2}[/tex] not all 0 such that [tex]\lambda_1x_1 + \dotsb + \lambda_{n+2}x_{n+2}[/tex] and (here's the important part and where this differs from linear dependence) [tex]\sum_{i=1}^{n+2}\lambda_i = 0[/tex]

    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.
  12. Dec 14, 2007 #11
    No you can use fractorials to solve this. How many possible subsets of [tex]X[/tex] 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 lets see. The sum of the number of subsets of [tex]1,2,3,4, ....or |X| [/tex] 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.
    Last edited: Dec 14, 2007
  13. Dec 15, 2007 #12
    Well of course there is more than one way of doing this. I just said to use [tex]\mathbb{F}_3^k[/tex] 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.
  14. Dec 28, 2007 #13
    As ramsey said the solution comes from the fact that the power set [tex]\mathcal{P}[/tex] has more elements than the maximum sum of any subset. Let's now put the problem in a more general setting.

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

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

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

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

    And now we can play ball! :smile:

    If you choose [tex]N=2048[/tex] then the first natural number that makes [tex](*)[/tex] true is [tex]n=15[/tex].
    Of course someone could choose some [itex] n[/itex] and read from [tex](*)[/tex] the proper values of [tex] N[/tex]
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook