How many years can we do a secret santa? A friend of mine recently implemented a program to assign the people in his family for doing a secret santa. As usual everybody receives and gives exactly one present. In addition he imposed the constraint that you are not allowed to give a present to the person you gave a present last year.
When he told me about this, I asked myself the following question. If we impose the stronger constraint that you are not allowed to give a present to somebody you gave a present in any of the previous years, what is the minimal amount of years such that it is possible to assign people according to this rules?
Clearly, if $n$ people are involved an upper bound will be $n-1$. But is this really the worst case that might happen? So is it possible that after $m<n-1$ it is impossible to assign people with the above restrictions?
 A: The one-sentence summary is: for $k \geq 1$, a $k$-regular bipartite graph has a perfect matching by Hall's theorem.
The longer version: We take two copies of your family, one as "gift givers" and one as "gift receivers", and we build a bipartite graph, with an edge going from giver $x$ to receiver $y$ if $x$ has not gifted to $y$ before. Then, every vertex has precisely $n - m$ neighbours in the $m$th year -- that is, it is $(n-m)$-regular. Now, a new secret Santa assignment is precisely a perfect matching in this graph, and the existence of such a matching follows for instance from Hall's theorem: 

If for each subset $A$ of the givers, and $R(A)$ the set of receivers who can still receive a gift from a member of $A$, we have $|A| \leq |R(A)|$, then a perfect matching exists.

In this case, the condition clearly holds: because any $A$ has $(n-m)|A|$ edges incident to its vertices, therefore $R(A)$ has at least that many; but each vertex has precisely $n-m$ incident vertices. Hence indeed $|A| \leq |R(A)|$.
