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: Having trouble applying Hall's Theorem

  1. Jan 21, 2008 #1
    1. Let k>0 and let A1,A2,...,An be a collection of k-subsets of finite set X such that every element of X appears in exactly k sets in the collection. Prove that |X| = n

    2. Teacher provided us with the following hints:
    -- Use a variation of Hall's Theorem.

    3. I have no clue how to approach this problem. I don't even understand how proving |X|=n implies anything?
    Last edited: Jan 21, 2008
  2. jcsd
  3. Jan 21, 2008 #2


    User Avatar
    Science Advisor

    ?? |X|= n is the conclusion you want to prove! Why should it imply anything?

    "k- subsets" here means subsets of X containing exactly k members? The "overlapping" is the problem here so imaging "painting" the members of each Ai a different color! In other words, imagine that these are all distinct items. Since there are n sets, each containing k items, how many items are there altogether.

    But we are told that each item in X appears in exactly k sets. In other words each item in X is counted k times in the formula above.
  4. Jan 21, 2008 #3
    By that, I meant that I don't know understand what solving for |X| = n proves and therefore I can't figure out the reasoning and logic to bring me to that solution.

    But thanks for the tips! I'll see if I can use it to help me figure it all out.
  5. Jan 21, 2008 #4


    User Avatar
    Science Advisor

    ??? It proves just what it says: that X contains n elements!

    I can't think what else you could mean.
  6. Jan 22, 2008 #5

    Hahaha, well I guess that's the meaning that I missed. Sorry for my horrible math skills. The last time I took any university level math was 5 years ago. I'm just going back to school now for some upper level math courses to complete a minor in Math.

    I've basically forgotten everything.
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook