# A Basic System of Sets Combinatorics Problem

I think I have seen theorems like this before, but since the question is very simple I was unable to really search for an answer on here; didn't find it, at least.

I have $n+1$ not necessarily distinct sets $Q_k \subset \lbrace 1, 2, \dots n \rbrace$. Further, we assume each $Q_k$ contains at least two elements, and that $Q_1 \cup Q_2 \cup \cdots \cup Q_{n+1} = \lbrace 1, 2, \dots, n \rbrace$. If we let $\mathcal{Q}$ be the collection of the $Q_k$'s, Is it true that there is an injection $f: \lbrace 1, 2, \dots, n \rbrace \rightarrow \mathcal{Q}$ such that $j \in f(j)$ for all $j$?

That is to say, if $\mathcal{Q} = \lbrace Q_k \rbrace$ is a covering of $\lbrace 1, 2, \dots, n \rbrace$ by $n+1$ subsets each containing at least two elements, can we pair off the points $1, 2, \dots, n$ with some $n$ of $Q_k$'s so that each integer is paired off with a subset containing it?

Thanks a lot! Either a reference or proof is fine!

This looks like a case for Hall's theorem. You have a bipartite graph with one part indexed by $\{1,2,\ldots,n\}$ and the other by the $Q_i$ and we join $j$ and $Q_i$ when $j\in Q_i$. By Hall's theorem there is a matching of the type you need iff for each $A\subseteq\{1,\ldots,n\}$, there are at least $|A|$ $Q_i$ with $Q_i\cap A\ne\emptyset$.