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

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