#Given a group of 10 two digit numbers, prove that there are two subsets in which the sum of all

57 messages · Page 1 of 1 (latest)

placid canyon
#

Continuation: members is equal.

dawn flameBOT
#
  1. Do not ping the Moderators, unless someone is breaking the rules.
  2. Do not ping the Helper Moderators, unless there is a conflict between helpers.
  3. Do not ping other members randomly for help.
  4. Ask your question and show the work you've done so far. If you've posted a screenshot of a question, specify which part you need help with.
  5. Wait patiently for a helper to come along.
  6. If the Helper has answered your question, remember to thank them with the Mathematics Ranks bot and close the thread with:

+close
Feel free to nominate the person for helper of the week in #helper-nominations
If you're happy with the help you got here, and the server overall, you can contribute financially as well:

placid canyon
#

I don't know how to attack this problem.

#

Probably includes Pigeonhole principle

#

But Idk where to use it

#

maybe there must be two numbers with difference of less or equal to 9

#

but I really can't see how that helps me

river patrol
#

Because as written, it's trivial.

#

Or, wait.

#

Nevermind.

placid canyon
#

Probably should have written sub group

#

and not sub set

river patrol
#

...no, that's not the problem.

#

Okay, a 2-digit number is between 10 and 99, right?

placid canyon
#

yes

river patrol
#

So the trick to pigeonhole principle problems is generally to try to construct the counterexample and see what limits you run up against.

#

Or, wait, there's a simpler method here.

placid canyon
#

I think we should look at the differences between two numbers

river patrol
#

So the smallest "sum" we can construct is obviously the "sum" of one number, which is a minimum of 10, right?

placid canyon
river patrol
#

And the largest would be the sum of all 10 numbers, which is a maximum of the sum of integers from 89 to 99.

#

That's 1034.

#

Which means there's 1025 possible sums. Except there aren't, because obviously if we have a 10 or an 11, we can't get a 1034 or a 1033, so we can reduce it to 1023.

#

We can reduce it way more than that, but that's all we need.

#

Or wait.

#

If we have a 12 we can't have a 1032.

#

So 1022 possible sums.

river patrol
placid canyon
#

I am

#

I wasn't here

#

but I think I got it

#

without power sets

river patrol
placid canyon
#

There are 10 numbers in the group, therefore there are at 2^10 -1 subsets (not including the empty set). As you said, we have at most 1025 possible sums, and because 2^10-1 is bigger than 1025, we must have a sum that repeats.

river patrol
#

Also, that's not correct.

#

2^10 - 1 = 1023.

placid canyon
#

my mistake

placid canyon
river patrol
#

But you're correct. We have a set, S, of 10 two-digit numbers. We want to prove that, within the set of nonempty subsets of S, there exist two sets whose sum of elements is the same.

placid canyon
#

But the way you reduced it to 1022 solves this

river patrol
#

So our pigeons are our nonempty subsets, and our pigeonholes are our sums.

#

Actually, the greatest sum you can get with a 10 in the mix is 955.

#

So 10 is mutually exclusive with everything greater than 955.

#

And 11 is mutually exclusive with everything greater than 956.

#

and 12 is mutually exclusive with everything greater than 957.

#

That brings us down to 1022 possible sums, which is less than our number of nonempty subsets.

#

Because our set of possible sums either excludes {10, 11, 12} or it excludes {1034, 1033, 1032}.

#

If we can reach any of the sums in one set, we can't reach any of the sums in the other set.

#

Which means there are at least three sums we can't reach.

placid canyon
#

Thank you!

#

+close

tawny adderBOT
# placid canyon +close
Please thank your Helpers before closing!

Please thank the helpers who assisted you by clicking the buttons below. You can thank each helper only once. Once you're done, click "Close Post" to close this thread.

tawny adderBOT
# tawny adder

Thank you for your feedback! Techie Literate has been awarded 1 helper_points. They now have 871 helper_points. They have 0 helper_points daily left for today.