Today’s puzzle

[jon-nyc]

That’s a reasonable starting place.

[jon-nyc]

The total number of possible sums is a bit less than that, since the min is 1+2+3+...+10.

[jon-nyc]

There’s a key insight which makes it trivial to compute in your head in milliseconds.

[Horace]

@jon-nyc said in Today’s puzzle:

The total number of possible sums is a bit less than that, since the min is 1+2+3+...+10.

We are supposed to consider sets of any size.

[jon-nyc]

Of course. My bad.

[Horace]

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.

[jon-nyc]

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.

[Horace]

I don't find that insight useful to arrive at the idea of counting unique combinations, but YMMV.

[jon-nyc]

No, just the easy calc. It's all the 10 digit binary numbers.

[Horace]

Yes, I like how binary digits map to the idea of including/excluding things from a set.