Five friends - Alex, Becky, Claire, Devin, and Edgar - are participating in a gift exchange. The friends are sitting in alphabetical order around a hat. Each person writes their name on a piece of paper and throws it into the hat. The rules of the gift exchange are:
- Each person draws a name from the hat simultaneously.
- If any person draws their own name, everyone passes their piece of paper to the person on their right.
- This continues until nobody has their own name.
Is it possible for the friends to have drawn the names such that no matter how many times they pass to the right somebody always has their own name?
What if Edgar decides to not participate in the gift exchange?
What if their friend Felicia joins them?
Let's say that there are $n$ people and we number them $0, 1, \dots, n-1$.
Note that if a person has their own paper, they will not have their own paper again until exactly $n$ passes later. If this process never ends we need to have a cycle of size $n$, and thus during every single round there must be exactly one person that has their own name or else we run out of papers during some other round.
Thus one person must get their own name immediately, another person gets their own after 1 turn, another after 2 turns, etc...
So we're looking for a permutation $P$ of the numbers $0, \dots, n-1$ such that:
$$P_{x+k \bmod n} = x$$
has a solution for all $k \in [0, n-1]$, using zero-based indexing in $P$. Simply setting $k = x$ gives a solution for odd $n$, as $2$ and $n$ are coprime and thus $2x \bmod n$ will uniquely generate all residues:
$$P_{2x \bmod n} = x$$
E.g. for $n = 5$ we get:
$$P_0 = 0, P_2 = 1, P_4 = 2, P_1 = 3, P_3 = 4$$
However this doesn't prove that there is no solution for even $n$. Maybe someone else can contribute that (I have a feeling I've come across this before and that it is a well-known problem, but my google-fu is lacking at the moment).
There is a simple rephrasing of the problem: does there exist a permutation $P$ of size $n$ such that there doesn't exist any cyclic shift that when composed with $P$ forms a derangement.