1. Not finding help here? Sign up for a free 30min tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Combinatorics: looking for an alternative solution

  1. Nov 4, 2016 #1

    Math_QED

    User Avatar
    Homework Helper

    1. The problem statement, all variables and given/known data

    Show that every subset with 6 elements of {1,2,3,4, ..., 9} contains 2 elements with sum 10.

    I solved this (solution below) but I want to do this easier using the pidgeon hole principle.

    2. Relevant equations

    Pidgeon hole principle
    Combinatorics

    3. The attempt at a solution

    Claim: Every subset of {1,2,3, ..., 9} has either the following number combinations in it:
    (1,9),(2,8),(3,7),(4,6)

    Proof:

    Let A be the set with subsets with 6 elements of {1,2, ..., 9} that have (1,9) in it.
    Let B be the set with subsets with 6 elements of {1,2, ..., 9} that have (2,8) in it.
    Let C be the set with subsets with 6 elements of {1,2, ..., 9} that have (3,7) in it.
    Let D be the set with subsets with 6 elements of {1,2, ..., 9} that have (4,6) in it.

    ##|A \cup B \cup C \cup D| = |A| + |B| + |C| + |D| - |A \cap B| - |A \cap C| - |A \cap D| - |B \cap D| - |B \cap C| - |C \cap D| + |A \cap B \cap C| + |A \cap B \cap D| + |B \cap C \cap D| + |A \cap C \cap D| - |A \cap B \cap C \cap D|
    = 4\binom{7}{4} - 6\binom{5}{2} + 4\binom{3}{0} + 0
    = 84##

    But, the total amount of subsets with 6 elements is ##\binom{9}{6} = 84##. We deduce that every subset has 2 elements with sum 10.

    Can someone give a hint on a good way to do this using the pidgeon hole principle? This is supposed to be an exercise that has to be solved using PHP.
     
    Last edited: Nov 4, 2016
  2. jcsd
  3. Nov 4, 2016 #2

    fresh_42

    Staff: Mentor

    You could put pairs that sum up to 10 into a box. Now try to select six numbers.
     
  4. Nov 5, 2016 #3

    Math_QED

    User Avatar
    Homework Helper

    What exactly do you mean?
     
  5. Nov 5, 2016 #4

    fresh_42

    Staff: Mentor

    If you pair numbers that add up to ten, e.g. ##(2,8)## and consider the set of these pairs (box, container, whatever), then the task turns into choosing six numbers, such that no pair will end up in the set of your choice. Is this possible?
     
  6. Nov 6, 2016 #5

    Math_QED

    User Avatar
    Homework Helper

    Okay. Here is the new attempt:

    Suppose we take 4 elements out of {1,2, ..., 9} such that the sum is not 10. This means, we selected from each pair (1.9), (2.8), (3,7), (4.6) one element and the other one can't be chosen. But then, the only possibility left is to choose a 5. If we would take a sixth element, we would need to take another number that was not yet selected from the pairs, and this is the only option left. Thus we find in every subset of 6 element 2 elements that sum up to 10.
     
  7. Nov 6, 2016 #6

    fresh_42

    Staff: Mentor

    This was the idea.

    As a general hint (not necessarily for you, but all students who might read this): As I saw your statement with all these sets ##A,B,C,D## I first read it to the end without checking any formulas. You wrote "pigeonhole principle", so I looked it up. I've read something about containers, so I thought about the way these containers could be shaped according to the task. This gave me "sum up to ten" for the containers, and the pairs to be in them.

    I only mention this, because it is always a good idea to get an overview of a task, before starting to solve it. I usually recommend:
    1. Read it without calculating anything. Only to find out what it's about.
    2. Read it again and only write down all the information that is given. Again without calculations, but eventually with units!
    3. Determine what has to be calculated, resp. found, and which data it depends on (e.g. in case of exercises like cross-multiplication)
    4. Make sure you have all definitions correct and at hand, which might be needed.
    This procedure often helps a lot to save time during tests (and homework).
     
  8. Nov 6, 2016 #7

    PeroK

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member

    I would organise the set 1-9 as:

    1, 9
    2, 8
    3, 7
    4, 6
    5

    Now, pick any six of those!
     
  9. Nov 6, 2016 #8

    Math_QED

    User Avatar
    Homework Helper

    That makes it pretty visual haha, but is equivalent to what I wrote. Anyway, thanks for your help!

    Thanks for the help and hint!
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?
Draft saved Draft deleted