Cute! I love little problems where it's quite possible to solve in your head - I get the satisfaction of doing maths without having to get off the couch or grab a pen.
Short video, yet informative. Loved how your explanation, simple and clear. You look great, and your accent is awesome, I enjoy it. Thanks for the video. 🇸🇦❤
If we only had 2 subsets, we could convert from 2 distinct subsets to non-overlapping subsets quite easily. If the two sets overlap, we remove their intersection (we can show that the remaining sets A\B and B\A must be non-empty if A and B are distinct and have the same sum). This argument doesn't work for 3 subsets though, e.g. {2, 3, 5, 7}, {2, 3, 12}, and {5, 12} are distinct and have the same sum, but can't be reduced to subsets with the same sum.
@@DrBarker I did notice the same trick, but wasn't confident enough to conclude it is impossible before giving up and watching your video. My reasoning with counting 1024 vs 455 was the same as yours though. The length of the video is what even inspired me to try: it was short so I knew there must be a short insight! Thank you for your vids
More generally, given M distinct integers n such that 1≤n≤N, we have 2^M distinct subsets and M*(2*N-M+1)/2 possible sums. Therefore, the minimal number of distinct subsets with the same sum will be ceil(2^(M+1) / (M*(2*N-M+1))).
In the particular example given in the video, the sum 87, and also the sum 145, each of them is a sum of 13 different subsets, which is the maximum this case. No other 13 or more distinct subsets share the same sum. Overnight brute force calculation suggests, that not just 3 distinct subsets can be guaranteed, but even 6 of them, for any choice of 10 integers from 1-50 inclusive. I have no clue how to approach such claim rigorously :-).
@@markogenyk-berezovskyj1351Interesting! I suppose once we have 3 subsets, we can take their complements to get another 3 subsets which will all have the same sum, but this won't necessarily be the same sum as the original 3 subsets. The pigeonhole argument misses a lot of detail about which sum values can actually be achieved, e.g. we can't have 3 sums with a value of 0, 1, 2, 3, 4, and even if we do have 3 sums with a certain value, that must restrict the number of other possibilities.
If the set is still 10 numbers large, then of course the max sum can only be up until 912. Which 10 consecutive integer's sum is the closest to 912 and still smaller? When you find it, the largest of those 10 integers is the smallest 'N' required.
I'd be interested to see if there's a simple way to count the number of subsets with the same sum, given 10 fixed integers from 1-50. We could brute force this here since the numbers are small enough, but is there a more efficient way of doing this? I can see how we could create a lot more "trivial" subsets, given 3 subsets with the same sum, by just adding the same element to each subset. To avoid this, we could just consider 3 subsets where A ∩ B ∩ C is empty.
This is almost identical to the "Subset Sum Problem", which is known to be NP-complete; this means that an efficient algorithm (or even a mathematical description) is unlikely to exist.
I can totally see you post a video about one of the Millenium problems and begin it with "OK, so we're gonna solve the Navier-Stokes problem"
😂😂😂
Cute! I love little problems where it's quite possible to solve in your head - I get the satisfaction of doing maths without having to get off the couch or grab a pen.
This is so cool - can't wait to show my students
It is very interesting problem, thanks.
Short video, yet informative.
Loved how your explanation, simple and clear. You look great, and your accent is awesome, I enjoy it.
Thanks for the video.
🇸🇦❤
I spent way too long trying to solve this interpreting 'distinct' as 'non-overlapping'
If we only had 2 subsets, we could convert from 2 distinct subsets to non-overlapping subsets quite easily. If the two sets overlap, we remove their intersection (we can show that the remaining sets A\B and B\A must be non-empty if A and B are distinct and have the same sum).
This argument doesn't work for 3 subsets though, e.g. {2, 3, 5, 7}, {2, 3, 12}, and {5, 12} are distinct and have the same sum, but can't be reduced to subsets with the same sum.
@@DrBarker I did notice the same trick, but wasn't confident enough to conclude it is impossible before giving up and watching your video. My reasoning with counting 1024 vs 455 was the same as yours though.
The length of the video is what even inspired me to try: it was short so I knew there must be a short insight! Thank you for your vids
So the subsets don't have to be disjoint from each other. I think I would have stated the problem as just "3 subsets" instead of "3 distinct subsets".
More generally, given M distinct integers n such that 1≤n≤N, we have 2^M distinct subsets and M*(2*N-M+1)/2 possible sums.
Therefore, the minimal number of distinct subsets with the same sum will be ceil(2^(M+1) / (M*(2*N-M+1))).
In the particular example given in the video, the sum 87, and also the sum 145, each of them is a sum of 13 different subsets, which is the maximum this case. No other 13 or more distinct subsets share the same sum. Overnight brute force calculation suggests, that not just 3 distinct subsets can be guaranteed, but even 6 of them, for any choice of 10 integers from 1-50 inclusive. I have no clue how to approach such claim rigorously :-).
@@markogenyk-berezovskyj1351Interesting! I suppose once we have 3 subsets, we can take their complements to get another 3 subsets which will all have the same sum, but this won't necessarily be the same sum as the original 3 subsets.
The pigeonhole argument misses a lot of detail about which sum values can actually be achieved, e.g. we can't have 3 sums with a value of 0, 1, 2, 3, 4, and even if we do have 3 sums with a certain value, that must restrict the number of other possibilities.
Why type of math is this? It's very interesting.
The thing I find tricky about combinatorics is your not always looking for the best bound
Instead of 1 to 50, what if we choose from 1 to N? Find smallest N such that we can still find 3 subsets that sum same
If the set is still 10 numbers large, then of course the max sum can only be up until 912.
Which 10 consecutive integer's sum is the closest to 912 and still smaller?
When you find it, the largest of those 10 integers is the smallest 'N' required.
Ni'ce.
this makes me wonder about the frequency of the valid sums
I'd be interested to see if there's a simple way to count the number of subsets with the same sum, given 10 fixed integers from 1-50. We could brute force this here since the numbers are small enough, but is there a more efficient way of doing this?
I can see how we could create a lot more "trivial" subsets, given 3 subsets with the same sum, by just adding the same element to each subset. To avoid this, we could just consider 3 subsets where A ∩ B ∩ C is empty.
This is almost identical to the "Subset Sum Problem", which is known to be NP-complete; this means that an efficient algorithm (or even a mathematical description) is unlikely to exist.