Last question

  • #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.
 

Answers and Replies

  • #2
quasar987
Science Advisor
Homework Helper
Gold Member
4,783
18
?!
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?
 
  • #3
1,425
1
?!
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?

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:
  • #4
291
0
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.

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:
1,2,...,13,1000
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.
 
  • #5
Kummer,
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:

Related Threads on Last question

  • Last Post
Replies
7
Views
3K
  • Last Post
3
Replies
53
Views
14K
  • Last Post
Replies
2
Views
2K
  • Last Post
Replies
20
Views
2K
  • Last Post
Replies
5
Views
4K
  • Last Post
Replies
3
Views
2K
Replies
13
Views
968
  • Last Post
Replies
12
Views
2K
  • Last Post
Replies
4
Views
2K
  • Last Post
3
Replies
65
Views
10K
Top