A system of distinct representatives

[Mr.Cauliflower]

Hello,

I've been struggling with this exercise:

Let X be set with n^2+n+1 elements and let S be system of (n+1)-sized subsets of X such that every two sets in S have at most one common element and |S| = n^2 + n + 1. 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 (J in Hall's theorem) and somehow directly as well, but I still can't prove it.

Thank you for any advices.

 

[matt grime]

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?

 

[Mr.Cauliflower]

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?

I'm sorry, my initial post already edited.

 

[shmoe]

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.