On Wed, 3 Oct 2012, Victor Miller wrote
Say that a finite set of integers, A, has *property P* is there are two non-empty disjoint subsets S and T of A, such that sum(S) = sum(T) (where sum(X) is the sum of the elements of X).
1) Show that every 10 element subset of {1,...,100} has property P (this is fairly easy). 2) Is it true that every 9 element subset of {1,...,100} has property P?
I saw this several years ago and came up with a cute solution to part 2. First, part 1: There are 1024 subsets of A, each of which has sum in the range from 0 to 1000, so by the pigeon-hole principle, two of the sums must be equal. Remove their intersection from each to get two disjoint subsets with the same sum. Now part 2: We restrict to a certain collection of sums, namely those of at most 6 numbers, but including at least 2 of the 6 largest ones. There are 2^9 = 512 total sums. There are 1 + 9 + 36 sums of 9, 8, or 7 numbers. There are 2^3 = 8 subsets of the smallest three numbers, so there are 8*(1 + 6) subsets containing at most 1 of the 6 largest numbers. So there are 512 - 46 - 56 = 410 sums in our collection. The largest sum in our collection is the sum of the 6 largest numbers, while the smallest is the sum of the 5th and 6th largest numbers. The difference between these is the sum of the 4 largest numbers, so all of our sums are in a range of size at most 100*4 + 1 = 401 < 410. Thus two sums are equal, and we are done, as above. In fact, if you just know that the numbers are at most 103, then 103 + 102 + 101 + 100 + 1 < 410 still tells you that two disjoint sums are equal. In other words, if you have 9 natural numbers with distinct sums, the largest is at least 104. More complicated arguments can get you the exact bound, but it's interesting that this argument gets you this far, so it might have been the intent of the original poser. David P. Moulton