1. Limited time only! Sign up for a free 30min personal 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!

Homework Help: A system of distinct representatives

  1. Jun 16, 2006 #1

    I've been struggling with this exercise:

    Let [itex]X[/itex] be set with [itex]n^2+n+1[/itex] elements and let [itex]S[/itex] be system of [itex](n+1)[/itex]-sized subsets of [itex]X[/itex] such that every two sets in [itex]S[/itex] have at most one common element and [itex]|S| = n^2 + n + 1[/itex]. Prove that S has a system of distinct representatives.

    Of course this is an exercise for use of Hall's theorem (aka Marriage theorem). I tried it by induction of index set ([itex]J[/itex] in Hall's theorem) and somehow directly as well, but I still can't prove it.

    Thank you for any advices.
    Last edited: Jun 16, 2006
  2. jcsd
  3. Jun 16, 2006 #2

    matt grime

    User Avatar
    Science Advisor
    Homework Helper

    What is an exercise in Hall's Theorem? You didn't actually ask a question, or state a problem. Is the problem to show that such an S with those properties exists? Doesn't exist?
  4. Jun 16, 2006 #3
    I'm sorry, my initial post already edited.
  5. Jun 19, 2006 #4


    User Avatar
    Science Advisor
    Homework Helper

    Just some hints to get you going-

    Given an element of X, how many sets in S must it appear in? Consider the largest collection you can have in S with a non-empty intersection to get an upper bound. Once you have this, do some counting.
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook