Today’s puzzle

[George K]

@Doctor-Phibes

[Doctor Phibes]

How vulgar.

[Klaus]

@jon-nyc said in Today’s puzzle:

Amy asks Brad to pick ten different numbers between 1 and 100, and to write them down secretly on a piece of paper.

She now tells him she's willing to bet $100 to $1 that his numbers contain two nonempty disjoint subsets with the same sum! Is she nuts?

My first guess would be that there are so many ways to form subsets that two disjoint ones necessarily must have the same sum. A kind of pigeonhole principle.

That would involve the addition of a couple of binomial coefficients...

Will look into this more later. No time right now.

[jon-nyc]

Bumping this in case Klaus wants to revisit.

Will post answer later if he doesn’t.

[Horace]

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.

[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.