I am currently studying the Math for CS course on MIT OCW, I am stuck on the following question for which I cannot find a solution:
Scholars through the ages have identified twenty fundamental human virtues: honesty, generosity, loyalty, prudence, completing the weekly course reading-response, etc. At the beginning of the term, every student in 6.042 possessed exactly eight of these virtues. Furthermore, every student was unique; that is, no two students possessed exactly the same set of virtues. The 6.042 course staff must select one additional virtue to impart to each student by the end of the term. Prove that there is a way to select an additional virtue for each student so that every student is unique at the end of the term as well.
Suggestion: Use Hall’s theorem. Try various interpretations for the vertices on the left and right sides of your bipartite graph.
I have partitioned G in X and Y where X is the set of virtues with |X|=20 and Y is the student. I know that the cardinality of every vertex in X is 8, and that there is a unique matching, but I don't know how to progress.
We have to envisage the possibility that there are ${20\choose 8}=125\,970$ students, each of them incorporating another set of $8$ virtues. On the other hand there are ${20\choose 9}=167\,960$ combinations of $9$ virtues.
We therefore set up a bipartite graph $G$ with vertex set $L\cup R$ as follows: On the left we have ${20\choose 8}$ vertices $v$ representing the collections of $8$ virtues, and on the right we have ${20\choose 9}$ vertices $w$ representing the collections of $9$ virtues. From each eight-set $v$ draw edges to the $12$ nine-sets $w$ containing $v$ as a subset.
I claim that this graph meets the condition of Hall's theorem.
Proof. Consider any nonempty subset $P\subset L$, and let $Q\subset R$ be the set of vertices connected to at least one $v\in P$. There are $12|P|$ edges emanating from $P$, but any $w\in Q$ can receive at most $9$ of them. It follows that $$|Q|\geq{12|P|\over 9}>|P|\ .\qquad\square$$ Hall's theorem therefore guarantees the existence of a perfect matching. A practical procedure then could be as follows: Using a constructive proof of Hall's theorem the staff of course 6.042 sets up a lookup table for all correspondences $v\mapsto w$ once and for all. Any student signing in for the course would then have to name her eight virtues whereupon she will be assigned a ninth according to the table.