Based on the following riddle I have a mathematical question:
A salesman sells two kinds of candy that look alike very much except that one kind is 1 gram heavier than the other one. The salesman has 11 bags of candy. Each bag contains either one kind of candy, or the other, so no mix. Each bag contains 1000 pieces of candy.
He want to use his scale only once and he wants to know what kind of candy each of the bags contains. How does he solve this?
$2^{10}$ yields 1024, which is a problem since each bag contains maximum 1000 pieces of candy. However, by splitting the first piece of candy in half a solution can be found: $\frac{1}{2}$ from the first bag, 1 from the second, 2 from the third, 4 from the fourth etc.
Now my question is this: are there any solutions to this riddle that don't force us to split the candy? My intuition says no, but how to prove?
For example: how can we we sure that possibilities like 100, 101, 102, 104, 108, 116 etc... don´t work in principle? (of course you can show it by calculating all possibilities, but that's not elegant)
Edit Most elegant solution so far: {1000-0, 1000-1, 1000-2, 1000-4,...,1000-512}
Yes! There are more efficient answers. Here is one, from https://oeis.org/A096858: $$\{285,433,510,550,570,581,587,590,592,593,594\}$$ This set of $11$ positive integers has the property that all $2^{11}$ of its subset sums are unique.
You can find out more by researching sets with unique subset sums and the Conway-Guy sequence. OEIS has a couple good links to start with.