1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Last question

  1. Jul 8, 2007 #1
    so embarrased askin so much :redface:

    On a table there are 14 cards. On each card there is a number between 1 to 1000. Show it is possible to divide the cards into two piles so that the total sums are the same.
  2. jcsd
  3. Jul 8, 2007 #2


    User Avatar
    Science Advisor
    Homework Helper
    Gold Member

    Let card #1 to #13 all have the number 1 and let the 14th card have number 1000. 13 is not the same as 1000. Maybe you read or wrote the problem wrong?
  4. Jul 8, 2007 #3
    Though I think she means that all cards have a different number assigned to them, it doesn't take away the fact that the hypothesis presented is wrong. Suffice to have among the fourteen cards an odd number of cards having odd numbers assigned to in order for it to be impossible.
    Last edited: Jul 8, 2007
  5. Jul 8, 2007 #4
    As the two posters said you have indeed made a mistake.

    The correct version of the problem should be:
    "Given 14 cards with numbers from 1 to 1000 on them show that you can choose some of those cards to be divided into two piles with equal sums"

    For example, as Werg22 said let the cards be:
    Then your original formulation is false. By the correct formulation on top you can choose some of those cards, i.e. 1,2,3 and divide those into two equal piles, i.e. (1+2) and (3).

    To prove this we need to state this problem in a different manner involving sets.
    "Let S be a set of 14 numbers, with each number between 1 and 1000. Show that there exists two proper disjoint subsets A and B such that sum(A) = sum(B)"

    There are 2^14 - 2 = 16382 possible subsets. Each subset will be assigned a number, that number is the sum of its elements. Now the lowest possible sum is 1 and the largest is 1000+999+...+992 = 8964. So there are 8964 possible set sums. Since 16382 > 8964 there exists two distinct (but not necessarily disjoint) sets A and B with sum(A) = sum(B) by the Pigeonhole Principle. If A and B are disjoint then we are done. If not the remove the elements that they have in common, that will preserve their sums (and the sets do not vanish because they are distinct). So we will end up with two disjoint sets with equal set sums.
  6. Oct 28, 2007 #5
    in your solution, why does the largest sum only have 9 numbers in it? Shouldn't it be the sum of the largest 13 numbers?
    Last edited: Oct 28, 2007
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook