Having trouble applying Hall's Theorem

1. Jan 21, 2008

junho

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. Jan 21, 2008

HallsofIvy

Staff Emeritus
?? |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.

3. Jan 21, 2008

junho

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.

4. Jan 21, 2008

HallsofIvy

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

I can't think what else you could mean.

5. Jan 22, 2008

junho

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.