• 0
Sign in to follow this  
Followers 0

Fourteen sacks of gold

Question

Posted · Report post

A treasure hunter has just found 14 sacks of gold on a pedestal in a temple. The problem is, by taking the gold sacks he awakened the two guardians of the temple and was captured. The guardians have agreed to spare his life if he can give to both of them the same non-zero amount of gold, without opening the sacks.

  • Each sack is marked with a distinct 3 digit number (anything from 001 to 999) and contains that much gold.
  • After the guardians have received their gold, the treasure hunter must place all remaining gold sacks back on the pedestal.

To make this more difficult for you, I will not tell you how much gold each sack contains. Instead I will ask you to show that the treasure hunter can always appease the guardians.

A more mathematical way of phrasing the problem: given a set of 14 integers S = {n1, n2, ..., n14}, where 0 < ni < 1000 for all i, show that there must exist two disjoint non-empty subsets of S with the same sum.

0

Share this post


Link to post
Share on other sites

2 answers to this question

  • 0

Posted · Report post

There is a set of ten sacks for which this fails.

Suppose the numbers were 2n, n = 0, 1, 2, ..., 9, after which we'd need 4 digits.

These numbers form a basis set, none of which are combinations of the others.

But if we add a 3 to the set, we can always get two equal sets:

1 + 2 = 3

1 + 3 = 4

1 + 3 + 4 = 8

1 + 3 + 4 + 8 = 16

etc.

0

Share this post


Link to post
Share on other sites
  • 0

Posted · Report post

There are 2^14-1 = 16383 non-empty subsets of S, sum of each non-empty subset of S is a positive integer <= 14*999 = 13986.


There have to exist two distinct non-empty subsets of S, call them A and B, with the same sum (due to the pigeonhole principle).
(A-B) and (B-A) are non-empty disjoint subsets of S with the same sum.

0

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!


Register a new account

Sign in

Already have an account? Sign in here.


Sign In Now
Sign in to follow this  
Followers 0

  • Recently Browsing   0 members

    No registered users viewing this page.