Hello,(adsbygoogle = window.adsbygoogle || []).push({});

I've been struggling with this exercise:

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

Thank you for any advices.

**Physics Forums | Science Articles, Homework Help, Discussion**

Dismiss Notice

Join Physics Forums Today!

The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

# Homework Help: A system of distinct representatives

**Physics Forums | Science Articles, Homework Help, Discussion**