Subset-ly Different Sum

This problem involves constructive thinking. The statement asks us to get as many elements as possible within the given range. Start greedily with the two elements 1, 1. Of course we can't have 2 in the set, so next comes 3. We can't have 4, 5 in the set, so next comes 6. Next comes 12, then 24 and so on. This sequence has 12 elements before it exceeds 2017.

You should be able prove inductively that a new element cannot be less than 2 times the largest of the set/sequence constructed so far (which is akin to proving that any number less than that can be expressed by the previously constructed set).

if the desired set 's' has size 'z', then the number of distinct subset sums is 2^z. 'z' should be such that 2^z<=sum(s). when the largest member of the set is 2017, z is 14 or less. also its easy to see a way to create a set of size 11, simply use 2^0,2^1,2^2, ... 2^10. so the ultimate answer is a size of 11, 12, 13, or 14.

my feeling is that to maximize z, we want to make sum(s) large. thus starting from 2017 to 1, i wrote a program to add elements (from largest to smallest) to the set so long as it doesn't cause a duplicate sum, and skip elements that cause a duplicate sum. doing this resulted in a set of size 12. so the answer is 12, 13, or 14.

it turns out to be 12, but i guessed and didn't actually prove this fact.

Here is the (Matlab) code that I wrote for this problem. It starts with a set with two random elements and then adds a new random element in each loop (without repeating elements), where it tests tons of random, different-sized subsets against each other. If the sum is equal for any of the sets that are compared, then the loop breaks, and the element is not added to the set. The program runs the test 10 different times, and records the size of the final set each time in the array w. (It is far from optimized.) tic, c=10; w=zeros(c,1); for b=1:c, v=ceil(rand(1,2) 2017); a=randperm(2017); a=a(logical((a~=v(1)). (a~=v(2)))); for j=a, flag=0; for m=1:1200, for k=1:length(v)-1, for n=1:length(v), r=randperm(length(v)); s=randperm(length(v)); if k~=n, if sum([v(r(1:k)) j])==sum(v(s(1:n))), flag=1; break, end, elseif k==n && sum(v(r(1:k))~=v(s(1:n)))>0, if sum([v(r(1:k)) j])==sum(v(s(1:n))), flag=1; break, end, end, end, if flag==1, break, end, end, if flag==1, break, end, end, if flag==0, v=[v j]; end, end, w(b)=length(v); end, toc, w On my laptop, the code takes about 45 minutes. The average of the results was typically around 12.5, so I figured 12 was a good guess. A partial justification that testing such a tiny number of combinations of sets in comparison to every single possible set is that the number of total sums is significantly smaller than the number of total sets. This means you should expect to see the same sum appearing extremely often. I suspect there is a bound you can create using the Pigeonhole Principle that becomes violated whenever the set contains 13 or more elements. It would be cool to see someone prove that. Then the task would be to find a set with 12 elements where no two distinct subsets have the same sum.