# Homework Help: A system of distinct representatives

1. Jun 16, 2006

### 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.

Last edited: Jun 16, 2006
2. Jun 16, 2006

### 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?

3. Jun 16, 2006

### Mr.Cauliflower

I'm sorry, my initial post already edited.

4. Jun 19, 2006

### 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.