Open Side Menu Go to the Top
FAQ Today's Posts Search Twitter Discord
Register
Number theory problem Number theory problem
Post Reply Subscribe
...
05-06-2021 , 10:31 PM
#1
d2_e4's Avatar
d2_e4
View Profile Send Message Find Posts By d2_e4 Find Threads By d2_e4
certifiable moron
Join Date: Sep 2014 Posts: 12,142
A friend just gave me this:

prove that for any set of 10 unique numbers [1,100] there will be 2 subsets with the same sum

I have no idea where to even start. Suggestions welcome.
Number theory problem Quote
05-06-2021 , 10:54 PM
#2
PairTheBoard
View Profile Send Message Find Posts By PairTheBoard Find Threads By PairTheBoard
Carpal \'Tunnel
Join Date: Dec 2003 Posts: 10,039
Quote:
Originally Posted by d2_e4
A friend just gave me this:

prove that for any set of 10 unique numbers [1,100] there will be 2 subsets with the same sum

I have no idea where to even start. Suggestions welcome.
Do the 2 subsets have to partition the set of 10? i.e. Do they have to be mutually exclusive and cover the set of 10?


PairTheBoard
Number theory problem Quote
05-06-2021 , 11:57 PM
#3
d2_e4's Avatar
d2_e4
View Profile Send Message Find Posts By d2_e4 Find Threads By d2_e4
certifiable moron
Join Date: Sep 2014 Posts: 12,142
I think he is basically saying, if we pick 10 random numbers from the set [1,100] we can always find 2 subsets within that set that have the same sum. So, yes, they are mutually exclusive.
Number theory problem Quote
05-07-2021 , 12:07 AM
#4
PairTheBoard
View Profile Send Message Find Posts By PairTheBoard Find Threads By PairTheBoard
Carpal \'Tunnel
Join Date: Dec 2003 Posts: 10,039
Quote:
Originally Posted by d2_e4
I think he is basically saying, if we pick 10 random numbers from the set [1,100] we can always find 2 subsets within that set that have the same sum. So, yes, they are mutually exclusive.
Suppose the 10 numbers are 1,2.3,...,10

Would the two subsets {1,2} and {3} count?


PairTheBoard
Number theory problem Quote
05-07-2021 , 12:16 AM
#5
NewOldGuy
View Profile Send Message Find Posts By NewOldGuy Find Threads By NewOldGuy
Pooh-Bah
Join Date: Mar 2009 Posts: 5,935
Quote:
Originally Posted by d2_e4
A friend just gave me this:



prove that for any set of 10 unique numbers [1,100] there will be 2 subsets with the same sum



I have no idea where to even start. Suggestions welcome.
It's pretty easy to come up with examples which prove this false. He may need to clarify the problem.
Number theory problem Quote
05-07-2021 , 01:38 AM
#6
David Sklansky's Avatar
David Sklansky
View Profile Send Message Find Posts By David Sklansky Find Threads By David Sklansky
Administrator
Join Date: Aug 2002 Posts: 17,096
I answered this already in the politics forum where you also asked it. There are 1023 subsets and only 955 sums. So there must be duplicates.
Number theory problem Quote
05-07-2021 , 08:15 AM
#7
lastcardcharlie's Avatar
lastcardcharlie
View Profile Send Message Find Posts By lastcardcharlie Find Threads By lastcardcharlie
Carpal \'Tunnel
Join Date: Aug 2006 Posts: 10,435
Searching through politics to find the proof sounds like fun.
Number theory problem Quote
05-07-2021 , 10:32 AM
#8
David Sklansky's Avatar
David Sklansky
View Profile Send Message Find Posts By David Sklansky Find Threads By David Sklansky
Administrator
Join Date: Aug 2002 Posts: 17,096
Quote:
Originally Posted by lastcardcharlie
Searching through politics to find the proof sounds like fun.
I repeated the whole proof here. You don't see how I got 955 and 1023? !023 is 2 to the tenth minus one. 955 is the sum of the largest ten numbers.
Number theory problem Quote
05-07-2021 , 10:40 AM
#9
lastcardcharlie's Avatar
lastcardcharlie
View Profile Send Message Find Posts By lastcardcharlie Find Threads By lastcardcharlie
Carpal \'Tunnel
Join Date: Aug 2006 Posts: 10,435
Nice.

Pardon my obtuseness.
Number theory problem Quote
05-07-2021 , 11:31 AM
#10
PairTheBoard
View Profile Send Message Find Posts By PairTheBoard Find Threads By PairTheBoard
Carpal \'Tunnel
Join Date: Dec 2003 Posts: 10,039
What's the trickiest opening move in chess?


PairTheBoard
Number theory problem Quote
05-07-2021 , 05:44 PM
#11
d2_e4's Avatar
d2_e4
View Profile Send Message Find Posts By d2_e4 Find Threads By d2_e4
certifiable moron
Join Date: Sep 2014 Posts: 12,142
Quote:
Originally Posted by PairTheBoard
Suppose the 10 numbers are 1,2.3,...,10

Would the two subsets {1,2} and {3} count?


PairTheBoard
I think so.
Number theory problem Quote
05-07-2021 , 05:47 PM
#12
d2_e4's Avatar
d2_e4
View Profile Send Message Find Posts By d2_e4 Find Threads By d2_e4
certifiable moron
Join Date: Sep 2014 Posts: 12,142
Quote:
Originally Posted by PairTheBoard
What's the trickiest opening move in chess?


PairTheBoard
I1

You want to play I'm prob like 1600 ELO?
Number theory problem Quote
05-07-2021 , 06:22 PM
#13
PairTheBoard
View Profile Send Message Find Posts By PairTheBoard Find Threads By PairTheBoard
Carpal \'Tunnel
Join Date: Dec 2003 Posts: 10,039
Quote:
Originally Posted by d2_e4
I1

You want to play I'm prob like 1600 ELO?
I don't play anymore. But for the answer to my question, I was thinking of your name.


PairTheBoard
Number theory problem Quote
05-10-2021 , 08:53 PM
#14
NewOldGuy
View Profile Send Message Find Posts By NewOldGuy Find Threads By NewOldGuy
Pooh-Bah
Join Date: Mar 2009 Posts: 5,935
Quote:
Originally Posted by David Sklansky
I answered this already in the politics forum where you also asked it. There are 1023 subsets and only 955 sums. So there must be duplicates.
I'm unclear on how this answers the original query. He asked (bolding mine)

"prove that for any set of 10 unique numbers [1,100] there will be 2 subsets with the same sum"

You seem to be saying that for the entire universe of possible sets of 10, that some of them must have duplicate sums. Not that all of them must, which I believe is false simply by thinking of a couple counterexamples.

Maybe I've misunderstood one of you.
Number theory problem Quote
05-10-2021 , 09:10 PM
#15
lastcardcharlie's Avatar
lastcardcharlie
View Profile Send Message Find Posts By lastcardcharlie Find Threads By lastcardcharlie
Carpal \'Tunnel
Join Date: Aug 2006 Posts: 10,435
I understand it to mean, for any set X containing 10 integers between 1 and 100, there exist two distinct subsets of X whose sums are equal. (Fairly clearly, these two subsets can also be required to be disjoint.)

("Unique" is redundant, as all elements of a set are distinct, if that's what it means. E.g. {1, 1} is not a set.)
Number theory problem Quote
05-10-2021 , 10:42 PM
#16
Aaron W.
View Profile Send Message Find Posts By Aaron W. Find Threads By Aaron W.
Carpal \'Tunnel
Join Date: Sep 2002 Posts: 30,132
Quote:
Originally Posted by NewOldGuy
I'm unclear on how this answers the original query. He asked (bolding mine)

"prove that for any set of 10 unique numbers [1,100] there will be 2 subsets with the same sum"

You seem to be saying that for the entire universe of possible sets of 10, that some of them must have duplicate sums. Not that all of them must, which I believe is false simply by thinking of a couple counterexamples.

Maybe I've misunderstood one of you.
What collection is the "set" and what is the "subset"?
Number theory problem Quote
05-10-2021 , 10:46 PM
#17
Aaron W.
View Profile Send Message Find Posts By Aaron W. Find Threads By Aaron W.
Carpal \'Tunnel
Join Date: Sep 2002 Posts: 30,132
Quote:
Originally Posted by lastcardcharlie
I understand it to mean, for any set X containing 10 integers between 1 and 100, there exist two distinct subsets of X whose sums are equal. (Fairly clearly, these two subsets can also be required to be disjoint.)

("Unique" is redundant, as all elements of a set are distinct, if that's what it means. E.g. {1, 1} is not a set.)
The result is still valid if you were allowed to use multisets.

Suppose you have ten boxes of ping pong balls labeled 1 to 100. Draw one ball from each box. Then it is possible to create two disjoint collections from those ten selections that add to the same total.
Number theory problem Quote
05-10-2021 , 11:18 PM
#18
NewOldGuy
View Profile Send Message Find Posts By NewOldGuy Find Threads By NewOldGuy
Pooh-Bah
Join Date: Mar 2009 Posts: 5,935
After full enumeraration I can only construct a set of 7 values between 1 and 100 that have no subsets with the same sum. You can't add an 8th member without allowing a duplicate sum. The 7 values are all the powers of 2.

So I retract my objection. But I still don't understand David's proof.
Number theory problem Quote
05-10-2021 , 11:34 PM
#19
lastcardcharlie's Avatar
lastcardcharlie
View Profile Send Message Find Posts By lastcardcharlie Find Threads By lastcardcharlie
Carpal \'Tunnel
Join Date: Aug 2006 Posts: 10,435
There are 1023 non-empty subsets of the set containing the 10 numbers, and the sum of each subset is a number between 1 and 955. So there is bound to be repeats.
Number theory problem Quote
05-10-2021 , 11:56 PM
#20
NewOldGuy
View Profile Send Message Find Posts By NewOldGuy Find Threads By NewOldGuy
Pooh-Bah
Join Date: Mar 2009 Posts: 5,935
Quote:
Originally Posted by lastcardcharlie
There are 1023 non-empty subsets of the set containing the 10 numbers, and the sum of each subset is a number between 1 and 955. So there is bound to be repeats.
I get it now.
Number theory problem Quote
Post Reply Subscribe
...
      
Feedback is used for internal purposes. LEARN MORE
Contact Us Privacy Statement TOS
Top
Powered by:  Hand2Note
Copyright ©2008-2022, Hand2Note Interactive LTD
m