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!

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

    HallsofIvy

    User Avatar
    Staff Emeritus
    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

    HallsofIvy

    User Avatar
    Staff Emeritus
    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.
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?



Similar Discussions: Having trouble applying Hall's Theorem
Loading...