Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Combinatorics Challenge

  1. Sep 7, 2006 #1
    I rarely care enough about one problem to ask for help, but there are a million problems that are similar to this one and I don't really understand any of them.

    The problem I'm looking at reads:

    In a room there are 10 people, none of whom are older than 60 (ages are considered as whole numbers only) but each of whom is at least 1 year old. Prove that one can always find two groups of people (with no common person) the sum of whose ages is the same.

    The author failed to define "group" (which makes me even more confused), but I would assume that a group consists of at least one person.

    I observe that there is a possibility of (2^10)-1 sums, each of which add up to between 10 and 600. I also believe that there are fewer ways to add up to 10 or 600 and that there are a lot of ways to add to 300.

    If anyone can help me out in any way at all, I'd be appreciative.
  2. jcsd
  3. Sep 7, 2006 #2
    hahha there's already a thread on that exact same question. Sorry i Don't have the link...use the search option for combinatorics.
  4. Sep 7, 2006 #3
    Must be in my class!
  5. Sep 7, 2006 #4
    hmm, interesting question :smile:


    Basically, we have 1023 groups (or possible sums) and only 591 possible values for the groups (sums), so by the pigeonhole principle there are two groups with the same value. If the groups have a common person(s) just remove that person(s) from the group (the sum of the ages will still be the same).
    Last edited: Sep 7, 2006
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook