Today’s puzzle
-
It seems tempting to count the number of disjoint set pairs (which I take to mean not overlapping) available from a set of 10 things, and compare that with the total number of possible different sums, which seems to be around 955 (the possible range being 1 to 955). If that ratio is greater than 1, it's impossible for the guy to win the bet. It still may be impossible if the ratio is less than 1, but greater than 1 is sufficient proof that it is impossible.
-
-
well it doesn't have the nice insight that you're looking for but it's not too difficult to count the number of 10 choose n for n of 1 to 5 and multiply the sum by 2. You multiply by 2 because for every combination of n from 10, for n=1 to 5, you have the complementary set of size 10-n. Each set must sum to a unique number. Except you don't multiply by 2 for the size 5 set, since 10 choose 5 accounts for both the primary and complimentary sets.
10 choose 1 = 10
10 choose 2 = 45
10 choose 3 = 120
10 choose 4 = 210
10 choose 5 = 252(10+45+120+210)*2 + 252 = 1022, meaning the bet is impossible for the guy to win because that's more than the possible number of unique sums.
-
The insight is that 'disjoint sets' is a red herring.
If you had non-disjoint sets that had equal sums, then you just take out the common member(s) and they still are equal.
So you just figure out how many unique sets you can make out of 10 objects, which is 2^10, but subtract 1 because 0000000000 isn't a valid set.
So 1023 non-empty sets, which is greater than 955.
