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.