Today’s puzzle
-
wrote on 25 May 2020, 10:54 last edited by
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?
-
wrote on 25 May 2020, 14:18 last edited by
Determining whether Amy is nuts would require a clinical evaluation by a trained professional and should not be attempted by laymen on internet forums.
-
wrote on 25 May 2020, 14:23 last edited by
-
wrote on 25 May 2020, 14:59 last edited by
-
wrote on 25 May 2020, 15:26 last edited by
How vulgar.
-
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?
wrote on 25 May 2020, 15:53 last edited by 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.
-
wrote on 30 May 2020, 16:32 last edited by
Bumping this in case Klaus wants to revisit.
Will post answer later if he doesn’t.
-
wrote on 30 May 2020, 17:29 last edited by
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.
-
wrote on 30 May 2020, 17:36 last edited by
That’s a reasonable starting place.
-
wrote on 30 May 2020, 17:38 last edited by
The total number of possible sums is a bit less than that, since the min is 1+2+3+...+10.
-
wrote on 30 May 2020, 17:38 last edited by
There’s a key insight which makes it trivial to compute in your head in milliseconds.
-
wrote on 30 May 2020, 17:49 last edited by
@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.
-
wrote on 30 May 2020, 17:52 last edited by
Of course. My bad.
-
wrote on 30 May 2020, 20:45 last edited by 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.
-
wrote on 30 May 2020, 21:28 last edited by 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.
-
wrote on 30 May 2020, 21:35 last edited by
I don't find that insight useful to arrive at the idea of counting unique combinations, but YMMV.
-
wrote on 30 May 2020, 21:39 last edited by
No, just the easy calc. It's all the 10 digit binary numbers.
-
wrote on 30 May 2020, 21:40 last edited by
Yes, I like how binary digits map to the idea of including/excluding things from a set.
